Paper: Hybrid Garbage Collection for Multi-Version Concurrency Control in SAP HANA

Juchang Lee, Hyungyu Shin, Chang Gyoo Park, Seongyun Ko, Jaeyun Noh, Yongjae Chuh, Wolfgang Stephan, and Wook-Shin Han. 2016. Hybrid Garbage Collection for Multi-Version Concurrency Control in SAP HANA. In Proceedings of the 2016 International Conference on Management of Data (SIGMOD ’16). Association for Computing Machinery, New York, NY, USA, 1307–1318. DOI:https://doi.org/10.1145/2882903.2903734 (pdf)

요약

인메모리 데이터베이스 중 하나인 SAP HANA의 가비지 컬렉션에 대해 설명하고 있는 페이퍼.

MVCC를 구현하고 있는 데이터베이스에서 OLAP 워크로드 등으로 인해 버전을 유지하기 위한 메모리가 증가한다거나 버전들을 처리하기 위한 코스트가 증가하는 것을 방지하기 위해서 가능한 한 사용되지 않는 버전들을 적게 유지하는 효율적인 가비지 컬렉션 메커니즘은 매우 중요하다. 기본적으로 가비지 컬렉션의 대상이 되는 버전들은 현재 실행중인 트랜잭션으로부터 접근이 불가능한 – 미래에도 접근할 필요가 없는 버전들이라고 볼 수 있다. 이를 구현하기 위한 일반적인 접근은 현재 실행중인 트랜잭션이 접근하는 가장 오래된 스냅샷 타임스탬프 (minimum global snapshot timestamp)을 추적하고 이보다 이 전에 생성된 버전들을 삭제하는 것이다.

이 페이퍼에서는 이를 개선하기 위한 구간 가비지 컬렉션 (interval garbage collection), 그룹 가비지 컬렉션 (group gabage collection), 테이블 가비지 컬렉션 (table garbage collection), 그리고 이들을 조합한 하이브리드 가비지 컬렉션 (hybrid garbage collection)을 제안하고 있다.

SAP HANA의 버전 관리

레코드를 변경하는 INSERT/UPDATE/DELETE 오퍼레이션들은 버전 스페이스에 버전을 추가하는데, 버전 스페이스는 레코드 식별자 (RID)를 기준으로 하는 해시테이블로 구성되어있다. 버전 체인은 최근의 버전부터 저장하는 방식 (latest-first)을 채택하고 있다. 인플레이스 업데이트 (in-place update)를 채택한 다른 데이터베이스와는 달리 테이블 스페이스에는 가장 오래된 버전 (oldest version)이 저장되고, 가비지 컬렉션에 의해 테이블 스페이스의 버전이 더이상 액세스되지 않을 때 새로운 버전으로 업데이트된다.

각 버전은 그 버전을 생성한 트랜잭션에 해당하는 TransContext를 가리키고 있고, 그룹 커밋에 의해 동일한 커밋 식별자 (commit ID)를 가진 트랜잭션은 동일한 GroupCommitContext를 가리키게 된다.

전역 그룹 가비지 컬렉터 (Global Group Garbage Collector)

최소 스냅샷 타임스탬프를 효율적으로 얻기 위해서 레퍼런스 전역 STS 트래커 (global snapshot timestamp tracker)를 유지한다. 이는 스냅샷 타임스탬프의 정렬된 리스트로 각각의 타임스탬프는 레퍼런스 카운팅으로 관리된다. 트랜잭션이 시작될 때 레퍼런스 카운트가 증가되고, 종료될 때는 레퍼런스 카운트가 감소되며 0에 도달하면 스냅샷 타임스탬프는 리스트로부터 삭제된다. 최소 스냅샷 타임스탬프를 얻기 위해서는 단순히 전역 STS 트래커 리스트의 첫번째 항목을 액세스하면 된다.

그룹 커밋 단위로 가비지 컬렉션을 수행하기 위해서 GroupCommitContext들이 커밋 ID 순으로 정렬된 리스트를 유지한다. 전역 그룹 가비지 컬렉터는 이 리스트를 순차적으로 방문하면서 최소 스냅샷 타임스탬프와 같거나 더 작은 커밋 ID를 가진 그룹커밋에 해당하는 버전들을 가비지 컬렉션한다.

구간 가비지 컬렉터 (Interval Garbage Collector)

전역 그룹 가비지 컬렉터는 스냅샷 타임스탬프의 최소값 이전만 가비지 컬렉션만 하기 때문에, 최소 값 이상의 타임스탬프를 가진 스냅샷들에 대해서는 한계가 있다. 한편, 최소값 이상의 타임스탬프를 가진 스냅샷이라고 하더라도 버전 체인 내의 모든 버전을 필요로 하는 것은 아니다. 특정 타임스탬프 상에서 생성된 스냅샷은 그 타임스탬프 이후의 버전 하나만을 필요로 하기 때문에, 이 구간에 속하지 않는 버전들은 가비지 컬렉션 대상으로 볼 수 있다.

구간 가비지 컬렉터는 간단히 말해, 실행중인 트랜잭션의 스냅샷 타임스탬프들과 각각의 버전 체인을 비교해서 액세스할 가능성이 없는 버전들을 가비지 컬렉션하는 방식이다. 이 때문에, 매우 정확하지만 비용이 많이 드는 가비지 컬렉션이라고 할 수 있다. 이 페이퍼에서는 이를 위한 모델을 정식화하고 이를 구현하기 위한 머지 기반의 알고리즘을 제시하고 있다. GroupCommitContext 리스트로부터 버전 체인들을 얻는 것으로 설명하고 있고, RID 테이블로부터 얻는 대체 구현도 제시하고 있다.

테이블 GC (Table GC)

SAP HANA의 경우 Stmt-SI라고 불리는 구문 (statement)별로 스냅샷을 가지는 모델을 디폴트로 채택하고 있다. 이 때문에 각각의 스냅샷이 액세스하는 테이블을, 트랜잭션 완료 시점이 아니라, 구문을 해석한 시점에 미리 알 수 있다. 테이블 GC는 이를 통해, 특정 테이블만 액세스하는 스냅샷의 부정적인 효과를 데이터베이스 전체가 아니라 테이블로 제한하는 방식이다.

테이블 GC의 구현은, 오랫동안 살아남은 스냅샷이 액세스하는 테이블을 확인해서, 스냅샷 타임스탬프 객체를 전역 STS 트래커로부터 테이블별 STS 트래커로 이동한 후, 테이블별 STS 트래커로부터 테이블별 최소 스냅샷 타임스탬프를 결정하고, 이를 이용해 각 버전의 가비지 컬렉션에 활용한다.

내부 트랜잭션의 경우 API를 통해 트랜잭션이 액세스하는 테이블을 지정할 수 있기 때문에, 실제로는 Stmt-SI가 아닌 Trans-SI에서도 테이블 GC가 많이 활용된다고 한다.

하이브리드GC (HybridGC)

전역 그룹 가비지 컬렉터, 테이블 가비지 컬렉터, 구간 가비지 컬렉터는 서로 다른 영역에 대해 가비지 컬렉션을 수행하고 있기 때문에, 세가지의 가비지 컬렉터를 모두 채용하는 것이 가비지 컬렉션의 효과성이나 데이터베이스의 성능에 긍정적인 영향이 있음을 보이고 있다.

내가 배운 것 & 생각한 것

  • 데이터베이스 사용자로서 오래 걸리는 (long-lived) 트랜잭션으로 인한 MVCC 데이터베이스의 성능 저하 등의 문제에 대해서는 어렴풋한 개념을 가지고 있었지만, 데이터베이스 상의 가비지 컬렉션 메커니즘에 대해서 자세한 내용을 접해본 것은 이 페이퍼를 읽고 관련된 강의를 들었던 작년 겨울이 처음이다.

  • 효율적인 가비지 컬렉션을 위해서 스냅샷 및 그룹 커밋들의 정렬된 리스트를 활용하고 있다.

  • 구간 가비지 컬렉터에 대해서 수학적인 모델과 알고리즘만 제시하고 있기 때문에 직관적으로 이해하는 것은 조금 어려웠다. 간단한 개념도만 있었다면 매우 이해하기 쉬웠을 것이다. 한편, 실질적인 접근성 (reachability)을 기준으로 모든 버전을 체크하는 것은 Java와 같은 언어 런타임의 가비지 컬렉션과 거의 차이가 없다는 생각이 들었다. 단, 과거의 버전에 대한 액세스가 새로 생겨날 가능성은 없으므로, 언어 런타임의 가비지 컬렉션보다는 동시성에 관한 난이도는 높지 않다고 생각했다.

  • 구간 가비지 컬렉터에 의해 버전 체인의 중간에 있는 버전들이 가비지 컬렉션 될 경우, 만약 델타 버전을 채택하고 있다면 삭제된 구간의 델타 버전들을 통합할 필요성이 있을텐데, 여기서는 그러한 언급이 없는 것으로 보아, 델타가 아닌 각 버전별 값을 저장하는 것으로 보인다.

  • 언어 런타임에서와 마찬가지로 워크로드에 따라서 각각의 가비지 컬렉터에 어느 정도의 CPU 리소스와 동시성을 투자해서 수행할지는 미묘한 튜닝 또는 셀프 튜닝의 문제가 될 것 같다.

  • 인메모리 데이터베이스에서 특정 워크로드에 의해서 가비지들이 갑자기 많아진다면 실용적으로 사용하는 것에 굉장히 크리티컬한 문제가 될 것 같으므로, 특히 인메모리 데이터베이스에 있어서, 신뢰할만한 가비지 컬렉션 메커니즘은 굉장히 중요한 것 같다. 한편, 버전 스페이스 오버플로우가 발생할 경우 오래된 버전을 디스크로 기록하고 일부 트랜잭션을 중지하는 등의 SAP HANA 기능에 대한 언급이 있기는 하다.

Paper: Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems

Thomas Neumann, Tobias Mühlbauer, and Alfons Kemper. 2015. Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (SIGMOD ’15). Association for Computing Machinery, New York, NY, USA, 677–689. DOI:https://doi.org/10.1145/2723372.2749436 (pdf)

요약

HyPer의 MVCC 구현에 관한 페이퍼.

많은 DBMS들이 MVCC를 구현하고 있지만, 대부분의 경우, 직렬성 (Serializability)을 보장하기 보다는 이보다 더 약한 격리 수준인 스냅샷 격리 (Snapshot Isolation; SI) 만을 보장하고 있다. 일반적으로 스냅샷 격리를 직렬적으로 만들기 위해서는 높은 비용이 필요한 것으로 알려져있는데, 이 페이퍼에서는 적은 비용으로 직렬성을 보장하는 MVCC 구현을 제안하고 있다.

이 구현의 기본적인 접근은 메인 테이블에는 최신 버전을 유지하고 in-place update를 하되, 새로운 버전으로부터 오래된 버전 순서대로 (newest-to-oldest) 연결된 버전 벡터를 통해 이전 버전에 대한 액세스를 제공한다.

흥미로운 것은 아직 커밋되지 않은 트랜잭션에 의해 추가되는 버전이다. 위의 그림에서 Ty는 아직 커밋되지 않은 트랜잭션의 ID로 커밋된 시간과 구분하기 위해서 263 이상의 매우 큰 값으로 할당된다. Ty 트랜잭션에 의해 메인 테이블에서는 ‘7’이라는 값이 in-place update되고, 이 값은 Ty 트랜잭션에게만 보이는 값이 된다. 한편, 버전 벡터의 Ty에 해당하는 항목에는 Ty와 Ty 트랜잭션이 일어나기 전의 값이 저장된다. 따라서, T5 이후에 시작된 (Ty 이외의) 트랜잭션에서는 Ty 트랜잭션이 생성한 버전으로부터 ‘8’이라는 값을 얻게된다.

커밋되지 않은 데이터를 가진, 즉 트랜잭션 ID를 가진 버전이 존재하는 레코드에 대해 쓰기 오퍼레이션을 하려는 트랜잭션은 바로 중지되고 롤백된다.

Serializability Validation

직렬성을 보장하기 위해서 트랜잭션에서 일어난 읽기 오퍼레이션들이 다른 트랙잭션에 의해 영향을 받지 않았음을 보장하기 위한 검증 단계 (validation phase)를 필요로 한다.

기존의 방식은 주어진 트랜잭션의 모든 읽기 오퍼레이션을 기록하고, 트랜잭션이 끝나기 전에 다시 한번 읽기 오퍼레이션을 모두 수행함으로써 다른 트랜잭션으로부터의 영향이 없었음을 검증하는데, 이는 스캔이 많은 워크로드에서 굉장히 높은 비용을 요구하게 된다.

이 시스템에서는 Precision Locking이라는 오래된 기법을 이용하는데, 기본적으로 읽기 오퍼레이션이 아니라 읽기 오퍼레이션의 조건 (predicate)들을 기록하고, 검증단계에서는 해당 트랜잭션의 라이프타임 동안 발생한 트랜잭션들의 쓰기 오퍼레이션들이 읽기 오퍼레이션들의 조건과 겹치는 지를 확인하는 방식이다.

검증할 트랜잭션의 라이프타임 동안 발생한 트랜잭션들을 효율적으로 찾기 위해서 최근의 트랜잭션 리스트를 유지하고, 이 트랜잭션에 함께 저장된 undo 레코드를 통해서 쓰기 오퍼레이션들을 확인할 수 있다.

Efficient Scanning

스캔을 할 때 레코드별로 버전 벡터가 존재하는지 여부를 체크하는 것을 피하기 위해, 일정한 범위의 레코드들마다 버전 벡터가 존재하는 레코드의 범위를 저장하고 (VersionedPositions), 이를 통해 버전 벡터가 존재하지 않는 범위에서는 더 빠르게 스캔할 수 있도록 도와주는 메커니즘을 가지고 있다. 불필요한 버전들은 계속 가비지 컬렉션에 의해 제거되므로, 소수의 레코드들만이 버전을 가지고 있는 것을 가정하고 있다.

Evaluation

  • VersionPositions를 통해서 약 5배 가량의 스캔 throughput 개선이 이루어졌다.
  • 스냅샷 격리 (SI)에 대비해 직렬성을 보장하는 레코드 레벨 조건 로깅이나 애튜리뷰트 레벨 조건 로깅은 약 5-7%의 비용만을 요구했다.

내가 배운 것 & 생각한 것

  • 낙관적인 동시성 제어를 사용하는 MVCC 구현, OLTP/OLAP 둘다에 최적화, LLVM을 이용한 코드 생성 등의 기능들이 상용화되는 인메모리 데이터베이스 구현에서 많이 보이고 있다.
  • Precision locking을 이용한 낙관적인 트랜잭션의 검증은 듣고나면 당연한 것 같지만, Hyper의 독특한 방식이라고 생각한다. 기존의 데이터베이스에서 반드시 이런 접근을 할 필요는 없었다고 생각하는데, 포인트 쿼리와 업데이트들 만으로 구성된 OLTP 트랜잭션이라면 읽기 집합 (read set)을 이용한 검증이 그리 비효율적이지는 않다고 생각된다. 대량의 스캔을 포함한 OLAP 트랜잭션에 대해서는 2번의 읽기를 하는 것만으로도 비용이 굉장히 높아지므로, 이것을 최근의 트랜잭션 리스트를 유지하는 비용 및 쓰기 집합 (write set)의 크기에 따른 성능 저하와 트레이드 오프한 것으로 볼 수 있는 것 같다.
  • 우리가 흔히 사용하는 데이터베이스에서는 스냅샷 격리를 사용하는 것이 보편적이고 그 이상은 비용효율적이지 않다는 선입견을 가지고 있었는데, 직렬성을 보장하면서도 충분히 좋은 성능을 보여주는 이 페이퍼를 본 후에 그러한 선입견을 깰 수 있었다.

Jepsen report on RedisRaft

RedisRaft에 대한 Jepsen 리포트가 나왔다.

https://jepsen.io/analyses/redis-raft-1b3fbf6

RedisRaft는 Redis Labs에서 개발하고 있는, Raft를 이용해 replication을 구현한 Redis module이다. 약 2018년 초에 PoC 프로젝트로 시작되었고, 2019년 중반부터 본격적으로 개발하기 시작했다고 한다. 실제로 RedisRaft의 GitHub repository를 확인해보아도 Yossi Gottlieb라는 개발자가 약 1년 전부터 commit을 하기 시작한 것을 알 수 있다. 현재는 개발 중이고 2021년에 GA로 내놓을 예정이라고 한다.

실제로 분석을 통해 21개의 버그를 발견했고 다양한 성격의 문제들이 있었지만, RedisRaft가 가져다 사용한 Raft 구현에도 여러 버그가 있었고 치명적인 문제로도 연결되었던 것 같다. Paxos나 Raft 알고리즘은 대략적인 얼개를 구현하는 것은 어렵지 않을지는 몰라도 여러가지 실패 모드들을 제대로 구현하는 것은 굉장히 어렵기로 잘 알려져있다. 참고로, RedisRaft가 사용하고 있는 Raft 구현은 C로 쓰여진 https://github.com/willemt/raft. 이러한 이슈들을 보면 일단 데이터베이스에서도 그렇지만, 분산시스템에서는 더더욱 사려깊게 설계된 테스트가 굉장히 중요하다는 것을 다시 한 번 확인할 수 있었다. 그리고, 정확한 분산시스템을 쓰는 것이 얼마나 어려운 것인지, 그리고 시간이 드는 것인지도 다시금 떠올릴 수 있었다.

한편, Antirez도 이 리포트를 언급하며 Redis를 state machine으로 보고 Raft를 외부에 구현하는 것에 대한 아이디어와 설계에 대해 RedisRaft의 주저자인 Yossi Gottlib과 얘기했었다고 언급했다. 아이디어 자체야 새로운 것은 아니겠지만, 미니멀리스트인 Antirez로서는 충분히 예상되는 디자인. 분산시스템 분야 사람들은 Antriz가 취하는 여러가지 ‘실용적인’ 절충들에 대해서 탐탁치 않아하는 것이 사실이고, Redis cluster 설계에 대한 평가도 그리 좋지 않았다. Jensen의 Kyle Kingsbury도 이에 답글을 달아 이에 대해서 우리가 설득하려고 하지 않았냐고 그러한 논의를 상기시킨다. Antirez는 만약 그랬으면 Redis는 망했을거라고. 거의 Antirez 혼자서 Redis의 대부분의 기능들을 개발하는 상황 상 만약 그가 Raft 구현의 정확성에 시간을 쏟았다면 아마도 다른 부분의 진척은 굉장히 느려졌을거라는 상상은 충분히 할 수 있다. 분산시스템 개발은 그만큼 어렵다. 이렇게 서로 다른 의견을 가진 사람들이지만 어떤 형태로든 협력해서 또다른 좋은 프로덕트가 나오게 된 것은 좋은 일이라 생각한다.

COVID-19 이후의 출근

2월 중순 이후로 4개월 가까운 재택 근무 끝에 지난 월요일에 오랜만에 회사에 출근했다. 도쿄도에서는 확진자 재생산 수가 2에 육박해서 경보 (이른바, 도쿄 앨러트)가 발령된 상태였지만, 긴급 사태 선언 해제 이후로 대부분의 백화점, 음식점, 상가들은 문을 연 상태. 통근 인파를 피해서 11시 쯤 집을 나섰다. 마스크를 쓰지 않은 사람은 보기 힘들 정도. 매일 아침 들르던 회사 앞 스타벅스에서 테이크아웃.

엘리베이터에서 잠시 어느 층을 눌러야할지 고민했었다. 엔지니어들이 대부분인 내가 일하는 층에서는 대략 10% – 20% 정도 인원이 근무하고 있었다. 내 책상에 가니 먼지가 뽀얗게 앉아있어서 먼저 먼지를 닦아내는 일부터 했다. 맥북은 자동 업데이트 때문에 각종 업데이트 알림 등이 떠 있는 상태. 내 맥북에서 회의록 위키 페이지를 주기적으로 자동 생성하는 프로그램을 돌리고 있는데 이것 때문에 cron 작업이 동작하지 않고 있었나보다.

오피스라고 해도 어차피 회의실에서 물리적인 회의를 하는 것도 아직 허용되지 않는 상태다. 평소처럼 개발 작업을 진행했는데, 느낀 점은 출근한 사람 수가 적고 조용해서 집중이 잘 된다는 점. 평소 때도 우리 오피스는 상대적으로 조용한 편이라고 생각하지만 통로쪽 자리다보니 집중에 방해되는 요소는 얼마든지 있다.

역시 통근 인파를 피해서 오후 4시 반 정도에 오피스를 나와서 혼자 자주 가던 교자 가게에 가서 늦은 점심을 먹었다. 다른 가게들처럼 들어가면서 손 소독제로 손을 소독해야하고, 카운터 석 사이사이에 투명 플라스틱 칸막이가 설치되어 있다. 거리에 인파도 여느 때 수준처럼 느껴졌다.

오후 6시에 한국 오피스와의 회의가 있었기에 서둘러 집에 돌아왔는데 땀이 많이 나서 샤워부터 해야했다. 출근할 때는 N95 마스크를 쓰고 갔는데, 너무 더워서 퇴근할 때는 만약을 위해 가져간 Surgical mask를 쓰고 돌아왔다. 그나마 전철은 너무 붐비지 않아서 다행이라는 생각이 들었다.

회의에 이어서 릴리즈 작업 등을 하다가 9시 즈음에 리모트 근무를 마쳤다. 오피스 근무와 리모트 근무를 합쳐서 대략 7시간 반 근무를 한 셈.

오랜만의 출근 후 느낀 점을 적어보자면,

  • 일본 사회는 이미 코로나 바이러스 문제가 해결된 것처럼 돌아가기 시작한 것 같다.
  • 거리를 걷거나 외식을 하니 기분이 나아졌다.
  • 통근 인파를 피해서 출퇴근을 하고 집에 돌아와서 또다시 같은 성격의 리모트 근무를 해야한다면 출퇴근 시간에 무슨 의미가 있는가 의문이 들었다.

시니어 소프트웨어 엔지니어의 입장에서 다른 사람을 설득하거나 충돌을 해결하는 등의 높은 수준의 비언어적 의사소통을 해야하는 경우가 아니라면 오피스 근무를 해야할 이유가 굉장히 적은 것 같다. 오히려 쥬니어들의 경우에는 자신의 진척이나 작업의 방향성을 기꺼이 옆에서 살펴봐주고 사소한 것들도 즉각적으로 피드백을 줄 수 있는 동료들이 없으면 힘들 수도 있다고 생각한다. 그렇다고 하더라도, 자신이 처한 어려움을 적극적으로 커뮤니케이션해서 스스로 해결해나가는 성향의 엔지니어라면 아마 큰 문제는 겪지 않으리라고 생각한다. 말하자면, COVID-19는 쥬니어 엔지니어의 커리어 성장에 가해지는 제약조건이자 자극점으로서 기능하게 된 상황이라고 생각한다.

한편으로는, 우리 엔지니어링 조직은 오랜 기간 동안 리모트 근무를 하더라도 문제가 없도록 엔지니어링 도구, 엔지니어링 프로세스 나아가서는 엔지니어링 문화까지 세심하게 다듬어왔다고 생각하기 때문에 이번 COVID-19 사태에 따른 장기간 리모트 근무에도 커다란 불편함은 발생하지 않지 않았나 싶기는 하다. 개인적인 관점으로는 오픈 소스 개발 문화가 항상 그 모델의 중심에 있었다고 생각하는데, COVID-19 사태를 계기로 앞으로 더욱 더 그런 모델에 가까이 다가갈 수 있는 기회가 되지 않을까 생각이 든다.

Talk: Making Work Visible: How to Unmask Capacity Killing WIP

Amazon에서 책을 구입하려고 살펴보다가 ‘Making Work Visible’이라는 책이 눈에 띄길래 검색해봤더니 저자가 책을 출판하기 전 같은 제목으로 강연한 짤막한 비디오가 있길래 보게 되었다.

동시에 진행하는 일(work-in-progress)이 너무 많으면 제 때 비즈니스 가치를 생산하는 것이 어렵기 때문에, 이를 가시화하고 동시에 진행하는 일을 더 늘리지 않는 근거로 삼거나, 그것들이 늘어나는 문제들을 체계적으로 해결해야한다는 이야기를 하고 있다.

Too much WIP sabotages our ability to deliver work on time

동시에 진행하는 일이 많아지는 원인으로 계획되지 않은 일, 우선순위의 충돌, 의존관계 등을 들고 있고, 각각을 흔한 Kanban 보드에서 어떻게 가시화할 것인지를 얘기하고 있다.

  • Unplanned work
    • Add a swim lane for maintenance work and unplanned work in the Kanban board
  • Conflicting priorities
    • Only one top priority
    • Add a swim lane for cadence work: ones with hard due-dates
  • Dependencies
    • Visualize dependencies by adding parent-children relationships to the tickets

동시에 진행하는 일의 가시화가 이루어지면, 이를 이용해 동시에 진행하는 일을 추가하지 않기 위한 체계를 구축하거나, 문제를 찾아 해결하라고 얘기하고 있다.

  • Use WIP limits: WIP limits intentionally insert tension
  • Limit WIP to find problems: Remove barriers of too much WIP

마지막으로, 보스들이 부탁을 하면 이를 쉽게 거절할 수 있는 사람들은 많지 않다며, 보스들은 항상 이를 유념해달라고 부탁을 하며 강연을 마무리 지었다.

사실 동시에 진행되는 일이 많아지는 상황 자체는 정말 해결하기 어렵다. 팀원의 수는 나를 포함해 2-3명에 불과한데, 중요한 비즈니스 요구들이 엄청나게 몰려올 때, 이를 쉽게 거절하기란 쉽지 않다. 서비스의 운영 상태가 좋지 않아 해결해야할 문제가 산적해있고, 매일 매일 장애가 터진다면 이 역시 저런 테크닉만으로 해결하기는 어려울 것이다. 강연자도 이에 대해서는 강연에서 언급하고 있기도 하다. 하지만, 이러한 상황을 결국 극복한 조직들은 모두 WIP를 제한하는 형태로 업무 프로세스를 구성해나간 것을 보면 장기적으로는 틀리지 않은 방향이라는 생각이 들었다.

Paper: An Empirical Evaluation of In-Memory Multi-Version Concurrency Control

Yingjun Wu, Joy Arulraj, Jiexi Lin, Ran Xian, and Andrew Pavlo. 2017. An empirical evaluation of in-memory multi-version concurrency control. Proc. VLDB Endow. 10, 7 (March 2017), 781-792. (PDF)

요약

이 페이퍼는 인메모리 데이터베이스에서의 MVCC의 4가지 주요한 디자인 선택 – 동시성 제어 프로토콜, 버전 스토리지, 가비지 컬렉션, 인덱스 관리 – 을 설명하고, 각각의 디자인 선택을 Peloton DB에 구현한 후 OLTP 워크로드 하의 병목을 분석하고 있다.

공통적인 DBMS 메타데이터

  • 트랜잭션
    • 각각의 트랜잭션은 유일하고 단조증가하는 타임스탬프를 트랜잭션의 id로서 할당받는다.
  • 튜플
    • 각각의 버전은 4개의 메타데이터 필드를 가진다.
    • txn-id: 해당 버전에 대한 write lock을 표현하며, 0이라면 lock이 걸리지 않은 상태이고, 어떤 트랜잭션의 id가 기록되어 있다면, 그 트랜잭션에 의해 해당 버전이 write lock이 걸린 것을 나타낸다.
    • begin-ts, end-ts: 튜플 버전이 유효한 논리적인 시간 범위를 나타낸다. 처음에는 0으로 설정되고, 만약 어떤 튜플 버전이 삭제된다면 begin-ts는 INF가 된다.
    • pointer: 이전이나 이후의 튜플 버전을 가리키는 포인터로 버전들의 체인을 구성한다.

동시성 제어 프로토콜 (Concurrency Control Protocol)

  • Timestamp Ordering (MVTO)
    • 튜플을 읽은 마지막 트랜잭션의 id가 기록되는 read-ts라는 필드가 추가된다.
    • 어떤 트랜잭션이 쓰기를 위해 새로운 버전을 생성하려고 할 때, 그 트랜잭션 id가 마지막 버전의 read-ts보다 클 때만 이를 허용한다. 즉, 이미 새로운 트랜잭션에 의해서 읽힌 데이터를 과거의 트랜잭션이 갱신할 수 없는 액세스의 순서를 보장하고 있다.
  • Optimistic Concurrency Control (MVOCC)
    • 트랜잭션들이 서로 충돌할 가능성이 낮다고 가정하고, 액세스하려는 튜플에 대한 lock을 얻는 대신, 우선 튜플들에 액세스를 수행하고, 충돌이 없었는지를 검증하고, 마지막으로 결과를 쓰는 3개의 phase로 나뉘어 진행된다.
    • read phase: 읽기와 업데이트 작업이 이루어진다. 읽기는 begin-ts, end-ts에 해당하는 버전을 찾아 읽기가 이루어지고, 업데이트는 txn-id가 설정된 새로운 버전을 생성하는 방식으로 이루어진다.
    • validation phase: 트랜잭션에 대해서 commit 시점을 나타내는 새로운 타임스탬프를 부여하고, 트랜잭션 내에서 읽었던 튜플들이 어떤 트랜잭션에 의해서 업데이트 되었는지 확인한다. 만약 그렇다면 트랜잭션은 중지된다.
    • write phase: 트랜잭션에서 만들어진 새 버전들을 모두 DB에 쓰고, begin-ts를 commit 타임스탬프로, end-ts를 INF로 설정한다.
  • Two-phase Locking (MV2PL)
    • 모든 트랜잭션은 액세스를 하기 위해서 튜플의 현재 버전에 대한 lock을 얻는다.
    • write lock은 txn-id를 이용하고, read lock은 어떤 튜플에 대해 현재 읽기 액세스를 하고 있는 수를 나타내는 read-cnt라는 필드를 도입한다.
  • Serialization Certifier
    • 동시적으로 진행되는 트랜잭션들로부터 문제가 있는 구조를 찾아내기 위한 serialization graph를 유지하는 프로토콜이라고 하는데, 이 페이퍼에 기술된 설명만으로는 이해하기 어려웠다.

버전 스토리지 (Version Storage)

  • Append-only Storage
    • 튜플을 업데이트하기 위해서, 현재 버전의 내용을 새로운 버전으로 복제하고, 수정을 가한다.
    • 버전 체인을 구성하는 순서에 따라서, Oldest-to-Newest (O2N)과 Newest-to-Oldest (N2O)로 나뉜다.
      • O2N: 새로운 버전이 추가될 때마다 인덱스를 갱신하지 않아도 되는 이점이 있지만, 마지막 버전을 읽기 위해서 항상 버전 체인을 따라가야하는 단점이 있다. 따라서, 버전 체인을 짧게 유지하는 것이 관건이 된다.
      • N2O: 버전 체인을 따라가지 않아도 되는 장점이 있는 반면, 새 버전이 추가될 때 모든 인덱스도 업데이트해야하는 단점이 있다.
  • Time-Travel Storage
    • 마스터 버전은 메인 테이블에 저장하지만 오래된 버전들은 별도의 테이블에 저장한다.
    • 인덱스는 항상 마스터 버전을 가리키므로 새 버전이 추가되어도 변경이 필요없다.
  • Delta Storage
    • 마스터 버전은 메인 테이블에 유지하고, delta 버전들은 별도의 테이블에 유지한다.
    • 튜플의 일부만을 수정하는 UPDATE 작업에 이상적이다.
    • 여러 컬럼을 읽어야 할 경우, 모든 데이터를 얻기 위해서 버전 체인을 따라가야한다.

가비지 컬렉션 (Garbage Collection)

  • Tuple-level Garbage Collection
    • Background Vacuuming (VAC)
      • 만료된 버전을 찾기 위해서 백그라운드 쓰레드가 데이터베이스를 주기적으로 스캔하는 방식.
      • 마지막 스캔 이후로 변경되지 않은 튜플은 검사하지 않도록 하기 위한 비트맵을 통해 최적화를 할 수 있다.
    • Cooperative Cleaning (COOP)
      • 트랜잭션을 실행하는 동안 버전 체인을 따라가며 만료된 버전을 찾아내는 방식.
      • O2N append-only 스토리지에만 적용할 수 있다.
      • 트랜잭션이 액세스 하지 않는 튜플에 대해서는 GC가 불가능하므로 별도의 쓰레드로 GC를 수행할 필요가 있다.
  • Transaction-level Garbage Collection
    • 하나의 epoch이 끝나면 그 epoch에 속한 트랜잭션들이 생성한 버전들은 제거되어도 된다.
    • 트랜잭션 단위로 GC가 일어나므로 트랜잭션 단위의 스토리지 최적화가 가능하다.
    • 트랜잭션의 읽기/쓰기 액세스가 일어난 버전들을 추적하기 위한 비용이 발생한다.

인덱스 관리 (Index Management)

  • Logical Pointers
    • 튜플의 버전 변화에 따라 변화하지 않는 논리적인 식별자를 인덱스 엔트리에 사용한다.
    • 데이터베이스는 논리적인 식별자를 버전 체인의 head로 변환하기 위한 indirection layer를 필요로 한다.
    • Primary Key (PKey): 튜플의 primary key를 논리적인 식별자로 사용하거나,
    • Tuple Id (TupleId): 별도의 식별자를 발급하여 사용하는 방법이 있다.
  • Physical Pointers
    • 특정 버전의 물리적인 포인터를 인덱스 엔트리에서 사용하는 방법이다.
    • 어떤 튜플이 업데이트 될 때는, 모든 인덱스에 새로 생성된 버전을 추가해야한다.

디스커션

  • 일반적인 믿음과는 달리 동시성 제어 프로토콜 보다 버전 스토리지 방식이 인메모리 MVCC 데이터베이스의 scalability에 있어서 가장 중요한 부분이었다.
    • Delta storage 방식이 메모리 할당 방식과 상관없이 높은 성능을 보여주었다. 특히 튜플의 일부만이 수정될 때 효율적이고, 반면 테이블 스캔에 있어서는 낮은 성능을 보여주었다.
  • 워크로드에 알맞는 동시성 제어 프로토콜을 사용함으로써 성능을 개선할 수 있으나, 전반적으로 여러 워크로드에 대해서 MVTO가 좋은 성능을 보여주었다.
  • Transaction-level GC가 가장 좋은 성능을 보여주었다.
  • Logical pointer 방식이 높은 성능을 보여주었다.

내가 배운 것 & 생각한 것

  • 데이터베이스 마다 MVCC를 구현하는 방식 자체가 여러가지 디자인 결정에 따라 달라질 수 있고, 그에 따라 성능도 상당히 달라질 수 있느 점을 알았다.
  • MVCC에 대한 4가지의 디자인 결정과 각각마다 가능한 옵션에 대해서 비교적 상세히 이해할 수 있게 되었다.
  • 각각의 디자인 결정이 완전히 독립적인 것도 아니거니와, 캐시 레벨의 성능 최적화를 해야하는 인메모리 데이터베이스 특성상, 한번 결정한 디자인 선택을 구현 후 바꾸는 것은 매우 어려운 결정이 될 것이다. 자신의 데이터베이스를 구현한다면 그 데이터베이스가 앞으로 처리해야할 워크로드에 대해서 이해하고, 이에 적합한 디자인 결정하는 것이 매우 중요한 일인 것 같다.

Paper: Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores

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: Main Memory Database Systems: An Overview

H. Garcia-Molina and K. Salem. 1992. Main Memory Database Systems: An Overview. IEEE Trans. on Knowl. and Data Eng. 4, 6 (December 1992), 509-516. (PDF)

요약

1991-1992년에 쓰여진 이 페이퍼는 당시 인메모리 데이터베이스 시스템에 대한 연구들과 프로토타입 인메모리 데이터베이스들에 대한 서베이 페이퍼라고 할 수 있다.

Introduction

먼저 인메모리 데이터베이스 시스템에 대한 흔한 질문들에 대해서 답하고 있다.

전체 데이터가 메인 메모리에 들어갈 것이라 가정하는 것은 합당한가?

  • 어떤 애플리케이션의 경우에는 데이터의 크기가 메모리 용량의 증가보다 더 느린 속도로 증가할 수도 있고, 어떤 애플리케이션의 경우에는 실시간 제약이 있어서 반드시 메모리 상에 적재되어야 한다.
  • 하지만, 메모리에 적재될 수 있는 애플리케이션도 존재하므로, 이러한 경우, 하나 이상의 데이터베이스 시스템에 저장하고 가장 액세스 빈도가 높은 종류의 데이터를 인메모리 데이터베이스에 저장하는 것을 고려할 수 있고, 실제로도 IMS의 사례에서 이를 보여주고 있다.

인메모리 데이터베이스와 매우 커다란 캐시를 가진 디스크 기반 데이터베이스의 차이점은 무엇인가?

충분히 커다란 캐시를 가지고 있다면 데이터가 항상 메모리 상에 존재하겠지만, 메모리의 장점을 전부 활용하지는 못한다.

  • B-tree와 같이 디스크 액세스를 위해 설계된 인덱스 구조를 가진다.
  • 디스크에 존재할 수 있는 데이터를 액세스하기 위해서, 메모리 상의 데이터를 액세스할 때에도 버퍼 매니저를 사용해야 한다.

특수한 하드웨어를 도입함으로써 메인 메모리가 nonvolatile하다고 가정할 수 있는가?

  • 배터리가 들어간 메모리 보드, UPS 등을 통해서 더 나은 신뢰성을 제공할 수 있지만, 장애의 가능성을 0으로 줄여주지는 못한다.
  • 하지만, 신뢰성이 높아진다면 백업의 빈도 등을 줄여줌으로써 성능 개선에 기여할 수 있다.
  • 배터리가 들어간 메모리 보드나 UPS는, 디스크와 달리 신뢰성을 보장하기 위해 어떤 일을 해야하는 ‘active’한 컴포넌트이므로 장애의 가능성에 기여한다.
  • 백업 메커니즘의 성능이 인메모리 데이터베이스 시스템에 있어서 매우 중요할 것이다.

Impact of Memory Resident Data

Concurrency Control

  • 인메모리 데이터베이스에서 트랜잭션은 디스크 기반 데이터베이스에 비해서 짧아지므로 lock contention도 상대적으로 적을 것이다.
  • 따라서, 인메모리 데이터베이스의 경우 좀 더 큰 lock granularity를 선택할 수 있고, 이를 통해 동시성 관리의 비용이나 CPU cache flush의 비용을 크게 줄일 수 있다.
  • 하지만, 여전히 짧은 트랜잭션과 수명이 긴 트랜잭션이 동시에 수행될 수 있도록 하기 위한 방법이나 멀티프로세서 시스템을 활용하기 위한 방법은 필요하다.
  • 전통적인 데이터베이스에서 lock table 대신, 오브젝트 자체의 1-2 bit를 사용해서 lock을 구현할 수 있다.

Commit Processing

  • 메모리는 volatile하기 때문에 commit 전에 디스크에 로깅을 하는 것이 필요한데, 디스크 액세스는 인메모리 데이터베이스 시스템에서 커다란 성능 bottleneck을 유발할 수 있다.
    • 디스크에 비해 상대적으로 빠르고 작은 stable memory를 도입해서 로그의 일부를 저장할 수 있다. 트랜잭션과 별도로 stable memory에 쓰여진 로그를 디스크에 기록하는 프로세스가 존재할 수 있다.
    • Precommitting – 로그가 디스크에 쓰여지기 전에 트랜잭션의 lock들을 릴리즈하는 방식 – 을 사용해서, lock contention을 줄여 다른 트랜잭션의 응답시간을 개선할 수 있다.
    • Group commit – 복수의 트랜잭션의 로그들을 메모리에 모아뒀다가 한번에 디스크로 flush하는 방식 – 을 사용해서 로깅 bottleneck을 완화할 수 있다.

Access Methods

  • 인메모리 데이터베이스의 인덱스 구조를 위해 여러가지 형태의 해싱과 T-tree와 같은 트리들이 제안되고 있다.
  • 그러한 인덱스 구조들은 공통적으로, 데이터 자체가 아니라 데이터로의 포인터를 저장함으로써 메모리의 이점을 잘 활용하고 있다.

Data Representation

  • 튜플은 데이터로의 포인터 집합으로 표현될 수 있다.
  • 커다란 데이터가 반복적으로 나타난다면 중복 저장하지 않음으로써 공간 효율을 높일 수 있다.
  • 가변 길이 데이터를 포인터로 표현함으로써 데이터구조 디자인을 단순화할 수 있다.

Query Processing

  • 데이터에 대한 포인터 메커니즘을 이용해서 어떤 오퍼레이션을 매우 효율적으로 수행할 수 있다.
    • 예를 들어, 두 테이블을 하나의 attribute를 기준으로 join하려는 경우 그 데이터를 사용하는 튜플로의 포인터를 통해서 엄청나게 효율적으로 join을 수행할 수 있다.
  • 전통적인 데이터베이스에서는 디스크 액세스를 줄이려고 했지만, 인메모리 데이터베이스에서는 CPU 비용을 줄이는 것에 집중해야한다.

Recovery

  • 인메모리 데이터베이스에서는 트랜잭션들은 메모리 상의 데이터만을 이용하므로, 체크포인팅이나 복구가 디스크 상의 데이터를 액세스하는 유일한 이유다.
    • 따라서, 인메모리 데이터베이스에서는 체크포인팅에 최적화해서 매우 커다란 블럭 사이즈를 사용할 수 있다.
  • 복구할 때 많은 양의 데이터를 읽어들여야 하는 문제를 해소하기 위해서 필요한 데이터 블럭부터 로드하거나 여러 개의 디스크로부터 병렬적으로 로드하는 방법을 고려할 수 있다.

Systems

IBM에서 개발한 상용 제품인 Fast Path 이 외에 몇가지의 인메모리 데이터베이스 연구용 프로토타입들에 대해서 간단히 소개하고 있다.

내가 배운 것 & 생각한 것

  • 나도 품어왔던, 인메모리 데이터베이스에 대해서 가장 기본적인 질문들 – 특히, “충분히 많은 메모리 캐시를 가진 디스크 기반 DB를 쓰면 되잖아?” – 에 대해서 명확하게 답하고 있다.
  • 전통적인 데이터베이스 아키텍처 상의 각각의 모듈 또는 기능들에 대해서 인메모리 데이터베이스는 어떻게 다른지, 그리고 어떤 해결책을 고려할 수 있는지를 비교적 짧지만 매우 쉽게 이해할 수 있도록 쓰여져있다.
    • 인메모리 데이터베이스 시스템에서 고려해야할 빅 픽처를 이해하는 데 도움이 된다는 의미에서 도움이 되었다.
    • “OLTP Through the Looking Glass, and What We Found There” 리뷰에서 언급한 것과 마찬가지로, 구체적인 해결책에 대해서는 다양한 문맥에서 더 나은 진척들이 있기 때문에 이 페이퍼에 쓰여진 것만을 고려해서는 안된다.
  • 1992년 이후로 여러가지 변화 – 하드웨어의 발전, OS 및 프로그래밍 시스템의 발전, 인메모리 데이터베이스 분야의 연구 – 가 있었기 때문에, 몇몇은 현재 시점에서는 유효하지 않은 것 같다.
    • Optane DC Memory와 같은 non-volatile memory가 제품화되고 있으므로, 이제 ‘passive’한 메모리 하드웨어가 생겨났다고 할 수 있다.
    • 결국 many-core 시스템의 이점을 잘 활용하기 위해서는 여전히 lock granularity는 중요한 것 같다. 다만, 데이터베이스 lock granularity를 가진 KeyDB가 좋은 성능을 보여주는 것을 보면 완전히 틀린 말은 아니다.
    • optimistic concurrency control에 대해서는 많이 언급하지 않고 있다.
    • 이 페이퍼에서는 CPU 비용을 측정하는 것이 어렵다고 언급되어 있으나, 이후로 CPU 비용에 대해서 측정하는 방법이 많은 발전을 이루었다.

Paper: OLTP Through the Looking Glass, and What We Found There


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년대 후반에 시작된 프로젝트인 레디스가 어떤 동기로 시작하게 되었을까 많이 생각을 해보았다. 이 페이퍼에서 얘기하고 있는 디스크 기반 데이터베이스 시스템과 멀티쓰레드 지원, 트랜잭션 지원 등의 오버헤드를 완전히 제거해버린 시스템이니까. 그리고, 인메모리 데이터베이스 시스템을 만든다면 레디스와 대비해 어떤 기능적인 장점을 가져야 하고 그러인한 성능 오버헤드에 대해 어느 부분을 신경을 써야하는 가에 대해서 고민하는 시발점이 되었다.

잉크젯 프린터 수리하기 vs. 새로 사기

약 2년 전에 아이들 사진을 집에서 좋은 품질로 인쇄하려고 잉크젯 프린터를 샀다. 그 전에는 사진을 인쇄하는 용도로는 소형 포토 프린터를 가지고 있었고, 텍스트를 -주로 논문들 – 인쇄하는 용도로는 레이저프린터를 가지고 있어서 수년 동안 잘 사용하고 있었는데 마침 토너가 다 떨어진 참이었다.

내가 산 모델은 Canon의 TS8030이라는 모델로 고화질 사진 인쇄, 스캐너, 복사가 가능한 가정용 복합기 개념의 제품이었다. 사진들의 인쇄 품질도 그럭저럭 마음에 들었다. 신분증 복사 같은 것들은 가족들을 위한 서류 작업 때문에 꽤나 자주 해야하는 일이고, 일이 바쁘게 진행되는 회사에서 시간을 내서 하기에 어렵다보니, 이를 집에서 할 수 있어서 매우 편리하게 활용할 수 있었다. 반면에 문서들의 인쇄 품질은 레이저 프린터에 비하면 읽기 싫을 정도로 마음에 들지 않았다. 종이 품질 때문에 그런지 모르겠지만 잉크가 살짝 퍼지면서 폰트가 조금 뭉개지는데 이게 레이저프린터의 깔끔한 느낌과는 매우 대조적이었다.

그럭저럭 한 1년 남짓 썼을까 갑자기 인쇄를 하려고 하면 내부에서 딱딱 소리가 나면서 아무것도 프린트되지 않는 현상이 나타났다. 몇번이고 헤드 청소도 하고 내부도 살펴보았지만 원인을 파악하기는 힘들었고, 워낙 정신없이 살아가다보니 수리 맡길 엄두조차 나지 않았다.

아내는 사진을 인쇄해서 집안 액자에 넣어 둔다든지 앨범을 만드는 것도 좋아하기에 내게 몇번이고 수리해달라고 부탁을 했었다. 오늘에야 드디어 생각이 미쳐서 수리를 알아봤더니, 고객이 딱히 포장해두지 않아도 택배를 통해서 포장-회수-수리-반납-대금납입을 해주는 캐논 재팬의 서비스가 있었다. 요금은 3240엔. 어딘가에 신경을 쓰는 것이 내게는 매우 부족한 자원이기에 돈을 들여서라도 신경을 덜 써도 되도록 해주는 것까지는 좋았다.

그런데 문제는 수리 비용. 보증기간 내에서는 수리 비용이 무료지만, 보증기간이 지나면 수리비용은 일률 14,040엔. 문제는 이 프린터를 구입한 가격이 19,000엔 가량이었다는 것이다. 게다가 새로 구입하는 비용은 TS8130이 14,000엔, TS8230이 28,000엔 정도다. 게다가 TS8130과 TS8230은 디자인이 다를 뿐 기능적으로 큰 차이도 없다. 잉크는 TS8030은 BCI-370/BCI-371 잉크를 사용하지만, TS8130/TS8230은 BCI-380/BCI-381을 사용한다. 과연 얼마나 차이가 날까.

결국은 TS8130을 구입하기로 했다. 논문 등 텍스트 인쇄의 품질은 레이저 프린터가 월등하기에 조금 고민이 되기는 했지만, 아내를 만족시키는 것이 아마 더 중요하겠지.

한편으로는 개별 수리 건들을 처리해야하는 인적 비용이 제품의 생산단가보다 더 비싸고, 매년 신규 모델을 내놓고 신규 모델에는 높은 가격을 책정한다거나, 잉크 모델을 바꿔버려서 이익을 보는 신기한 프린터 비즈니스의 세계를 조금 엿볼 수 있었다.