Published on

key-value storage 동작 방식 정리

Authors
  • avatar
    Name
    이건창
    Twitter

Introduction

개요

키-밸류 스토리지 동작을 부족한 부분을 해결하는 방식으로 정리했다.

동작 상상해보며 워밍업

저장소를 설계한다면 영속화를 고려한다. 영속화하는 경우 데이터는 다음처럼 파일에 기록된다.

images

특정 key의 value를 수정한다면 다음처럼 파일에 기록된다.

images

데이터 변경마다 파일을 읽고 작성하는 작업은 부담이다. 다음처럼 파일 끝부분에 데이터를 계속 추가하고 제일 최신에 저장된 key-value를 참조한다면 파일을 읽고 쓰는 작업을 줄일 수 있다.

images

작성마다 파일에 데이터를 추가하는 건 다음 단점이 있다.

  • 여러 클라이언트가 파일 접근을 동기화해야 한다.
  • 데이터가 계속 추가되므로 디스크 요구 용량이 늘어난다.
  • 파일을 작성하는 작업을 동기화해야 한다.

이런 단점을 보완하기 위해 LSM 트리를 사용한다. LSM 트리는 Log-Structured Merge-Tree의 약자로 디스크에 데이터를 저장하는 방법과 구조를 의미한다.

images

간단하게 과정을 설명한다.

  1. Memtable에 데이터를 저장한다.
  2. Memtable이 꽉 차면 SSTable로 변환한다.

Memtable과 SSTable은 다음 특징을 가진다.

  • Memtable
    • 메모리에 저장되는 데이터 구조로 key-value를 저장한다.
    • 탐색이 쉬운 구조로 key를 정렬해 저장한다. 보통 이진 트리로 저장하며 self balancing 특징을 가진다.
  • SSTable
    • Sorted String Table의 약자로 정렬된 문자열 테이블을 의미하며 디스크에 저장되는 단위다.
    • 동시성을 고려해 SSTable은 불변성을 가진다.

Memtable에 데이터를 저장하다가 꽉 차면 SSTable로 변환한다. 즉, SM 트리에서는 모든 쓰기 작업, 즉 삽입, 업데이트, 삭제가 저장소에 지연 적용된다.

여러 클라이언트 요청을 메모리로 처리하는 덕분에 내부 파일 접근 동기화가 간단해진다.

이후 SSTable이 여러개 모이면 단계적으로 컴팩션을 진행한다.

images

디스크 요구 용량을 줄일 수 있다.

이떄 컴팩션은 단계적으로 진행된다. L1, L2, L3 단계로 나눠져서 모일떄마다 다음 단계로 이동한다. 불변성을 깨드리지 않기 위해 단계적으로 진행하는 모습처럼 보인다.(JVM GC survivor1, survivor2 방식처럼 새로운 영역에다 데이터를 옮기는 방식처럼 말이다.)

덕분에 다음 문제점을 해결한다.

  • 여러 클라이언트가 파일 접근을 동기화해야 한다. : 여러 클라이언트는 Memtable에서 작업한다. SSTable 접근 동기화는 비교적 쉽다.
  • 디스크 요구 용량이 늘어난다. : SSTable을 단계적으로 컴팩션한다.
  • 파일 접근 영역 동기화해야 한다. : Memtable에서 SSTable 생성하는건 작업자 한 명으로 충분하다.

쓰기 관련 이슈는 전부 해결했지만 조회가 어렵다. 단계적으로 저장된 SSTable을 모두 조회하는 문제가 발생한다.

이를 해결하기 위해 Bloom Filter를 사용한다.

images

해당 키가 존재하는지 다음 방식으로 확인하면 된다고 생가하는데 틀렸다.

  1. Bloom Filter에 key에 맞는 일부 영역을 마킹한다.
  2. key가 존재하는지 확인할 때 Bloom Filter에 동일한 영역이 마킹된지 확인한다.

그림처럼 다른 키로 인해 칠해져있을 가능성이 있기 때문이다. 사용하는 이유는 해당 키가 존재하지 않음을 확실하게 알 수 있는 방식을 활용하기 위해서다.

만약 해당 키가 마킹돼있다면 키가 존재할 가능성이 있으니 키를 찾으러 떠나야 한다. 완벽한 정답은 아니다. 그러나 Bloom Filter를 사용하면 조회 성능 최적화가 가능하다.

Bloom Filter에 사용할 마킹 영역 넓이에 따라 결과 정확도가 달라진다. 그러나 마킹 영역이 넓어진다는건 마킹할 시간이 늘어난다는 의미니 주의해야 한다.

정보 구체화

Memtable 구조

요약하면 다음과 같은 특징이 있다.

  • skiplists 기반으로 구현한다.
  • freezing 로직이 존재한다.

Memtable은 skiplist 자료구조를 사용한다. skiplist 특징은 다음과 같다.

  • 조회, 삽입, 삭제가 O(log n) 시간 복잡도를 가진다.
  • 연결 리스트 구조를 유지하면서 범위 탐색이 빠르다.
  • 동시 쓰기를 지원한다.

B-트리와 유사항 동작을 지원하지만 skiplist는 정렬된 컬렉션에 대한 동시 쓰기가 가능하다.

skiplist 구현을 선택하는 결정적 이유는 잠금 없는 동시 읽기 및 쓰기를 지원하기 위해 삭제 기능을 제공하지 않는 모습처럼 보인다. skiplist는 각 계층이 있으며 다음과 같은 형태를 띤다.

images
GIF 참고자료 링크

삽입시 최하위 계층에서부터 삽입하고 위 계층 추가 여부는 동전 던지기로 진행한다. (즉, 확률 반반 결정이다.) 50% 확률로 다음 계층에 추가하게 됐다면 최상위 계층까지 동전 던지기를 진행한다.

skiplist 삭제는 모든 계층에서 원소를 찾고 삭제를 진행한다. 그리고 최상위 계층에 원소가 없어진 경우 최상위 계층을 없앤다. 이 떄, 값 변경은 동시성을 제어한다.

Memtable 삭제는 해당 키에 빈 값을 넣어서 처리한다.

Memtable은 SST 크기만큼의 Crate(박스) 단위로 데이터를 저장한다. 즉, 여러 개 Memtable이 존재하고 가변 상태인 Memtable과 불변 상태인 Memtable로 구성된다.

  • 가변 상태인 Memtable : 쓰기 작업을 진행한다.
  • 불변 상태인 Memtable : 쓰기 작업이 완료된 상태다.

그래서 해당 Memtable이 가변인지 불변인지 판단하는 로직에 잠금을 제외하곤 잠금을 필요로 하지 않는다.

images

즉, 적재된 Memtable 순으로 조회시 잠금 없이 데이터를 조회할 수 있다.

images

Memtable의 메모리 레이아웃이 효율적인가? 데이터 지역성이 좋은가? Memtable 효율성을 높이는 방법은 어떤게 있을까?

Memtable 크기를 계속해서 늘릴 수 없다. 그래서 SSTable 크기만큼 계속해서 freezing 한다. 그게 불변 상태인 Memtable이다.

SSTable 구조

LSM 전체구조는 다음과 같다.

images

SSTable 구조에서 블록 단위로 데이터를 저장한다.

-------------------------------------------------------------------------------------------
|         Block Section         |          Meta Section         |          Extra          |
-------------------------------------------------------------------------------------------
| data block | ... | data block |            metadata           | meta block offset (u32) |
-------------------------------------------------------------------------------------------

출처 : skyzh - mini lsm

디스크 구조의 기본 단위는 블록이다. 블록은 일반적으로 운영 체제의 페이지 크기와 SSD의 페이지 크기와 같다. 블록 구조는 다음과 같다.

SSTable에서 데이터를 찾는 방법

요약하면 다음과 같다.

  1. SSTable의 Block Section에 데이터 존재 유무를 확인하기 위해 Meta Section 정보로 저장되는 범위를 파악한다.
  2. Block에서 Data Section에 데이터를 존재 유무를 확인하기 위해 Offset Section 정보로 저장되는 범위를 파악한다.

SSTable에서 데이터 찾는 방법을 설명하겠다. 블록1에 a, b, c 데이터가 저장되고 블록2에 e, f, g 데이터가 저장되면 Meta Section에는 각 블록에 저장된 데이터 범위가 기록된다. 만약 b 데이터를 찾는다면 Meta Section에서 블록1에 저장됨을 확인하고 블록1에 접근한다.

--------------------------------------
| block 1 | block 2 |   block meta   |
--------------------------------------
| a, b, c | e, f, g | 1: a/c, 2: e/g |
--------------------------------------

출처 : skyzh - mini lsm

Block에서 데이터를 찾는 방법을 알아보겠다. Block에는 다수 Entry가 저장된다.

----------------------------------------------------------------------------------------------------
|             Data Section             |              Offset Section             |      Extra      |
----------------------------------------------------------------------------------------------------
| Entry #1 | Entry #2 | ... | Entry #N | Offset #1 | Offset #2 | ... | Offset #N | num_of_elements |
----------------------------------------------------------------------------------------------------

Entry 구조는 여러 개 key, value 데이터가 저장된다. Entry 는 정렬된 상태이니 원하는 데이터를 적절한 방법으로 찾으면 된다.

-----------------------------------------------------------------------
|                           Entry #1                            | ... |
-----------------------------------------------------------------------
| key_len (2B) | key (keylen) | value_len (2B) | value (varlen) | ... |
-----------------------------------------------------------------------
Discuss on Twitter • View on GitHub