Read-Log-Update

---

- Hide Paper Summary

---

Highlights:

1. RLU can be considered as a reduced form of timestamp based STM, which makes it more lightweight and actually usable.

Questions

1. The “RLU Deferring” section is highly unclear and even sometimes self-contradictory. For example, at the second page of section 3.7, it is said “it significantly reduces the contention on the global clock, since this clock only gets updated after RLU synchronization calls”, while at everywhere else the global clock is said to be updated before the synchronize call.

2. I don’t quite buy the argument that RLU deferral generally optimizes things, because the thread still has to execute a synchronization barrier waiting for all other threads, and then write back the log (i.e. in the general case the number of synchronizations and write backs do not change). It is only beneficial when the same object is updated by the same thread repeatedly, at which time multiple write backs and synchronizations can be batched into one, at the cost of delayed visibility of data (i.e. not linearizable since non-overlapping readers after the writer in real time cannot observe the change). The paper leaves out this important assumption and simply claim that deferred updates are good in all cases.

3. I can hardly image why the order of setting the local write counter and incrementing the global clock matters. If the former happens first, readers always see a valid version as shown in the paper. If the latter happens first, it is also fine, because the write timestamp is initialized to +∞ every time write starts, readers will think that the write is from a far future and still access the master copy.

4. There should be two GC, one to the old master copy, another to the private log. The first GC happens after readers are redirected to the private copy, during which readers to the master copy is drained. The second GC should also be after the copy back is complete and the object is unlocked, since there can still be readers on the private copy. This GC waits for readers to be drained from the log, only after which the log is reused. The second GC is not mentioned anywhere in the paper.

5. I would suggest paper authors not putting pseudo source code as much as possible. If the text is obsecure, pseudo code can only introduce even more unclarity.

This paper proposes a new synchronization paradigm called “Read-Log-Update” (RLU). Similar to Read-Copy-Update (RCU), RLU duplicates the object under modification before applying changes to the private copy. The important difference, however, is that while RCU only supports updating single-entry objects (i.e. the object must only be accessed via one single pointer), due to the fact that RCU relies on atomic exchange of the sole pointer providing access to it, RLU has no such contraint, and supports a broader range of object types.

We present the process of reading and writing an RLU object as follows. Each object in RLU is extended with a header, which contains a pointer pointing to the private copy of the object in a thread’s log, or a NULL pointer. This object header serves two purposes in RLU. First, it is a writer lock which serializes writers on the same object. A writer should first read the lock before accessing the object, and checks whether the lock value is NULL. If not, the writer should retry. Second, the header also provides a “redirection” mechanism for other readers to find the updated version, as we will see later. A global clock counter, initially set to zero, provides the notion of time in RLU, which is used to serialize between readers and writers. Every thread has two local counters, local read counter and local commit counter, and a private buffer for the copy of the object. The local read counter is initialized from the global clock before accessing the object, while the local commit counter is set to +∞ before the access.

In RLU, reader threads either access the master copy of the object, or access the private copy. Whether or not reads are redirected are determined by two factors. First, if the object is not currently locked, the reader should always access the master copy, since no writer has ever started updating the object. Second, if the object is locked, but the writer (whose identity is the value of the lock) has not finished updating it, the reader should also refrain from accessing the partially updated object to avoid inconsist reads. On the writer side, given that the object is not currently locked by another writer, the object will first be copied to the private buffer before any modification is made. When the modification is complete, the writer will publish writes by allowing readers to be redirected from the master copy to its private copy. This redicrection mechanism is described as follows. The writer thread first sets its own commit counter to the current value of the global clock plus one, before it atomically increments the global clock.

Too many inconsistencies in the paper, not going to finish it