<div id="readability-page-1" class="page"><div><p>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:<a href="https://doi.org/10.1145/2723372.2749436">https://doi.org/10.1145/2723372.2749436</a> (<a href="https://db.in.tum.de/~muehlbau/papers/mvcc.pdf">pdf</a>)</p><h2>요약</h2><p><a href="https://hyper-db.de/">HyPer</a>의 MVCC 구현에 관한 페이퍼.</p><p>많은 DBMS들이 MVCC를 구현하고 있지만, 대부분의 경우, 직렬성 (Serializability)을 보장하기 보다는 이보다 더 약한 격리 수준인 스냅샷 격리 (Snapshot Isolation; SI) 만을 보장하고 있다. 일반적으로 스냅샷 격리를 직렬적으로 만들기 위해서는 높은 비용이 필요한 것으로 알려져있는데, 이 페이퍼에서는 적은 비용으로 직렬성을 보장하는 MVCC 구현을 제안하고 있다.</p><p>이 구현의 기본적인 접근은 메인 테이블에는 최신 버전을 유지하고 in-place update를 하되, 새로운 버전으로부터 오래된 버전 순서대로 (newest-to-oldest) 연결된 버전 벡터를 통해 이전 버전에 대한 액세스를 제공한다.</p><figure><img data-attachment-id="942" data-permalink="http://blog.lastmind.io/archives/941/screenshot_20200626_193442" data-orig-file="https://i2.wp.com/blog.lastmind.io/wp-content/uploads/2020/07/Screenshot_20200626_193442.png?fit=1430%2C830" data-orig-size="1430,830" data-comments-opened="1" data-image-meta="{&quot;aperture&quot;:&quot;0&quot;,&quot;credit&quot;:&quot;&quot;,&quot;camera&quot;:&quot;&quot;,&quot;caption&quot;:&quot;&quot;,&quot;created_timestamp&quot;:&quot;0&quot;,&quot;copyright&quot;:&quot;&quot;,&quot;focal_length&quot;:&quot;0&quot;,&quot;iso&quot;:&quot;0&quot;,&quot;shutter_speed&quot;:&quot;0&quot;,&quot;title&quot;:&quot;&quot;,&quot;orientation&quot;:&quot;0&quot;}" data-image-title="hyper-mvcc" data-image-description="" data-medium-file="https://i2.wp.com/blog.lastmind.io/wp-content/uploads/2020/07/Screenshot_20200626_193442.png?fit=300%2C174" data-large-file="https://i2.wp.com/blog.lastmind.io/wp-content/uploads/2020/07/Screenshot_20200626_193442.png?fit=1024%2C594" width="1430" height="830" src="https://i2.wp.com/blog.lastmind.io/wp-content/uploads/2020/07/Screenshot_20200626_193442.png?fit=648%2C376" alt="" sizes="(max-width: 1000px) 100vw, 1000px" data-old-src="data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-srcset="https://i2.wp.com/blog.lastmind.io/wp-content/uploads/2020/07/Screenshot_20200626_193442.png?w=1430 1430w, https://i2.wp.com/blog.lastmind.io/wp-content/uploads/2020/07/Screenshot_20200626_193442.png?resize=300%2C174 300w, https://i2.wp.com/blog.lastmind.io/wp-content/uploads/2020/07/Screenshot_20200626_193442.png?resize=1024%2C594 1024w, https://i2.wp.com/blog.lastmind.io/wp-content/uploads/2020/07/Screenshot_20200626_193442.png?resize=768%2C446 768w"></figure><p>흥미로운 것은 아직 커밋되지 않은 트랜잭션에 의해 추가되는 버전이다. 위의 그림에서 Ty는 아직 커밋되지 않은 트랜잭션의 ID로 커밋된 시간과 구분하기 위해서 2<sup>63</sup> 이상의 매우 큰 값으로 할당된다. Ty 트랜잭션에 의해 메인 테이블에서는 ‘7’이라는 값이 in-place update되고, 이 값은 Ty 트랜잭션에게만 보이는 값이 된다. 한편, 버전 벡터의 Ty에 해당하는 항목에는 Ty와 Ty 트랜잭션이 일어나기 전의 값이 저장된다. 따라서, T5 이후에 시작된 (Ty 이외의) 트랜잭션에서는 Ty 트랜잭션이 생성한 버전으로부터 ‘8’이라는 값을 얻게된다.</p><p>커밋되지 않은 데이터를 가진, 즉 트랜잭션 ID를 가진 버전이 존재하는 레코드에 대해 쓰기 오퍼레이션을 하려는 트랜잭션은 바로 중지되고 롤백된다.</p><h3>Serializability Validation</h3><div><div><p><a href="http://blog.lastmind.io/wp-content/uploads/2020/07/Screenshot_20200701_184818.png"><img data-attachment-id="943" data-permalink="http://blog.lastmind.io/archives/941/screenshot_20200701_184818" data-orig-file="https://i1.wp.com/blog.lastmind.io/wp-content/uploads/2020/07/Screenshot_20200701_184818.png?fit=676%2C656" data-orig-size="676,656" data-comments-opened="1" data-image-meta="{&quot;aperture&quot;:&quot;0&quot;,&quot;credit&quot;:&quot;&quot;,&quot;camera&quot;:&quot;&quot;,&quot;caption&quot;:&quot;&quot;,&quot;created_timestamp&quot;:&quot;0&quot;,&quot;copyright&quot;:&quot;&quot;,&quot;focal_length&quot;:&quot;0&quot;,&quot;iso&quot;:&quot;0&quot;,&quot;shutter_speed&quot;:&quot;0&quot;,&quot;title&quot;:&quot;&quot;,&quot;orientation&quot;:&quot;0&quot;}" data-image-title="hyper-predicate-space" data-image-description="" data-medium-file="https://i1.wp.com/blog.lastmind.io/wp-content/uploads/2020/07/Screenshot_20200701_184818.png?fit=300%2C291" data-large-file="https://i1.wp.com/blog.lastmind.io/wp-content/uploads/2020/07/Screenshot_20200701_184818.png?fit=676%2C656" src="https://i1.wp.com/blog.lastmind.io/wp-content/uploads/2020/07/Screenshot_20200701_184818.png?resize=300%2C291" alt="" width="300" height="291" sizes="(max-width: 300px) 100vw, 300px" data-recalc-dims="1" data-old-src="data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-srcset="https://i1.wp.com/blog.lastmind.io/wp-content/uploads/2020/07/Screenshot_20200701_184818.png?resize=300%2C291 300w, https://i1.wp.com/blog.lastmind.io/wp-content/uploads/2020/07/Screenshot_20200701_184818.png?w=676 676w"></a>직렬성을 보장하기 위해서 트랜잭션에서 일어난 읽기 오퍼레이션들이 다른 트랙잭션에 의해 영향을 받지 않았음을 보장하기 위한 검증 단계 (validation phase)를 필요로 한다.</p><p>기존의 방식은 주어진 트랜잭션의 모든 읽기 오퍼레이션을 기록하고, 트랜잭션이 끝나기 전에 다시 한번 읽기 오퍼레이션을 모두 수행함으로써 다른 트랜잭션으로부터의 영향이 없었음을 검증하는데, 이는 스캔이 많은 워크로드에서 굉장히 높은 비용을 요구하게 된다.</p></div><p>이 시스템에서는 Precision Locking이라는 오래된 기법을 이용하는데, 기본적으로 읽기 오퍼레이션이 아니라 읽기 오퍼레이션의 조건 (predicate)들을 기록하고, 검증단계에서는 해당 트랜잭션의 라이프타임 동안 발생한 트랜잭션들의 쓰기 오퍼레이션들이 읽기 오퍼레이션들의 조건과 겹치는 지를 확인하는 방식이다.</p><p>검증할 트랜잭션의 라이프타임 동안 발생한 트랜잭션들을 효율적으로 찾기 위해서 최근의 트랜잭션 리스트를 유지하고, 이 트랜잭션에 함께 저장된 undo 레코드를 통해서 쓰기 오퍼레이션들을 확인할 수 있다.</p></div><h3>Efficient Scanning</h3><p>스캔을 할 때 레코드별로 버전 벡터가 존재하는지 여부를 체크하는 것을 피하기 위해, 일정한 범위의 레코드들마다 버전 벡터가 존재하는 레코드의 범위를 저장하고 (VersionedPositions), 이를 통해 버전 벡터가 존재하지 않는 범위에서는 더 빠르게 스캔할 수 있도록 도와주는 메커니즘을 가지고 있다. 불필요한 버전들은 계속 가비지 컬렉션에 의해 제거되므로, 소수의 레코드들만이 버전을 가지고 있는 것을 가정하고 있다.</p><h3>Evaluation</h3><ul><li>VersionPositions를 통해서 약 5배 가량의 스캔 throughput 개선이 이루어졌다.</li><li>스냅샷 격리 (SI)에 대비해 직렬성을 보장하는 레코드 레벨 조건 로깅이나 애튜리뷰트 레벨 조건 로깅은 약 5-7%의 비용만을 요구했다.</li></ul><h2>내가 배운 것 &amp; 생각한 것</h2><ul><li>낙관적인 동시성 제어를 사용하는 MVCC 구현, OLTP/OLAP 둘다에 최적화, LLVM을 이용한 코드 생성 등의 기능들이 상용화되는 인메모리 데이터베이스 구현에서 많이 보이고 있다.</li><li>Precision locking을 이용한 낙관적인 트랜잭션의 검증은 듣고나면 당연한 것 같지만, Hyper의 독특한 방식이라고 생각한다. 기존의 데이터베이스에서 반드시 이런 접근을 할 필요는 없었다고 생각하는데, 포인트 쿼리와 업데이트들 만으로 구성된 OLTP 트랜잭션이라면 읽기 집합 (read set)을 이용한 검증이 그리 비효율적이지는 않다고 생각된다. 대량의 스캔을 포함한 OLAP 트랜잭션에 대해서는 2번의 읽기를 하는 것만으로도 비용이 굉장히 높아지므로, 이것을 최근의 트랜잭션 리스트를 유지하는 비용 및 쓰기 집합 (write set)의 크기에 따른 성능 저하와 트레이드 오프한 것으로 볼 수 있는 것 같다.</li><li>우리가 흔히 사용하는 데이터베이스에서는 스냅샷 격리를 사용하는 것이 보편적이고 그 이상은 비용효율적이지 않다는 선입견을 가지고 있었는데, 직렬성을 보장하면서도 충분히 좋은 성능을 보여주는 이 페이퍼를 본 후에 그러한 선입견을 깰 수 있었다.</li></ul></div></div>

The Last Mind

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)의 크기에 따른 성능 저하와 트레이드 오프한 것으로 볼 수 있는 것 같다.
우리가 흔히 사용하는 데이터베이스에서는 스냅샷 격리를 사용하는 것이 보편적이고 그 이상은 비용효율적이지 않다는 선입견을 가지고 있었는데, 직렬성을 보장하면서도 충분히 좋은 성능을 보여주는 이 페이퍼를 본 후에 그러한 선입견을 깰 수 있었다.

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

댓글