[데이터 중심 애플리케이션] 저장소와 검색

해시 색인

프로그래밍 언어에서 볼 수 있는 사전 타입과 유사.

 

파일에 추가만 한다면 디스크 공간이 부족.

해결: 세그먼트로 로그를 나누는 방식.

세그먼트 파일들에 대해 컴팩션을 수행 컴팩션은 로그에서 중복된 키를 버리고 각 키의 최신 갱신 값만 유지.

 

추가와 세그먼트 병합은 순차적인 작업이기 때무에 무작위 쓰기보다 훨씬 빠르다.

세그먼트 파일이 추가 전용이나 불변이면 동시성과 고장 복구는 훨씬 간단하다.

오래된 세그먼트 병합은 시간이 지남에 따라 조각화되는 데이터 파일 문제를 피할 수 있다.

 

해시 테이블은 메모리에 저장해야 하므로 키가 너무 많으면 문제가 된다. 디스크에 해시 맵을 유지할 수 있지만 불행하게도 디스크 상의 해시 맵에 좋은 성능을 기대할 수 없다. 해시 충돌 해결을 위한 복잡한 로직도 필요.

범위 질의에 효율적이지 않다.

SS테이블과 LSM 트리

세그먼트 파일의 형식에 키로 정렬하면 범위 질의 가능.

압축할 수 있어서 용량의 효율성을 올릴 수 있다.

SS테이블과 생성과 유지

유입되는 데이터는 인메모리 균형 트리 데이터 구조에 추가.

임계값보다 커지면 SS테이블 파일로 디스크에 기록.

메모리 소신을 위해 분리된 로그를 디스크상에 유지. 멤테이블을 복원할  때만 필요.

SS테이블에서 LSM 트리 만들기

정렬된 파일 병합과 컴팩션 원리를 기반으로 하는 저장소 엔진.

전문 검색 엔진 루씬도 유사한 방법 사용.

성능 최적화

존재하지 않은 키를 찾으려면 오래 걸림: 블룸 필터

B 트리