### Topic : Nonblocking open addressing hash table with rebuild operation
題目來自 Future work of [DHASH: Dynamic Hash Tables With Non-Blocking Regular Operations](https://ieeexplore.ieee.org/document/9714033)
## DHASH
* 討論 hash table 的 robust 議題 (i.e. change pre-defined hash functions when they can not evenly distribute incoming data to the hash table buckets).
* Most existing hash tables, including resizable ones, are unable to solve this problem effectively.
* 設計 rebuild operation that is lightweight and does not noticeably degrade the performance of concurrent regular operations.
* regular operations are non-blocking, while the rebuild operation is blocking.

## Chaining vs. Open addressing
不同的 key 對應到相同 bucket 稱為 collision.
### Chaining
### Open addressing
根據 probing 策略選擇下一個 bucket
#### insert 0, 8, 16, 24 (mod 8)

digraph ele_list {
    rankdir= LR
    node[shape=record]    
    ht1 [label="<0> 0 |<4> 8 |<8> 16 |<12> 24|- |- |- |-", style="bold", height=2]
    ht1:0 -> ht1:4 [headlabel="collision!           ", labeldistance=4]
    ht1:4 -> ht1:8 [headlabel="collision!            ", labeldistance=4]
    ht1:8 -> ht1:12 [headlabel="collision!           ", labeldistance=4]
}

* probe sequence : probe 所經的 bucket 稱為 probe sequence
* 若 probe sequence 很長 lookup time complexity : constant time -> O(n)

## 研究目標
* open addressing hash table with rebuild operation
* nonblocking regular operation
* prove linearizability, nonblocking
## Extensions
* nonblocking rebuild operation
* multi-word keys
* key 長度超過 one word 無法使用一個 atomic load, atomic store, CAS 存取

## How to make rebuild operation nonblocking
#### DHASH's rebuild operation

21: void ht_rebuild(ht *htp, nbuckets, hash) {
22:     if ( trylock(rebuild_lock) != SUCCESS ) return -EBUSY;
23:     if ( ! rebuild_is_required() ) return -EPERM;
24:     htp_new := ht_alloc(htp, nbuckets, hash);
25:     htp->ht_new := htp_new;
        /* Wait for operations not aware of htp_new . */
26:     synchronize_rcu();
27:     for each bucket htbp in htp {
28:         for each node htnp in htbp {...

### DHASH's insert operation

90: int ht_insert(ht *htp, long key) {
91:     retry:
92:     htnp := allocate_node(key);
93:     htp_new := htp->ht_new;
94:     if htp_new = NULL{
            /* IO(k) */
            /* insert node to old hash table */
 99:    }
 100:   else{
            /* IN(k) */
            /* insert node to new hash table */
 105:   }...
       

### Solution 1

90: int ht_insert(ht *htp, long key) {
91:     retry:
92:     htnp := allocate_node(key);
93:     htp_new := htp->ht_new;
94:     if htp_new = NULL{
            /* IO(k) */
            /* insert node to old hash table */
            if(rebuild operation started before insert finish)
                goto retry;
 99:    }
 100:   else{
            /* IN(k) */
            /* insert node to new hash table */
 105:   }...

### Solution 2

21: void ht_rebuild(ht *htp, nbuckets, hash) {
22:     if ( trylock(rebuild_lock) != SUCCESS ) return -EBUSY;
23:     if ( ! rebuild_is_required() ) return -EPERM;
24:     htp_new := ht_alloc(htp, nbuckets, hash);
25:     htp->ht_new := htp_new;
        /* Wait for operations not aware of htp_new . */
26:     Assist();
27:     for each bucket htbp in htp {
28:         for each node htnp in htbp {...

---
### Bounding searches
#### insert 需確認是否增加 bound

void ConditionallyRaiseBound(int h, int index): // Ensure maximum ≥ index
    do
        <old bound,scanning> := bounds[h]
        new bound := max(old bound,index)
    while ¬CAS(&bounds[h],<old bound,scanning>,<new bound,false>)

#### delete 需確認是否減少 bound

void ConditionallyLowerBound(int h, int index): // Allow maximum < index
    <bound,scanning> := bounds[h]
    if scanning = true
        CAS(&bounds[h],<bound,true>,<bound,false>)
    if index > 0 // If maximum = index > 0, set maximum < index
        while CAS(&bounds[h],<index,false>,<index,true>)
            i := index-1 // Scanning phase: scan cells for new maximum
            while i > 0 ∧ ¬DoesBucketContainCollision(h, i)
                i--
            CAS(&bounds[h],<index,true>,<i,false>)

### Insertion of open addressing
* 檢查是否有相同的 key 在 hash table 中
* 將 key insert 進 hash table

困難的地方在於如何確保這兩個動作是 atomic.
#### obstruction-free insert
二個步驟:
* Find an empty slot in the probe sequence and insert the new key into that slot.
* Check if there is same key in the hash table.
* 若遇到相同的 key 且狀態為 `inserting` : 將該 bucket 狀態改為 `busy`
* 若遇到相同的 key 且狀態為 `member` : 放棄 insert 並 return false

bool Insert(Key k) // Insert k into the set if it is not a member
    int h = Hash(k);
    int i = 0; // Reserve a cell
    while (!CAS(Bucket(h, i), <-, empty>, <k, busy>))
        i++;
        if (i >= size)
            throw "Table full";
    
    // Attempt to insert a unique copy of k
    do
        *Bucket(h, i) = <k, inserting>;
        ConditionallyRaiseBound(h, i);
        
        int max = GetProbeBound(h); // Scan through the probe sequence
        for (int j = 0; j < max; j++)
            if (j != i)
                if (*Bucket(h, j) == <k, inserting>) // Stall concurrent inserts
                    CAS(Bucket(h, j), <k, inserting>, <k, busy>);
                if (*Bucket(h, j) == <k, member>) // Abort if k already a member
                    *Bucket(h, i) = <k, busy>;       
                    ConditionallyLowerBound(h, i);
                    *Bucket(h, i) = <k, empty>;
                    return false;
    while (!CAS(Bucket(h, i), <k, inserting>, <k, member>));   
    return true;

> 若 inserts 互相 stall 會造成 live-lock，因此上述 insert 為 obstruction-free.
obstruction-free 的定義為:
> * At any point, a single thread executed in isolation for a bounded number of steps will complete its operation.
> * 與 lock-free 的差別為是否會造成 live-lock

#### lock-free insert
若遇到 concurrent insert 相同的 key，則在 probe sequence 排序較後的 insert 放棄，排序較前的 insert 成功.
排序較後的 insert 須等待 (blocking) 或幫助 (nonblocking) 排序較前的 insert 完成才能 return 否則會違反 linearizability.

bool Insert(Key k): // Insert k into the set if it is not a member
    h := Hash(k)
    i := -1 // Reserve a cell
    do
        if ++i ≥ size
            throw "Table full"
        <version, state> := Bucket(h, i) → vs
    while ¬CAS(&Bucket(h, i) → vs, <version, empty>, <version, busy>)
    Bucket(h, i) → key := k
    while true // Attempt to insert a unique copy of k
        *Bucket(h, i) → vs := <version, visible>
        ConditionallyRaiseBound(h, i)
        *Bucket(h, i) → vs := <version, inserting>
        r := Assist(k, h, i, version)
        if Bucket(h, i) → vs != <version, collided>
            return true
        if ¬r
            ConditionallyLowerBound(h, i)
            Bucket(h, i) → vs := <version + 1, empty>
            return false
        version++

bool Assist(Key k, int h, int i, int veri): // Attempt to insert k at i
    max := GetProbeBound(h) // Scan through probe sequence
    for j := 0 .. max
        if i != j
            <ver_j, state_j> := Bucket(h, j) → vs
            if statej = inserting ∧ Bucket(h, j) → key = k
                if j < i // Assist any insert found earlier in the probe sequence
                    if Bucket(h, j) → vs = <ver_j, inserting>
                        CAS(&Bucket(h, i) → vs, <ver_i, inserting>, <ver_i, collided>)
                        return Assist(k, h, j, ver_j)
                else // Fail any insert found later in the probe sequence
                    if Bucket(h, i) → vs = <ver_i, inserting>
                        CAS(&Bucket(h, j) → vs, <ver_j, inserting>, <ver_j, collided>)
            <ver_j, state_j> := Bucket(h, j) → vs // Abort if k already a member
            if state_j = member ∧ Bucket(h, j) → key = k
                if Bucket(h, j) → vs = <ver_j, member>
                    CAS(&Bucket(h, i) → vs, <ver_i, inserting>, <ver_i, collided>)
                    return false
    CAS(&Bucket(h, i), <ver_i, inserting>, <ver_i, member>)
    return true

---
:::spoiler {state="open"} Reference
[DHash: Dynamic Hash Tables With Non-Blocking Regular Operations](https://ieeexplore.ieee.org/document/9714033)
[Lock-free Dynamic Hash Tables with Open Addressing](https://arxiv.org/abs/cs/0303011)
[Concurrent Hash Tables: Fast and General(?)!](https://arxiv.org/abs/1601.04017)
[Non-blocking hashtables with open addressing](https://timharris.uk/papers/2005-hashtable.pdf)
[Dynamic-Sized Nonblocking Hash Tables](https://dl.acm.org/doi/10.1145/2611462.2611495)
:::