[Concurrency] Lock-Free 자료구조

멀티스레드 코드를 작성한다고 하면, 우리는 기본적으로 Mutex와 같은 비관적 Lock 방법을 고려한다. 가장 단순하고, 문제를 해결하기 쉽기 때문이다.

대충 이런 식으로, 컬렉션에 Lock을 씌워서 데이터에 접근하기 전후로 Lock 걸고 풀고 하면서 쓰는 것이다.

Lock은 강력하고 비교적 다루기 쉽지만, 단일 공유 지점에서의 접근이 너무 빈번하거나 길다면 필연적인 성능 저하나 불공정성, 긴 지연시간(상대적으로) 등이 발생할 수 있다.
그래서 가끔은 이러한 한계를 벗어나고자 자료구조 수준에서 구현을 마개조한 것을 쓰곤 한다. 그런걸 Lock-Free 자료구조라고 부른다.

보통은 queue나 stack, key-value map 정도를 구현해서 쓰는 것 같다. queue의 빈도가 가장 높다.

세부적인 구현 방법을 제시하지는 않고, 얼개만 정리해보겠다.

기반 알고리즘

Lock-Free 자료구조는 Lock-Free 연산들에 기반해서 구현된다.
Compare And Swap, Atomic Load&Store 같은 것들이 대표적이다.

이 기반 연산 방법론들에 대해서 잘 모른다면, 전부 알아두길 권한다.
https://blog.naver.com/sssang97/224054767242
https://blog.naver.com/sssang97/223131630420
https://blog.naver.com/sssang97/223131730615
https://blog.naver.com/sssang97/223356930725

Lock-Free 자료구조에는 구현 방법이 딱히 정립되어있는건 아니지만, 보통은 Compare and Swap 기반의 접근법을 많이 응용한다.

Linked List 처럼 Node를 동적으로 이어붙이는 자료구조의 경우에는 대충 이런 느낌으로 구현이 된다.
아래 코드는 rust crate인 "lockfree"의 deque 구현체 예시다.

애초에 임의의 노드값 통째로를 Atomic Operation의 대상으로 쓰지는 못한다. 하드웨어 수준 제한 때문이다.
그래서 위처럼 노드의 포인터를 대상으로 Atomic 연산을 돌린다.

List의 끝 포인터에 Atomic 연산으로 최신 값을 append하고, Atomic store로 중간에 다시 연결을 했다.
이렇게 한다면 Acqrel=>Release 쌍의 memory ordering을 통해서 최소한의 순서를 보장할 수는 있다.
근데 코멘트에 쓰여있듯이 저 삽입에 대한 가시성에 지연이 생길 수도 있다.

이건 프로덕션으로 검증된건 아니고 실험적인 구현이라서 이게 최적이라고 할 수는 없다. 그냥 하나의 예시일 뿐이다.

혹은, 이런 식으로 comapre and swap 방식을 사용하기도 한다.
간단한 stack 구현례다.

이런 구현 방식은 좀 더 빠릿하게 돌긴 하지만, set 행위 자체에 실패 가능성이 생기고, 그 때문에 루프 재시도로 인한 spinning이 발생할 수 있다는 지점이 생긴다. 당연히 CPU 리소스를 더 먹는다.

주의점

사실 Lock-Free 자료구조가 필요한 수준의 응용프로그램은 그다지 많지는 않다. 보통은 게임 서버 같은 매우 빠르고 집중적인 실시간-동시성 처리가 필요한 부분에 드물게 사용되곤 한다.
그게 아니라면 추천하기 어렵다. 사용사례에 최적화된 Lock-Free 자료구조를 만드는 것은 생각보다 쉽지 않고, 동시성 구조에서 발생하는 매우 많은 잠재적 버그들이 발생할 가능성이 높기 때문이다.

게다가, Lock-Free 자료구조를 쓴다고 해서 반드시 빨라지거나 리소스를 잘 활용하게 되는 것은 아니다. 오히려 Lock-Free 접근법 특유의 뺑뺑이 루프 때문에 CPU 리소스를 더 소모할 가능성이 매우 높다.

더군다나, 일반적인 편견들과 다르게 Mutex로 대표되는 표준 Lock 매커니즘들은 OS 수준 지원에 기반해서 리소스를 효율적으로 잘 사용하게끔 설계되어있다. 괜히 다들 Lock을 쓰는게 아니라는 것이다.
물론 특유의 wake-up 구조에서 나오는 약간의 레이턴시는 존재한다. 하지만 그게 문제가 될 경우는 잘 없다.

그래서 통상적으로 Lock-Free 자료구조는, 레이턴시가 매우 낮아야 하거나, 극도의 동시 처리량을 요구하는 프로그램을 만들 때 적합하다. 그리고 CPU 리소스를 훨씬 많이 먹기 때문에 코어가 굉장히 많은 단일 머신을 쥐어짜는데 더 용이하다. 코어 몇개 되지도 않는 가난한 컴퓨팅 환경에는 어울리지 않는다.

Lock-Free 알고리즘의 사용을 결정하려면 반드시 확실한 벤치마킹과 검증을 거쳐야만 한다.

참조
https://velog.io/@cedongne/Server-Lock-free
https://stackoverflow.com/questions/64938715/when-should-we-choose-locking-over-lock-free-data-structures
https://stackoverflow.com/questions/1585818/when-are-lock-free-data-structures-less-performant-than-mutual-exclusion-mutexe
https://www.baeldung.com/lock-free-programming
https://xtozero.tistory.com/7
https://www.linkedin.com/pulse/low-latency-rust-lock-free-data-structures-luis-soares-m-sc--va5xf/
https://www.reddit.com/r/cpp/comments/vg4myt/is_lockfree_programming_is_always_better_than/