OrioleDB

What is OrioleDB

OrioleDB 홈페이지

OrioleDB는 ‘PostgreSQL을 위한 Storage Engine’ 로서, 새로운 테이블 액세스 방법 프레임워크 및 기타 표준 Postgres 확장 인터페이스를 기반으로 개발되었다고 한다.

C언어로 구성되어 있고, 그 외에 Python, PLpgSQL 등을 사용하여 개발하였다.

OrioleDB에서 말하는 Main Feature는 다음과 같다.

• SSD/NVRAM등의 최신 하드웨어에 최적화하여 CPU 보틀넥을 회피
• Pararrel Apply 가능한 저수준 Write-Ahead Log를 구현해서 분산에 적합한 설계
• Raft 콘센서스 기반 복제에 최적화 되어 Active-Active 멀티마스터 가능

2021년 11월에 발표되었으나, 아직 정식 릴리즈는 되지 않은 상태이다.

Structure 및 Architecture

2022년 12월 1일 기준 공식적인 Inner Structure Document는 존재하지 않는 것으로 보인다. 단, Architecture 상으로 다음 기능들이 공개되어 있다.

• Indexes
• Dual pointers
• Page structure
• Copy-on-write checkpoints
• Undo log
• Row-level WAL
• System catalog
• Data compression

Indexes

OrioleDB는 인덱스 일체형 테이블(index-organized table, A.K.A IOT)에 데이터를 저장한다. 즉, 테이블과 인덱스를 모두 가지고 있는 구조로서, 인덱스를 찾고 RowId를 이용한 테이블 엑세스가 필요없는 구조이다.

인덱스를 경유하지 않으므로 분리형 테이블에 비해 논리적 엑세스가 1회 줄어드는 이점이 있지만, 인덱스에 테이블 데이터도 포함되어 있으므로 인덱스만 스캔하는 경우 더 많은 블럭을 스캔해야 한다.

저장 형태는 B-Tree와 같은 Leaf-node에 데이터를 저장하고, Secondary index는 rowid 대신 Primary Key를 사용해야 한다.

일체형 테이블을 도입하여 엑세스 효율이 높고, 범위가 넓은 경우 처리에 용이하나, 유연하지 못하고 데이터 갱신 시 오버플로우가 발생하는 단점도 존재한다.

• Postgres는 직접적으로 인덱스 일체형 테이블을 지원하지 않고, CLUSTER가 유사한 기능을 지원한다.

인덱스 분리형 테이블은 인덱스가 테이블과 달리 별개의 객체로 존재하는 구조로, 일반적인 RDB의 저장 형식이다. 데이터 저장 시 인덱스의 영향을 받지 않으므로 부담이 적고, 데이터 값과 무관하게 저장되는 특징을 지니고 있다.

전통적인 테이블 엑세스 구조는 테이블에 엑세스하기 위해 rowid를 이용하여 탐색하지만, IOT는 인덱스와 테이블이 데이터를 모두 가지고 있다. 그로 인해 각 인덱스 row마다 임의의 위치에 흩어져 있는 테이블에 랜덤 액세스하는 부담이 거의 없지만, 인덱스에 데이블 데이터도 포함되어 인덱스만 스캔하는 경우 더 많은 블럭을 스캔해야 하는 단점도 존재한다.

Dual Pointers

OrioleDB는 dual pointers라고 불리우는 스키마를 사용, 버퍼 매핑과 지연 보틀넥을 회피할 수 있다. non-leaf인 in-memory 페이지의 downlink가 다른 in-memory 페이지 혹은 storage 페이지를 짚어낼 수 있고, buffer table 없이 direct link를 사용하여 in-memory 페이지를 탐색할 수 있다. 즉, 어떠한 버퍼 테이블 없이 직접 링크를 사용하여 in-memory 페이지를 탐색할 수 있다는 뜻이다.

만약 스토리지를 가리키고 있는 downlink 링크를 경유해야 한다면 반드시 메인 메모리에 스토리지 페이지를 불러와야 한다. 이 경우 해당 downlink는 in-memory downlink로 대체되어야 한다.

Postgres의 전통적인 버퍼 관리 전략은 다음과 같다.

각 페이지 별로 엑세스 할 때마다 버퍼 매핑 데이터 구조를 조회해야 한다. 즉, 각 B-tree 조회를 하려면 버퍼 매핑 데이터를 여러 번 탐색해야 한다. 또한, 캐시된 데이터 자체에 엑세스 하는 것은 최신 하드웨어에서는 확장되지 않는다고 한다.

OrioleDB의 dual pointers 구조는 다음과 같다.

퍼버 매핑 테이블이 존재하지 않으므로, 메인 메모리 페이지에서 직접 스토리지 페이지에 접근할 수 있다. 이 때, 메인 메모리 페이지는 메인 메모리와 스토리지 페이지 양쪽을 참조할 수 있으나, 스토리지 페이지는 메인 메모리 페이지를 참조할 수 업고, 오직 스토리지 페이지 끼리만 참조할 수 있다. 상기 구조에서, 메인 메모리와 스토리지 페이지 1,2,3은 표기만 같을 뿐 그 내용은 완전히 다르다.

이 스키마를 implement하려면 우측 링크를 희생해야 한다. 사실 in-memory 포인터와 스토리지 포인터 사이에서 downlink와 우측 링크를 전환하기에는 복잡하고 느리다. 기술적으로 OrioleDB B-tree는 아직 이 우측 링크를 품고 있지만, 이는 페이지를 분할할 때(새 페이지로 나누거나, 부모 노드에 대한 삽입 downlink 사이에만 존재함) 일시적으로만 사용한다. 즉, 트리 페이지 탐색과 동시에 완료된 분할이 이루어질 경우 부모 쪽에서 탐색을 다시 시도해야 한다. 이렇게 되면 트리 페이지를 양쪽으로 관계를 형성하는 과정이 더 복잡해 지는데, 링크를 사용하는 대신 부모 쪽에서 child를 찾아야 한다.

기능적인 복잡함은 자처하더라도, 불필요한 링크 희생을 통한 일관성있는 페이지 탐색을 도모하는 것이라 생각된다.

Page Structure

OrioleDB의 헤더에는 state atomic 변수가 존재한다. 이 atomic 변수는 다음 사항들을 기능적으로 지원해준다.

• 페이지의 exclusive lock 지원. 한 번에 하나의 exclusive lock 페이지 locker만 존재한다. 이는 페이지의 수정이나 다른 프로세스가 페이지를 읽어들이지 못하도록 할 수 있게 한다.
• exclusive locker는 페이지 열람자를 차단하기 위해 업그레이드 할 수 있다. 열람자가 블록되면, locker는 페이지 콘텐츠를 변환하기 시작한다.
• 페이지 콘텐츠의 변경 횟수를 트래킹한다.

결국 atomic을 통해 특정 페이지를 수정하고자 할 때 다중 쓰레드 발생 시 다른 쓰레드가 특정 쓰레드에 영향을 주지 못 하는 쪽으로 데이터를 보존해주는 것 같다.

Page의 tuple은 chunk로 분할되어 있다. 각 chunk마다 연관된 high key가 존재하는데, 마지막 chunk의 high key는 페이지의 high key로 정의된다.

페이지에서 특정한 tuple이 요구될 경우, 모든 페이지를 복제할 필요 없이 high key만 복제하고 적절한 page chunk를 찾아 복사하면 된다. partitial한 pagestate 구조는 부분적으로 읽은 페이지를 추적하는 역할을 한다.

Copy-on-write checkpoints

OrioleDB는 copy-on-write checkpoint와 row-level WAL을 활용한다.

상기와 같은 구조가 있고, 7 페이지가 수정되었을 때, checkpoint는 7*을 storage에 기록한다. 이 때 copy-on-write 정책에 의해 여유 공간에 기록된다. checkpoint가 non-leaf 페이지에 기록되어야 할 때, in-memorry downlink를 하나의 storage로 대체한다.

이 때, storage 페이지에서 새 7*을 참조해야 하므로 페이지 3도 수정된 것으로 간주된다. 그래서 페이지 3*도 1*과 같이 할당되지 않은 storage 공간에 저장된다.

최종 결과는 이런 형태가 될 것이다. 이전에 존재하던 1, 3, 7 페이지는 여유 공간으로 남게 되고, 7*, 3*, 1*에 재배치된 것을 알 수 있다. 즉, 한 페이지에 변화가 일어났을 때, 그 페이지로부터 상향식으로 변화가 이뤄져 여유 공간에 재배치된 후 기존의 storage는 할당이 해제된다. 일관된 Tree Image가 storage에 존재하게 되는 것이다.

OrioleDB는 fuzzy checkpointing을 지원한다. 즉, checkpoint와 트리 수정이 동시에 가능한 것이다. 너무 빠르거나 빈번한 checkpoint는 성능에 도움이 안 되기 때문에 이는 필수적이다.

페이지 1~6은 main memory와 storage(checkpoint 1)에 동시에 존재하고, 페이지 7은 storage(checkpoint 1)에만 존재한다고 가정한다. 그리고 tree가 왼쪽에서 오른쪽으로 이동하기 위한 여정(checkpoint)을 시작하려 한다.

페이지 4에 변화가 발생하였고,이미 2, 4, 5페이지의 하위 tree를 통과하였다. 연관된 페이지인 4*와 2*는 checkpoint 2 라는 storage에 기록된다.

이 때, 4와 2는 직접적인 연결이 있었기 때문에 같은 checkpoint에 저장된다. 이 때, 페이지 5는 4→2를 경유하며 background writter가 checkpoint 3에 따로 저장하였다.

이 때, 직접적인 이동 경로인 1과 3, 7은 같은 checkpoint에 저장된다. 우측 탐색이기 때문에 굳이 3의 좌측에 존재하는 페이지 6은 접근하지도 않았다.

일반적으로 non-leaf 페이지를 checkpointing 하는 것은 상기 예시보다 더 까다롭다. non-leaf 페이지에 대한 checkpoint 수행 도중 병합과 분할이 동시에 일어날 수 있기 때문이다. 이러한 경우가 발생하면 변화가 일어난 child에 근거하여 non-leaf 페이지를 재구성해야 한다. 그러므로, 기본 메모리에 존재하지 않는 non-leaf page 이미지를 따로 저장해야 한다. 여기서 더 나아가, 단일 메인 메모리 페이지에 해당하는 여러 storage 페이지를 작성할 수도 있다.

요약하면, 페이지에 변화가 일어났을 때, 그 상위 페이지와 함께 checkpointing 하여 연관 관계에 의거하여 같은 sotrage에 저장하는 역할을 한다고 볼 수 있을 것 같다.

Undo log

OrioleDB는 Undo log를 사용하여 트랜잭션과 MVCC를 구현한다. row-level 실행 취소 레코드는 row version의 체인으로 구성된다. Tuple header는 list에 연결되어 있으며, head는 데이터 페이지에 위치하고 나머지 요소는 Undo log에 위치한다.

몇몇 Undo log는 tuple header와 tuple body(update record)에 포함되지만, 일부는 tuple body를 변경하지 않고 tuple header(삭제/row-level lock record)만 포함한다. undo record는 row versions chain에 존재하는 것 외에도 트랜잭션 체인에도 존재한다. 트랜잭션이 중단되면, 해당 체인을 통하여 모든 undo record를 재실행한다.

Undo log의 스냅샷은 checkpoint 중에 작성된다. 복구 도중, checkpoint 중에 진행 중인 트랜잭션 중 일부를 롤백해야 할 수 있기 때문에 이 작업이 필요하다. checkpoint 외에도 해당 공유 메모리에 적합하지 않을 때 예상되는 스토리지에 실행 취소 로그를 작성할 필요가 없다.

때때로 트랜잭션 체인의 일부만 재수행해야 할 때가 있다. OrioleDB 관점으로 예를 들면, ROLLBACK TO SAVEPOINT 구현은 트랜잭션의 undo log chain을 지정된 지점으로 재수행한다. INSERT ... ON CONFLICT ... 중에 추론적 삽입을 중단하는 것도 같은 방식으로 작동한다. 그러나 트랜잭션의 일부를 재수행할 때 chain을 취소하면 해당 데이터가 재수행 전에 (부분적으로) checkpoint 될 수 있기 때문에 복구 중에 여전히 필요할 수 있다. 이를 추적하기 위해 복구가 이미 재수행된 분기를 탐색할 수 있는 가능성을 제공하는 special branch undo records를 추가한다.

몇몇 undo records는 커밋 시 몇 가지 동작을 요구한다. OrioleDB이 구현한 TRUNCATE 구현은 트랜잭션 커밋 시 오래된 relfilenode를 삭제하고 트랜잭션 중단 시 새 relfilenode를 삭제하는 Undo log를 발생시키고, 커밋 중인 작업이 필요한 undo record에 다힌 별도의 리스트를 추적한다.

OrioleDB는 block-level에서의 undo record를 지원한다. block-level undo record는 모든 페이지에 적용되는 변경 사항이다.

OrioleDB는 undo records에 대해 세 가지 타입의 block-label을 지원한다.

• Compact undo record. 하나의 데이터 페이지는 하나의 undo page 이미지를 참조한다.
• Split undo record. 두 개의 데이터 페이지는 하나의 undo page 이미지를 참조한다.
• Merge undo record. 하나의 데이터 페이지는 두 개의 undo page 이미지를 참조한다.

Row-Level WAL

OrioleDB는 복구와 대체에 대해 Row-level 차원의 WAL(Write-Ahead Log)을 지원한다. Row-level WAL은 위에서 설명한 구조적으로 일관된 checkpoint가 필요하다. Row-level 차원의 WAL record에는 트랜잭션 시작, 행 삽입, 행 업데이트, 행 삭제, 트랜잭션 커밋/중단 등이 포함된다.

OrioleDB는 데이터에 관해 다음 세 가지의 B-tree가 존재한다.

• TOAST tree
• Primary key tree
• Secondary keys tree

TOAST tree와 Primary key tree는 WAL Logging의 대상이지만 Secondary keys tree는 그렇지 않다. Secondary Key는 TOAST와 Primary Key의 변경에 의거하여 복구를 수행한다.

Checkpointer는 secondary key에 접근하기 전에 우선 TOAST key와 primary key에 접근한다. 그러므로, secondary key는 shceckpoint에서는 TOAST key 및 primary key보다 더 최신 상태이다. 멱등성(동일한 요청을 여러 번 하여도 결과는 달라지지 않는 성질)에 의거하여, 일부 변경 사항이 secondary key에 두 번 이상 적용되는 경우 최종 상태에 영향을 미치지 않도록 보장한다.

OrioleDB는 WAL record가 병렬 애플리케이션으로 구현되어 있다. 각각의 작업자는 자체적으로 primary key values set을 (hash값에 따라)를 담당하며, 시작 프로세스는 row-level WAL record를 작업자에 연결된 대기열에 배포한다.

쿼리 자체는 각각 다른 페이스로 수행될 수 있다. MVCC anomalies(다중 버전 동시성 제어 이상 현상)를 피하기 위해 모든 작업자가 해당 트랜잭션과 관련된 모든 작업을 완료한 경우에만 트랜잭션이 커밋되고 열람자에게 보여진다고 가정할 수 있다.

System catalog

체크포인트, 페이지 쓰기/제거 및 복구 등의 기능은 트리를 논리적으로 조작한다. 그러기 위해 tuple key를 비교하고, tuple의 length를 계산하는 등의 작업을 수행할 수 있어야 한다. 이 루틴을 수행하려면 일부 메타 정보에 엑세스해야 하는데, PostgreSQL 데이터베이스에 완전히 초기화된 연결 없이 이러한 루틴을 수행해야 하는 제약 조건이 있다.

이 문제를 해결하기 위해 OrioleDB는 루틴을 수행하는 데 필요한 최소한의 정보로 OrioleDB의 시스템 카탈로그 아날로그인 “System Tree"를 구현한다.. 시스템 트리에는 테이블, 관련 트리, 데이터 유형 등에 대한 정보가 포함되어 있다.

Data compression

OrioleDB는 block level에서 데이터 압축을 지원한다. 압축 트리에서 storage 페이지는 zstd 알고리즘으로 압축되어, 가변 길이를 가질 수 있다. 이 때문에 압축된 트리에서 여유 공간을 관리하기 위해 더 복잡한 메커니즘을 유지해야 한다. OrioleDB는 offset을 기준으로 정렬된 규모를 유지하고, offset과 length를 기준으로 규모를 정렬한다. 이를 통해 두 번째 tree에서는 새 storage block에 가장 적합한 여유 규모를 검색할 수 있다. 첫 번째 tree는 인접한 규모를 찾고 조인을 시작하는 데 사용된다.