SeqLock: An Optimistic and Write Prefered

Posted on

Foreword

Lock is a crucial component in computer system including database, file system, parallel computation system, etc. It limit different threads to access the same resource simultaneously. It can be seen as a mutual exclusion concurrency control policy. These multiple accessing phenomena can be divided into three kinds: Write-Write conflict, Write-Read conflict, Read-Read conflict (not exist). Write-Read Lock (a.k.a., Exclusive Lock & Shared Lock) can stop the same resource accessing from multiple writer and support multi-reader and single write (SWMR) naturally. The Write-Read Lock also has two main kinds of algorithm: Read-Preferred and Write preferred. Unfortunately, this lock mechanism always assume the conflict may happening (pessimistic), and is un-friendly to the process which will block the process and even bring with deadlock.

SeqLock: An Optimistic Lock

The sequential lock (seq-lock) is composed with a read lock (sequencer) and a write lock to avoid the multi writer accessing.
This mechanism is also known as retry lock. When read operation is finished, the reader will check the lock again. Readers read the sequence number before and after reading the shared data. If the sequence number is odd on either occasion, a writer had taken the lock while the data was being read and it may have changed. If the sequence numbers are different, a writer has changed the data while it was being read. In either case readers simply retry (using a loop) until they read the same even sequence number before and after.

The following paragraph is from wikipedia.

1
The reader never blocks, but it may have to retry if a write is in progress; this speeds up the readers in the case where the data was not modified, since they do not have to acquire the lock as they would with a traditional read-write lock. Also, writers do not wait for readers, whereas with traditional read-write locks they do, leading to potential resource starvation in a situation where there are a number of readers (because the writer must wait for there to be no readers). Because of these two factors, seqlocks are more efficient than traditional read-write locks for the situation where there are many readers and few writers. The drawback is that if there is too much write activity or the reader is too slow, they might livelock (and the readers may starve).

The pseudo is here. (Please notice that there are multiple writers here)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Lock write_lock
Write_Lock():
  write_lock.lock()
  atomic_increment(SN)
Write_Unlock():
  atomic_increment(SN)
  write_lock.unlock()
Reader_Lock():
  do 
    ret = atomic_read(SN)
  while ret % 2 == 0  // is odd
  start_sn = ret
Reader_Unlock():
  return start_sn != atomic_read(SN)
// Usage: To read data
do
  Reader_Lock()
  // DO read
while Reader_unlock()

A Simple Implementation

  • Here is a toy. In my codes, I use STL atomic variable to implement spin-lock (test and set) and sequencer. In the distributed system with RDMA, RDMA atomic verbs can replace the CAS and FAA operation of the gcc complier to build up distributed seq-lock.
  • Another simple implementation can be find here