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 기능에 대한 언급이 있기는 하다.