Distributed Systems: Distributed Locks

TODO:

merge with Programming: Synchronization

Tutorials

redis: distributed locks tutorial	https://redis.io/topics/distlock
dzone: distributed locks tutorial	https://dzone.com/articles/everything-i-know-about-distributed-locks

Algorithms

Single Master Locks without Fallback

A lock strategy from redis that does not addresses having a single point of failure.

• create a redis key with
  • a random/unique value, unique across all clients
  • a TTL
  • only created if key doesn't already exist

• you can then safely delete the lock only if the lock contains your unique string

NOTE:

there is a race-condition here, beteween GET and DEL

Multi-Master Locks (introduces Fallback)

See description of Redlock algorithm here https://redis.io/topics/distlock
A lock strategy from redis that addresses the above problem of a single point of failure.

Algorithm:

# use odd-number of redis servers (replicated? partitioned?) (ex: 5)

acquire lock:
  - get current time in milliseconds

  - try to acquire locks sequentially across all servers (using unique random value for lock request).
    Use a shorter timeout than the key's TTL.

  - lock acquired?:
      success: |
        if you successfully acquire a majority of the locks,
        and less time has elapsed while trying locks than the lock duration,
        consider the lock acquired
      failure: |
        otherwise, try to unlock all instances (even if lock acquire failed).

retry lock:
  - re-attempt at a random interval (bounded) 
    so less likely to conflict with other lock attempts

Additional Considerations:

- locks should not be persisted across restart (depend on the other servers)
  (alternatively, redis should not restart until TTL exceeded)

- jobs performed while lock is valid must not exceed the key's TTL!!

Addressed Concerns:

- variations in clock time
- inconsistent server reboots
- inconsistent power outages

Locking Concepts

Lock Fencing

Use of a number/value that increases each lock acquisition.
This prevents outdated requests related to previous locks from impacting the current lock.