LockFreeHash

LockFreeHashing

Fine-grained Lock의 문제 멀티 쓰레드 상황에서 Hash에 consistency를 유지하고 싶다면 hash의 key에 lock을 걸어서 사용하는게 일반적인 방식일 것이다. 우리는 Hash를 사용하는 이유는 시간복잡도가 매우 낮기 때문일 것이다. 하지만 hash key 1개당 가지고 있는 데이터 수가 늘어나게 되면 이러한 시간복잡도로 인한 장점은 무색해진다. 따라서 Bucket 크기를 늘려야하는 시점이 오게 된다. Fine-grained Lock을 사용하는 상황에서 bucket을 증가시킨다고 하면 어떤 식으로 증가시켜야할까? 다음 그림을 보자 이 상황에서 우리가 bucket의 크기를 늘리게 된다면 늘어난 bucket에 대해 lock을 할당해야할 것이다. 하지만 lock의 갯수를 늘리는게 맞는 ..