Lock-free stack과 성능

대부분의 플랫폼에서 compare-and-swap 이라 부르는 연산을 지원한다.¹ 이 명령어는 CAS( address, expected_value, new_value ) 의 형태로 쓰이는데, address의 값이 expected_value 이면 new_value로 바꾸고, 그렇지 않으면 바꾸지 않는다. 그리고 성공 여부나 이전 값을 반환하는 형태로 되어있다. 

이런 원시적인(…) 동기화 명령어를 사용하면 링크드 리스트 기반의 스택을 락(lock)없이 만들 수 있다. 즉 top 이 스택의 맨 위를 가리키는 구현이라 할 때, push 같은건 아주 naive하게 만들면, 다음처럼 구현하면 된다. (절대로 이 스택 구현을 바로 쓰지 말 것. 자세히 설명하진 않지만 ABA 문제에 대한 고려가 없다)

bool push( T* const value )
{
    Node* old_top = top;
    Node<T> node = new Node( value, old_top );
    while( !compare_and_swap( top, old_top, node ) ) // top을 혼자 변경한 경우 성공. Node용 메모리 할당이 메모리 재활용 떄문에 ABA문제가 생길 수 있지만 여기서는 신경끈다(…)
    {
        // A 지점
        old_top = top;
        node->next = old_top;
    }
} 

내가 알고 있던 구현은 ABA 문제에 대한 해결을 빼면 사실 여기까지다. 간단하고, 대부분의 프로그래머가 쉽게 인지할 수 있는 수준 의 코드일 법하다. 근데 사실 이 코드에서는 top 에서 엄청난 수의 경쟁(contention)이 생길 수 있고, _ 코어 수가 늘어나면_ 이 경쟁은 더 큰 비용을 낳는데도 더 많이 일어나게 된다. 즉, lock-free로 만들었다고 해서 “성능 잘나오네"는 아닐 거라는 점.

내 경우엔 사실 이게 별 수 없다고 생각했는데, The Art Of Multiprocessor Programming에서 다루는 concurrent stack에는 아이디어가 두 개 더 들어가있더라.

Backoff scheme

우선 쉬운 녀석 먼저. 사실 코어 수가 늘어나면 1. 충돌할 확률이 높고 2. CAS 연산 자체가 수반할 비용이 증가한다. 그래서 경쟁이 있는 것 같으면(=즉 A 지점에 다다르면), 아예 back-off 해서 잠시 쉬어버리는 것. LAN/WLAN의 binary exponential backoff 비슷하게 생각해주면 OK.

이 정도까진 좀 더 생각해보면 나오는 아이디어.

Elimination array

스택에서 push()와 pop()은 서로서로 cancel-out 해버린다. 즉, concurrent한 push()와 pop() 호출은 사실 top을 수정 안하고 두 스레드가 값을 교환하면 끝이란 얘기.  저자 중 한명의 논문이고 이 아이디어를 좀 더 복잡하게 구현한 논문(A Scalable Lock Free Stack Algorithm)이 웹에 있던데 한 번 읽어보면 좋을듯.

일단 아이디어 자체는, lock-free(혹은 wait-free면 더 좋고)하게 아이템을 교환할 수 있는 elimination array를 두고,

1.  push/pop 하기 전에 elimination array의 랜덤한 index를 하나 고르고
2. 그 위치에 push 혹은 pop 시도
3. 적당한 timeout² 을 두고 다른 스레드가 오길 대기. 
4. 3의 시도에서 바로 만나거나, 기다리다 만나거나 여튼 짝이 맞는 상대(push면 pop, 혹은 그 반대로)면 아주 즐겁게 값을 교환하고 스택을 떠남. 짝이 틀리면 1로 가서 재시도.
5. 타임아웃이 일어나면 스택 자체에 push/pop 시도

하는 형태로 동작하게 하자는 것. 이러면 top 하나에서 compare-and-swap하며 생기는 병목을 막는 훌륭한 알고리즘이 된다. 심지어 이 elimination array 자체가 일종의 백오프 스킴으로도 작용함…

  ps. 여기서 지나가는 문제. lock-free이면 wait-free인가? wait-free이면 lock-free인가? 둘의 차이는?