concurrent skip-list

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를 얻어야한다. 그러나 그 제약이 미치는 영향은 크지 않아서 성능은 제일 좋다고 한다.