Synchronization

Question 1

Cache Organization

Answer 1

caches are organized in fixed-size chunks called cache lines
* on most CPUs a cache line is 64 bytes
* data accesses go through cache, which is transparently managed by the CPU
* caches implement a replacement strategy to evict pages

Question 2

Cache Coherency Protocol

Answer 2

CPU manages caches and provides the illusion of a single main memory
using a cache coherency protocol

Question 3

Performance Implications of Cache Coherency

Answer 3

• reads result in copies of data in local caches
• writes invalidate cache lines on other cores
• communication between cores is fairly expensive (happens through shared
  L3 or main memory)

Question 4

x86-64 Memory Model

Answer 4

x86-64 implements Total Store Order (TSO), which is a strong memory model
* this means that x86 mostly executes the machine code as given
* loads are not reordered with respect to other loads, writes are not reordered
with respect to other writes
* however, writes are buffered (in order to hide the L1 write latency), and reads
are allowed to bypass writes
* a fence or a locked write operations will flush the write buffer (but will not
flush the cache)
* important benefit from TSO: sequentially consistent loads do not require
fences

Question 5

Concurrent List-Based Set

Answer 5

• keys are stored in a (single-)linked list sorted by key
• head and tail are always there (unendlichkeit elements)

Question 6

Coarse-Grained Locking

Answer 6

• use a single lock to protect the entire data structure
  + very easy to implement
  − does not scale at all

Question 7

Lock Coupling

Answer 7

hold at most two locks at a time
* interleave lock acquisitions/releases pair-wise
* read/write locks allow for concurrent readers
+ easy to implement
+ no restarts
− does not scale

Question 8

Optimistic Lock Coupling

Answer 8

• associate lock with update counter
• write:
• acquire lock (exclude other writers)
• increment counter when unlocking
• do not acquire locks for nodes that are not modified (traverse like a reader)
• read:
• do not acquire locks, proceed optimistically
• detect concurrent modifications through counters (and restart if necessary)
• can track changes across multiple nodes (lock coupling)
  + easy to implement
  + scalable
  − restarts

Question 9

Terminology: Non-Blocking Algorithms

Answer 9

• killing a thread at any point of time should not affect consistency of the data
  structure (this precludes locks)
• non-blocking data structures may be beneficial for (soft) real-time
  applications
• classification (from strong to weak):
• wait-free: every operation is guaranteed to succeed (in a constant number of
  steps)
• lock-free: overall progress is guaranteed (some operations succeed, while
  others may not finish)
• obstruction-free: progress is only guaranteed if there is no interference from
  other threads

Question 10

Lock-Free List

Answer 10

• insert and remove are lock-free, contains is wait-free
• remove: marks node for deletion, but does not physically remove it
• marker is stored within the next pointer (by stealing a bit of the pointer)
• contains traverses marked nodes (but needs same check as Lazy variant)
  + contains always succeeds
  + scalable
  − insert/remove may restart

Question 11

Lazy

Answer 11

• contains is wait-free
• insert/remove traverse list only once (as long as there is no contention)
• add marker to each node for logically deleting a key

+ usually only one traversal necessary
+ scalable
− insert/remove have to lock

Question 12

Locks

Answer 12

• locks are usually implemented using atomics
• waiting and suspending threads is an interesting problem 4
• tradeoff between speed on ’fast path’ and resource usage on ’slow path’

Question 13

Memory Reclamation for Lock-Free Data Structures

Answer 13

after deleting a node in a lock-free data structure, lock-free readers might
still be accessing that node
* freeing/reusing that node immediately can cause correctness problems
and/or crashes

Question 14

Reference Counting

Answer 14

• associate every node with an atomic counter
• effectively results in similar behavior as locks
  + easy to use
  − does not scale

Question 15

Epoch-Based Memory Reclamation

Answer 15

• global epoch counter (like timestamp, but incremented infrequently)
• per-thread, local epoch counters
• before every operation: enter epoch by setting local epoch to global epoch
• after every operation: set local epoch to ∞ indicating that this thread is not
  accessing any node

+ fairly low overhead, scales well
+ no need to change data structure code (simply wrap operations)
− a single slow/blocking thread may prevent any memory reclamation

Question 16

Traditional Hazard Pointers

Answer 16

Pointers for lock free operations

• observation: most lock-free operations only require a bounded number of
  node pointers at any point in time: hazard pointers
• during traversal, one can store these into a limited number of thread-local
  locations
• hazard pointers effectively announce to other threads “I am currently
  accessing this node, do not reclaim it”
• after storing the hazard pointer, one may need to check reachability again
• before physically reclaiming a node, check if any thread has a hazard pointer
  referencing that node
• normally the hazard pointer stores have to be sequentially consistent
  + non-blocking
  − high overhead: stores to HP must be sequentially-consistent
  − invasive: requires some data structure changes

Question 17

Implementing Shared Concurrent Counters

Answer 17

• alternative 1: shared global atomic counter
• alternative 2: per-thread counters, add up on demand
• alternative 3: approximate counter storing the logarithm of the counter value
  (incremented probabilistically)

Question 18

ART: lock coupling

Answer 18

• easy to apply to ART
• modifications only change 1 node and (potentially) its parent
• additional lock for root note changes
• can use read/write locks to allow for more concurrency

Question 19

ART: optimistic lock coupling

Answer 19

• fairly straightforward: add lock and version to each node
• how to detect that root node changed?
  1. extra optimistic lock for root pointer (outside of any node)
  2. always keep the same Node256 as root node (similar to static head element in
  list-based set)
  3. after reading the version of the current root, validate that the root pointer still
  points to this node

Question 20

ART with ROWEX

Answer 20

+ wait-free lookups
− much more complicated than OLC, requires invasive changes

Question 21

B tree: lock coupling

Answer 21

must detect root node changes (e.g., additional lock)
* structure modification operations may propagate up multiple levels:
* eagerly split full inner nodes during traversal (good solution for fixed-size keys)
* restart operation from the root holding all locks

Question 22

B tree: optimistic lock coupling

Answer 22

• writers usually only lock one leaf node (important for scalability)
• additional issues due to optimism:
• infinite loops: one has to ensure that the intra-node (binary) search terminates
  in the presence of concurrent modifications
• segmentation faults/invalid behavior: a pointer read from a node may be
  invalid (additional check needed)
• OLC is a good technique for B-trees

Question 23

B-link tree

Answer 23

• B-tree synchronization with only a single lock at a time (no coupling)
• observation: as long as there are only splits (no merges), the key that is
  being searched may have moved to a right neighbor
• solution: add next pointers to inner and leaf nodes, operations may have to
  check neighbor(s)
• fence keys may help determining whether it is necessary to traverse to
  neighbor
• the B-Link tree idea was very important when data was stored on disk but is
  also sometimes used for in-memory B-tree synchronization (

Question 24

B-tree Contention Split

Answer 24

for skewed workloads, lock contention at some lock can become a problem
* contention may be caused by page granularity rather than one very hot entry
* contention split optimization: if lock cannot be acquired on first try, with a
certain probability split node even if it is not full

Question 25

Bw tree

Answer 25

Latch-free B+Tree index
→ Threads never need to set latches or block.
Key Idea #1: Deltas
→ No updates in place
→ Reduces cache invalidation.
Key Idea #2: Mapping Table
→ Allows for CAS of physical locations of pages.

Question 26

Bw tree

Answer 26

Latch-free B+Tree index
→ Threads never need to set latches or block.
Key Idea #1: Deltas
→ No updates in place
→ Reduces cache invalidation.
Key Idea #2: Mapping Table
→ Allows for CAS of physical locations of pages.

Question 27

bw-tree: structure modifications

Answer 27

Split Delta Record
→ Mark that a subset of the base page’s key range is now
located at another page.
→ Use a logical pointer to the new page.
Separator Delta Record
→ Provide a shortcut in the modified page’s parent on what
ranges to find the new page.

Question 28

Lock-Free Hash Table: Split-Ordered List

Answer 28

all entries are stored in a single lock-free list (see lock-free list-based set)
sorted by the hash value of the key

Question 29

Recursive Split Ordering

Answer 29

key idea: store keys ordered by bit-wise reverse hash

Question 30

Deletion

Answer 30

• problem: deleting a node using CAS pointed to from a bucket does not work
  (because it is also being pointed to from the list)
• solution: for every split bucket, insert a special sentinel node into the list