Concurrent Hashing

- Closed-Address Hash Sets (Unbounded)

1. 개념

 list, stack, shared counter를 concurrent하게 만드는 방법을 알아보았으니, 이번에는 Hash set도 concurrent하게 만들어보자. hash set은 add, remove, contains operation을 지원한다.

2. Coarse-grained hash set

 그냥 접근할 때 락 건다. bucket array 하나 잡고, hash function에 따라 해당하는 bucket에 operation을 실행한다. bucket 안에 여러개를 저장하면, 포인터로 연결해서 sequential하게 찾아야한다. resize는 add 했을때 조건이 되면 resize한다. sequential programming.

3. Fine-grained hash set

 이건 bucket마다 lock을 건다. 주의할 점은 resize 할때 bucket은 커지지만, lock 개수는 커지지 않으므로 lock 개수가 L개라면, modulo L 로 락에 접근해야 한다.

4. Lock-free hash set

 lock-free 하게 만들려면 생각 좀 많이 해봐야 할 것이다. 이전에 구현하던 방법대론 안되니까 List를 사용해야 한다. List를 만들고, bucket은 short cut이 되면 hash set이 구현된다. 근데 이 short cut으로 연결하려는데 recursive split-ordering이란 순서대로 bucket을 sentinel node에 연결해야 한다. 여기서 sentinel node란 data에 연결되는 포인터가 두 개 이상이 되지 않도록(contention이 쉽게 많이 일어나므로), 시작지점 더미 노드를 만드는 것이다. sentinel node는 보통 queue에서도 head, tail과 같이 데이터가 아닌 부분을 말한다. 

 

 recursive split-ordering으로 2 bits에 대해 순서를 매기면, 00, 01, 10, 11 을 다 뒤집어서 생각하면 된다. 00은 00번째, 01은 10번째, 10은 01번째, 11은 11번째인데, 즉 0, 2, 1, 3 순 대로 sentinel node가 위치하게 된다. 그리고, 데이터는 자신의 좌측에서 가장 가까운 sentinel의 bit와 자신의 LSB(least significant bits)가 같아야 한다. 따라서, sentinel node를 (x)로 표현하고 데이터는 x 로 표현해서 어떤 hash set을 나타내면, 

head->(0)->8->4->(2)->6->2->(1)->5->(3)->3->tail 

다음과 같이 표현할 수 있다. 여기서 3 bits로 늘리자고 하면, 다시 recursive split-ordering을 통해 4, 5, 6, 7의 순서를 정할 수 있고, LSB에 따라 데이터를 넣어주면 된다.

 이렇게 데이터를 만들고 나면, add, remove, contains는 쉽게 CAS로 만드는 방법을 생각할 수 있다.

- An Open Addressed Hash Set (array-based)

5. Cuckoo hashing

 Cuckoo란, 새의 일종인데 남의 새집에 가서 알들을 치워버리고 자신의 알을 낳는 종이다. Cuckoo Hashing은 array 두 개를 갖고 두 hash function을 가진다. 데이터를 add 할때, 첫 번째 array에 가서 무조건 바꿔본다. 바꿔서 null 이면 멈추고, 데이터가 있으면 두 번째 array로 가서 똑같이 한다. 그 때에도 데이터가 있으면 resize 한다. 이걸 concurrent하게 할려면, 2 dimension array로 리스트 테이블을 만들어야 하는데, 이건 책을 보는게 낫다. 나중에 쓰일 일도 없을 것이다.

6. Hopscotch hashing

 이건 좋다. concurrency도 되고, array-based라 cache coherence도 보장된다. 또한, 여기서 사용하는 constant H = 32일 경우, resize 할 확률은 1/32! 이다. 설명은 다음 페이지로 대체한다.

https://tessil.github.io/2016/08/29/hopscotch-hashing.html