Implementing a Distributed Lock Service in Go

In distributed systems, ensuring that only one process or instance can access a shared resource at any given time is crucial for maintaining data consistency and preventing race conditions. This challenge asks you to build a fundamental component of such systems: a distributed lock service. You will implement a mechanism that allows multiple Go applications to acquire and release a lock, ensuring mutual exclusion across different machines.

Problem Description

Your task is to design and implement a distributed lock manager in Go. This manager should provide two primary operations: AcquireLock(key string, ttl time.Duration) and ReleaseLock(key string).

• AcquireLock(key string, ttl time.Duration): This function should attempt to acquire a lock for a given key.
  • If the lock is not currently held, it should be acquired by the caller, and the function should return true along with a unique identifier for the lock (e.g., a token or session ID).
  • If the lock is already held by another caller, the function should block until the lock is released or its Time-To-Live (TTL) expires.
  • The ttl parameter specifies how long the lock will be valid. If the lock holder fails to release the lock within this duration, the lock should automatically expire and become available for others.
  • If the lock is acquired, the returned identifier must be used when releasing the lock.
• ReleaseLock(key string): This function should release a previously acquired lock for the given key.
  • It must only succeed if the caller is the current owner of the lock (identified by the unique identifier returned during acquisition).
  • If the lock is released successfully, the function should return true.
  • If the lock does not exist, is expired, or is held by another party, the function should return false.

You are free to choose the underlying storage mechanism for managing the locks, but it must be external to the Go application itself to simulate a distributed environment. Common choices include Redis, ZooKeeper, or etcd. For this challenge, you can simulate this external dependency by creating a mock implementation of your chosen storage.

Examples

Example 1: Simple Lock Acquisition and Release

// Assume a lock service is initialized and accessible.
// A client attempts to acquire a lock for "resource_A".
lockManager.AcquireLock("resource_A", 10*time.Second) // Returns "lock_id_1", true

// Another client attempts to acquire the same lock.
lockManager.AcquireLock("resource_A", 10*time.Second) // Blocks or returns false if not blocking immediately

// The first client releases the lock.
lockManager.ReleaseLock("resource_A", "lock_id_1") // Returns true

// Now the second client can acquire the lock.
lockManager.AcquireLock("resource_A", 10*time.Second) // Returns "lock_id_2", true

Example 2: Lock Expiration

// A client acquires a lock for "resource_B" with a short TTL.
lockManager.AcquireLock("resource_B", 2*time.Second) // Returns "lock_id_3", true

// The client waits for 3 seconds without releasing the lock.
time.Sleep(3 * time.Second)

// Another client attempts to acquire the lock.
lockManager.AcquireLock("resource_B", 10*time.Second) // Returns "lock_id_4", true (because the previous lock expired)

// The original holder of "lock_id_3" attempts to release the lock.
lockManager.ReleaseLock("resource_B", "lock_id_3") // Returns false (lock is no longer held by "lock_id_3")

Example 3: Releasing a Lock Not Held or by Wrong ID

// A lock for "resource_C" is not held.
lockManager.ReleaseLock("resource_C", "some_random_id") // Returns false

// A client acquires a lock for "resource_D".
lockManager.AcquireLock("resource_D", 10*time.Second) // Returns "lock_id_5", true

// Another client attempts to release it with a different ID.
lockManager.ReleaseLock("resource_D", "another_id") // Returns false

Constraints

• The AcquireLock operation should be able to handle multiple concurrent requests.
• The ReleaseLock operation must be atomic and safe for concurrent access.
• The TTL mechanism must be robust; expired locks should be reliably reclaimed.
• Your implementation should include a mock storage mechanism that mimics the behavior of an external distributed key-value store (e.g., Redis SETNX with EXPIRE or similar patterns).
• The unique lock identifier returned by AcquireLock should be sufficiently unique to prevent accidental releases by other clients. A UUID is a good candidate.

Notes

• Consider how you will handle the blocking behavior of AcquireLock. You might use channels and goroutines effectively.
• Think about the atomicity requirements for AcquireLock and ReleaseLock when interacting with your mock storage.
• The choice of the mock storage can simplify or complicate the implementation. For instance, simulating Redis commands like SETNX and EXPIRE can be a good starting point.
• Ensure your mock storage is thread-safe.