데이터 중심의 애플리케이션 설계 - 해시 인덱스

키-값 데이터에 대한 인덱스는 일반적이며 더 복잡한 인덱스를 위한 유용한 구성 요소다.

키-값 저장소는 프로그래밍 언어의 사전(Dictionary) 타입과 매우 유사하다, 일반적으로 해시 맵(해시 테이블)으로 구현된다.

앞의 예제에서처럼 데이터 저장소가 파일에 추가하는 것만으로 구성되어 있다고 가정하자.
이 경우 가장 간단한 인덱싱 전략은 모든 키가 데이터 파일의 바이트 오프셋(값을 찾을 수 있는 위치)에 매핑되는 인메모리 해시 맵을 유지하는 것이다.

• 파일에 새 키-값 쌍을 추가하려면: 데이터의 오프셋을 반영하도록 해시 맵도 업데이트한다.
• 값을 조회하려면: 해시 맵을 사용하여 데이터 파일에서 오프셋을 찾아 해당 위치로 이동한 다음 값을 읽으면 된다.

이러한 간단한 키-값 저장소가 Riak의 기본 스토리지 엔진인 Bitcask의 원리다.
Bitcask는 해시 맵이 메모리에 완전히 보관되기 때문에 모든 키가 사용 가능한 RAM에 맞아야 한다는 조건 하에 고성능 읽기 및 쓰기를 제공합니다.
Bitcask와 같은 스토리지 엔진은 각 키의 값이 자주 업데이트되는 상황에 매우 적합합니다.
예를 들어 키는 고양이 동영상의 URL이고 값은 동영상이 재생된 횟수(재생 버튼을 누를 때마다 증가)일 수 있습니다.
이런 종류의 워크로드에서는 쓰기 횟수는 많지만 고유한 키가 많지 않으므로 키당 쓰기 횟수는 많지만 모든 키를 메모리에 보관하는 것이 가능하다.

디스크 공간이 부족해지는 것을 어떻게 피할 수 있을까?

추가만 가능한 로그의 디스크 공간 부족 문제 해결하기

좋은 해결책은 로그가 특정 크기에 도달하면 세그먼트 파일을 닫고 새 세그먼트 파일에 하위 쓰기를 수행하여 로그를 일정한 크기의 세그먼트로 분할하는 것이다. 그런 다음 이러한 세그먼트에 대해 압축을 수행한다.
압축은 로그에서 중복 키를 버리고 각 키에 대해 가장 최근 업데이트만 유지하는 것을 의미한다.

실제로 세그먼트 병합을 구현하기 위해서는 더 많은 요구사항이 따른다.

• 파일 형식: CSV는 로그에 가장 적합한 형식이 아니다. 먼저 문자열의 길이를 바이트 단위로 인코딩한 다음 이스케이프 없이 원시 문자열을 인코딩하는 바이너리 형식을 사용하는 것이 더 빠르고 간단하다.

• 레코드 삭제하기: 키와 관련 값을 삭제하려면 데이터 파일에 특수 삭제 레코드(tombstone이라고도 함)를 추가해야 한다. 로그 세그먼트가 병합될 때 tombstone은 병합 프로세스에 삭제된 키에 대한 이전 값을 모두 삭제하도록 지시한다.

• 크래시 복구: 데이터베이스가 다시 시작되면 인메모리 해시 맵이 손실된다. 전체 세그먼트 파일을 처음부터 끝까지 읽고 모든 키에 대한 가장 최근 값의 오프셋을 기록하여 각 세그먼트의 해시 맵을 복원할 수 있다.
  하지만 세그먼트 파일이 큰 경우 시간이 오래 걸릴 수 있으며, 서버 재시작에 어려움을 겪을 수 있다.
  Bitcask는 각 세그먼트의 해시 맵 스냅샷을 디스크에 저장하여 메모리에 더 빠르게 로드할 수 있어 복구 속도를 높인다.

• 부분적으로 기록된 레코드: 데이터베이스는 로그에 레코드를 추가하는 도중을 포함하여 언제든지 충돌할 수 있다.
  Bitcask는 체크섬을 파일에 포함하여, 로그에서 이러한 손상된 부분을 감지하고 무시한다.

• 동시성 제어: 쓰기는 엄격하게 순차적인 순서로 로그에 추가되므로, 일반적으로 하나의 쓰기 스레드만 사용하는 것이 일반적이다.
  데이터 파일 세그먼트는 추가만 허용하고, 파일이 변경되지 않으므로 여러 스레드에서 동시에 읽을 수 있다.

추가 전용 로그는 다음의 장단점을 가지고 있다.

추가 전용 로그의 장점

• 랜덤 쓰기보다 훨씬 빠르다. 왜냐하면, 추가 및 세그먼트 병합은 순차적 쓰기 작업이기 때문이다.
• 동시성 제어와 크래시 복구가 간단하다. 값을 덮어쓰는 중에 크래시가 발생하여 이전 값의 일부와 새 값의 일부가 서로 접합된 파일이 남는 경우를 걱정할 필요가 없다.
• 파일 조각화 문제를 방지할 수 있다.

추가 전용 로그의 장점

• 키의 갯수가 매우 많으면 문제가 됩니다. 해시 테이블은 메모리에 꼭 맞아야 하기 때문이다.
• 범위 쿼리가 효율적이지 않다. 예를 들어, kitty00000과 kitty99999 사이의 모든 키를 쉽게 스캔할 수 없으며, 해시 맵에서 각 키를 개별적으로 조회해야 한다.