Xiangyao Yu, George Bezerra, Andrew Pavlo, Srinivas Devadas, and Michael Stonebraker. 2014. Staring into the abyss: an evaluation of concurrency control with one thousand cores. Proc. VLDB Endow. 8, 3 (November 2014), 209-220. (PDF)

요약

이 페이퍼는 OLTP DBMS의 다양한 동시성 제어 방식들이 굉장히 많은 수의 코어를 가진 환경에서 어떻게 scale하는지 시뮬레이터를 통해서 실험하고, 그리고 bottleneck은 무엇인지 분석하고 있다.

Concurrency Control Schemes

Two-Phase Locking (2PL)

어떤 요소를 액세스하기 위해서는 먼저 lock을 얻어야하는 pessimistic 방식이다. 2PL은 필요한 lock들을 얻는 growing phase와 lock들을 릴리스하는 shirinking phase로 이루어진다.

2PL은 deadlock을 어떻게 처리하느냐에 따라서 다음의 3가지 변형들이 존재한다.

• 2PL with Deadlock Detection (DL_DETECT)
  • deadlock detector가 트랜잭션 사이의 wait-for 그래프 상의 사이클을 탐지해서 만약 데드락이 발견될 경우 어떤 트랜잭션을 중지시키는 방식.
• 2PL with Non-waiting Deadlock Prevention (NO_WAIT)
  • 데드락이 발생한 후에 이를 탐지하는 것이 아니라, 데드락이 발생하리라 의심되면 lock이 실패하도록 하고 트랜잭션이 중지되는 방식.
• 2PL with Waiting Deadlock Prevention (WAIT_DIE)
  • 어떤 트랜잭션이 먼저 시작했지만 lock을 얻지 못했을 경우, lock을 가진 트랜잭션을 기다릴 수 있는 방식. timestamp ordering을 위해서 각 트랜잭션은 타임스탬프를 얻어야 한다.

Timestamp Ordering (T/O)

트랜잭션의 serialization 순서를 미리 생성하고 이에 따라 실행하는 방식이다. 각각의 트랜잭션은 단조증가하는 유일한 타임스탬프를 배정받고, DBMS는 이를 이용해 충돌하는 오퍼레이션들을 적절한 순서대로 처리한다.

T/O의 변형들은 충돌 체크를 위한 granularity와 충돌 체크를 어느 시점에 수행하는 지에 따라 다음의 4가지로 나뉜다.

• Basic T/O (TIMESTAMP)
  • DBMS는 트랜잭션의 타임스탬프와 트랜잭션이 액세스하려는 tuple을 마지막으로 액세스한 타임스탬프를 비교해서, 마지막으로 액세스하기 전의 트랜잭션은 거부하는 방식이다. tuple이 lock에 의해 보호되지 않으므로 repeatable reads를 위해 읽기 쿼리는 tuple의 로컬 복제본을 만들어야 한다. 트랜잭션이 중지되면, 새로운 타임스탬프를 부여받고 재시작된다.
• Multi-version Concurrency Control (MVCC)
  • 쓰기 오퍼레이션은 트랜잭션의 타임스탬프가 붙어있는 새로운 버전의 tuple을 생성한다. 읽기 오퍼레이션은 버전들의 리스트에서 어느 버전을 읽을 지 결정함으로써 모든 오퍼레이션의 serializable ordering을 유지한다.
  • MVCC의 이점 중 하나는 늦게 도착한 트랜잭션이 거부되지 않고 기존의 버전을 이용해 실행될 수 있다는 점이다.
• Optimistic Concurrency Control (OCC)
  • 트랜잭션의 모든 쓰기 오퍼레이션은 독립적인 공간에서 이루어지고 commit하는 시점에 트랜잭션의 읽기 오퍼레이션들이 다른 트랜잭션의 쓰기 오퍼레이션들과 겹치는지를 검사한다. 겹치는 것이 없다면 쓰기 오퍼레이션의 결과가 데이터베이스로 쓰여지고, 그렇지 않다면, 트랜잭션은 중지되고 재시작된다.
  • OCC의 이점은 실제로 데이터베이스에 쓰기 오퍼레이션이 이루어지는 구간이 작기 때문에 contention이 줄어든다는 것이다.
  • Silo나 Microsoft의 Hekaton과 같은 구현이 있다.
• T/O with Partition-level Lock (H-STORE)
  • 데이터베이스는 파티션들로 나뉘고 각각의 파티션은 lock에 의해 보호되고 각 파티션 별 실행 엔진 – 단일 쓰레드에 의해서만 액세스될 수 있다. 트랜잭션은 트랜잭션이 액세스하려는 모든 파티션에 대한 lock을 얻어야 한다.
  • 트랜잭션이 도착하면, 각 파티션의 lock을 얻기 위한 큐에 추가된다. 각 파티션의 실행 엔진은 큐로부터 트랜잭션을 꺼내와서 그 트랜잭션의 타임스탬프가 큐 내에서 가장 오래된 것일 때 lock을 얻을 수 있도록 한다.
  • Smallbase와 H-Store와 같은 구현이 있다.

Design Choices and Optimizations

각각의 접근을 변경하지 않는 선에서 scalability를 높이기 위해 적용한 최적화들을 설명하고 있다.

General Optimizations

• Memory Allocation
  • malloc bottleneck을 피하기 위해 tcmalloc/jemalloc와 유사하게 쓰레드별 메모리 풀을 유지하는 malloc 구현을 개발. 워크로드에 따라서 풀의 크기를 조정하는 것이 차이라고.
• Lock Table
  • 컨텐션을 줄이기 위해서 중앙 집중적인 lock table 대신 튜플별 lock을 사용.
• Mutexes
  • deadlock detector나 timestamp allocator에 사용되는 뮤텍스를 줄이거나 없앰.

Scalable Two-Phase Locking (2PL)

• Deadlock Detection
  • deadlock detection 알고리즘의 데이터구조를 각 코어별로 파티셔닝해서 lock-free하게 만듬.
• Lock Thrashing
  • 컨텐션이 높은 상황에서 lock을 기다리는 시간으로 인해 성능이 저하되는 현상이 보임.
• Waiting vs. Aborting
  • 트랜잭션의 중지 타임아웃을 조정함으로써 중지 비율과 lock thrashing 사이의 트레이드 오프를 조정할 수 있다.
  • 이 페이퍼의 실험에서는 100us로 고정했으나, 애플리케이션의 워크로드 특성에 따라 조정되어야 할 것이라고 얘기하고 있다.

Scalable Timestamp Ordering (T/O)

• Timestamp Allocation
  • atomic addition을 사용하더라도 1000 코어 상황에서는 cache coherence traffic에 의해 타임스탬프 할당이 bottleneck이 됨.
  • Silo에서 제안된 것처럼 batched atomic addition을 사용하는 방법, CPU clock을 사용하는 방법, 빌트인 하드웨어 카운터를 사용하는 방법을 제안하고 있다.
  • batched atomic addition을 사용할 경우 컨텐션이 높은 상황에서 conflict로 인해 재시작된 트랜잭션이 timestamp ordering에 의해 계속 재시작되는 현상이 성능 저하의 요인이 된다.
  • 코어들 사이에 동기화된 clock은 인텔 CPU에서만 제공된다고 한다.
  • 빌트인 하드웨어 카운터는 현재의 CPU들에서는 존재하지 않는다고 한다.
• Distributed Validation
  • OCC의 validation 스텝이 상대적으로 짧지만 scalability에 문제가 되기 때문에, 튜플별 validation을 사용함으로써 해결했다고 한다.
• Local Partitions
  • H-STORE 프로토콜에서 다른 파티션의 튜플을 액세스하기 위해 각 파티션별 쓰레드 사이에 IPC를 하는 대신 shared memory를 이용해서 오버헤드를 줄임.

DBMS Bottlenecks

실험을 통해 다음과 같은 bottleneck들이 식별되었다.

• lock thrashing
• preemptive aborts
• deadlocks
• timestamp allocation
• memory-to-memroy copying

워크로드에 따라서 어떤 알고리즘이 더 나은 성능을 보이기 때문에, 상황에 따라서 2개 이상의 알고리즘을 조합 – 컨텐션이 낮을 때는 DL_DETECT, 높을 때는 NO_WAIT – 하거나, 둘 이상의 알고리즘을 채용 – MySQL의 DL_DETECT + MVCC – 할 수 있다고 얘기하고 있다.

또한 타임 스탬프 할당이나, 메모리 카피 등의 문제를 해결하기 위해서 여러가지 형태의 하드웨어 지원이 필요하다고 얘기하고 있다.

Multi-core vs. Multi-node Systems

여러 노드의 시스템에서는 분산 트랜잭션이라는 새로운 성능 bottleneck이 생겨나기 때문에 대규모의 OLTP 시스템이 아니라면 오히려 커다란 DRAM을 가진 단일 many-core 시스템이 더 나을지도 모른다고 얘기하고 있다.

Future Works

• 여러 동시성 제어 알고리즘 들의 bottleneck은 알고리즘에 내재한 문제들이므로 소프트웨어만으로 해결하기 어렵고 하드웨어와 협동해서 해결해야한다고 얘기하고 있다.
• 동시성 제어 알고리즘은 DBMS의 여러 컴포넌트 중의 하나일 뿐으로 다른 컴포넌트들 – logging, index 구현 등에 대해서도 비슷한 분석이 이루어지면 유익할 것이라고 얘기하고 있다.
• 이 페이퍼의 실험은 여러 코어를 가진 하나의 CPU에 대한 실험이므로 여러 소켓을 가진 시스템에 대한 실험이 필요하다고 얘기하고 있다.

내가 배운 것들 & 생각한 것들

• 내게는 동시성 제어 알고리즘을 크게 2PL과 T/O로 분류하고 그 안에 MVCC등이 들어갈 수 있다는 것이 새로운 지식의 구조화에 해당하는 것이어서 큰 도움이 되었다.
• 실험을 수행하기 전에 수행한 최적화로부터 이러한 알고리즘을 구현할 때 맞닥뜨리는 가장 기본적인 bottleneck에 대해서 알 수 있었다.
• 1000 코어는 아직은 데이터센터에서 흔히 볼 수 있는 시스템은 아니라서 조금 비현실적이라는 생각이 들지만, AWS 등에서도 96 vcpu 정도의 compute 리소스를 할당할 수 있는 점을 생각하면, 200-500 코어 시스템에 대해서 고민하는 것도 그리 먼 미래는 아닌 것처럼 보인다. 특히, 굉장히 긴 수명주기는 가진 소프트웨어라고 할 수 있는 데이터베이스의 경우에는 10년 정도의 스케일을 바라보고 디자인 결정들을 해야하는 부분도 있으리라 생각한다. 다만, 그러한 시스템을 필요로 하는 워크로드가 존재하는지만 문제일 것이다.
• 컨텐션이 높아지면 어떤 알고리즘이라고 해도 절대적인 성능 자체가 order of magnitude로 떨어지므로, 사실상 워크로드에 알맞는 파티셔닝 외에는 해결책이 없는 것으로 보인다.
• 일반적인 굉장히 많은 사용자 서비스를 제공하는 웹 서비스들의 워크로드에서 실험에서와 같이 컨텐션이 높은 워크로드 (theta=0.8)는 흔치 않다고 생각한다.
• 컨텐션이 심하지 않고, 500 코어 이하의 구간을 보자면 NO_WAIT, MVCC 등이 최고는 아니라고 하더라도 적절히 높은 수준의 성능을 보여주고 있는데, NO_WAIT는 abort rate가 너무 높기 때문에, 결국은 MVCC가 그나마 괜찮은 선택지가 아닌가 싶고, 추측이지만, 실제 인메모리 데이터베이스 시스템들도 그래서 MVCC를 많이 채용하고 있는 것이 아닌가 싶다.

관련 리소스

• Paper review by Adrian Colyer

Stavros Harizopoulos, Daniel J. Abadi, Samuel Madden, and Michael Stonebraker. 2008. OLTP through the looking glass, and what we found there. InProceedings of the 2008 ACM SIGMOD international conference on Management of data(SIGMOD ’08). (PDF)

요약

이 페이퍼에서는 인메모리 데이터베이스 시스템에서 Logging, Locking, Latching, Buffer management 등의 기능을 하나씩 제거했을 때 어떠한 성능 변화가 일어나는지를 보여주고 그 결과로부터 미래의 OLTP 데이터베이스에 대해 시사하는 바가 무엇인지에 대해서 논하고 있다.

• 하드웨어의 변화 그리고 수많은 데이터 중심 애플리케이션들로부터 나타난 다양한 요구 때문에, 표준적인 OLTP 데이터베이스 시스템에서 당연시 되어왔던 logging, concurrency (latching, locking), B-tree, buffer management와 같은 기능들의 일부분만을 가진 데이터베이스들 – Logless/Single-threaded/Transaction-less 데이터베이스들이 나타나고 있다.
• Shore라는 표준적인 OLTP 데이터베이스 아키텍처를 가진 데이터베이스 시스템에 인메모리 워크로드를 실행하는 실험 셋업을 갖추고, logging, latching, locking, buffer management 등의 기능을 하나씩 제거하면서 instruction의 수가 어떻게 변화하는지를 측정했다.
• 실험 결과를 통해 logging, latching, locking, buffer management와 같은 기능들이 전체 대비 상당히 높은 CPU 비용을 소비하는 것을 알 수 있었다.

이러한 결과로부터 미래의 OLTP 데이터베이스 엔진에 대해 다음과 같은 방향성을 제시하고 있다.

• 동시성 제어 (Concurrency Control)
  • dynamic locking은 disk-based OLTP 데이터베이스일 때 좋은 선택이었지만, 메모리 기반 워크로드의 경우에는 다시 따져볼 필요가 있고, optimistic concurrency control 방식이 더욱 나은 선택지가 아닌가 하는 의견을 제시하고 있다.
• 멀티코어 지원 (Multi-core Support)
  • 많은 수의 코어를 가진 컴퓨터가 늘어나고 있고, 동시성이 높은 프로그램들이 성숙하고 있기 때문에, latching과 관련해 더 나은 구현과 멀티쓰레딩의 부담에 대해서 탐색해볼 필요가 있다고 얘기하고 있다.
  • 다른 옵션으로는, 각각의 머신은 하나의 코어를 가진 컴퓨터처럼 볼 수 있는 가상화 환경이 갖춰졌음을 언급하고 있는데, 아마도 각각의 데이터베이스 시스템은 싱글쓰레드 시스템으로 동작할 수 있게 된 것을 함축하고 있는 듯 하다.
  • 이러한 두가지의 접근을 보완해서, 하나의 쿼리를 병렬적으로 처리할 수 있는 시도에 대해서도 언급하고 있다.
• 복제 관리 (Replication Management)
  • logging을 이용한 active-passive 복제의 경우 여러가지 문제점들을 가지고 있지만 이렇게 밖에 할 수 없었던 이유는 log를 실행하는 것이 복제본에서 트랜잭션을 실행하는 것보다 훨씬 적은 비용이 들었기 때문인데, 인메모리 데이터베이스 시스템에서는 트랜잭션의 비용이 매우 낮으므로, active-active 복제에 대해서 고려할 수 있다고 얘기하고 있다.
  • 이 때, two-phase commit을 이용하는 것은 추가적인 지연이 너무 크기 때문에 timestamp ordering등의 테크닉을 이용해야하리라고 제안하고 있다.
• Cache-conscious B-trees
  • 데이터 구조를 최적화하기 보다는 이외의 부분 – 동시성 제어나 복구 – 을 최적화하는 것이 더 중요한 것 같다고 얘기하고 있다.
  • 하지만, 그러한 최적화 후에는 B-tree의 캐시 미스가 새로운 bottleneck일 수 있고, 다른 데이터 구조도 살펴봐야 한다고 얘기하고 있다.

내가 배운 것

• 2008년 시점에 이미 학계에서도 전통적인 OLTP 데이터베이스로부터 다른 접근들이 나타나고 있었고, 인메모리 데이터베이스라는 커다란 트렌드가 이미 시작하고 있었던 것 같다. 그러한 트렌드를 정확히는 알지 못하지만, 적어도 여러 다른 페이퍼나 제품들의 역사를 보면 2000년대 후반부터 2010년에 중반까지 그러한 트렌드가 이어졌고 그 결과 현재와 같이 수많은 상용 인메모리 데이터베이스 제품들이 나오게 된 것 같다.
• 전통적인 OLTP 데이터베이스 엔진에서 대부분의 logging, latching, locking, buffer management의 CPU 비용이 80% 이상에 이를 정도로 높은지에 대해서는 전혀 알고 있지 못했다. 기존에는 디스크 액세스가 커다란 bottleneck이었겠지만 적어도 인메모리 데이터베이스 시스템을 만든다면 이러한 기능들에 대해서 세심한 주의를 기울여서 디자인 선택을 해야할 것 같다.
• 이 페이퍼에서 제시하고 있는 방향성에 대해서, 실제로 이 페이퍼에서 수행할 실험결과로부터 직접적으로 도출되는 방향성이라고 보기는 매우 힘들고, 다만 그 당시 시점의 트렌드나 분위기를 설명하고 있는 것으로 이해했다. 각각의 이슈에 대해서 더욱 엄밀하고 자세히 설명하고 있는 페이퍼들이 많으리라고 생각하므로 심각하게 받아들이지는 않아도 될 것 같다.
• 이 페이퍼를 읽고 역시 2000년대 후반에 시작된 프로젝트인 레디스가 어떤 동기로 시작하게 되었을까 많이 생각을 해보았다. 이 페이퍼에서 얘기하고 있는 디스크 기반 데이터베이스 시스템과 멀티쓰레드 지원, 트랜잭션 지원 등의 오버헤드를 완전히 제거해버린 시스템이니까. 그리고, 인메모리 데이터베이스 시스템을 만든다면 레디스와 대비해 어떤 기능적인 장점을 가져야 하고 그러인한 성능 오버헤드에 대해 어느 부분을 신경을 써야하는 가에 대해서 고민하는 시발점이 되었다.