db: SingleDelete 구현(Pebble issue #222)
개요
Pebble은 LevelDB/RocksDB에서 영감을 받은 카크로치디비용 키-밸류 저장소입니다. 현재(2019년 8월)는 개발 진행중인 상태이며, 2020년 카크로치디비 적용을 계획하고 있습니다.
이슈 선택
카크로치디비처럼 이슈가 많지 않아 적절한 대상을 찾기 힘들었습니다. 익숙하지 않은 프로젝트라 perf: N 레벨 compaction(N > 2) 조사, vfs: sstables를 열 때 POSIX_FADV_RANDOM 사용 등 몇가지 이슈를 먼저 확인해보았는데 용어부터가 낯설었습니다. 그 중 db: SingleDelete 구현이 다른 기능에 영향을 주지 않고 구현할 수 있을 것으로 생각되어 해결하기로 정했습니다. 보통이라면 이슈를 먼저 살펴보았겠지만, 작업시간이 오래(약 2-3주) 걸릴 것으로 예상되어 먼저 진행여부를 알리는 코멘트를 추가했습니다.
이슈 파악
이슈에 설명된 Delete의 동작방식과 SingleDelete 요구사항은 다음과 같습니다.
Delete 동작방식
Delete는 tombstone을 만들고, 이 tombstone은 이전 버전의 모든 키를 제거합니다. compaction 과정에서 tombstone은 더 이상 이전버전의 키가 없다고 판단될 때까지 아래 레벨로 전파됩니다(일반적으로 바닥까지 도착함).
SingleDelete 요구사항
키에 단 한 번만 쓰고 삭제하는 사용패턴의 경우 삭제 tombstone을 바닥까지 compaction하는 것은 낭비입니다. compaction에서 Set과 SingleDelete를 동시에 확인하면, 둘 모두를 제거할 수 있습니다. 예를 들어, Set(“a”) 다음에 SingleDelete(“a”)가 뒤따르는 경우, memtable을 플러시 할때 Set과 SingleDelete는 결합되어 제거되므로 디스크에 기록되지 않습니다.
RocksDB와 달리 Delete/Merge와 함께 수행되었을 경우 undefined 처리 대신 Delete로 변환했으면 합니다.
의문점
구글에서 rocksdb single delete use case로 검색해보아도 적절한 사례는 찾지 못해 이 기능 구현의 필요성에 대한 의문이 있었습니다. 하지만 결국 MyRocks에서 SingleDelete를 사용하기 시작한 커밋에서 사용사례를 찾았습니다(세컨더리 키나, 모든 컬럼을 포함하는 기본키의 경우 구현 레벨에서 덮어쓰는 일이 일어나지 않는 것을 보장하고 있었음).
코드 분석
RocksDB에 처음 SingleDelete가 지원된 첫 커밋을 살펴보았지만, 바로 코드 작성자의 의도가 이해되지 않았습니다. 대신 RocksDB 최신 리비전의 compaction_iterator.cc에서 상세한 설명을 확인할 수 있었습니다.
다음 경우에 SingleDelete 컴팩션에서 제외할 수 있다:
1. `PUT`을 만나거나 키가 이후 레벨에 존재하지 않을 때
2. 이미 `snapshot`에서 `record`를 반환했거나 이전 `earliest_write_conflict_snapshot`이 없을 때
컴팩션(compaction)
먼저 컴팩션의 개념에 대해 이해해야 구현을 시작할 수 있었습니다. 이는 LSM 트리의 동작 중 하나이며, 데이터를 다음 레벨로 옮기며 정리하는 동작입니다.
LSM에 대해서도 알아야 했지만 글의 범위가 너무 확장되어 생략합니다.
레벨 0, 1, 2, 바닥(LBottom)에 다음과 같은 데이터가 있다고 생각해 봅시다.
L0:
A:
SET: a
B:
DEL:
SET: b
L1:
B:
SET: b`
L2:
LBottom:
B:
SET: b``
L0에서 L1으로의 컴팩션 과정에서 A의 SET은 그대로 유지되지만, B의 SET은 이후 실행된 DEL에 의해 무효화됩니다. 이미 삭제된 키의 이전 값을 기억할 필요는 없기 때문입니다.
L0 > L1 컴팩션
L0:
L1:
A:
SET: a
B:
DEL:
L2:
LBottom:
B:
SET: b``
이 과정에서 DEL을 제거할 수는 없습니다. 그 이유는 바닥 레벨(LBottom)에 도착하기 전에는 DEL을 tombstone으로 남겨 불필요한 B 키에 대한 명령어를 모두 정리해 주어야 하기 때문입니다. 따라서 LBottom까지 컴팩션이 수행되어야 B의 DEL이 제거됩니다.
L1 > L2 컴팩션
L0:
L1:
L2:
A:
SET: a
B:
DEL:
Lbottom:
L2 > LBottom 컴팩션
L0:
L1:
L2:
Lbottom:
A:
SET: a
하지만, SINGLEDEL는 다릅니다. SINGLEDEL는 사용자가 단 한 번의 SET 사용할 것을 강요하기 때문에, SET을 만나자 마자 삭제해버릴 수 있습니다. 이 결과로 LBottom까지 불필요한 복사작업이 일어나지 않습니다.
다음과 같은 데이터가 있다고 생각해 봅시다.
L0:
A:
SINGLEDEL:
SET: a
L1:
L2:
LBottom:
L0 > L1 컴팩션
L0:
L1:
L2:
Lbottom:
따라서 추가와 삭제가 정확하게 한 번씩만 일어나는 워크로드에서 성능 향상을 얻을 수 있습니다.
Pull Rrequest 제출
PR을 만들어 제출했습니다. 먼저 API를 추가하고 실패하는 테스트 케이스를 작성했습니다. 그 다음 다른 코드들을 참고하며 SingleDelete를 구현하였고 특히 기존의 Delete 키(InternalKeyKindSingleDelete)가 사용된 부분의 수정에 집중했습니다. 마지막으로 SingleDelete와 Delete의 차이를 나타내는 벤치마크를 추가했습니다. 데이터 기반의 컴팩션 이터레이터 테스트가 이미 준비되어 있었는데 처음에는 7개 정도의 테스트가 추가되었습니다.
리뷰
카크로치디비는 리뷰어블이라는 코드리뷰 툴을 사용합니다. GitHub에서도 어느정도의 코드리뷰 기능을 지원하지만 리뷰어블은 더 다양한 기능과 편리한 UX를 제공해줍니다. 리뷰는 여러 방면에서 진행되었는데 주요 내용은 다음과 같습니다.
- 다양한 예외사항에 대한 수정 및 테스트 케이스 추가(7개 > 38개)
SINGLEDEL의 동작방식에 대한 논의(몇 개의SET을 커버해야하는가,MERGE나DEL과 같은 명령어와 만났을 때는 어떻게 동작해야 하는가, 우리가 의도하지 않은 방식으로 사용자가 API를 사용했을 때는 어떻게 동작해야 하는가 등)
마무리하며
약 10일간 8개의 커밋을 통한 이터레이션 끝에 머지되었습니다. 작업 기간동안 핵심 API의 구현에 대한 변경(SINGLEDEL가 몇 개의 SET을 커버할 것인가에 관련하여)이 두 번 정도 있었습니다. 이번 작업을 통해 LSM 트리의 개념을 이해할 수 있었고, 성능 향상을 위해 특수한 워크로드에 대한 API를 추기하는 아이디어는 매우 신선하게 느껴졌습니다.
감사합니다.