LockFreeHashing
Fine-grained Lock의 문제
멀티 쓰레드 상황에서 Hash에 consistency를 유지하고 싶다면 hash의 key에 lock을 걸어서 사용하는게 일반적인 방식일 것이다.
우리는 Hash를 사용하는 이유는 시간복잡도가 매우 낮기 때문일 것이다. 하지만 hash key 1개당 가지고 있는 데이터 수가 늘어나게 되면 이러한 시간복잡도로 인한 장점은 무색해진다. 따라서 Bucket 크기를 늘려야하는 시점이 오게 된다.
Fine-grained Lock을 사용하는 상황에서 bucket을 증가시킨다고 하면 어떤 식으로 증가시켜야할까?
다음 그림을 보자
이 상황에서 우리가 bucket의 크기를 늘리게 된다면 늘어난 bucket에 대해 lock을 할당해야할 것이다. 하지만 lock의 갯수를 늘리는게 맞는 걸까? 여러 쓰레드가 위의 hash를 사용하고 있는 상황에서 새로운 lock을 도입하게 된다면 중간에 holl이 발생하게 되고 이에 따라 데이터의 consistency가 떨어지게 된다.
따라서 다음과 같이 기존에 사용하고 있는 lock에 대해 다음과 같이 Lock을 재사용해야할 것이다.
하지만 이런식으로 Lock을 사용하는건 당연히 시간복잡도 측면에서 전혀 이득이 없을 것이다.
LockFreeHash
Bucket의 크기를 늘리는데 있어서 Lock을 사용하고 있는 Hash구조라면 전혀 이득이 없기 때문에 Lock을 사용하지 않고 Hash를 만드는 방법이 필요한 것이다.
우리가 Lock이 필요한 이유는 Bucket에 data가 mapping되어있기 때문에 data에 접근하려면 bucket을 잠그고 접근해야하는 것이다.
그렇기 때문에 data에 bucket을 mapping을 해보자는 아이디어를 차용해서 다음과 같은 LockFreeHash를 만들게 된 것이다.
1) bucket을 mapping하는 방법은?
우리가 table 크기가 4인 상황에서 k라는 키를 가진 node가 들어가야하는 bucket은
[k mod 4] 로 구하게 된다. 이는 bucket index를 key의 i개의 LSB들로 정하기 때문이다.(여기서 i는 table 크기가 2의 i 제곱이라고 표현될 때 값이다.)
10은 1010(2)로 표현이 가능하다. 이때 이를 거꾸로 뒤집고 2번째 LSB를 구하게 되면 2가 나오게 된다. 이렇게 bucket의 index를 구하게 된다.
2) 삭제는 어떻게 할까?
LockFree를 만족시키 위해서는 Delete에서 1개의 cas로만 해결을 해야한다. 하지만 위와 같은 구조로 진행하게 된다면 2개의 cas가 필요하게 된다. 이 때문에 sentinel Node를 도입하게 된다.
bucket index에 맞는 Sentinel Node를 미리 만들어두고 이를 삭제하지 않고 유지시킨다. 이렇게 되면 bucket index와 연결된 link는 삭제 될 필요가 없어지게 되어 삭제할 대상에 대한 linked list내에서의 cas만 적용해주면 된다.
3) 삽입은 어떻게 할까?
만약 우리가 삽입하고자 하는 bucket index에 대한 sentinel node가 없는 상황이라면 다음과 같은 과정을 통해 node를 삽입하게 된다.
//해당 코드는 설명을 위한 코드이기 때문에 문법에 오류가 있습니다
void LinkedList::AddNode(Node* prevNode) {
Node* newSentinelNode
Node* nextNode = prevNode->next;
newSentinelNode->next = prevNode>next;
CAS(&(prevNode->next), &nextNode, newSentinelNode);
Bucket[i]->next = newSentinelNode;
Node* newNode;
newNode->value = 10;
newNode->next = nextNode;
CAS(&(newSentinelNode->next), &nextNode, newNode);
}성균관대 남범석 교수님의 SWE3032 강의를 듣고 정리한 글입니다.
긴 글 읽어주셔서 감사합니다.
틀린 부분이 있으면 댓글을 달아주시면 감사하겠습니다.
📧 : may3210@g.skku.edu