Hash tries

Hash tries (Hash array mapped tries) are trees composed of internal nodes and leaves. Leaves store key-value bindings.

Race

T1要插入k5到C2，与此同时T2要插入k4到C1。T1成功的进行了CAS，但是T2进行的CAS操作是在老的C2上，最后导致k4丢失。

Cuckoo hashing

Cuckoo hashing是Rasmus Pagh, Flemming Friche Rodler在2001年提出的，在hash table中用于解决hash collision的一种方法，是一种开放寻址法的hash table。

specification

• no duplicate key

• deleting non-existent key leads to return false

• leaf-oriented BST

  • all keys currently in the dictionary are stored in the leaves of the tree.
  • Internal nodes of the tree are used to direct a Find operation along the path to the correct leaf.
  • The keys stored in internal nodes may or may not be in the dictionary.

features

• non-blocking

• linearizable

  for every execution, one can assign a linearization point to each completed operation and some of the uncompleted operations so that the linearization point of each operation occurs after the operation starts and before it ends, and the results of these operations are the same as if they had been performed sequentially, in the order of their linearization points.

Introduction

RCU, this barrier-based mechanism, allows for simple epoch-based reclamation of the old copies, and the mechanism as a whole eliminates many of the atomic read-modify-write instructions, memory barriers, and cache misses that are so expensive on modern multicore systems.

About RLU

• Novel extension of RCU framework that support read-only traverals concurrently with multiple updates.
• In a semi-automated way.
• Removes from the programmer the burder of handcrafting the concurrent copy management using only single pointer manipulations.
• Can be API-compatible with RCU.

About Implementation of RLU

• Clock-based logging mechanism.
• Object-level write-log per thread.

Algorithms

Idea

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

// For all operations:

   +--------------+
   |all operations|
   +------+-------+
          |
          |
+---------v-----------+
|read the global clock|
+---------+-----------+
          |
          |
       +--v--+
       |start|
       +-----+

// For writer:
                              +------+
              +--+            |writer|
              |               +---+--+
              |                   |
              |                   |
              |     +-------------v-------------------------------+
              |     | copy the object into a its own              |
modification<-+     |thread wirte-log and lock the original object|
              |     +-------------+-------------------------------+
              |                   |
              |                   |
              |      +------------v-------------+
              |      |manipulate the object copy|
              +---+  +--------------+-----------+
                                    |
                                    |
              +---+    +------------v------------------------------+
              |        |increments the write clock and global clock|
              |        +------------+------------------------------+
              |                     |
              |                     |
              |      +--------------v----------------+
              |      |splits operations into two sets|
              |      +--------------+----------------+
              |                     |
      commit<-+                     |
              |     +---------------v-----------------+
              |     |wait for old operations to finish|
              |     +---------------+-----------------+
              |                     |
              |                     |
              |     +---------------v--------------------+
              |     |   write back the new objects       |
              |     |from the writer-log into the memory,|
              |     |  overwriting the old objects,      |
              |     |      release the locks             |
              +---+ +------------------------------------+

The writer’s modifications are:

Brief Introduction

1. a synchronization mechanism.

2. allowing read to occur concurrently with updates.

3. supports concurrency between a single updater and multiple readers.

4. ensures that reads are coherent by maintaining multiple versions of objects and ensuring that they are not freed up until all pre-existing read-side critical sections complete.

5. defines and uses efficient and scalable mechanisms for publishing and reading new versions of an object, and also for deferring the collection of old versions.

declaration

one basic type + zero or more derived types

basic type

char, signed char, unsigned char, short, unsigned short, int, unsigned int, long, unsigned long, float, double, void, struct tag , union tag, enum tag, long long, unsigned long long, long double

derived types

*: pointer to … - always on the left side []: array of … - always on the left side (): function returning … - always on the left side