Concurrent Non-Blocking Linked List

Intro

Competitive Programming에서 다루는 대부분의 자료구조들은 Sequential한 환경을 기준으로 고안되고 구현된다. 하지만 이제 단일 프로세서의 성능 개선 한계에 가까워지면서, 멀티 프로세서를 잘 활용하는 것의 중요성이 더욱 더 커지고 있다. 기존에 단일 프로세서에서 동작하던 로직을 몇몇의 일반적인 Lock이나 Shared Message Queue등을 통해 멀티 프로세서에서 동작하도록 하는 것은 성능상의 한계가 있다. 그러한 기초적이고 일반적인 방법을 통해서는 여전히 많은 부분들이 Sequential하게 남아 있어, 프로세서의 개수를 많이 늘린다고 해서 성능 개선이 많이 증가하지 않기 때문이다. 관련 분석으로는 Amdahl의 법칙을 찾아보자.

그러한 배경에서, 이 글에서는 다수의 스레드가 효율적으로 동시에 사용할수 있는 Linked List를 어떻게 구현할 수 있을지를 살펴본다. 특히 그중에서도 Lock을 사용하지 않고 모든 동작이 유한 시간 안에 완료됨이 증명 가능한 Non-blocking한 Linked List 중, Timothy Harris의 디자인을 살펴본다.

Key Points & Brainstorming

Concurrent Linked List의 기본적인 필요성과 당위성은 ‘여러 작업이 동시에 진행된다고 해도, 서로 간섭하는 것은 매우 적다’ 로 설명할 수 있다. 많은 스레드 (16개 이상)가 있는 환경에서 Linked List를 통해 Set을 관리한다고 가정하자. 당연히 스레드가 많은 만큼 속도 개선을 기대할 것이고, 반대로 말하면 서로 다른 스레드가 서로의 작업을 최대한 방해하지 않아야 한다는 뜻이다.

이 글에서는 Linked List의 가장 기본적인 연산인 Insert(key), Erase(key), Find(key) 세 가지만 고려하도록 하자.

예시를 들어 생각해보자. 많은 스레드들 중 하나만 골라서 동작하도록 하는 Lock (혹은 mutex) 는 많이 알려져 있다. 이를 통해 가장 naive한 Linked List의 구현을 생각해볼 수 있는데,

Linked List에 Lock을 달아놓고, 모든 스레드들은 Lock을 통해서만 접근할 수 있도록 하여, 하나의 스레드만 리스트를 읽거나 변화시키도록 한다.

이렇게 구현하면 (Lock이 잘 구현되어있고 캐시를 무시한다는 가정 하에) 오류는 없을 것이라는 것을 알 수 있다. 하지만, 임의의 시간에 하나의 스레드만 리스트에 접근할 수 있기 때문에, 효율성은 그다지 좋지 않다. 요컨대, 스레드의 수가 늘어도 Insert 100만회를 하는 시간은 거의 그대로일 것이다. 오히려, Lock에 필요한 자원 때문에 더 느려질 수도 있다.

조금 더 개선하기 위해, 리스트에 대한 다음과 같은 관찰을 활용할 수 있다.

Insert, Delete를 할 때, 리스트가 변화하는 구간은 많아야 2-3개 노드이다.

즉, 리스트 전체에 Lock을 걸 필요 없이, 내가 바꿀 노드와 그 앞뒤 노드에만 Lock을 걸고 나면, 리스트의 다른 부분을 사용하는 연산들은 동시에 동작할 수 있다는 뜻이다. 구체적으로는 다음의 예시를 생각해보자. (여전히 디테일은 생략되어 있음에 유의하자.)

key의 오름차순으로 순서대로 리스트를 관리한다. 각 노드별로 Lock을 걸 수 있도록 한다. Find: 앞에서부터 순서대로, key 이상인 노드가 나타날때까지 순회한다. 만약 가는 길에 Lock이 걸려 있는 노드가 있으면, 멈춘다. Insert: key가 들어가야 하는 위치를 Find로 찾는다. 해당 위치의 앞뒤 두 노드의 Lock을 걸고, 새 노드를 추가하고, Lock들을 해제한다. Erase: 없애야 하는 노드를 Find로 찾는다. 해당 노드와 앞뒤 노드에 Lock을 걸고, 노드를 제거하고, Lock을 역순으로 해제한다. 여러 노드에 Lock을 한번에 걸 때, 앞쪽부터 걸도록 한다. 만약 걸다가 다른 연산에 의해 Lock을 거는데 실패하면, 역순으로 모든 Lock을 풀고, 다시 Find부터 시작한다.

한 노드에 Lock을 걸 수 있는 스레드는 하나밖에 없기 때문에 여러 스레드가 동시에 한 노드를 업데이트하는 경우가 없어 리스트의 정합성이 유지되며, 이전 구현과 비교하면 여러 스레드가 동시에 (다른 곳에서) 작업할 수 있어 성능이 개선되었다고 생각할 수 있다.

하지만, 여전히 Lock이 걸려 있는 경우 다른 연산들이 해당 노드들을 지나갈 수 없기 때문에 불필요한 Congestion이 발생하며, 비슷한 영역에 연산이 계속해서 들어오는 경우 한 연산이 계속해서 재시도하게 되는 Starvation이 발생할 가능성이 있다. 즉, 연산이 완료되는 시간의 상한이 없다.

이러한 문제점을 개선하여 고안한 것이 아래에서 설명할 Non-blocking Linked List이다.

Compare-and-swap

여러 개의 스레드를 사용하기 위해서는 필연적으로 공유하는 메모리 공간을 관리하게 된다. 이 때 여러 개의 스레드에서 실행하는 연산 (어셈블리어 기준 명령어)들이 어떤 순서로 실행될지 모르기 때문에, 기존의 read, write 기능만 사용해서 공유 메모리 공간을 관리하기는 무척 까다로워진다. 이러한 문제를 해결하기 위해 하드웨어 레벨에서 read나 write가 아닌 다른 명령어도 지원하며, C++나 JAVA 등의 언어에서는 이러한 명령어를 프로그래머가 직접 사용할 수 있도록 기능을 제공한다.

그러한 연산 중에서 가장 파워풀한 것이 Compare-and-swap (CAS) 연산이다. CAS(addr, old, new)를 하면, addr에 있는 값이 old인 경우에 new로 값을 변경하며, 연산의 성공 여부를 boolean으로 반환한다. CAS연산을 통해 모든 Sequential한 로직을 멀티스레드 환경에서 consistent하게 동작하도록 구현할 수 있음이 증명되어 있다. 그렇기에 CAS 연산을 잘 활용하여 (Lock 없이도) 멀티스레드 환경에서 효율적으로 동작하는 자료구조를 고안하는 것이 주요 과제 중 하나이다.

Harris Linked List

https://timharris.uk/papers/2001-disc.pdf

Harris의 구현을 살펴보자.

List의 구조체 구성은 흔히 생각하는 것과 크게 다르지 않다. 다만, 이 논문에서 다음 노드를 가리키는 Node *next 포인터 변수는 포인터 이외의 용도로도 쓰인다. 일반적으로 포인터가 가리키는 값은 4바이트 이상의 구조체이기 때문에, 가장 아래 두 비트는 항상 00이다. 이 점을 활용해서 2비트의 추가 정보를 관리할 수 있는데, 이 논문에서는 추가적으로 한 비트를 erase 연산 중에 ‘곧 지워질 노드’임을 표시하는 ‘marking’에 사용한다. 따라서 marking 데이터는 next 포인터와 함께 관리된다고 생각하면 된다.

Insert, Erase (Delete), Find 연산 모두 Search 연산을 공통적으로 사용하는데, Search(key)는 두 값 left_node, right_node 을 반환한다. 마킹되어 있지 않은 노드 중에서, key 이상의 값을 가지는 첫번째 노드를 right_node, 그 바로 앞 노드를 left_node로 하여 반환한다. 이 기능을 만족하는 실제 구현은 가장 아래에 표현한다.

Insert 연산은 간단히 구현할 수 있다. 넣어야 하는 위치를 Search로 찾은 후에 새로운 노드를 만들어 둔다. 그리고 Search로 찾은 위치가 여전히 유효하다면, 새로 만든 노드를 CAS 연산을 통해 atomic하게 삽입한다.

Erase(Delete)에서는 atomicity를 유지하기 위해 크게 두 단계로 나누어 진행한다. 첫 단계는 지울 노드를 찾아 ‘곧 지워질 것임’을 마킹하는 단계, 그 다음 단계는 마킹한 노드를 실제로 없애는 단계이다.

마킹은 앞서 언급한 것 처럼 next 포인터 안에 함께 관리된다는 점에 유의하자. 또한, Search 함수의 조건 중 ‘반환값이 마킹되어 있지 않을 것’ 이 있는데, 그렇기 때문에 Search 함수 안에서 마킹되어 있는 노드들을 리스트에서 실제로 제거하도록 구현되었다. 따라서 Erase 함수 안에서 마킹된 노드를 제거하기 위해 Search 함수를 부르는 것을 볼 수 있다.

Find 함수는 Search 함수가 제대로 구현되어 있다면 직관적이다.

Search 함수는 크게 세 부분으로 나뉘어져 있다. 리스트를 따라 순회하는 부분, left와 right 사이에 지워야 하는 노드가 있는지 확인하고 분기하는 부분, 필요한 경우 그 사이의 마킹된 노드를 제거하는 부분이 있다.

is_marked_referecne(node.next) == true 이면, node가 지워져야 한다는 점에 유의하자.

실제 C++ 구현은 https://github.com/Diuven/pillar/blob/main/structures/harrisList.cpp 에 업데이트될 예정이다.

Analysis

위의 의사코드에 do-while문이 많고, 심지어 goto문 까지 있는데 과연 무사히 빠져나올 수 있는지 의심될 수 있다. 이에 대한 축약된 설명은 이렇다:

Insert와 Delete의 do-while문은 CAS를 이용한 업데이트 한번이면 빠져나온다.
마킹된 노드를 제거하는 CAS연산은 Delete와 Find에서 시행되고, 노드에 마킹은 Delete 연산 한번에 한번만 발생한다.
Search, Insert, 또는 Delete에서 CAS 조건에 실패하여 반복하는 경우, 그 중간에 다른 스레드가 CAS 연산으로 리스트를 바꿨기 때문일 수밖에 없다. 그러나 그런 경우는 연산 한번에 최대 두번만 발생할 수 있다.

정확한 설명은 논문의 5.1 단을 참고하자.

논문이 출판될 당시에 2-16스레드 환경에서 실험해본 결과에 따르면, 기존의 lock을 사용하는 Linked List보다 두배가량 개선된 성능을 보여줬으며, 당시에 알려져 있던 다른 Non-blocking Linked List보다 눈에 띄는 개선을 보여줬다.

Closing

Linked List는 단순한 자료구조이기 때문에 병렬화하는 것도 비교적 어렵지 않게 가능했다. 그리고 Harris의 리스트 구현은 현재까지도 잘 사용되고 있는 것으로 알려져 있다. 그러나 현재 알려져 있는, Sequential 환경에서 잘 작동하는 다양한 자료구조들을 효율적이게 병렬화하는 것은 일반적으로 무척 어렵다. 이후에는 concurrent BST, concurrent size 등을 Linearlization과 함께 살펴보며 어떤 난점이 있는지 알아보도록 하자.