[250426] Build a Database

Method: get(byte[] key) -> byte[]

Get 메서드는 데이터베이스에서 레코드를 검색하여 해당 레코드 또는 **None**을 반환합니다. 먼저, 이 메서드는 MemTable에 레코드를 쿼리한다. 둘째, MemTable에서 결과를 찾을 수 없으면 가장 낮은 수준에서 가장 높은 수준까지 SSTables를 쿼리한다.

레코드가 발견되면 가장 낮은 레벨의 레코드를 반환하는데, 이는 상위 레벨의 레코드가 더 오래되었을 가능성이 높기 때문이다.

Method: set(byte[] key, byte[] value) -> bool

Set 메서드는 데이터베이스에 키-값 쌍을 설정(SET)한다. 처음에 이 레코드는 MemTable과 WAL에 삽입된다. 멤테이블이 용량에 도달하면 새 SSTable이 생성되고 멤테이블과 WAL이 지워진다. 더 많은 테이블이 생성되면 압축은 하위 레벨에서 상위 레벨로 SSTable을 병합하여 오래된 레코드를 정리한다.

Method: delete(byte[] key) -> bool

삭제 메서드는 이 레코드가 삭제되었음을 나타내는 부울을 (Tombstone)이라고 저장하여 데이터베이스에서 레코드를 제거한다. 이 메서드는 Set 메서드와 비슷하지만 값이 없다. 데이터를 더 쓰는 대신 데이터베이스에서 이 레코드를 제거하면 안 되는 이유는 무엇인가? 데이터베이스에서 레코드를 지우려면 해당 키가 포함된 모든 SSTable을 다시 작성해야 하기 때문에 툼스톤을 추가한다. 이는 몇 밀리초 안에 응답을 기대하는 데이터베이스 클라이언트에게는 너무 많은 시간이 소요될 수 있습니다. 적절한 시간 내에 삭제 작업을 수행하려면 툼스톤을 사용하여 디스크 공간을 조금 희생해야 합니다.

툼스톤을 사용하면 이후 검색을 수정해야 한다. 툼스톤은 이 레코드가 가장 최근에 삭제되었음을 의미하므로 새로운 Get은 툼스톤에 도달하면 중지되고 None을 반환.

Method: scan(byte[] high_key, byte[] low_key) -> RecordIterator

Scan 메서드는 low_key**와 **high_key 사이의 모든 레코드를 수집. 이터레이터가 생성되어 모든 SSTable을 검색하고 두 키의 범위 내에 있는 레코드를 반환. 이는 각 SSTable에서 **low_key**(또는 그 다음으로 높은 값)를 찾아 다음 레코드가 **high_key**보다 클 때까지 레코드를 하나씩 읽어오는 방식으로 수행.

스캔은 여러 레코드 그룹을 집계할 때 유용. 예를 들어 날씨 앱에서 온도 기록의 키는 {station #}/{timestamp} 형식일 수 있다. 주어진 기간 동안의 모든 기록을 가져오려면 최소 및 최대 타임스탬프 키가 있는 스테이션 번호를 스캔. 이 결과를 통해 기상 관측소의 온도를 그래프로 그릴 수 있다. 유용하지만 스캔은 모든 SSTable에서 읽어야 하기 때문에 비용이 많이듬. 스캔은 기록이 적은 단거리에 가장 적합.

RocksDB의 MemTable은 기본적으로 SkipList를 사용합니다. 스킵리스트는 링크된 목록과 매우 유사하지만 추가 링크가 많습니다. 링크의 첫 번째 레이어는 링크된 목록과 일치합니다. 추가 레이어는 이전 레이어에서 점점 더 작은 요소의 하위 집합을 선택하여 만들어집니다. 추가 레이어는 요소를 건너뛰는 LinkedList입니다.

RockDB는 유명한 프로젝트이고 RockDB의 구현은 데이터베이스의 설계의 정점을 보여주며, 성능을 향한 끊임없는 노력의 결과물이라고 함.

우리는 일단 SkipList 를 구현하지 않고, Vector 를 사용할 것.

MemTable Struct

/// MemTable holds a sorted list of the latest written records.
///
/// Writes are duplicated to the WAL for recovery of the MemTable in the event of a restart.
///
/// MemTables have a max capacity and when that is reached, we flush the MemTable
/// to disk as a Table(SSTable).
///
/// Entries are stored in a Vector instead of a HashMap to support Scans.
pub struct MemTable {
  entries: Vec<MemTableEntry>,
  size: usize,
}

/// MemTable entry.
pub struct MemTableEntry {
  pub key: Vec<u8>,
  pub value: Option<Vec<u8>>,
  pub timestamp: u128,
  pub deleted: bool,
}

뭐 대충 이렇게만 봐도 어떻게 저장될지 느낌이 온다. rust 에 대해선 잘 모르지만…

Memtable 을 하나 생성해보자.

/// Creates a new empty MemTable
pub fn new() -> MemTable {
  MemTable {
    entries: Vec::new(),
    size: 0,
  }
}

키로 검색을 해보자. Rust 는 Vec 구현체에 이진검색을 지원한다고 함.

/// Performs Binary Search to find a record in the MemTable.
///
/// If the record is found `[Result::Ok]` is returned, with the index of record. If the record is not
/// found then `[Result::Err]` is returned, with the index to insert the record at.
fn get_index(&self, key: &[u8]) -> Result<usize, usize> {
  self
    .entries
    .binary_search_by_key(&key, |e| e.key.as_slice())
}

그럼 이제 SET 으로 저장해보자. 동일한 키를 찾으면 덮어쓰거나, 새 항목을 삽입할 수 있는 위치를 찾아야 한다. get_index 함수가 이 작업을 도와줌.

/// Sets a Key-Value pair in the MemTable.
pub fn set(&mut self, key: &[u8], value: &[u8], timestamp: u128) {
  let entry = MemTableEntry {
    key: key.to_owned(),
    value: Some(value.to_owned()),
    timestamp,
    deleted: false,
  };

  match self.get_index(key) {
    // 키가 존재하면 덮어쓰기
    Ok(idx) => {
      // If a Value existed on the deleted record, then add the difference of the new and old Value to the MemTable's size.
      if let Some(v) = self.entries[idx].value.as_ref() {
	if value.len() < v.len() {
	  self.size -= v.len() - value.len();
	} else {
	  self.size += value.len() - v.len();
	}
      }
      self.entries[idx] = entry;
    }
    // 키가 존재하지 않으면 새 항목 삽입
    Err(idx) => {
      self.size += key.len() + value.len() + 16 + 1; // Increase the size of the MemTable by the Key size, Value size, Timestamp size (16 bytes), Tombstone size (1 byte).
      self.entries.insert(idx, entry)
    }
  }
}

삭제할 땐 Tomstone 레코드를 삽입하면 된다.

/// Deletes a Key-Value pair in the MemTable.
///
/// This is achieved using tombstones.
pub fn delete(&mut self, key: &[u8], timestamp: u128) {
  let entry = MemTableEntry {
    key: key.to_owned(),
    value: None,
    timestamp: timestamp,
    deleted: true,
  };
  match self.get_index(key) {
    Ok(idx) => {
      // 삭제된 레코드에 값이 존재하면 멤테이블의 크기에서 값의 크기를 빼기
      if let Some(value) = self.entries[idx].value.as_ref() {
	self.size -= value.len();
      }
      self.entries[idx] = entry;
    }
    Err(idx) => {
      self.size += key.len() + 16 + 1; // 키 크기, 타임스탬프 크기 (16바이트), 툼스톤 크기 (1바이트)
      self.entries.insert(idx, entry);
    }
  }
}

이제 값 조회를 해보자. Vector의 Binary Search를 사용한다.

/// Gets a Key-Value pair from the MemTable.
///
/// If no record with the same key exists in the MemTable, return None.
pub fn get(&self, key: &[u8]) -> Option<&MemTableEntry> {
  if let Ok(idx) = self.get_index(key) {
    return Some(&self.entries[idx]);
  }
  None
}

데이터베이스 설계에서 뜨거운 논쟁 주제 중 하나는 버퍼링된 I/O와 버퍼링되지 않은 I/O입니다. 현재 애플리케이션은 데이터베이스에 더 많은 성능을 요구하고 있지만, 기본 디스크는 이 속도를 따라가지 못하고 있습니다. 디스크를 더 빠르게 보이도록 하기 위해 운영 체제는 디스크의 일부를 메모리에 매핑합니다. 디스크에 대한 변경 사항은 메모리에서만 발생하며, 일정 시간마다 OS가 변경 사항을 물리적 디스크에 기록합니다. 이것이 버퍼드 I/O로, 데이터를 버퍼에 기록한 후 최종적으로 디스크에 플러시하는 방식입니다. 버퍼드 I/O는 언버퍼드 I/O를 사용함으로써 피할 수 있습니다. 언버퍼드 I/O는 데이터를 직접 물리적 디스크에 기록합니다.

Google의 LevelDB(RocksDB의 전신)에 따르면(https://github.com/google/leveldb/blob/main/doc/index.md#synchronous-writes), 버퍼드 I/O는 “동기식 쓰기보다 천 배 빠를 수 있습니다.” 성능 이점은 명확하지만, OS나 물리적 서버가 고장나면 모든 버퍼된 쓰기가 손실됩니다. 기본 데이터의 복제 전략이 있거나 데이터를 쉽게 재생할 수 있다면 이 위험은 수용 가능할 수 있습니다.

RocksDB는 WAL의 레코드를 블록 형식으로 저장하도록 선택합니다. 각 블록은 32KB이며 최대 하나의 레코드만 포함합니다. 블록보다 큰 레코드는 여러 블록 크기의 청크로 나뉩니다. 각 블록의 시작 부분에는 블록의 무결성을 확인하기 위한 블록 콘텐츠의 체크섬이 있습니다. github 리포지토리에서 복사한 전체 블록 형식은 아래와 같습니다:

+----------+-----------+-----------+----------------+--- ... ---+
| CRC (4B) | Size (2B) | Type (1B) | Log number (4B)| Payload   |
+----------+-----------+-----------+----------------+--- ... ---+
CRC = 32bit hash computed over the payload using CRC
Size = Length of the payload data
Type = Type of record
       (kZeroType, kFullType, kFirstType, kLastType, kMiddleType )
       The type is used to group a bunch of records together to represent
       blocks that are larger than kBlockSize
Payload = Byte stream as long as specified by the payload size
Log number = 32bit log file number, so that we can distinguish between
records written by the most recent log writer vs a previous one.

필자는 RocksDB가 블록 모델을 사용한다는 것을 처음 봤을 때, 작은 레코드가 많은 패딩 바이트를 남기며 디스크 공간을 낭비한다는 점에 놀랐다고 한다. RocksDB의 설계자들은 이 점을 인지하고 있으며, 단점 섹션에 이에 대한 설명을 남겨두었습니다. 하지만 그들은 이 모델을 사용하는 데 좋은 이유가 있습니다. MapReduce와 같은 도구는 이 블록 디자인을 활용해 파일을 배치 처리 작업용으로 분할하는 데 사용할 수 있습니다.

저는 이 방법을 절대 사용하지 않을 것이지만, Facebook에는 아마도 RocksDB에서 아카이브된 WAL을 처리해야 하는 일부 처리 작업이 있을 것입니다.

버퍼링된 I/O의 경우, RocksDB는 OS 쓰기 버퍼를 사용하며 사용자에게 OS가 이를 디스크에 강제로 동기화하도록 하는 옵션을 제공합니다. 이는 LevelDB 설계를 따르기 때문에 프로세스가 충돌하는 경우에도 데이터를 복구할 수 있습니다.