---
tags: CS Master
---
# 111/6/8 meeting: DHASH - Dynamic Hash Tables with Non-blocking Regular Operations

## Introduction
* Hash table: an array of buckets
* One way of dealing with collision: separate chaining, which uses a list for the nodes with same hash value.
* Average length of the list: average load factor
* In general cases, given a specified average load factor, hash tables offer the advantage of constant-time lookup operations, such that they have been widely used throughout computer systems.
* Most existing hash tables are lacking of robustness. Unable to change hash function while **unable to distribute evenly** (no constant time lookup).
* Universal hashing (randomly choosing hash function) only works when input is diverse.
* This paper:
* Change hash function on the fly for even distribution. No more long traversing on lists.
* New size and seed as well $\to$ Dynamic
* Prior work:
* Only non-blocking for regular operation
* When redistributing they used locks per bucket $\to$ blocking
* Our work: DHash
* a new distributing mechanism that can atomically and efficiently distribute each node without needing to acquire any per-bucket mutex locks
* Utilize lock-free and wait-free algorithms for buckets
* DHash's rebuilding is scalable and paralleled

## DHash algorithm overview
* Hazard period: a short time period during which in neither the hash tables can this node be found.
* Use a global pointer for nodes in hazard period
* old_ht $\to$ global pointer $\to$ new_ht


## DHash implementation
Note: we use RCU as synchronization mechanism. Reference counting and hazard pointer could be used with more engineering efforts.

### Preliminaries
* `rcu_read_lock() / rcu_read_unlock()`: defines the read-side critical section.
* `synchronize_rcu()`: works as a wait-for-readers barrier
* `call_rcu()`: an asynchronous version of `synchronize_rcu()`. Call callback when read-side critical section end.

Algorithm 1: Structures and API of DHASH’s bucket.

struct node {long key; <node *ptr, flag> next};
/* Has been logically removed by delete operation.*/
#define LOGIC_RM (1UL < < 0)
/* Is being distributed by rebuild operation.*/
#define IN_HAZARD (1UL < < 1)
struct list {node *head};
struct snapshot {node **prev, *cur, *next};
/* Search the node in list htbp.*/
list_find(list *htbp, key, snapshort *sp)
/* Insert node htnp into list htbp.*/
list_insert(list *htbp, node *htnp)
/* Search the node in list htbp, set the node’s flag, and try to physically delete the node.*/
list_delete(list *htbp, long key, long flag)

**Choice of hash function:** We suggest first utilize some widely-used non-cryptographic hash functions (e.g., Jenkins’ hash function). Or fallback to universal hashing.

### Data structures
Algorithm 2: Structures and auxiliary functions.

struct ht {ht *ht_new; long (*hash)(long key); int nbuckets; list *bkts[]};
/* Global variables.*/
struct node *rebuild_cur;
mutex rebuild_lock;

#define logically_removed(htnp) (htnp->next & LOGIC_RM)
clean_flag(node *htnp, long flag) {
    atomic_fetch_and(htnp->next, ∼flag);
}
ht_alloc(ht *htp, int nbuckets, long (*hash)(long key)) {
    htp->ht_new := NULL; htp->hash := hash;
    htp->nbuckets := nbuckets; htp->bkts := allocate(nbuckets);
}

### Rebuild operation
Algorithm 3: Rebuild operation of DHASH

Parameters - nbuckets: Size of the bucket array.
             hash: User-specified hash function.
Local variables - struct node *htnp, *htbp, *htbp_new; struct ht *htp_new;

void ht_rebuild(ht *htp, nbuckets, hash) {
    if ( trylock(rebuild_lock) != SUCCESS ) return -EBUSY;
    if (!rebuild_is_required()) return -EPERM;
    htp_new := ht_alloc(htp, nbuckets, hash);
    htp->ht_new := htp_new; /* Wait for operations not aware of htp_new.*/
    synchronize_rcu();
    for (each bucket htbp in htp) {
        for (each node htnp in htbp) {
            rcu_read_lock();
            rebuild_cur := htnp;
            smp_wmb();
            key := htnp->key;
            if (list_delete(htbp, key, IN_HAZARD)!= SUCCESS)//Hflag
                continue;
            clean_flag(htnp, IN_HAZARD)/* unHflag*/
            htbp_new := htp_new->bkts[htp_new->hash(key)];
            if (list_insert(htbp_new, htnp) != SUCCESS)
                call_rcu(htnp, free_node);
            smp_wmb();
            rebuild_cur := NULL;
            rcu_read_unlock();
        }
    }
    /* Wait for operations accessing nodes via htp->bks[]. */
    synchronize_rcu();
    htp_tmp := htp; htp := htp_new;
    /* Wait for operations accessing old hash table.*/
    synchronize_rcu();
    unlock(rebuild_lock);
    free(htp_tmp);
    return SUCCESS;
}

:::danger
為什麼他不先進入 reader CS 再取得 node reference (line28)? 這樣還要再檢查有沒有被 delete (line33)
:::
:::danger
> line38 invokes call_rcu(), which reclaims the node after currently unfinished operations pointing to this node have been completed.

如果 node 本來就會被移除那就直接移除就好了吧？幹麻先插入再移除？可能連 rcu_lock() 都不用，只要檢查有沒有被設置 LOGIC_RM，有的話就 `continue`
:::

* for each node in bucket
* move to `rebuild_cur`
* can old be delete? If no, left it for clean_flag
* insert to new table
* One potential issue: it may redirect lookup operations traversing the old hash table to the wrong lists
* Use `bkt_id` to record current bucket id and compare everytime
* After deleting, before inserting, invokes a `synchronize_rcu()` to wait all regular operation leave RCU read-side CS. Slow down a bit but no need for extra field and compare. $\to$ we use this cause rebuild is infrequent.

### Lookup operation
Algorithm 4: Lookup operation of DHASH.

Local variables: struct node *cur, *htbp, *htbp_new; struct ht *htp_new;
                 struct snapshot ss;
node *ht_lookup(ht *htp, long key) {
    htbp := htp->bkts[htp->hash(key)];
    if (list_find(htbp, key, &ss) = SUCCESS) { return ss.cur };
    if (htp->ht_new = NULL) { return -ENOENT };
    smp_rmb();
    cur := rebuild_cur;
    if (cur and (cur->key = key) and !logically_removed(cur))
        return cur;
    smp_rmb();
    htp_new := htp->ht_new;
    htbp_new := htp_new->bkts[htp_new->hash(key)];
    if (list_find(htbp_new, key, &ss) = SUCCESS) { return ss.cur };
    else return -ENOENT;
}

* Search in the old table $\to$ global pointer $\to$ new table.
* Guarantees that lookup operations can always find the node.

$Lemma\space1.$
If DHASH contains a node $\alpha$ with the key value of k, the function `ht_lookup(k)` can find $\alpha$, no matter if a rebuild operation is in progress.

$proof.$
We assume that the set algorithm used as the implementation of hash table buckets is linearizable. Therefore, `list_find()`, `list_insert()`, and `list_delete()`, can be treated as atomic operations that take place as "point" events.

By inspecting the code of `ht_rebuild()` in algorithm 3,

By inspecting the code of `ht_lookup()` in Algorithm 4,

When the rebuild and the lookup threads are simultaneously accessing the node $\alpha$, there are three types of interleaving between these two threads:
* 
* 
* $insert(new,\alpha)$

Combined with the event sequences 1 and 2, we get the following event sequence:


It follows that

Overall, if there is a node with the matching key in DHASH, it is guaranteed that the function `ht_lookup(k)` can find the node and return a pointer to it, no matter if a rebuild operation is in progress.

### Delete operation
Algorithm 5: Delete operation of DHASH.

Local variables: struct node *cur, *htbp, *htbp_new; struct ht *htp_new;
int ht_delete(ht *htp, long key) {
    htbp := htp->bkts[htp->hash(key)];
    if (list_delete(htbp, key, LOGIC_RM) = SUCCESS)/*Rflag*/
        return SUCCESS;
    htp_new := htp->ht_new;
    if (htp_new = NULL) return -ENOENT;
    smp_rmb(); //checking if a rebuild operation is in progress
    cur := rebuild_cur;
    while (cur and (cur->key = key)) {
        cur_next := cur->next;
        if (cur_next & LOGIC_RM) break;
        if (cas(cur->next, cur_next, cur_next | LOGIC_RM))/*Rflag*/
            return SUCCESS;
        cur := rebuild_cur;
    }
    smp_rmb();
    htbp_new := htp_new->bkts[htp_new->hash(key)];
    if (list_delete(htbp_new, key, LOGIC_RM) = SUCCESS)/*Rflag*/
        return SUCCESS;
    return -ENOENT;
}

:::danger
論文提到的 The second stage 實際把 node 移除的 psuedo code 和說明怎麼沒寫？怎麼做的？在什麼時候做的？
:::

Challenges of deleting a node:
* how to find the node
* same logic as `ht_lookup()`
* how to delete this node which is concurrently being distributed from the old hash table to the new one by the rebuild operation
* Logical/physical delete (Common in concurrent program. Sometimes memory don't even get reclaimed)


$Lemma\space 2.$
No matter where the node is (either in one of the hash tables, or is referenced by rebuild_cur), a delete operation can successfully delete it by setting its LOGIC_RM bit.

$Lemma\space 3.$
If DHASH contains a node α with the key k, the function ht_delete(k) can delete the node α by successfully setting its LOGIC_RM bit, no matter if a rebuild operation is in progress.

Flag are all set using $cas$

### Insert operation
Algorithm 6: Insert operation of DHASH.

Local variables: node *htnp, *htbp, *htbp_new; ht *htp_new;
int ht_insert(ht *htp, long key) {
    retry:
    htnp := allocate_node(key);
    htp_new := htp->ht_new;
    if (htp_new = NULL) {
/* IO(k)
*/
        htbp := htp->bkts[htp->hash(key)];
        ret := list_insert_dcss(&htp->htp_new, NULL, htbp, htnp) ;
        if (ret = SUCCESS) return SUCCESS ;
        else if (ret = -EADDR1) {free(htnp); goto retry (line 91);}
    }
    else {
    /* IN(k)*/
        if (ht_lookup(htp, key) = SUCCESS) {free(htnp); return -EEXIST;}
        htbp_new := htp_new->bkts[htp_new->hash(key)];
        if (list_insert(htbp_new, htnp) = SUCCESS)
            return SUCCESS;
    }
    free(htnp);
    return -EEXIST;
}

:::danger
又 `if` 又 `dcss` ? 是不想寫 critical section 嗎？檢查兩遍感覺很多餘
:::
:::info
line 102 `ht_lookup()` 只是拿來檢查是否有已經存在的 node，如果用 bloom filter 會不會比較快？
:::

* When there are no rebuild operations, which is the common case, DHASH inserts new nodes into the only (i.e., old) hash table
* Otherwise, new nodes are inserted into the new hash table
* IO(k) and IN(k) may exist simultaneously, such that some synchronization mechanisms are required to prevent IO(k) and IN(k) from inserting duplicate nodes in DHASH.
* Once a rebuild operation starts, IO(k) stops, by using `dcss`
* An IN(k) first checks if any node with key k already exists in the old hash table or is currently referenced by `rebuild_cur`

Lemma 4.
Once a rebuild operation has started, IO(k) will fail, start over, and then attempt to insert the node into the new hash table; that is, it becomes IN(k).

Lemma 5.
When IN(k) attempts to insert a node α with key k into the new hash table on line 103, it is guaranteed that (1) the old hash table does not contain any node with key k , and (2) the node referenced by rebuild_cur does not have the key k .

Lemma 6.
If DH ASH does not contain a node with key k , the function ht_insert(k) can successfully insert a node α with key k in DH ASH; otherwise, the error message `-EEXIST` is returned without changing the hash table, no matter if a rebuild operation is in progress.

Overall, DH ASH always attempts to insert new nodes into either the old or the new hash table, depending on whether rebuild operation are absent,

### Parallelizing rebuild operation
* Use multiple thread to rebuild. Different bucket can be processed in parallel.
* bucket b is assigned to the rebuilding thread i if b % n = i.
* rebuild_cur becomes a global, per-thread variable;
* To check rebuild_cur, it checks the rebuild_cur pointers of all rebuilding threads.

## Correctness
We first prove that DHASH is linearizable to this sequential specification. That is, each of DHASH’s regular operations has specific linearization points, where the operation takes effect and maps the operation in our concurrent implementation to sequential operations so that the histories meet the specification.

### Linearization point
1. Every lookup operation that finds the node with the expected key via `rebuild_cur`, or in the old or the new hash table. We linearize the unsuccessful lookup operation within its execution interval at:
* the point immediately before a new node with the expected key is inserted into the old hash table
* the point where the search on the new hash table returns -ENOENT
2. every successful delete operation that finds the node with the required key via lookup
3. Every successful IN(k) linearizes in the invocation of `list_insert()`. Unsuccessful IN(k) linearizes on line 101 or 103, depending on where the existing node with the required key is found.

$Theorem 1$
DHASH is a linearizable implementation of a sequential set object.

**Progress guarantee:** The lookup, insert, and delete operations of DH ASH are non-blocking and can provide lock-free or wait-free progress guarantee, depending on the underlying set algorithm used.

* list_find()
* list_delete()
* list_insert()
* call_rcu()

In summary, DHASH provides a wait-free framework for regular operations. For the implementation of DHASH utilizing Michael’s lock-free linked list, the lookup, insert, and delete operations are lock-free. However, since DHASH is modular, programmers can instead choose a wait-free linked list and build their own DHASH that provides a stronger progress guarantee.

## Evaluation
We want to show DHASH's robustness, efficiency, and scalability.
1. DHASH’s rebuild operation is effective
2. DHASH’s rebuild operation is lightweight and does not noticeably degrade system performance in terms of throughput and response time of concurrent regular operations
3. DHASH’s rebuild operation is fast and scalable

* Initial array size 1k, max 64k
* An attacker thread continuously insert nodes at 300/s
* If list length is larger than the threshold (32), rebuild.

### Effects of Rebuilding


### DHash performance
* throughput
* response time

### Rebuilding efficiency


## Conclusion
* The core of DH ASH is a novel distributing mechanism that is atomic, non-blocking, and efficient in distributing every node from the old hash table to the new one.
* Experimental results indicate that DH ASH is the algorithm of choice for operating systems and applications under service-level agreement (SLA) contracts.

### 鳴謝
* We thank Pedro Ramalhete and ==Paul E. McKenney==, whose detailed suggestions greatly improved this paper.
* OSU Open Source Lab and Packet Incorporation for allowing us to access the 16-core PowerPC and the ==96-core ARM64== servers.