Cassandra 기본

카산드라를 database로 사용하면서 공부한 내용을 기록해보고자 합니다. 주 목적은 카산드라가 어떻게 데이터를 디스크에 저장하고 읽는지 살펴보고 그 과정에서 들었던 의문을 기록하기 위함입니다.

 

Write 과정

write 과정은 크게 4가지로 요약할 수 있습니다.

• commit log에 데이터 로깅
• memtable에 데이터 쓰기
• memtable로 부터 데이터 flushing
• SSTables를 통해 disk에 데이터 저장

Commit log에 데이터 로깅

commit log는 디스크 영역에 존재하며 append-only한 특징을 가집니다. commit log에 카산드라 모든 노드에 대한 변경 내역을 적습니다. 그래서 write 요청이 들어오면 commit log에 먼저 데이터가 기록됩니다. 디스크 영역의 commit log에 변경사항을 적는 과정은 shutdown 시 데이터의 durability를 보장합니다. 만약 cassandra가 재시작되면 commit log 내 변경사항들이 memtable에 반영됩니다. 

모든 mutations는 commit log segments에 쓰기 최적화되어 저장하여 디스크에 쓰는 데 필요한 seek 수를 줄입니다. commitlog_segment_size 를 통해 segments 최대 사이즈를 지정할 수 있으며, 새 segment를 만드는 기준이 됩니다. segments는 카산드라가 SSTable의 특정 포인트보다 오래된 데이터를 기록했을 때 잘려집니다.

Memtable에 데이터 쓰기

카산드라 in-memory 자료구조인 Memtable 에 데이터를 저장합니다. (on-heap 또는 부분적 off-heap) 카산드라는 commit log 작성 이후 데이터를 Memtable에 저장하게 됩니다. 즉, write-back 캐시라고 할 수 있습니다. 카산드라 노드는 memtable에 작성되면 비로소 쓰기가 성공했다고 판단합니다. 

• memtable이 초기화 된다면?
  • commit log로 복구
• 노드가 shut down 된다면?
  • rf(replication factor)만큼 데이터가 다른 노드에 복제되었을 것이니 repair로 복구 가능하므로 eventual consistency함.

보통 memtable는 테이블 당 하나이며, write buffer입니다. 디스크에 데이터를 쓰는것이 아닌 memory에 쓰기에 Cassandra의 쓰기작업이 빨라질 수 있었습니다. 여기에서 MySQL같은 RDBMS와 비교하자면, MySQL은 쓰기 작업시 search 를 먼저 요구하므로 cassandra에 비해 write 성능이 떨어질 수 있습니다.

Memtable로 부터 데이터 flushing

데이터를 flush 할 때 카산드라는 데이터를 정렬된 memtable 순서대로 디스크에 씁니다. 이렇게 disk에 flush되면 불변의 SSTables가 됩니다. 이러한 flush 작업은 여러 이유로 수행됩니다.

1. memtable의 메모리 사용량이 구성된 threshold를 초과할 때 (memtable_cleanup_threshold)
2. commit-log가 최대 사이즈에 도달해 commit-log segments가 해제되도록 memtable flush를 강제할 때

1번 상황에서는 다음 flush가 성공할 때까지 카산드라가 쓰기 작업을 block 합니다. commit-log의 데이터는 memtable의 해당 데이터가 SSTable로 flush된 후 제거됩니다. 그래서 2번의 경우에 flush를 진행하는 것으로 추측합니다(개인적인 추측).

SSTables를 통해 disk에 데이터 저장

Memtable과 SSTable은 table 단위로 관리됩니다. 이와달리 commit log는 테이블들 사이에서 공유됩니다. SSTables는 immutable하여 flush과정 이후에는 쓰기가 불가능합니다. 따라서 partition은 일반적으로 여러 SSTables 파일에 걸쳐 저장되며 읽기 작업을 위해 SSTable 구조를 다음과 같이 생성합니다.

Data.db	SSTable의 기본 데이터
Index.db	데이터 파일의 위치에 대한 포인터가 있는 row key의 index
Summary.db	SSTable Index Summary 보유 (memory에 저장된 partition index sample)
Filter.db	SSTable에 액세스하기 전 memtable에 row data가 있는지 확인하는 메모리(off heap)에 저장된 구조(bloom filter)
CompressionInfo.db	압축되지 않은 데이터 길이, chunk offsets 및 기타 압축 정보에 대한 정보가 들어있는 파일
Statistics.db	SSTable 내용에 대한 통계 metadata
Digest.crc32	데이터 파일 size_bytes의 CRC32 체크섬?보유
CRC.db	압축되지 않은 파일의 chunk에 대한 CRC32 보유
TOC.txt	Table of Contents. SSTable에 대한 모든 구성요소 목록을 저장.

Cassandra Storage

Bloom Filter 자료구조

Cassandra는 읽기 경로에서 memtables의 데이터(RAM)와 SSTables의 데이터(Disk)를 합칩니다. 요청되는 partition에 대한 모든 SSTable 데이터 파일 확인을 피하기 위해 Bloom Filter라는 자료 구조를 사용합니다.

Bloom Filter는 2가지 가능성 중 하나를 택할 수 있습니다. 1. 데이터가 지정된 파일에 확실하게 존재하지 않거나, 2. 데이터가 지정된 파일에 존재할 수 있다.(false positive) 즉, SSTable에 데이터가 존재한다고 보장할 수는 없지만, 더 많은 RAM을 소비하면 정확해 집니다.

Bloom Filter는 여러개의 서로다른 해시 함수를 사용하며, 원소를 추가할 때 k가지 해시 값을 계산 후 각 해시 값에 대응하는 비트를 1로 설정합니다. 그 후 검사시 해당 원소에 대해 k가지 해시 값을 계산한 후 각 해시 값에 대응하는 비트 값을 읽습니다. 모든 비트가 1인 경우 존재한다 판단하며, 나머지는 존재하지 않는다고 판단합니다. 

Bloom filter - Wikipedia

이를 통해 SSTable에 key가 있는지 확인하는 작업이 유발하는 Disk IO 작업을 줄일 수 있습니다. Bloom Filter는 key를 여러 해쉬값으로 지정해 버킷 저장소에 저장합니다. 그래서 버킷을 활용해 key가 존재하는지 확인합니다. Cassandra는 Filter.db 파일에 Bloom filter를 저장하며 직렬화해 저장(Offheap에 위치)합니다.

Row Cache

Row Cache도 Off-Heap에 존재합니다. Read시 Row Cache, Partition key Cache가 활성화되어있다면, row cache를 먼저 체크한 뒤 없다면 Partition key cache가 disk 탐색을 더 효율적으로 만드는 hit을 제공합니다. Row Cache에 요청한 row가 존재한다면 disk seek 없이 반환합니다. row cache에 없고 partition key cache에 존재한다면 SSTable의 row에 접근한 후 데이터를 반환하고 row cache에 올립니다. 

Index (Partition Index File)

인덱스는 Disk에 저장됩니다. Cassandra는 partition key의 해시값으로 데이터를 분산시켜 저장할 것이고, 그에 따라 다른 column을 기준으로 데이터를 찾으려하면 많은 노드들을 방문해 데이터를 모아야할 것입니다. 따라서, 이러한 문제를 피하기 위해 각 노드는 자체 데이터를 인덱싱해 가지고 있습니다. 

Partition summary에서 partiton key의 range를 찾고, 원하는 partition key의 위치를 찾기 위해 partition index를 찾습니다. 첫번째탐색은 partition key의 위치를 탐색할 때 수행됩니다. range로 순차적 column 읽기가 수행되고, 그 정보로 Partition Index는 compression offset map으로 이동해 데이터가 있는 디스크에서 compressed block을 찾습니다. partition index를 검색해야할 경우, 원하는 데이터를 찾기 위해 2 번의 디스크 검색이 필요합니다.

 

Partition Summary

Partition Summary는 off-heap에 존재하는 구조로 partition index의 샘플을 저장합니다. Partition index가 모든 partition key들을 포함하는 반면에 partition summary는 X개의 키를 샘플링하고 인덱스 파일에서 모든 X번째 키의 위치를 맵핑합니다. 20개의 키를 샘플링한다고 예시를 들어보면, 1~20번까지의 key의 SSTable에서의 위치를 저장할 것입니다. partition data 위치를 찾기 위한 검색을 단축하는 데 사용되며 가능한 partition key 값의 범위를 찾은 뒤 partition index가 검색됩니다.

Compression offset map

Compression offset map은 partition data의 정확한 디스크 위치에 대한 포인터 정보를 저장하고 있습니다. 이 정보는 off-heap에 존재하며 partition key cache 혹은 partition index를 통해 접근됩니다. 디스크 위치를 식별한 뒤에는 원하는 압축된 partition data가 알맞은 SSTable들로부터 가져와지고, 결과 집합을 수신할 수 있습니다.

Hints

Hinting은 쓰기 작업 중 수행되는 data repair 기술입니다. 복제 노드가 mutation 작업에 대해 unavailable 상태라면, coordinators는 복제 데이터를 각자 local 파일시스템의 임시 hints에 저장합니다. Hints는 데이터 불일치 기간을 줄이는데 도움이 되는 중요한 방법입니다. Coordinators는 replica nodes가 ring에 복귀하면 hints를 빠르게 replay합니다. 하지만 Hints도 결국 eventual consistency를 완벽히 보장하진 않습니다. 

Hinted Handoff

Hinted Handoff는 카산드라가 unavailable 노드들에 hint를 적용하는 프로세스를 말합니다. 

보통, RF가 3이면 Coordinator가 mutation을 수신해 3 개의 replicas에 보냅니다. 만약 replica node가 unavailable 상태면 coordinator 노드가 hint를 파일시스템에 저장 후 3h(max_hint_windowwin_ms) 동안 유지합니다. 3h 내에 노드가 복구되면 coordinator 노드는 복제본에 대한 hinted mutations들을 적용해 eventual consistency가 유지되도록 합니다. 즉, 노드가 3h 내에 돌아오지 않는다면 read-repair나 full/incremental anti-entropy repair가 mutation을 전파할 때 까지 대상 복제본이 동기화되지 않게 됩니다.

Read Repair 과정

카산드라는 read 요청 중 data replicas를 repair하는 프로세스를 수행합니다. read consistency level에서 읽기 요청과 관련된 모든 replicas가 일치하면 바로 클라이언트에 데이터가 반환되며 read repair는 수행되지 않습니다. 그러나, replicas가 consistent하지 않다면 읽기 요청에 관련된 replicas를 일관되게 만들기 위한 read repair가 수행되며 가장 최신 데이터가 클라이언트에 반환됩니다. read-repair는 foreground에서 수행되며 read-repair가 끝나기 전까지는 클라이언트에 반환되지 않는 blocking 작업입니다.

Coordinator 노드는 Read consistency level이 2일 경우 2개 노드에서 반환된 full data로부터 hash 값을 구해 비교합니다. hash 값이 다를 경우 read repair가 수행됩니다. 두 복제본의 데이터를 비교한 뒤 timestamp를 기준으로 가장 최근의 복제본이 선택됩니다. 하나의 복제본에 일부 columns에 대한 데이터만 있는 경우 데이터의 최신 복사본을 구성하기 위해 데이터를 병합해야 할 수도 있습니다. 

위의 그림처럼 RF가 3이고 read consistency level이 2일 경우 Replica2는 Replica3과 read repair작업으로 동일한 복제본을 공유하지만, Replica1은 읽혀지지않았을뿐더러 repair도 되지 않았습니다. 

Cassandra 4.0에서 Read Repair

Cassandra 4.0은 완전한 데이터 응답이 수신되지 않을 경우, read repair 중에 full read 요청을 보내는 데 추측성 재시도를  사용합니다. 추측성 재시도를 통해, 카산드라가 메시지를 보낸 초기 복제본 집합에서 응답을  받지 못할 수 있다고 판단되면, 추가 읽기 요청을 다른 복제본에 추측적으로 보냅니다.

Consistency level을 만족하기 위해 Full Data 응답만 Block합니다. 카산드라 4.0은 추측성 재시도든 read repair 기회든 상관없이 digest 불일치를 해결하는데 필요한 항목만 차단하고 일관성 수준을 충족하도록 충분한 전체 데이터 응답을 기다립니다. 만약 첫 접촉한 노드들에게 충분한 full data 읽기응답을 받지 못하면 새로운 노드에 접근하게 되고, 만약 노드 집합이 full data를 만들어내게 되면 read-repair가 진행되고있는 노드는 고려되지 않고 응답에서 제외됩니다. 

 

Cassandra Data Distribution

Cassandra 클러스터는 데이터 센터에 설치된 랙에 배치된 노드의 링 구조로 구성됩니다. virtual nodes 인 vnodes는 데이터 오너쉽을 실제 물리 머신에 할당합니다. 데이터를 분배하기 위해 consistent hashing 기술을 사용하여 각 노드가 여러 개의 작은 partition range(vnodes)를 소유합니다.

partitioner는 토큰을 생성하기 위해 partition key를 해싱하는 함수이며, 이 토큰 값은 row를 나타내고, 노드에 속하는 partition range를 식별할 때 사용됩니다.

Cassandra의 primary key는 1개 이상의 partition keys와 0개 이상의 clustering key로 이루어져 있습니다. 데이터를 고유하게 만드는 것 외에도 primary key의 partition key 요소는 데이터 배치에 중요한 역할을 하여 여러 노드에 분산된 데이터 읽기 및 쓰기 성능을 향상시킵니다.

Partition key

partition key는 데이터를 클러스터에 균등하게 분산하고 데이터를 효율적으로 쿼리하려는 목적입니다.

PRIMARY KEY (test_id)

위 처럼 PRIMARY KEY를 지정한다면, test_id가 partition key가 되며 카산드라는 consistent hashing을 사용해 hash 값을 구해 row data를 node의 partition range에 할당합니다. CQL로 read시 WHERE절에 partition key를 작성해주면 consistent hashing 기법으로 빠르게 정확한 노드와 partition range를 식별할 수 있습니다.

PRIMARY KEY ((test_id_1, test_id_2))

위와 같이 분산된 효율적인 데이터 배치를 위해 2개 이상의 column value로 구성된 composite partition key를 지정할 수 있습니다.

데이터를 효율적으로 검색하려면 select 쿼리의 where 절에 primary key 정의에 지정된 순서대로 모든 composite partition keys가 포함되어야 합니다.

Clustering Key

partitioning은 데이터가 배치되는 노드 내에서 partition range를 식별하는 프로세스이고, 이와 달리 clustering은 partition 내에서 데이터를 정렬하는 storage engine 프로세스이며 clustering key로 정의된 columns 기반입니다.

partition 내의 모든 데이터는 clustering key columns에 의해 정렬되어 storage에 연속적으로 저장되므로 결과적으로 정렬된 데이터 검색은 매우 효율적입니다.

PRIMARY KEY ((test_id_1, test_id_2), sort_key_1, sort_key_2)

위에서 clustering key는 sort_key_1과 sort_key_2입니다. 카산드라 스토리지 엔진은 partition 내에 sort_key_1과 sort_key_2에 따라 로그를 어휘적으로 정렬합니다. 기본적으로 데이터를 clustering key의 오름차순으로 정렬하지만 정렬 순서 제어도 가능합니다.

마찬가지로 where 절에 primary key 절에 정의된 것과 동일한 순서로 colums가 포함되어야 합니다.

위에서도 언급했듯이 디스크에 연속적으로 데이터가 저장되기에 search시 랜덤 액세스가 줄어들어 검색 속도가 빨라집니다. 물론, order by도 clustering order에 따라 정렬이 필요한 경우에는 필요없는 절이 됩니다.

 

Gossip

노드가 다른 노드와 주기적으로 상태 정보를 교환하는 P2P 통신 프로토콜입니다. Cassandra 노드끼리 1초마다 Gossip 프로세스가 수행되며 최대 3개의 다른 노드와 상태를 교환합니다. Gossip 메시지에는 version이 있으므로 gossip 교환 중에 특정 노드에 대한 최신 상태로 다른 정보를 덮어씁니다. 가십을 통해 노드 장애를 감지할 수 있으며 클러스터에 새 노드로 조인할 때에도 seed node와 새 노드에 대한 Gossip 프로세스를 bootstrap합니다. 

여기서 seed node란 새로운 노드가 클러스터에 조인할 때 방장과 같은 역할을 한다고 생각하면 됩니다. seed node로 지정된 노드는 새 노드가 조인할 때 클러스터의 기준이 되며 seed node 장애로 존재하지 않게 되면 기존 클러스터에 조인하지 못합니다. 그래서, dc당 seed node가 최소 3개로 지정되어 있습니다.

 

Snitch

Snitch는 어떤 데이터 센터와 랙에 노드가 속해 있는지 결정합니다. snitch는 카산드라에게 network topology에 대해 알려 요청이 효율적으로 라우팅되고 카산드라가 machine(?물리장비를 말하는 듯)을 데이터 센터 및 랙으로 그룹화하여 replica를 배치할 수 있게합니다.

특히 replication 전략은 새 snitch가 제공한 정보를 기반으로 복제본을 배치합니다. 따라서 모든 노드는 동일한 rack, datacenter로 돌아가야 하고 카산드라는 동일한 rack에 둘 이상의 복제본을 가지고 있지 않도록 최선을 다합니다.(물리적 위치는 아님)

 

Cassandra의 Streaming이 빠른 이유

SSTable Repair 과정이나 Bootstrapping 과정, 혹은 node를 추가하면서 Cluster를 확장시킬 때 Streaming이 매우 빠르게 동작한다는 것을 느꼈습니다. 이를 가능하게 하는 구현이 궁금하여 찾아본 내용을 기록합니다. Streaming이 수행될 경우는 다음과 같습니다.

• SSTable Repair
• Host Replacement
• Range movements
• Bootstrapping
• Rebuild
• Cluster expansion

Streaming based on Netty

카산드라 4.0부터 Streaming은 Netty로 Non-blocking I/O를 기반으로 동작합니다. 싱글 스레드, synchronous, blocking 모델의 streaming이 대체되었습니다. Netty는 여러 connections이 동시에 열리는 non-blocking, asynchronous, multi-threaded 스트리밍을 지원합니다. Non-blocking으로 스레드가 전송된 요청을 기다리지 않으므로 스레드가 blocked 되지 않고 응답이 다른 스레드에서 반환될 수 있습니다. asynchronous로 커넥션과 스레드들이 1:1 관계로 엮이지 않고 분리되며 스레드에 비해 커넥션이 여러개 더 열릴 수 있습니다. 

Zero Copy Streaming

4.0 이전에는 SSTables를 객체화해 불필요한 garbage가 생성되고일부 SSTables은 개별 partition이 아닌 전체 파일로 streaming될 수 있기에 전체 Streaming 프로세스가 느려졌습니다.

4.0 부터는 Zero Copy API를 사용해 전체 SSTables를 가능한 빨리 streaming할 수 있게 지원합니다. zero-copy는 sending, receiving 측 모두 user-space로 데이터를 가져오는 것을 방지(즉, context switching X)합니다. 이로써 Zero Copy streaming 성능은 하드웨어(Network, Disk IO)에 의해서만 제한됩니다.

 

Zero copy가 없었을 경우 디스크에서 파일 컨텐츠를 읽어 네트워크 소켓으로 데이터를 전송하므로 (Kernel <-> User space)의 컨텍스트 스위칭과 Data 복사가 불필요하게 빈번하게 일어나게 됩니다. 

Traditional data copying approach

Traditional context switches

Zero Copy로 다음과 같은 효과를 볼 수 있습니다.

사용자가 파일 전송을 요청하면 DMA 엔진이 디스크에서 파일을 읽어 kernel context에 위치한 Read buffer로 데이터를 복사한 뒤 바로 Socket buffer로 데이터를 복사하고 DMA 엔진을 통해 NIC buffer로 복사되어 데이터를 전송합니다.

Data copy with transferTo()

Context switching with transferTo()

여기에서 Read buffer의 데이터를 Socket buffer로 복사하지 않고 데이터 위치, 길이에 대한 정보가 있는 descriptors만 socket buffer에 추가 합니다. 그럼 DMA 엔진이 데이터를 즉시 kernel buffer로부터 protocol engine으로 이동시키며 cpu copy 절차가 없어지는 개선 구조가 완성됩니다.

Data copies when transferTo() and gather operations are used

참고자료

cassandra 공식문서

https://www.datastax.com/ko/blog/we-shall-have-order

We Shall Have Order! | Datastax

https://cassandra.apache.org/doc/latest/cassandra/new/streaming.html

Improved Streaming | Apache Cassandra Documentation