sjo200 - CS 대학원 수업 정리 블로그

1. 개념

 skip-list란, 메모리를 list보다 더 많이 사용해서 (그리고 여러 데이터를 스킵해서) 빠르게 이동하여 볼 수 있게 하는 structure이다. 포인터를 많이 사용해서, 이진탐색과 같은 time complexity를 갖게 된다. skip-list의 한 노드는 여러개의 포인터를 가진다. 가장 윗 level의 포인터가 같은 level인 데이터를 가리키고, 그 밑의 level의 포인터는 그 밑의 level의 데이터를 가리킨다. 이미지를 보면 이해가 빠를 것이다.

 contains를 실행할 땐, 이진탐색으로 찾듯이 가장 위 포인터를 보고 크면 밑으로 한칸씩 내려가서 보고, 작거나 같으면 그 포인터로 이동하면 된다. remove는 해당 node의 포인터들이 가리키는 level과 어떤 노드가 자신을 가리키는지 레벨별로 알아야 한다. 이를 prev[], succ[]으로 찾아 list에서 했듯이 포인터 하나하나를 이어줘서 노드를 삭제시킨다. add 할땐 add 할만한 위치를 찾아서 random level로 넣어준다.

2. lock-based skip-list

 list 구현하듯이, add, remove, contains operation을 실행할 때 락을 걸고 한다. 포인터들을 다 옮겨주면 된다. 근데, 바로다음의 lock-free에서 할 수 있는 concurrency는 여기서 할 수 없다. 예를 들어, remove시 포인터를 제일 위부터 차례대로 바꿔주면, 다른 operation의 실행에 영향이 없다. 왜냐하면 그 노드를 볼 때, 윗 레벨의 포인터가 없으면 그냥 그 노드는 그보다 낮은 레벨인 노드와 같이 취급할 것이기 때문이다. 노드를 lock하기 때문에 이런 concurrency를 얻지 못한다. 

3. lock-free skip-list

 list에서는 어떻게 lock-free로 구현했는지 잘 생각해보자. AtomicMarkableReference를 썼고, CAS도 당연히 썼다. 다 똑같이 적용된다. 바로 앞서 말했듯이, remove에서 포인터를 하나씩 없애갈 수 있다. CAS에서 실패하면 다시 찾아가서 CAS 하는것도 똑같다. 또 똑같이 AtomicMarkableReference가 없으면 list에서 생긴 (add가 remove된 데이터에 연결해놓고 true를 리턴하는 그 문제)문제가 똑같이 생긴다.

4. lazy skip-list

 이번엔 다시 lock을 사용한다. 포인터마다 각각, 즉 노드마다 level 갯수만큼 mark bit를 두고, mark bit가 있는 포인터만 사용한다. remove할땐 locked-based에서 했던 것처럼 윗 level부터 mark를 지워나가면 된다. 여기서 logical remove가 끝나면 physical remove를 어떤 시점에서 하긴 해야하는데, 이것 때문에 다른 문제가 발생한다. remove 되고있는 곳에 contains를 하는 쓰레드가 있는데 remove가 끝나고 다른 쓰레드가 똑같은 값을 가진 노드를 추가해버려서 return false할 수 있기 때문이다. 이것 때문에 quiescent consistency가 보장되지 않아서 약간의 constraint를 추가하여 consistency를 얻어야한다. 그러나 그 제약이 미치는 영향은 크지 않아서 성능은 제일 좋다고 한다.

- 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

1. 개념

Shared counting이란, 여러 쓰레드가 getAndInc를 한다고 생각하면 된다. 만약 진짜로 그렇게 한다면, bottleneck이 걸릴 것이므로, 이 챕터에서는 적은 contention으로 하게 해주는 structure를 소개할 것이다.

2. Software combining tree

 이건 좀 어려운 개념이다. 쓰레드(프로세서) 개수 / 2만큼 리프노드를 만들고, 쭉쭉 위로 둘씩 이어서 바이너리 트리를 만들어야 한다. 그리고 노드에서 contention하여 combining하는 것인데, combining하게되면, (왼쪽 노드가 combining 했을때) 오른쪽 노드 값을 합해서 부모노드로 들고 올라가는 것이다. 이후 distribute에서 왼쪽노드에 더해지기 전 값을 주고, 오른쪽노드에 왼쪽노드의 값을 더한 값을 주는 것이다. 편의를 위해 왼쪽, 오른쪽을 강제했다.

 이해를 돕기위해 다른 경우를 생각해보자. getAndInc에서는 먼저 접근한 놈은 상대적으로 나중에 접근한 놈보다 적은 값을 받는다. 나중에 접근한 놈은 먼저 접근한 놈부터 나중에 접근한 놈까지 더해진 값을 다 더해서 받기 때문이다. 이걸 combining tree와 같이 생각해보면 먼저 간 놈(combining 한 노드)이 적은 값을 받을 것이므로 나중에 간 combining 하지 못한 노드에게 큰 값을 주는 것이다. 코드를 보면 더 쉽게 이해될 것이다.

 장점으로는, contention을 한 노드에서 두 쓰레드만 하게 되므로 contention의 수가 대폭 줄어 효과적으로 contention을 해결할 수 있다. 그러나 단점으로는, 최악의 경우 n번의 counting을 할 때, O(nlogn)만큼 걸려서 오히려 비효율적이다. 따라서 많은 쓰레드가 contention하면서 counting할 때 사용하여야 좋은 structure이다.

3. counting network

 counting network는 balancer들을 여러개 사용해서 만드는 것이다. balancer란, 2개의 인풋에 2개의 아웃풋으로 만들어지는데, 한 토큰이 어느 인풋으로 들어오든 아웃풋이 매번 교차하면서 토큰을 내보내는 것이다. 따라서 어느 인풋으로 토큰을 주던지 두 아웃풋의 차이는 최대 1이다. 이걸 여러개 사용하면, 4개 인풋 4개 아웃풋인 모듈을 만들어 토큰이 차례대로 쌓이도록 할 수 있다. 이것을 network라고 한다.

 counting network를 쉽게 구성하는 방법에는 bitonic counting network, periodic counting network가 있다. 이는 검색하면 나오므로, 생략한다. 둘다 공통적으로, 재귀적인 구성을 통해 2^n의 인풋, 아웃풋을 가진 network를 만들 수 있다.

 어떻게 그게 가능한지 증명해보자. merger[k]를 k개 인풋 아웃풋인 network라고 하면, merger[k] 두개를 뒀을 때, 둘은 한 줄에서 약간 어긋나지만 잘 카운팅 될 것이다. 이를 merger[2k]인 두 개를 두고 인풋에 넣는다고 쳐도, 아웃풋은 비슷하게 어긋나지만 잘 카운팅 될 것이다. 어긋난다는 말은 한 줄씩 채워지지만, 마지막 줄의 빈 곳이 둘로 나눠질 수 있다는 것이다.

 여기서, 마지막에 merger 각자 아웃풋 1번째를 연결하는 밸런서 , 2번째를 연결하는 밸런서, ... 를 배치하면, 토큰은 올바르게 카운팅 된다. 이해가 안된다면 책을 보자.

4. diffracting tree

 이젠 인풋이 하나인 밸런서를 써보자. 그럼 당연히 contention이 일어날 것이다. 이 때, concurrent stack에서 사용한 EliminationArray를 사용해보자. 두 쓰레드가 만나 서로의 아이디를 교환한 뒤, 수가 작은 놈은 위로 보내고, 큰 놈은 아래로 보낸다. 이게 다다. 근데 성능이 좋다. 중요한 점은 linearizability가 보장되지 않아서, pipelining 하듯이 보내면 concurrency가 생긴다고 한다. 책에서 그 말밖에 안했는데, 아마 depth가 같은 놈끼리 토큰을 동시에 보내면 그게 되지 않을까 싶다.

 이외에 structure 몇 개가 더 있는 것 같은데 강의하지 않았다.