데이터의 효율적인 저장과 조회(SSTable, Bloom Filter, LSM Tree)

SSTable, Bloom Filter, LSM Tree

rate limiter와 key-value store의 설계 진행하면서 아래의 개념들을 순서대로 확인해보았다

1. 고가용성 rate limiter가 필요함
2. rate limiter에서 사용하는 알고리즘 확인
   • token bucket
   • leaky bucket (queue bucket)
   • fixed window counter (단위 시간당 고정된 갯수)
   • sliding window log (timestamp 기준으로 deprecate)
   • sliding window counter (% 기반으로 count 추정)
3. counter를 저장하기 위해서 고가용성, 분산 환경의 key-value store가 필요함
4. 어떤 Node에 저장될지 결정해야 함 : Consistent Hash
5. 고가용성, 데이터 다중화 : Quorum (N,R,W)
6. 데이터 다중화 과정에서 동기화를 보장해야 함 : Client Side, Versioning, Vector Clock
7. 장애를 탐지해야 함 : 가십 프로토콜
8. 일시적인 장애를 감내해야 함 : Quorum (N,R,M)
9. 영구적인 장애에서 데이터를 복구해야 함 : HashTable

위 과정까지 진행하면 대부분의 문제를 해결해서 데이터가 메모리 상에서 잘 관리됨을 보장할 수 있다. 다음으로는 메모리와 디스크 사이의 동기화 과정에 대해서 알아보아야 한다.

Bloom Filter

거대한 데이터 셋에서 특정 데이터가 존재하는지 아닌지 찾을 떄 사용한다.

• bloom filter return false : 데이터 셋에 존재하지 않음
• bloom filter return true : 존재할 수도 있고, 존재하지 않을 수도 있음

username을 등록할 때, 이미 해당 username이 이미 존재하는지 확인해야하는 경우가 있다.
이 때 bloom filter가 return false를 한다면, username을 사용할 수 있음이 보장된다.

bloom filter는 확률에 기반한 접근 방법이라서 정확도가 떨어진다고 볼 수도 있지만,
공간의 제약을 개선해준다는 점에서 유의미한 장점을 가진다.

동작 과정

Bloom Filter는 2가지로 구성된다.

1. Hash Function
2. a bit array with Length N

ADD

하나의 데이터에 대해서 여러개의 Hash Function을 적용한다.
그리고 각 값을 a bit array의 길이로 moduler를 해서 bit array의 값을 0->1로 변경한다.
이미 1이라면 그대로 둔다.

• arr[func_1(x) % N]=1
• arr[func_2(x) % N]=1
• arr[func_3(x) % N]=1

CHECK

bloom filter에 이미 존재하는지 확인하고 싶은 값 y에 대해서 아래의 값을 확인한다

• arr[func_1(y) % N]=1
• arr[func_2(y) % N]=1
• arr[func_3(y) % N]=1

특징

• Collision이 발생할 수 있는 확률이 존재하기 떄문에 존재하지 않음만 보장할 수 있다.
• 삭제 연산을 지원하지 않는다. 수행하면 다른 key에도 영향이 가기 때문이다.

SSTable

• Sorted Strings Table

• Apache Cassandra, BigTable에서 사용하는 데이터 저장 포멧

• SSTable은 Disk에서 데이터를 File에 효율적으로 저장하기 위한 포멧

  1. 데이터 블록(data blocks): 실제 키–값 쌍이 담긴 압축된 블록
  2. 인덱스 블록(index blocks): 블록별 최소·최대 키 정보

• 전체 데이터가 아닌 일부 데이터만 사용해서 Index 검색을 수행한다

• 특징

  • File로 저장되기 때문에 persistent함
  • append only를 지원해서 immutable함 (timestamp가 변경되면서 동일한 데이터가 중복해서 저장될 수 있음)

• 전체 데이터셋에 대한 Bloom Filter를 관리하여, 찾는 데이터의 key가 존재하는지 아닌지 확인한다

• key가 존재한다면 데이터 블록의 최소, 최대 값으로 SSTable을 특정하고, 특정된 디스크를 열어서 Value를 확인한다

• 데이터가 정렬되어 있음을 가정되어 있기 때문에, 어떤 SSTable에 저장되어있는지 확인이 가능하고, 특정된 디스트 내에서도 빠르게 데이터를 찾을 수 있다.

• B-Tree는 균형 잡힌 데이터 구조를 지원해서 Sequential, Random Access에서 균형잡힌 성능을 보여주고

• SSTable은 LSM Tree와 함께 사용되어 Heavy Write 상황에서 적합하다

LSM Tree

• Log-Structured-Merge Tree
• SSTable, Bloom Filter를 사용해서 데이터를 효율적으로 저장하는 구조

1. write에 대한 정보를 먼저 WAL에 저장

2. Memory에 Write

3. 임계치에 도달하면 Memory에서 Disk에 SSTable 구조로 flush

4. compression : 작은 파일로 구성된 SSTable을 하나의 큰 SSTable로 합치기 (Read 및 저장 공간 호율 개선)

   • SSTable은 immutable이기 때문에 timestamp가 변경되면서 동일한 데이터가 중복해서 저장될 수 있음
   • key 정렬
   • key에 version이 포함된 경우, 최신 버전만 남기기
   • File로 저장하면서 적절한 단계로 SSTable의 Layer를 나누어서 단계적으로 압축해서 저장함

5. 조회 과정

   • Memory
   • SSTable에 데이터가 존재하는지 확인 (Bloom Filter)
   • 존재한다면 리턴
   • 존재하지 않으면 다음 SSTable에서 조회

Reference

• How Bloom Filters Make Checking Millions of Usernames Lightning Fast
• SSTables : The secret sauce that behind Cassandra’s write performance
• SSTables and LSM Trees