카산드라 아키텍쳐

다뤄볼 내용

• cluster 토폴로지 구성
• 노드 p2p 방식 - 어떻게 cluster health를 유지하는지
• 데이터 CRUD 방식 - cassandra에 어떤 영향을 주는지
• 노드 안의 구성요소

Data Centers and Racks

rack : node의 논리적 집합

data center : rack의 논리적 집합

 

Gossip and Failure Detection

- 가십 프로토콜

유래 : 신뢰할 수 없는 경로를 통해 정보를 전달하는 방법 연구하는 과정

탈중앙화된 분산시스템에서 데이터 결함을 발견하기 위해 사용한다. (전체에게 알리지 않아도 전체가 알게 되는 것)

gossiper는 node 상태 list를 갖고있으며 syn/ack/ack2를 주고받는 3-handshake 방식으로 1초마다 node 상태를 확인한다.

gossiper가 대화하고자 한 상대가 죽은 것으로 판별되면 local list에 업데이트 하고 로그를 남긴다.

 

- 결함 발견 (failure detection)

"Phi Accrual Failure Detector"(피 발생 실패 감지기)라는 이름의 분산 컴퓨팅 알고리즘을 사용한다.

idea #1 : flexible 할 것 - application과 decoupling 되어야 한다.

idea #2 : heartbeats 로 node 생사여부 확인 가능해야 한다. - 너무 naive 하다 - "suspicion level" 이 생겼고 네트워크 환경 변동까지 고려하여 바람직하다.

따라서 heartbeats 한 번 안들렸다고 바로 node의 정상여부를 판단하지 않고 heartbeats sampling 과정을 거쳐 binary bit가 아닌 "level"으로 판단

phi 값은 피 발생 실패 감지기의 output으로, 서버 상태 "suspicion" 정도를 확인할 수 있다. phi 임계값으로 실패 민감도를 조정한다.

cassandra는 이 매카니즘으로 보통 10초안에 failed node를 감지할 수 있다.

 

Snitches

- snitch

효율적인 request route를 짤 수 있도록 네트워크 토폴로지 정보를 제공

read의 경우, 일관성 레벨을 고려하여 여러 replica에 접속한다.

빠른 속도를 위해 한 replica에서 full object를 읽고, 다른 replica에 hash values를 요구하여 data의 latest version을 보장하는데 여기서 replica를 선택하는데 도움을 주는 역할을 한다.

default snitch (simple snitch)는 토폴로지 unaware 하기에 data center와 rack을 고려하지 않는다.

data center가 많은 환경, 다양한 network 토폴로지와 cloud 환경(Amazon EC2, Google Cloud, Apache Cloudstack)을 지원하기 위해 여러 종류의 snitch가 있는데 snitch를 환경에 적절하게 고르는 것은 10장에서 다룬다.

 

- dynamic snitching : selected snitch를 DynamicEndpointSnitch 로 wrap하여 기본 토폴로지 정보를 얻는다. 다른 노드들과의 request 성능을 모니터링하다가 query를 최적의 replica로 보내는데 사용됨.

 

 

다음으로, 노드들이 어떻게 데이터를 주고받는지 알아본다.

Rings and Tokens

cassandra는 cluster에서 관리하는 데이터를 ring 구조로 표현, token은 ring 안의 node position을 결정하는 64bit 값이다.

이 특별한 배열은 연속 token 범위가 서로 다른 rack의 노드에 분산되도록 한다.

 

해시 함수를 사용하여 partition key에 대한 token을 계산하여 데이터를 node에 할당한다.

예시) "token(last_name)" 시 Nguyen은 같은 Node에 할당된다.

 

Virtual Nodes (Vnode)

노드별로 token 범위가 할당되어야 한다.

초기 cassandra에는 노드마다 single token 범위를 주었다. - 각 노드마다 token range 계산 필요, 노드 추가/삭제 리벨런싱 작업마다 data 옮기는 등의 많은 리소스가 들었다.

 

- virtual nodes : 하나의 실제 노드 안에 가상 노드를 여러 대 두고, 링을 아주 잘게 나눈 token 범위를 가상노드들에게 할당하여 데이터를 분산한다는 개념

Cassandra 1.2 부터 도입되었으며 2.0부터 각 노드는 기본값으로 256개의 vnode를 가지도록 설정되어있다.

이기종간의 cluster 유지를 더욱 쉽게 해주었으며, 부하가 더 균등하게 분산된다.

cassandra.yaml 의 num_tokens 변수로 vnode 개수 설정이 가능하고, ring에 속한 각 노드의 token range는 num_tokens 값에 비례하여 자동으로 계산된다.

&nbsp;<참고자료 1: &nbsp; Virtual vs single-token architecture >

 

Partitioners

cluster 안에서 data가 노드에 어떻게 분산되는지를 결정한다.

cassandra는 partition에 column을 구성, 각 row는 partition key를 갖고있다. (=row key)

partitioner는 partition key column을 바탕으로 token을 계산하는 hash함수 역할을 한다.

 

CQL Table은 최소 1개 이상의 Column을 primary key라는 것으로 지정해야 한다.

partition key로 지정된 column의 value를 기준으로 데이터를 분산한다.

 

1.2버전 이후로 Murmur3Partitioner가 기본 partitioner이며, 원하는 partitioner로 변경가능하지만 cluster 초기화 이후엔 partitioner를 변경할 수 없다.

murmur algorithm : 64bit의 hash 생성

 

Replication Strategies

Keyspace 생성시 설정되며 cluster내에서 replica들을 어떻게 분산시킬지를 결정한다.

- replication factor : 한 cluster 안의 replica 노드 개수

 

첫번째 replica는 token에 따라 결정되지만, 나머지 replica는 replication strategies를 따른다.

type으로 SimpleStrategy, NetworkTopologyStrategy 2가지가 지원된다.

- SimpleStrategy : ring에서 바로 다음 연속된 node에 replica을 배치

- NetworkTopologyStrategy : 각 replica를 다른 data center의 rack에 할당 가능  → 유효성 증가

(단일 data center 생성된 경우에도 권장되는데, 필요에 따라 data center를 추가하는 것이 더 간단하기 때문)

- OldNetworkTopologyStrategy : 하위 호환을 위한 레거시 복제 전략

 

Consistency Levels

Cassandra는 eventually consistent하기 때문에 발생한 개념

client에서 read, write 쿼리에 consistency level 설정이 가능 -> cassandra의 consistency는 조정가능한 속성

쿼리 결과를 return하기 전에 응답해야 하는 replica node 개수를 consistency level로 설정한다. (ONE, TWO, THREE, QUORUM, ALL 등 각 level 당 자세한 설명은 9장에서 계속)

consistency level이 높을수록 더 많은 node가 쿼리에 응답하며, 각 replica에 있는 값들이 같음을 더 확실하게 보장한다.

 

strong consistency를 판단하는 공식 : Read + Write > Replication Factor

예를 들어, R=2, W=2일때 Replication Factor=3이면, Write시 적어도 2개의 replica에 썼기 때문에 하나가 복제가 안되어 있다하더라도,

R-Value가 2이기 때문에, read시 꼭 하나는 새로운 data가 읽어지게 되고, 새로운 data를 update하는 정책 때문에 항상 최신의 데이터를 읽을 수 있다.

 

Replication Factors과 Consistency Levels 비교

Replication Factors : keyspace 생성시 할당, write 발생마다 값을 저장하는데 사용할 노드 수

Consistency Levels : query당 할당, client 측에서 확신을 가질 수 있다고 판단한 응답 노드 수

 

Queries and Coordinator Nodes

실제로 client에서 query를 요청할 때 일어나는 동작을 살펴본다.

Coordinator 노드 : client의 요청을 받게 되는 최초의 노드

write 쿼리 발생 시 : consistency level과 replication factor에 따라 replica와 통신 후 성공 판단

read 쿼리 발생 시 : coordinator 노드에 응답한 replica 개수가 consistency level을 충족시켰을 때 client로 쿼리결과값을 return

 

 

위 상황은 매우 이상적인 시나리오로, 가용성을 위한 메카니즘을 살펴본다.

Hinted Handoff

write 쿼리 발생 시, write 대상 노드의 status가 정상이 아니라면 Coordinator 노드에서 hint를 생성한다.

write 대상 노드 status가 정상이 되면, Coordinator 노드는 “hint”에서 “hand off”하면서 완료되지 못한 write를 지시한다.

cassandra는 각 파티션마다 별도의 hint를 보유하고 있다.

hint는 consistency level이 "ANY"인 경우를 제외하고는 consistency level을 위한 write로 count되지 않는다. 

failed 노드 상태가 지속될시 다른 노드에 hint가 쌓여있다가 한꺼번에 처리되는 경우 대비하여 hint 저장시간을 제한하고 있다.

 

참고) Amazon’s Dynamo에서 사용되고 있으며 Java Message Service의  Guaranteed Delivery 과 비슷한 개념이다. 

Java Message Service : 메세지 전송 실패시 wait 후, resend 하는 원리

 

 

Anti-Entropy, Repair, and Merkle Trees

- anti-entropy 프로토콜 : gossip 프로토콜의 한 종류로, replica 간의 data 비교에 사용된다.

 

replica 동기화에는 read repair, anti-entropy repair 2가지 방법이 있다.

- read repair

read 쿼리 수행 시 consistency level의 수만큼 replica node를 읽는 과정에서 out-of-date data를 감지한다. 

감지 즉시 data를 update하거나, 쿼리값 return 후 백그라운드로 처리한다.

 

- anti-entropy repair (=manual repair)

12장에서 소개되는 nodetool을 실행하여 수동으로 동작시킨다.

anti-entropy 프로토콜을 사용하여 한 노드에서부터 모든 replica의 데이터를 비교하고 각 replica를 최신 버전으로 업데이트하는 프로세스

1. 각 replica에 대한 Merkle 트리 구축 (SSTable을 모두 읽기 때문에 cpu, memory, disk i/o, network inbound/outbound 모두 급격히 증가)
2. Merkle 트리를 비교하여 차이점 발견

Merkle 트리 : 상위 노드는 자식 노드의 해시 값으로 구성된 이진 트리

비교는 Merkle 트리의 최상위 노드에서 시작된다.

왼쪽 자식 노드로 진행하여 비교 한 다음 오른쪽 자식 노드를 비교한다. 

노드가 다른 것으로 확인되면 해당 노드 범위에 일관되지 않은 데이터가 존재하는 것으로 판단하여 해당 Merkle 트리 노드 아래의 잎에 해당하는 모든 데이터가 새 데이터로 대체된다.

- cassandra와 Dynamo 모두 anti-entropy에 Merkle 트리를 사용하나 구현방식은 약간 다르다.

  cassandra는 각 table마다 Merkel 트리를 가지며, 비교하는 동안만 스냅샷으로 생성되고 이웃 node에게 전달될 때까지만 유지되어 network I/O를 줄였다.

 

 

Lightweight Transactions(LWT) and Paxos

앞서 소개된 strong consistency 는 race condition 경쟁조건을 방지하는데 불충분하다.

읽기 및 쓰기 쿼리간에 다른 클라이언트가 들어오지 못하도록 보장하고자 한다.

 

- LWT : paxos 기반의 linearizable consistency(선형화된 일관성) 보장하는 메카니즘

 

- Paxos

분산 트랜잭션에 대한 전통적인 two-phased commit 기반 접근 방식의 대안으로 등장

Paxos는 리더가 거래를 조정하지 않고도 분산된 피어 노드가 제안에 동의 할 수 있도록하는 합의 알고리즘

data를 변경하기 위해 coordinator node가 리더 역할을 하며 replica nodes에 새로운 값은 제시한다.

각 replica 노드는 제안을 확인하고 제안이 최근에 본 제안 인 경우 그보다 이전 제안은 수락하지 않을 것을 약속한다.

각 replica 노드는 수신한 마지막 제안 (아직 진행중인 제안)을 반환한다.

제안이 대다수의 replica에 의해 승인되면 리더는 제안을 커밋하지만 먼저 진행중인 제안을 있다면 그것을 먼저 커밋해야한다는 점에 주의해야 한다.

1. Prepare/Promise

2. Read/Results

3. Propose/Accept

4. Commit/Ack

Coordinator 노드와 replica 노드 사이에 4번의 round-trip이 발생한다. 이것은 고비용이므로 신중하게 LWT를 적용해야 한다.

싱글 파티션에 제한되므로 파티션간의 간섭도 발생하지 않는다. LWT는 chapter 9장에서 더 자세히 다룰 것이다.

 

참고) two-phased commit 단점 : prepare/commit 2단계 commit. 가용성의 손실과 부분실패시 높은 지연을 야기한다.

 

Memtables, SSTables, and Commit Logs

이제 노드 내부를 살펴본다. cassandra는 고성능, 영속성을 위해 data를 memory와 disk에 저장한다.

- Commit log

wirte 요청을 받은 노드는 혹시 모를 장애를 대비하여 data를 commit log라는 로컬 disk file에 저장한다. 그 후에 successful write이 count 된다.

노드에 장애가 발생하더라도 정상복구 후 commit log가 replay 된다.

각 commit log 에는 flag bit으로 data의 flush 여부를 저장하며 commit log가 limit size가 되면 rollover 된다.

> durable_writes : 해당 keyspace의 commit log 사용여부를 설정하는 변수

 

- Memtables

data는 commit log에 저장된 후, memory 영역의 memtables에 저장된다. 또는 memory caching에도 쓰여진다.

 

- SSTable

MemTable에 data가 충분히 쌓이면 노드는 disk 버전의 MemTable인 SSTable에 data를 flush한다.

이 작업은 nonblocking이며 여러 개의 memtable이 존재할 수 있다.

SSTable은 immutable하며, sequential하다는 특징을 가지고 있으며 Cassandra는 이러한 다수의 SSTable을 Compaction하여 데이터를 관리한다.

Google Bigtable의 "Sorted String Table"에서 유래되었으나, string 형식으로 저장하지는 않는다.

 

 

read 요청 수행 시에는 SSTables, memtables 를 읽어 data를 찾는다. (memtable은 아직 flush 되지 않은 경우를 고려)

다음으로, read 성능향상을 위한 메카니즘을 살펴본다.

 

 

Bloom Filters

read 성능향상을 위해 key를 hashing하는 방법으로 SSTable과 짝지어 사용한다.

read 쿼리 수행시 바로 disk로 가지 않고 Bloom filter를 통하여 해당 SSTable에 데이터가 존재하는지를 확인한다.

Bloom Filter : 긍정오류는 발생할 수 있지만, 부정오류는 발생하지 않는 확률적인 자료구조로, 없는 걸 있다고 거짓말 할 수는 있지만, 있는 걸 없다고 거짓말 하지는 않는다는 것 => 업다는 것은 정말 없다는 것

bloom filter 정확도는 filter size(memory 비용)와 정비례한다.

Apache Hadoop, Google Bigtable, Squid proxy cache 등 널리 사용된다.

 

 

Caching

- key cache : JVM heap에 저장되며 partition key를 row index에 매핑한 것으로 SSTable로의 빠른 접근을 도운다.

- row cache : off-heap memory에 저장되며 전체 rows를 캐싱한다.

- chunk cache :  off-heap memory에 저장되며 3.6 버전에 추가되었다.  자주 access 되는 SSTable chunk를 압축되지 않은 형태로 캐싱한다.

- counter cache : 2.1 버전에 추가되었다. 가장 자주 액세스하는 카운터에 대한 lock 경합을 줄여 성능을 향상시켰다.

default로 key, counter cache가 enable 되어 있으며, 자세한 cache 조율 방법은 13장에서 논의한다.

원하는 데이터가 여기 없다면 memtable, memtable에도 없다면 bloom filter 확인 단계로 넘어가 SStable에서 데이터를 찾게 된다.

- off-heap : EHcache에 의해 관리되지만 힙 외부에 저장되는 직렬화된 객체를 참조한다. Garbage Collector에 종속되지 않으며 메모리에서 관리되므로 heap 보다는 느리지만 disk 보다는 빠르다.

 

Compaction

SSTables의 immutable 속성은 cassandra write 성능에 큰 도움을 주었다.

빠른 read 성능과 오래된 data 정리를 위하여 주기적인 compaction이 일어난다. 그러나, Compaction을 하는 동안에는 disk 공간과 disk I/O를 일시적으로 많이 사용한다.

- compaction

SSTables가 merge 되면서 key가 merge, column이 경합, 사용되지 않는 값 삭제, 새 index 생성되면서 new single SSTable가 생성되는 작업

새로운 SSTable이 merge가 끝나서 만들어졌을 때, 원본 SSTable 들은 더 이상 쓰지 않는다고 표시되고, 나중에 JVM garbage collection(GC) 프로세스에 의해서 제거된다.

 

compaction 전략 3가지 - 13장에서 더 자세히 다룰 예정

- SizeTieredCompactionStrategy(default) : write-intensive tables용

- LeveledCompactionStrategy : read-intensive tables용

- TimeWindowCompactionStrategy : 날짜기반 데이터용

 

- Major(Full) Compaction : 여러 SSTable을 하나의 SSTable로 합치는 administrative operations. 오래된 데이터를 지우는 cassandra 기능을 제한하는 경향이 있어 사용하지 않는 것을 권장한다.

 

- Log Structured Merge Trees

cassandra storage engine의 기본 디자인이다.

Update에 대해 Update-in-Place가 아닌 Append 방식으로 수행한다. 분산된 Record들에 대해 "Position을 찾은 후 Update 하는 과정"을 제거함으로서 Write 성능을 개선했다.

읽기는 좀 느릴 수 있으나 Bloom filter와 SSTable indexes로 개선할 수 있다.

 

Deletion and Tombstones

data delete가 일어나는 경우를 알아보자

마찬가지로 노드 status가 정상이 아닌 경우 다시 복구되어도 그 노드는 delete 작업을 놓치고 다른 노드들과 re-sharing 할 수 있다.

tombstone : delete가 수행될 때 바로 data가 삭제되는 것이 아니라 삭제예정 데이터로 update한다.

자체 expiration data/time을 가지며, 기간이 만기되면 주기적인 Garbage Collection이나  SSTable의 Compaction 등의 이벤트가 발생할때 데이터가 삭제된다.

 

참고

1. 자료 출처 :  www.datastax.com/resources/ebook/oreilly-cassandra-definitive-guide
2. https://docs.datastax.com/en/archived/cassandra/2.0/cassandra/architecture/architectureDataDistributeDistribute_c.html
3. https://meetup.toast.com/posts/60
4. https://knight76.tistory.com/entry/cassandra-node-repair-%EC%B2%98%EB%A6%AC-%EB%B0%A9%EC%8B%9D