원문: https://github.com/facebook/rocksdb/wiki/Leveled-Compaction

Leveled Compaction

파일의 구조

디스크의 파일은 여러 레벨로 구성된다. 간단히 말해, 레벨-1, 레벨-2 또는 L1, L2 라고 부른다. 특수한 레벨인 레벨-0 (또는 짧게 L0)는 메모리의 쓰기 버퍼(memtable)에서 막 플러시된 파일들을 저장한다. 각 레벨은 (레벨 0를 제외하고) 하나의 정렬된 데이터의 연속이다:

각 레벨의 내부에는 (레벨 0를 제외하고), 데이터가 여러 SST 파일로 범위가 나누어져있다:

각 SST 파일의 key들이 정렬되어 있기 때문에, 레벨은 하나의 정렬된 데이터의 연속이다. (예시로 Block-based Table Format이 있다). Key의 위치를 찾으려면, 먼저 모든 파일의 시작/끝 key를 이진 검색(binary search)하여 key가 들어있는 파일을 식별한 다음, key 내부에서 이진 검색을 수행하여 정확한 위치를 찾는다. 그 레벨의 모든 키에 대해 전체 이진 검색을 한다.

0이 아닌 모든 레벨에는 타겟 크기가 있다. Compaction의 목표는 그 레벨의 크기를 타겟 크기보다 작게 만드는 것이다. 타겟 크기는 대개 기하급수적으로 증가한다:

Compactions

Compaction은 L0 파일의 수가 level0_file_num_compaction_trigger에 도달했을 때 발생하고, L0의 파일들은 L1에 병합(merge)된다. 일반적으로 L0 파일들은 key 값이 겹치기 때문에, 모든 L0 파일들을 compaction 대상 파일로 선택해야 한다:

Compaction 후, L1의 크기가 타겟 크기를 초과할 수 있다:

이 경우, L1에서 하나 이상의 파일을 선택하고, 그 파일과 중복되는 key 범위를 갖는 L2 파일들과 병합한다. 결과 파일은 L2에 새로 쓰여진다:

그 결과로 다음 레벨의 크기가 타겟 크기를 초과하는 경우, 이전과 동일하게 파일을 선택하여 다음 단계로 병합한다:

그 다음으로,

그 다음으로,

필요한 경우 여러 compaction을 동시에 실행할 수 있다:

허용되는 compaction의 최대 수는 max_background_compactions에 의해 결정된다.

그러나 L0에서 L1 compaction은 병렬화(parallelize)할 수 없다. 경우에 따라, 전체 compaction 속도를 느리게 하는 병목 현상이 발생할 수 있다. 이 경우, 사용자는max_subcompactions을 1보다 크게 설정할 수 있다. 이 경우 범위를 분할하고 여러 thread를 사용하여 compaction을 실행한다:

Compaction 선택

여러 레벨이 compaction을 유발할 때 RocksDB는 어느 레벨을 먼저 compaction 할지 선택해야 한다. 이를 위해, 각 레벨에 대해 점수가 생성된다:

• 0이 아닌 레벨의 경우, 점수는 레벨의 총 크기를 타겟 크기로 나눈 값이다. 이미 선택된 파일이 다음 레벨으로 compaction되는 경우, 해당 파일은 곧 사라질 것이므로 전체 크기에 포함되지 않는다.

• 레벨 0의 경우, 점수는 파일의 총 개수를 level0_file_num_compaction_trigger로 나눈 값이거나, max_bytes_for_level_base를 넘는 총 크기로, 둘 중 더 큰 값이다. (파일 크기가 level0_file_num_compaction_trigger보다 작으면, 점수가 아무리 크더라도 compaction은 레벨 0에서 발생하지 않는다)

RocksDB는 각 레벨의 점수를 비교하며, 가장 높은 점수를 가진 레벨이 우선 순위를 가지고 있다.

레벨의 타겟 크기

level_compaction_dynamic_level_bytes == false

만약 level_compaction_dynamic_level_bytes가 false면, 레벨 타겟은 다음의 방식으로 결정된다: L1의 타겟 사이즈는 max_bytes_for_level_base가 된다. 그리고 Target_Size(Ln+1) = Target_Size(Ln) * max_bytes_for_level_multiplier * max_bytes_for_level_multiplier_additional[n]이다. max_bytes_for_level_multiplier_additional의 기본값(default)은 모두 1이다.

예를 들어, 만약 max_bytes_for_level_base = 123456, max_bytes_for_level_multiplier = 10이고 max_bytes_for_level_multiplier_additional이 설정되지 않았다면, L1, L2, L3, L4의 크기는 각각 16384, 163840, 1638400, 16384000이 된다.

level_compaction_dynamic_level_bytes == true

마지막 레벨인 (num_levels-1)의 타겟 사이즈는 항상 그 레벨의 실제 사이즈다. 그리고 Target_Size(Ln-1) = Target_Size(Ln) / max_bytes_for_level_multiplier이다. 타겟 사이즈가 max_bytes_for_level_base / max_bytes_for_level_multiplier보다 작은 레벨은 채우지 않는다. 이 레벨들은 비어있는 채로 존재하고, 모든 L0 compaction은 그 레벨들을 건너뛰고 유효한 타겟 크기를 갖는 레벨을 대상으로 진행된다.

예를 들어, 만약 max_bytes_for_level_base가 1GB고, num_levels=6 그리고 마지막 레벨의 실제 크기가 276GB라면, L1-L6의 타겟 크기는 각각 0, 0, 0.276GB, 2.76GB, 27.6GB, 276GB가 된다.

이는 안정적인 LSM-tree 구조를 보장하기 위한 것으로, 만약 level_compaction_dynamic_level_bytes가 false이면 보장될 수 없다. 예를 들어, 이전의 예시를 그림으로 나타내면 다음과 같다:

데이터의 90%가 마지막 레벨에 저장되고 9%가 두번째 마지막 레벨에 저장됨을 보장 할 수 있다. 이것에는 여러 가지 이점이 있을 것이다.