8/16(수) 휴가라서, 그 다음 스터디 시간에 발표하겠습니다~

SSTable and Log Structured Storage: LevelDB

https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/

SSTable: Sorted String Table

simple abstraction to efficiently store large numbers of key-value pairs while optimizing for high throughput, sequential read/write workloads.
데이터는 key와 value로 구성되며, key 기준으로 데이터가 정렬 되어 있어야 한다.
SSTable 내(=하나의 세그먼트)에는 중복되는 key를 가진 데이터는 없어야 한다.

SSTable and BigTable: Fast random access?

Once an SSTable is on disk it is effectively immutable because an insert or delete would require a large I/O rewrite of the file.
sparse index로 데이터 검색을 개선 시킬 수 있다.
- Optionally, if the file is very large, we can also prepend, or create a standalone key:offset index for fast access.
- 이렇게 하면 random read 는 빠르고 쉽게 구현이 가능하다.
- 하지만, random write에 대한 개선은.....?

SSTables and Log Structured Merge Trees

we also want to support fast random writes. Google 의 BigTable 은 이를 어떻게 구현해냈을까?

random writes are fast when the SSTable is in memory (let's call it MemTable), and if the table is immutable then an on-disk SSTable is also fast to read from.
이 색인 구조는 LSM 트리 (Log-Structured Merge-Tree)의 이름으로 먼저 발표되었고, Google 의 BigTable 논문에서 SSTable, MemTable 이라는 용어가 소개되었다고 한다.
1. 쓰시가 들어오면, Memtable, 즉 in-memory balanced tree (ex. red-black tree, AVL tree) 에 추가한다.
2. Memtable 이 일정크기 이상 커지면, 디스크로 flushed 된다. 이미 키로 정렬된 key-value pair 를 유지하기 때문에, SSTable 세그먼트를 생성하게 되는 것. flush 동안의 write 연산은 새로운 Memtable 에 기록된다.
3. read 연산은 먼저 Memtable 에서 key 를 찾는다. 없다면, 디스크 상의 가장 최신 세그먼트부터 차례로 뒤진다.
4. 가끔 세그먼트 파일을 합치고 덮어 쓰여지거나 삭제된 값을 버리는 compaction 과 merge 과정을 수행한다. 이 과정은 백그라운드에서 수행된다.

SSTable 에 대한 index 를 유지할 수도 있다.

However, we will maintain all the SSTable indexes in memory, which means that for any read we can check the MemTable first, and then walk the sequence of SSTable indexes to find our data.
즉, SSTable index 를 메모리에 유지함으로써 random read 에 대한 속도를 개선하는 것.

Merge 가 쉽고 빠르다

merge sort 알고리즘에서 사용하는 방식과 유사
각 segment 별로 가장 앞의 데이터만 비교하여 우선순위가 높은 값을 가져와 새로운 segment에 넣어준다.
키가 같은 경우 가장 처음 나중에 생성된 segment의 데이터가 우선순위를 가진다.
위의 예시에서, 새로우 세그먼트의 처음은 Amelia:5000 -> Anthony:4000 -> Emma:3000 의 순서가 되겠다.

LSM & SSTables: Updates, Deletes and Maintenance

현재 기준 : random write, read 에 대해서는 좋은 성능을 기대할 수 있다.
- writes are always fast regardless of the size of dataset (append-only), and random reads are either served from memory or require a quick disk seek.
그렇다면 updates and deletes 에 대해서는 어떨까?
update
- 가장 최신 값이 MemTable -> 최신의 SSTable 순으로 기록되고, 읽을 때도 동일한 순서로 읽기 때문에 항상 업데이트된 값을 바라보게 된다.
- merge 과정에서 overwrite 된다.
delete
- tombstone 개념을 사용.
- 삭제 시 tombstone record 가 추가되고, 추후 merge 과정에서 제거된다.

SSTables and LevelDB

Google's BigTable, Hadoop's HBase, and Cassandra 등 다양한 곳에서 이 아키텍처를 사용한다.
- Cassandra Documentation 에 소개된 Store Engine Architecture : 위에서 설명된 아키텍처를 그대로 사용하고 있다. https://cassandra.apache.org/doc/latest/cassandra/architecture/storage_engine.html
LevelDB 는 Google's Bigtable 개념을 기반으로 하고, 위에 나온 아키텍처를 그대로 사용한 구현체다.
wikipedia 에 따르면, Google의 BigTable 구현은 구글의 공개되지 않은 코드 라이브러리를 포함하고 있어 오픈소싱이 불가능했고, 이에 BigTable 과 유사한 오픈 소스를 개발했고, 그게 바로 LevelDB 이다.
usage
- the backend database for Google Chrome's IndexedDB
- Bitcoin Core and go-ethereum store the blockchain metadata using a LevelDB database.
- Minecraft Bedrock Edition uses a modified version for chunk and entity data storage

참고

데이터 중심 어플리케이션 설계 3장: 저장소와 검색
- https://stackoverflow.com/questions/58168809/what-is-the-differences-between-the-term-sstable-and-lsm-tree
https://velog.io/@yunhongmin/SSTable-data-storage
https://en.wikipedia.org/wiki/LevelDB

Bloom filter

https://en.wikipedia.org/wiki/Bloom_filter

Bloom filter는 공간 효율적인 확률론적 데이터구조로, 요소가 집합의 구성원인지 여부를 테스트하는 데 사용된다. false positive는 가능하지만, false negative는 가능하지 않다. 즉 쿼리는 "possibly in set" or "definitely not in set" 반환한다.

N size의 bit array
한 개 이상의 hash function

[예시] black ip 집합 N=24인 bit array, 2개 hash function

hashFunction_1("192.170.0.1") : 2 
hashFunction_2("192.170.0.1") : 6

hashFunction_1("75.245.10.1") : 4 
hashFunction_2("75.245.10.1") : 10

hashFunction_1("10.125.22.20") : 10 
hashFunction_2("10.125.22.20") : 19

이제 인입되는 IP가 black ip인지 테스트.

hashFunction_1("75.245.10.1") : 4 
hashFunction_2("75.245.10.1") : 10

hashFunction_1("75.245.20.30") : 19 
hashFunction_2("75.245.20.30") : 23

false-positive

hashFunction_1("101.125.20.22") : 19 
hashFunction_2("101.125.20.22") : 2

언제 사용하면 되지?

집합의 크기가 굉장히 크거나 집합의 속해있는 원소의 크기가 커서 원소가 집합에 속해있는지 정확히 판단하는데 시간이 오래걸리는 경우 이 과정의 전처리 과정으로 Bloom Filter를 이용해서 아예 집합에 속할 일이 없는 원소를 미리 걸러낼 수 있다.

Cassandra architecture

Cassandra

Facebook에서 초기 설계되었으며, 아마존의 분산화된 스토리지 기술과 구글 빅테이블의 replication 기법을 같이 구현하기 위해 SEDA 아키텍쳐를 사용한다.

static
{
    stages.put(Stage.MUTATION, multiThreadedConfigurableStage(Stage.MUTATION, getConcurrentWriters()));
    stages.put(Stage.READ, multiThreadedConfigurableStage(Stage.READ, getConcurrentReaders()));
    stages.put(Stage.REQUEST_RESPONSE, multiThreadedStage(Stage.REQUEST_RESPONSE, FBUtilities.getAvailableProcessors()));
    stages.put(Stage.INTERNAL_RESPONSE, multiThreadedStage(Stage.INTERNAL_RESPONSE, FBUtilities.getAvailableProcessors()));
    stages.put(Stage.REPLICATE_ON_WRITE, multiThreadedConfigurableStage(Stage.REPLICATE_ON_WRITE, getConcurrentReplicators(), MAX_REPLICATE_ON_WRITE_TASKS));
    // the rest are all single-threaded
    stages.put(Stage.GOSSIP, new JMXEnabledThreadPoolExecutor(Stage.GOSSIP));
    stages.put(Stage.ANTI_ENTROPY, new JMXEnabledThreadPoolExecutor(Stage.ANTI_ENTROPY));
    stages.put(Stage.MIGRATION, new JMXEnabledThreadPoolExecutor(Stage.MIGRATION));
    stages.put(Stage.MISC, new JMXEnabledThreadPoolExecutor(Stage.MISC));
    stages.put(Stage.READ_REPAIR, multiThreadedStage(Stage.READ_REPAIR, FBUtilities.getAvailableProcessors()));
    stages.put(Stage.TRACING, tracingExecutor());
}

카산드라와 같은 시스템은 다음 설계 목표를 가진다.

full multi-master database replication
저지연의 global한 가용성
일반적인 하드웨어로 scale out하는 것
(linear throughput) 프로세서가 추가됨에 비례하는 throughput
유연한 스키마
파티션된 키 중심의 쿼리 (CQL)

Cassandra의 특징

카산드라의 인기 중 하나는 개발자들이 동적으로 데이터베이스들을 scale out 할 수 있는 데 있다. 각 노드들은 token range라는 것을 갖게 되고, 데이터들의 각 키는 partitioner에 의해 hashing 되는데 그 결과값은 token range안에 있다. 이 output에 해당하는 token을 가진 노드에 해당 데이터는 들어간다.

Gossip peer-to-peer communication between Cassandra nodes 카산드라의 failure detection은 peer-to-peer 방식 중 하나인 Gossip Protocol에 의해 이루어진다.

튜닝가능한 Consistent Level 카산드라의 Consistent level은 quorum 지정을 통해 조정이 가능하다.

Write 동작 단일 노드 관점에서 클라이언트가 Cassandra 노드에 데이터 쓰기를 요청하면, 요청은 디스크의 커밋 로그 파일에 저장되고, 그 다음 데이터는 memtable이라는 메모리 테이블에 쓰여진다. memtable이 미리 설정된 임계값에 도달하여 꽉 차면, 이는 SSTable이라는 변경 불가능한 구조로 디스크에 플러시된다. Cassandra의 각 테이블에는 해당하는 memtable과 SSTable이 있다.

Read 동작

결론적으로 이렇게 동작한다

https://cassandra.apache.org/doc/latest/cassandra/architecture/

Bigtable: A Distributed Storage System for Structured Data

개요

뛰어난 확장성을 가진 데이터 밀도가 낮은 테이블
- 수십억 개의 행과 수천 개의 열까지 확장, 수 테라바이트~수 페타바이트의 데이터까지 저장 가능함
각 행의 단일 값에 대한 색인이 생성됨 → row key
짧은 지연 시간으로 다량의 단일 키 입력 데이터를 저장하는 데 적합

장점

키/값 데이터에 높은 처리량과 확장성이 필요한 애플리케이션에 적합
일괄 맵리듀스 작업, 스트림 처리/분석, 머신러닝 애플리케이션의 스토리지 엔진으로도 좋음

스토리지 모델

각각 정렬된 키/값 매핑으로 구성되어 있고, 대규모로 확장 가능한 테이블

row key, column family, column qualifier

단일 항목을 기술하는 행과 각 행의 개별 값을 포함하는 열로 구성
단일 row key에서 각 행에 색인을 생성
서로 연관된 열은 column family로 그룹화됨
각 열은 column family와 column family 내 고유 이름인 column qualifier의 조합으로 식별됨

셀, 타임스탬프

각 행/열 교집합에는 여러 셀이 포함될 수 있음
각 셀에는 행과 열의 타임프탬프(t)가 적용된 고유한 버전의 데이터가 포함됨
- 하나의 열에 여러 셀을 저장하면 해당 행과 열에 저장된 데이터가 시간에 따라 어떻게 변화했는지에 대한 레코드 제공
희소한 테이블
- 특정 행에 열이 사용되지 않으면 공간을 차지하지 않음

아키텍처

Bigtable의 전체 아키텍처

태블릿 서버

모든 클라이언트 요청은 프론트엔드 서버를 통과한 후 Bigtable 노드로 전송됨
이러한 노드를 태블릿 서버라하고, 클러스터의 컨테이너인 Bigtable 인스턴스에 속하는 Bigtable 클러스터로 구성됨
클러스터의 각 노드는 클러스터에 대한 요청 중 일부를 처리함
- 클러스터에 노드를 추가하면, 클러스터에서 처리할 수 있는 동시 요청 수 증가 및 클러스터의 최대 처리량이 증가함
  
  위 다이어그램에서는 단일 클러스터가 포함된 인스턴스 하나를 보여주지만, 클러스터를 추가하여 데이터를 복제할 수 있음. 이를 통해 데이터 가용성과 내구성이 향상

태블릿

태블릿이라고 하는 연속된 행의 블록으로 분할되어 쿼리 워크로드를 분산시킴
태블릿은 Google 파일 시스템인 Colossus에 SSTable 형식으로 저장됨
각 태블릿은 특정 Bigtable 노드와 연결됨
모든 쓰기 작업은 Bigtable에서 인식되는 즉시 Colossus의 공유 로그에 저장되어 내구성이 향상

데이터는 Bigtable 노드 자체에 저장되지 않는다

각 노드는 Colossus에 저장되는 태블릿 집합에 대한 포인터를 가짐
그로 인해 얻는 효과
- 실제 데이터는 복사되지 않으므로 태블릿이 한 노드에서 다른 노드로 빠르게 재균등화됨. Bigtable은 단순히 각 노드에 대한 포인터만 업데이트
- 메타데이터만 교체 노드에 마이그레이션해야 하므로 Bigtable 노드 오류가 빠르게 복구됨
- Bigtable 노드가 실패해도 데이터를 손실되지 않음

부하 분산

각 Bigtable 영역은 클러스터 내에서 워크로드와 데이터 볼륨 간의 균형을 유지하는 기본 프로세스로 관리됨
- 분할: 사용량이 더 많거나 크기가 더 큰 태블릿을 둘로 나눔
- 병합: 액세스 빈도가 적거나 크기가 더 작은 태블릿을 병합
- 재균등화: 특정 태블릿의 트래픽이 급증하면, 태블릿을 두 개로 분할한 다음 새 태블릿 중 하나를 다른 노드로 이동
→ 분할, 병합, 재균등화를 자동으로 관리

쓰기 성능 향상을 위한 row key 설계

쓰기 성능을 최대한 활용하기 위해서는, 노드 간에 쓰기 작업을 가능한 한 균일하게 분배하는 것이 중요
1. 예측 가능한 순서를 따르지 않는 row key를 사용
  - 예를 들어, 사용자의 이름에는 특정 알파벳이 더 많이 사용되는 경향이 있음
  - row key의 시작 위치에 사용자의 이름을 포함하면 쓰기가 비교적 고르게 분배될 것임
2. 연관된 행을 서로 인접하도록 그룹화
  - 예를 들어 여러 유형의 날씨 데이터를 시간별로 저장할 경우, row key는 데이터가 수집되는 위치 다음에 타임스탬프가 오는 형식이 될 수 있음
  - 예: WashingtonDC#201803061617
  - 하나의 위치의 데이터 전체를 연속적인 행으로 그룹화
  - 다른 위치의 경우 행을 다른 식별자로 시작하게 됨
  - 많은 위치가 동일한 속도로 데이터를 수집하기 때문에 태블릿 간에 쓰기 작업이 균일하게 분산됨

https://static.googleusercontent.com/media/research.google.com/ko//archive/bigtable-osdi06.pdf https://cloud.google.com/bigtable/docs/overview?hl=ko

Merkle tree

발명자 랄프 머클의 이름을 따 머클트리라 부름
해시트리라고도 불리며 데이터 검증에 사용
루트 노드(머클루트)의 해시값을 비교해도 데이터가 잘못됐음을 파악할 수 있어 유용
데이터의 일부만 검증하고자 할때도 특정 노드의 해시값만 비교하면돼서 유용
보통 악의적인 데이터 변조가 있는지 확인하는데 사용하나 DB의 데이터 동기화 확인에도 사용됨
우리가 잘 아는 블록체인 / 깃 버전 관리 등에 머클트리를 사용함

구조

각 데이터들을 암호화하여 리프노드를 생성
인접한 노드들을 암호화하여 부모 노드 생성
이를 반복하여 루트 노드까지 생성

위의 방식으로 했으니 만약 머클루트가 다르면 데이터가 다를 수 밖에 없음 머클트리로 위조된 거래인지 확인하는 법은 다음과 같음

개인에게는 리프 거래만 가지고 있다고 함 (TX7을 가지고 있다 침)
위의 TX7이 맞는지 확인하고 싶음 -> 가진게 1e3a 와 af3d 뿐
위의 검은 노드들을 받아 해시해나가면서 루트까지 검증이 맞는지 확인

반대로 찾아갈때도 유용 (이미지 복사가 안되니 페이지에서 설명)

https://www.banksalad.com/contents/%EC%89%BD%EA%B2%8C-%EC%84%A4%EB%AA%85%ED%95%98%EB%8A%94-%EB%B8%94%EB%A1%9D%EC%B2%B4%EC%9D%B8-%EB%A8%B8%ED%81%B4%ED%8A%B8%EB%A6%AC-Merkle-Trees-%EB%9E%80-ilULl

참고

data-tech-newbie / system-design-interview

Chapter 6: Design a key-value store #4