TL;DR

  • Optimistic Lock Coupling(OLC)은 동시성 이진 트리에서 읽기 작업의 잠금 경합을 줄여 코어 수에 따른 확장성을 높이면서 안전한 동시 쓰기도 지원하는 방식임.
  • 기존 Lock Coupling은 읽기마다 루트 노드를 포함한 잠금을 반복해서 획득하고 해제하므로, 의미상 읽기 경합이 없어도 잠금 자체의 물리적 경합으로 확장성이 제한됨.
  • OLC는 쓰기 작업이 잠금을 사용하고 갱신 후 버전 번호를 증가시키며, 읽기 작업은 버전을 확인해 읽기 도중 변경이 감지되면 처음부터 다시 시도하는 방식임.
  • 검증 전에 읽은 값으로 동작하면 데이터 경쟁이 발생할 수 있으므로, unvalidated<T>, 잠금 가드, OptimisticView, OptimisticPtr로 검증을 타입 시스템에 인코딩하는 방식임.
  • 검증되지 않은 값에 대한 접근을 컴파일러가 차단함으로써 OLC의 읽기 성능을 유지하고, 검증 누락으로 생길 수 있는 미묘한 데이터 경쟁을 방지하는 설계임.

코어 수 증가와 잠금 경합

  • CPU 코어 수가 늘수록 동시 자료 구조의 확장성이 중요해지며, 4개 코어에서 원활한 자료 구조도 32개 코어에서는 알고리즘 한계가 아니라 동기화 방식 때문에 병목이 될 수 있음.
  • 이진 트리의 일반적인 잠금 설계는 트리와 각 노드에 잠금을 두는 방식임.
  • Lock Coupling은 자료 구조를 탐색하면서 현재 접근하는 부분의 잠금을 획득하고, 다음 부분으로 이동한 뒤 이전 잠금을 해제하는 방식임.
  • 모든 조회가 루트 노드를 지나므로 루트 잠금이 계속 획득·해제되며, 독자끼리 의미상 경합하지 않아도 잠금 자체에서 물리적 경합이 발생함.
  • 원문은 요소 10만 개의 트리에서 16코어·32스레드 9950X3D로 동시 조회를 실행해 잠금이 없는 방식과 Lock Coupling의 확장성을 비교함.

Optimistic Lock Coupling의 읽기 방식

  • OLC에서는 쓰기 작업이 기존처럼 잠금을 사용하고, 갱신을 마친 뒤 버전 번호를 증가시킴.
  • 읽기 작업은 접근 전에 버전 번호를 읽고 필요한 요소를 읽은 뒤 버전 번호를 다시 확인함.
  • 버전 번호가 바뀌었거나 요소가 잠긴 상태라면 읽기가 실패한 것으로 처리하고 재시도함.
  • 조회 코드는 읽기만 수행하고 읽은 값으로 동작하기 전에 동시 쓰기가 없었는지 확인하므로, 코어 수가 늘어날 때 확장성이 높아짐.
  • 원문은 조회 확장성 비교에 잠금 없는 방식, Lock Coupling, OLC를 포함함.

검증 누락 위험과 타입 시스템

  • OLC는 성능이 뛰어나지만, 읽은 값을 검증하기 전에 사용하면 코드에 데이터 경쟁이 생길 수 있음.
  • 간단한 코드에서는 검증 지점을 찾기 쉽지만, 복잡한 코드에서는 검증을 빠뜨리기 쉬움.
  • 이를 완화하는 방법은 검증이 필요하다는 사실을 타입 시스템에 인코딩해 컴파일러 지원을 받는 것임.
  • unvalidated<T>는 검증되지 않은 값을 나타내는 전용 타입이며, 잠금 가드의 validate 함수가 검증된 값을 선택적 값으로 반환하는 구조임.
  • 원래 값은 검증 절차를 거쳐야만 접근할 수 있도록 제한함으로써 해당 구성을 안전하게 만듦.

OptimisticView와 OptimisticPtr

  • 데이터에 대한 낙관적 뷰만 노출해 모든 값이 unvalidated<T>로 감싸지도록 하는 설계임.
  • OptimisticPtr는 원시 포인터를 보유하고, data()를 통해 노드의 OptimisticView를 제공함. C++의 제약 때문에 이 설계에서 operator->를 사용할 수 없음.
  • Node::OptimisticView는 키, 값, 왼쪽·오른쪽 자식 포인터, 잠금에 대한 접근자를 제공하며 각 결과를 검증되지 않은 값으로 반환함.
  • 키·값·자식 포인터는 atomic_ref와 memory_order_relaxed를 이용해 읽고, 잠금은 memory_order_seq_cst로 읽음.
  • lock() 접근자도 unvalidated<lock_guard>를 반환함. 다음 노드의 잠금으로 넘어가기 전에 현재 가드를 검증해야 하며, 이에 따라 잠금 획득 자체가 검증된 연결 과정에 포함됨.
  • 낙관적 코드는 OptimisticPtr를 통해서만 데이터에 접근하므로 사전 검증 없이 데이터에 접근할 수 없음.
  • OptimisticView의 접근자를 수동으로 구현해야 하는 점은 번거롭지만, 향후 컴파일러가 이를 자동으로 생성하기를 기대하는 설계임.

검증을 포함한 조회와 결론

  • 안전한 조회는 먼저 트리 잠금에서 낙관적 가드를 얻고, 루트 포인터를 검증한 뒤 노드를 탐색함.
  • 각 노드에서 키를 검증하고, 일치하면 값을 검증해 결과로 사용함. 일치하지 않으면 키 비교에 따라 자식 포인터를 검증하고, 다음 노드의 잠금도 검증한 뒤 가드를 넘김.
  • 어느 검증이든 실패하면 조회를 처음부터 다시 시작함. 따라서 안전하지 않은 OLC 코드와 흐름은 거의 같지만, 검증을 빠뜨리면 컴파일러가 오류를 표시함.
  • 이 방식은 다양한 자료 구조에서 낙관적 동시성 제어를 더 견고하고 사용하기 쉽게 만듦.
  • OLC는 안전한 동시 쓰기를 지원하면서 거의 잠금 없는 수준의 읽기 확장성을 제공하며, 검증 요건을 타입 시스템에 인코딩해 성능과 정확성을 함께 확보함.
  • 컴파일러가 런타임에 미묘한 데이터 경쟁으로 이어질 실수를 포착함.