Consistency

Data-centric consistency models에는 세 가지가 있다[1]. client-centric consistency models까지 덧붙여서 생각할 수도 있지만[2], 일단 NOSQL 특성에 주로 표현되는 것만 생각한다.

1. eventual consistency: 복제를 언젠가는 마쳐서, 다같이 같은 값을 보는 일관성을 보장한다.(가장 약한 보장)
2. causal consistency: 인과성이 있는 작업은 그 순서대로 보여야 한다.
3. sequential consistency: 모든 연산이 특정 순서대로 실행된 것으로 보여야 한다.

2번에 추가적인 설명을 하자면, insert A=1 이후 update A=2 를 했다면 맨 마지막 A=2 만 보이거나, A=1이 보인 뒤 A=2가 보여야한다는 말이다. 1번만 보장하는 DB의 경우에는, 방금 두 연산이 node X에서 실행된다고 하면 node X에서는 A=2가 보이고, 데이터를 복제중인 node Y에서는 A=1이 보이는 상황이 가능하기 때문이다.
이 때 2번의 경우에는 insert B=3을 어느 시점에 하더라도, B=3이 어떤 때에 보이는지는 관계없다. 왜냐하면 서로 인과성이 없기 때문이다.(1번도 당연히 같다. 더 약한 보장이기 때문이다.)

단일 리더 복제는 선형적이 될 수 있으며, 설계/동시성 버그/split brain 등으로 인해 비선형적이 되기도 한다. 주키퍼는 합의 알고리즘을 통해 단일 리더를 선출하고 동작하므로 선형적이라고 한다.
다중 리더 복제는 충돌이 필연적으로 발생하므로, 충돌 해소가 필요하며 이 때문에 비선형적이다.
리더 없는 복제는 write와 read를 할 때, 공유하는 node들에게도 실행해서 선형적임을 보장받을 수 있다. 그러나 선택에 따라 비선형적이 될 수도 있는데 이에 대해 설명한다.

리더 없는 복제의 정책

리더 없는 복제는 Dynamo에 기반한 DB에서 사용한다. 정족수(quorum) 쓰기와 읽기를 한다. dynamoDB와 같은 NOSQL은 보통 eventual consistency를 기본으로 제공하고, 정족수를 사용해서 sequential consistency를 제공한다고 알려져있다.

정족수 읽기가 2 이상일 경우(r > 1), 여러 읽기 도중 오래된 값을 가진 node가 있다면 이를 복구해준다. 이를 읽기 복구(read repair)라고 한다. 오래된 값을 가진 node가 있는 지 백그라운드 프로세스가 지속적으로 찾는 것을 안티 엔트로피 처리라고 한다. 두 메커니즘을 모든 DB가 구현하는건 아니다.
쓰기 가용성을 높이기 위해 정족수 w를 만족하지 않아도 일단 연결할 수 있는 node에 기록하는 것을 느슨한 정족수, 나중에 끊어진 node가 연결되면 수용한 쓰기를 보내주는 것을 hinted handoff라고 한다. DB마다 선택할 수 있는 정책이다.

쓰기 충돌이 일어나면 LWW(last-write-wins)를 해소 방법으로 쓰거나, version vector를 사용해서 동시에 일어났는지 판단하고 정책에 따라 값을 정할 수 있다. LWW는 모든 머신간 시간 동기화를 하기 힘드므로 사실상 부정확한(비선형적) 충돌 해소 방법이다. version vector를 통해 동시에 값이 바뀐걸 확인하고, 두 값의 합집합을 취하면 손실없이 데이터를 병합할 수 있다(version clock과 version vector는 다르다고 하지만, 예시이다.[3, 4]).

리더 없는 복제가 선형성을 보장하려면, 정족수를 w + r > n으로 설정하고, read 시 read repair를 동기로 하고, write할 client는 쓰기 충돌을 막기 위해, write를 보낼 node들의 최신 상태를 알아야 한다. Cassandra는 read repair를 동기로 하지만, write시 LWW로 충돌해소를 하기 때문에 선형성을 보장할 수 없다. 사실상 리더 없는 복제는 비선형적이라고 가정하는게 안전하다.

다중 리더 복제와 리더 없는 복제는 결함 노드, 네트워크 중단, 지연 시간 급증에서 견고하지만 일관성을 보장하기 힘들다.

Cassandra의 tunable consistency

Cassandra는 CAP에서 C를 eventual consistency로 제공하지만, linearizable consistency도 제공할 수 있다고 주장한다[5]. 정족수를 파라미터로 설정해서 r + w > n 이면 후자를 보장할 수 있다고 하는데, 이론적으로 거의 가깝지만 앞서 확인했듯이 LWW를 사용하므로 완벽하다고 하기는 어렵다. 그 외에도 파라미터에 다양한 값을 줄 수 있고, 값에 따라 consistency를 "tune"할 수 있다고 하는데 큰 의미는 없어보인다.

인용

[1] https://en.wikipedia.org/wiki/Consistency_model#Data-centric_consistency_models
[2] https://sergeiturukin.com/2017/06/29/eventual-consistency.html
[3] https://levelup.gitconnected.com/distributed-systems-physical-logical-and-vector-clocks-7ca989f5f780
[4] https://riak.com/why-vector-clocks-are-easy/
[5] https://docs.datastax.com/en/cassandra-oss/3.x/cassandra/dml/dmlAboutDataConsistency.html
참고: 책 "데이터 중심 애플리케이션 설계"

1. 개념

DB는 일반적으로 두 가지로 나뉜다고 한다.
RDBMS는 오래 전부터 사용되던, redo log를 적은 뒤 데이터 파일을 수정하는 방식(WAL)으로 동작하고, NOSQL은 Amazon Dynamo, Google Bigtable에서 비롯된, RDBMS 외의 DB를 말한다. (link: 둘의 차이))
그 중 NOSQL(ex Cassandra)에서 주로 사용하는 SSTable, LSM tree에 대해 알아보겠다.

2. SSTable (Sorted Strings Table)

segments

SSTable은 "segment files"이다. 각 segment 안은 key로 정렬된 key-value들이 저장되있고, 한 segment 안에는 unique한 key만 가질 수 있다. 또한, 당연히 value가 여러번 바뀔 수 있으니까 내부적으로 value에 timestamp 칼럼을 추가로 갖고 있을 것이다. (link: ex Cassandra)

3. LSM tree

memtable

LSM tree를 사용하는 DB는 insert, update 요청이 들어오면 최신 segment에 기록하는게 아닌, 메모리 안의 red-black tree에 저장한다. 이를 memtable이라고 한다. memtable의 entry 개수가 일정 이상이 되면 segment file로 flush한다. 즉, 여러 요청을 single sequential write로 만든다.

write, read

write는 memtable의 최신 segment에 해당하는 red-black tree에 수행하면 된다. read는 우선 최신 segment순대로 각 segment 안에 주어진 key가 있는지 확인해야 한다. memtable에 있는 segment에서 찾아진다면 red-black tree라서 쉽게 찾지만, memtable에 없어서 file로 flush된 segment에서 찾는다면 좀 복잡해진다. 이 segment들에서 binary로 쓰여진 key-value들을 하나씩 읽어나가야 할텐데, 이를 빠르게 하기 위해서 sparse index를 메모리에 저장해놓는다. 추가적으로, 찾는 key가 segment 안에 있는지 빠르게 알기 위해서 bloom filter를 사용한다.

sparse index, bloom filter

sparse index는 말 그대로 띄엄띄엄 어떤 offset에 어떤 key가 있는지 저장하는건데, SSTable은 정렬되있으니, 내 key가 어느 offset 사이에 있는지 찾으면 그 부분만 읽으면 된다. 읽는게 sequential하게 되므로 SSTable과 아주 잘 들어맞는 index이다. sparse index는 segment마다 하나씩 있고, 메모리에만 존재한다.
bloom filter는 다음 알고리즘으로 동작한다. 1)기록된 key는 여러 개의 해시값으로 만들어서 각 해시값에 표시를 한다. 2)찾을 key는 방금 사용된 여러 개의 해시값으로 만들어서 각 해시값을 확인한다.
우연히 없는 key에 대한 해시값들이 다 표시되있어서 false positive가 발생할 수 있다. 즉, key가 없는데도 segment안을 뒤져야할 수도 있다.

delete

SSTable에서는 삭제도 삭제한다는 내용을 append 해야된다. 간단히 삭제할 key에 대한 value를 'tombstone'으로 write하면 해결된다.

compaction

segment file 개수가 너무 많아지면 여러 개의 segment를 하나의 segment로 합쳐야한다. 이를 compaction이라 하는데, 각 file에서 최신 key-value만 남긴 segment를 만들고, 기존 file은 지우는 작업을 말한다. 참고로, tombstone을 가진 key-value는 기록을 하지 않음으로써 삭제한다. compaction은 background process로 동작한다. 추가로, 위 내용은 major compaction이라 하고, memtable을 flush 하고 tablet log(쓰기 요청 내역)를 지우는 것을 minor compaction이라고 한다. HBase에서는 minor compaction이 최근에 flush된 파일 몇 개를 하나로 합치는 것을 말한다.

4. 중간 정리

1. write는 memtable에 기록한다. sparse index, bloom filter는 필요하면 업데이트한다.
2. memtable이 너무 커지면 SSTable segment로 flush한다.
3. read는 최신 segment(memtable 포함)부터 찾는다. 각 segment의 bloom filter를 먼저 확인하고, 없으면 다음 segment로 가고, 있으면 그 segment에 해당되는 sparse index를 확인한다. sparse index에 맞는 부분을 sequential read로 확인한다.

5. recovery

1. tablet log를 보고 memtable 재생성
2. segment들의 sparse index 생성

6. 특징

1. 빠른 쓰기가 가능.
2. 읽기가 메모리 밖 범위에서 RDBMS(B tree)에 비해 느림. B tree vs LSM tree(https://stackoverflow.com/a/8654903)
3. memtable flush, segments compaction, tablet log가 함께 디스크 대역폭을 공유하므로 많은 쓰기가 발생하면 갑작스럽게 성능이 떨어질 수 있음.(=성능이 안정적이지 못함.)
4. major compaction이 느리게 진행될 때, minor compaction이 빠르게 진행된다면 디스크가 다 차버릴 수 있음. 이런 상황은 보통 DB에서 관리하지 않음. 명시적인 모니터링이 필요함.

참고

1. https://yetanotherdevblog.com/lsm/
2. 책: 데이터 중심 애플리케이션 설계
3. https://dzone.com/articles/state-storage-engine