intel TBB: concurrent hash table

C++에 익숙한 프로그래머가 멀티스레드;multi-threaded 프로그래밍을 배울 때 느끼게되는 의문점 중 하나는,

“싱글 스레드;single-threaded 프로그래밍에선 STL 컨테이너가 매우 유용한데, 멀티스레딩으로 가면 왜 int 수준의 스레드안전성;thread-safety 만을 보장해주는가”

라는 것이다. 어쩔 수 없이 어떤 락;lock 을 사용해서 STL 컨테이너 – vector<T>, queue<T>, map<T>나 tr1의 unordered_set<T, HashFunction > / unordered_map<K, V, HashFunction> 등등 – 를 보호하면서 사용하게 된다. 이를테면,

// concurrent_hash_map<K, V> table
{
    get_read_lock( &table );
    // ... operation with table (w/o writing) ...
    release_read_lock( &table );
}

{
    get_write_lock( &table );

    // ... write to table ...

    release_write_lock( &table );
}

같은 일련의 작업을 수행하게되는 것이다. (물론 경쟁;contention 이 적은 상황이라면 단일 락이나 뮤텍스가 더 효율적일 것이다)

이런 가장 기본적인 데이터 타입 – vector, queue, map (or hash-table) – 에 대한 멀티스레딩 버젼의 라이브러리로 intel TBB에서는 몇 가지 템플릿 컨테이너들을 제공한다. 그 중 하나가 바로 concurrent_hash_map< K, V, HashCompareFunction > 형태의 hash table이다¹. 

여기에 접근하는 방식은 위에 사용한 것을 STL과 최대한 유사한 인터페이스로 추상화 하려고 해놨다. STL의 iterator와 그런데로 비슷한 모양/개념을 가지고 있다. 그리고 많은 멀티스레드 응용에서 해쉬 테이블이나 맵의 접근을 read/write lock으로 제어하는데, 보통 읽기 연산 수가 쓰기 연산 수보다 훨씬 많기 때문에, 이에 대한 추상화도 제공한다.

• 하나의 해쉬 테이블 개체를 접근하기 위한 접근자;accessor를 정의한다. 이 accessor는 iterator와 비슷하게 사용한다.
• const_accessor 는 read lock 을 가지고 접근하는 것과 같은 형태다. pair<K, const V> 처럼 사용하게 되고, 모든 _read operation_은 동시에;concurrent 진행될 수 있다.
• accessor 는 write lock 을 가지고 접근하는 것과 같은 형태다. pair<K, V> 처럼 쓸 수 있고 다른 모든 스레드가 이걸 못 건드린다고 믿어도 된다.
• accessor 는 hash_map::find(accessor, key) 형태로 accessor를 참조자;reference 로 넘겨서 얻게되며, 이 때 accessor가 hash_map::accessor인지 hash_map::const_accessor인지에 따라 어떤 락이 잡히는지가 결정된다.
• Read/write 락은 테이블 전체에 걸리지 않으며, 테이블의 일부 segment라고 부르는 작은 영역에만 걸린다.
• 해당하는 락은 accessor.release() 혹은 accessor의 소멸자;destructor;dtor에서 제거.

이런 추상화를 제공하기 때문에 프로그래머 관점에서만 보면 일반적인 STL 컨테이너보다 아주 살짝 복잡한 인터페이스로 효율 좋고 / STL비슷한 컨테이너를 쓸 수 있게 된다. 특히나 해쉬 테이블 전체에 대한 락킹이 아니라 일부 엔트리 단위로 락이 잡히기 때문에 전체적으로 병렬성을 높이는 장점도 있다.

그런 의미에서 멀티스레드 응용에서 편히 쓸 수 있는 맵 이 필요하다면 이걸 쓰면 되지 않겠는가.

ps. 사실 이런식으로 “명시적인 락을 해야 데이터에 접근할 수 있는 방식 “에 대해서는 Rica의 이전포스팅 “멀티스레드 프로그래밍 안전하게 하기”에 사실상 같은 아이디어를 소개 하고 있다. 즉,

• Any thread can modify any state at any time.
• All synchronization is explicit, manual.
• No compile-time verification of correctness properties:
  • Deadlock-free
  • Race-free

같은 부분을 강제 하는 것인데, intel TBB의 hash_map도 저런부분을 강제한다. (혹은 보장한다)