SSTable(Sorted String Table)은 storage engine을 구성하기 위한 데이터 저장에 사용되는 데이터 구조 중에 하나이다. 이름 그대로 파일에 데이터가 정렬되어 저장되는게 특징이다.

SSTable 요구 조건

• 데이터는 key와 value로 구성되며, key 기준으로 데이터가 정렬 되어 있어야 한다.
• SSTable 내에는 중복되는 key를 가진 데이터는 없어야 한다.

만약 사람 이름별로 연수입을 저장한다고 하면 SSTable은 다음과 같이 구성된다.

SSTable의 장점

merge 가 쉽고 빠르다.

• 데이터가 SSTable로 저장된 여러개의 segment (디스크 파일)이 있다고 가정해보자. 각 segment 내 데이터는 키 기준으로 정렬이 되어 있으므로 merge sort 알고리즘을 사용하여 O(n) 속도로 병합을 할 수 있다. 병합 되는 동안에는 원본 segment에는 변경사항이 없고, 새로운 생성한 segment 파일에 데이터를 저장한다.

• merge sort 알고리즘을 사용한다. 각 segment 별로 가장 앞의 데이터만 비교하여 우선순위가 높은 값을 가져와 새로운 segment에 넣어준다. 아래 공유된 예시에서는 병합 초기에는 Emma, Amelia, Anthony 키를 비교하게 되고, 이 중 가장 우선순위가 높은 Amelia가 새로 생성된 segment에 가장 처음 들어간다. 그 다음은 Emma, Emma, Anthony 이 세가지를 비교하게 된다. 이 중에서는 Anthony가 다음 우선순위를 가지지므로, 이 데이터가 segment에 들어가게 된다.

  • 키가 같은 경우 가장 처음 나중에 생성된 segment의 데이터가 우선순위를 가진다. 위에 예시에서 Anthony 데이터를 segment에 넣은 이후, Emma, Emma, Emma 가 남게 되는데, 3번째 segment가 제일 최신 생성되었으므로 Emma: 3000 이 최종 segment에 들어간다.

sparse 인덱스로도 데이터 검색을 개선 시킬 수 있다.

• segment 내에서는 순서가 보장되므로, 모든 데이터에 대한 index를 생성할 필요가 없다. segment 내에 몇몇 포인트에 대해서만 index를 생성해 둔 sparse index 만으로도 속도 개선을 할 수 있다. range 검색에서도 괜찮은 성능을 제공한다.

• 데이터가 키 순으로 정렬이 되어 있는데 왜 binary search를 사용하지 않는지 궁금해 할수도 있다. 그러나 데이터의 길이가 데이터마다 다르기 때문에 binary search가 적용되기는 힘들다.

SSTable로 데이터 저장 구현

SSTable을 구성하려면 데이터가 sorting 되어 들어와야 한다. 그러나 일반적으로 데이터가 들어올 때 sortring된 데이터만 들어오는 경우는 없다. 데이터가 임의로 들어오는 상황에서 SSTable의 segment를 구성하려면 데이터가 들어갈 위치를 찾아야 하고, 중간에 끼워넣어야 하기 때문에 효율적이지 않다. 그렇다면 SSTable segment를 활용하여 어떻게 효율적인 데이터 저장 구조를 구현할 수 있을까?

데이터의 저장과 병합

• 처음 들어온 데이터는 메모리에 구성되어 있는 balanced tree에 저장된다. balanced tree는 AVL이나 red-black tree를 이용해 구성하면 된다.
• 메모리의 balanced tree에 어느정도 데이터가 쌓이면 (BT1), SSTable segment를 생성하여 BT1의 데이터를 저장한다. balanced tree에는 데이터가 순서대로 저장되어 있기 때문에, SSTable segment에는 append-only만으로 효율적으로 데이터를 저장할 수 있다. segment 가 생성되는 동안 새로 들어오는 데이터가 있으면, 메모리 상에 별도의 balanced tree (BT2)에 저장된다. SSTable segment로 데이터의 이동이 완료되면, BT1은 삭제한다. BT2도 동일한 방식으로 데이터를 저장해나간다.
• balanced tree는 메모리에 저장되기 때문에, 문제가 생기면 데이터가 유실될 수 있다. 이를 위하여 필요하다면 balanced tree에 데이터를 저장함과 동시에 파일로도 append only로 데이터를 동시에 저장하면 된다. 이 때 생성된 파일은 balanced tree에서 SSTable segment로의 변환이 완료되면, 삭제하면 된다.
• 때때로 SSTable segment 들을 병합한다. 병합 방식은 앞에서 설명한 방식과 같다.

데이터의 조회

• Balanced Tree를 가장 먼저 조회하고, 없다면 SSTable segment 들중에 가장 최근에 생성된 segment 순으로 조회한다.

장점

• SSTable segment 파일은 append-only 만으로 데이터가 저장되기 때문에 sequential write 연산만을 사용하여 데이터가 저장되어 매우 효율적이다. SSD 뿐만 아니라 magnetic 디스크 저장 장치에도 빠르게 데이터를 저장할 수 있다.
• SSTable의 segment는 immutable 하기 때문에, OS 파일 캐시가 사용되면 더욱 빠르게 조회가 가능해진다.

단점

• 만약 찾는 데이터가 없다면 balanced tree와 모든 segment 파일을 훑게 된다.