1. Intro

데이터 중심 애플리케이션 설계 3장을 읽으면서 가장 이해하기 어렵고 헷갈렸던 것이 SS 테이블과 LSM 트리의 개념적 차이였다.

둘다 세그먼트 병합과 컴팩션을 수행하는것은 동일해보이는데… LSM 트리가 알고리즘이라는 얘기도 책에 서술되어있고, 동시에 저장소 엔진이라는 개념도 서술되어있어서, 정확히 LSM 트리가 자료구조인지? 알고리즘인지? 데이터 저장소 엔진인지? 그럼 SS 테이블과의 연관관계는 무엇인지?가 상당히 이해하기 어려웠다.

책을 여러번 읽었으나, 차이점을 발견하지 못해 처음에는 거의 동일한 개념이라고 결론내릴려 했으나, 요새 핫한 ChatGPT에 혹시나 질문을 했더니 차이가 있다는 내용에 크게 맨탈 붕괴가 왔다. 특히 LSM 트리는 빠른 읽기와 쓰기를 보장해준다고 하는데, SS 테이블이 임의의 쓰기와 정렬된 읽기를 보장해주는 자료구조라는 관점에서 읽기와 쓰기가 동일하게 빠른것이 아닌가? 왜 LSM 트리만의 장점인거지? 라는 생각이 들었다.

• ChatGPT와의 질문 및 답변

  

나뿐만 아니라, 책 스터디를 함께 하는 Matthew도 동일하게 헤매고 있었고 둘다 개념을 이해하고 내재화하는데 어려워 추가적으로 많은 내용을 조사하게 되었고 결국 어느정도 정리를 할 수 있었다.

최종적인 정리된 내용은 다음과 같다.

2. SS 테이블 (Sorted String Table)

2.1. 정의

• 키로 정렬된 자료구조(Sorted String Table)
• 로그 구조화 저장소 세그먼트 내 저장된 키-값 쌍을 키로 정렬한 것

2.2. 특징

• 세그먼트 병합과 컴팩션

  • 세그먼트 병합과 컴팩션을 백그라운드 스레드에서 수행

  • 데이터 자체는 정렬된 형태로 세그먼트 파일로 저장되어있음 (디스크, HDD)

    

• 디스크에 저장된 데이터를 찾기 위한 인메모리 색인이 존재

  • 정렬된 데이터이므로 모든 키의 색인을 유지할 필요 없음

  • 희소 색인(sparse index)의 형태로 구성 가능

    

• 불변성의 특성을 띔

  • 한번 입력된 키-값 데이터는 수정되지 않음
  • 이로 인해 중복된 키가 존재 가능 → 공간 낭비 → 세그먼트 병합(Merge)를 통해 최적화 진행