[DB] Log structured 저장소

마틴 클레프만의 데이터 중심 애플리케이션 설계를 읽고 있다. 워낙 내용이 자세해서 한번 정리를 해야겠다고 생각했다. 내용을 정리하고 추가 개념 및 내 생각을 덧붙여서 글을 작성해야겠다. 

 

Log structured 

• 쓰기 작업은 로그 형태로 기록되며, 디스크에 순차적으로 저장된다. 이로써 쓰기 작업이 효율적으로 이루어진다. 

1. 해시 색인 (Hash Index) 

• 키를 데이터 파일의 바이트 오프셋에 매핑해 인메모리 해시 맵을 유지
• 새로운 키-값 쌍 추가할 때마다, 방금 기록한 데이터의 오프셋을 반영하기 위해 해시맵 갱신
• 값 조회 시, 해시 맵을 이용해 데이터 파일에서 오프셋을 찾아 해당 위치를 구하고 값을 읽음
• 항상 추가만 하기에 디스크 공간이 쉽게 부족 

2. 로그 구조화 저장소 세그먼트

• 특정 크기의 세그먼트로 로그를 나누는 방식
• 특정 크기에 도달하면 세그먼트 파일을 닫고 새로운 세그먼트 파일에 쓰기를 수행
• 세그먼트 파일에 대해 컴팩션(중복된 키를 버리고 각 키의 최신 갱신 값만 유지하는 것) 수행 가능

컴팩션과 세그먼트 병합을 동시에 수행

 

3. SS 테이블

• 키 값 쌍을 키로 정렬
• 각 키는 각 병합된 세그먼트 파일 내에 한 번만 나타나야 한다. 
• 세그먼트 병합이 간단하고 효율적 (병합정렬과 유사)
• 특정 키를 찾기 위해 더는 메모리에 모든 키의 색인을 유지할 필요가 없다. (handbag과 handsome 키의 오프셋만 알아도 handiwork의 오프셋을 알 수 있다.)

 

 

SS 테이블 세그먼트 병합 후, 각 키의 최신 값만 유지

 

어떻게 키를 정렬하면서 순차적 쓰기가 가능할까?

아래와 같이Log-structured Merge tree 알고리즘을 활용한다. 

• 쓰기가 들어오면 인메모리 균형 트리(e.g. 레드 블랙트리)에 추가한다. 이 인메모리 트리를 멤테이블 (memtable)이라고 한다.
• 멤테이블이 임곗값보다 커지만 SS 테이블 파일로 디스크에 기록한다.
• 읽기 요청을 제공할 때, 멤테이블 -> 최신 세그먼트 -> 두번째 오래된 세그먼트 순으로 찾는다. 

 

또한, LSM 트리 알고리즘에서 데이터베이스에 존재하지 않는 키를 찾는 경우, 느릴 수 있다. 멤테이블부터 가장 오래된 세그먼트까지 거슬러 올라가야 한다. 이 경우 블룸필터를 활용한다. 블룸필터는 어떤 값을 여러 해시 함수에 넣어 결과값들을 임의의 테이블에 인덱싱하여 해당되는 모든 값이 1인지를 따지는 자료구조이다. 즉 블룸필터를 통해 어떤 키가 데이터베이스에 존재하지 않음을 알 수 있다.