Cassandra(카산드라) 내부 구조

Cassnadra internal

Posted by nicewoong on February 11, 2018

Cassandra 내부적으로 Read / Write 는 어떻게 작동하는지 알아보자.


  • 칼럼 단위로 TimeStamp가 있다는 걸 인지하고 시작합시다. 
     {
  name: "userName",
  value: "Dave Jones",
  timestamp: 125555555 
 }



Storage Engine

  • 일반적인 DB에서 쓰이는 B-Tree 대신 Cassandra 에서는 Log-Structured Merge Tree (LSM Tree) 를 사용한다.


Log-Structured Merge Tree (LSM Tree)

  • 주로 RDBMS에서 사용 되고 있는 B+Tree와 비교해서 쓰기(Write) 성능이 우수하다는 특징을 가지고 있다.
  • 현대의 Store에 많이 사용되는 자료구조 (BigTable, Cassandra, HBase, Riak, … )
  • MemTable, SSTable, Commit Log라는 3개의 저장 공간을 사용


SSTable(Sorted String Table)

  • MemTable이 가득 차게 되면, 디스크에 SSTable을 생성
  • 변하지 않는(immutable) 파일
  • 내부 데이터는 key를 기준으로 정렬 되어짐
  • Index block을 배치하여 원하는 block을 이진탐색으로 검색
  • Bloomfilter 지원
  • 여러 SSTable을 합(compaction) 할 수 있음


Bloomfilter 란?

  • (참고) - Bloomfilter 란?(Naver D2 블로그)
  • (참고) - Bloom Filter 개요(개인 블로그 글)
  • Bloom Filter는 어떤 원소 bloomfilter2가 어떤 집합 bloomfilter1의 원소인지 확률적으로 판단하는 표시함수 이다.
  • 그러나 Bloom Filter를 이용하여 어떤 원소 bloomfilter2에 대한 membership query를 수행했을 때, 수행 결과가 ‘참’이라고 해도, 반드시 bloomfilter2가 bloomfilter1에 포함되는 것은 아니다(false positive).
  • (false positive).
    • 없다고 하면 확실히 없는 것, 있다고 하면 있을 수도 있고 없을 수도 있다.
    • (참고: false positive : 없는데 있다고 하는 것. false negative : 있는데 없다고 하는 것. )
  • 그러나 false positive가 발생하는 경우 데이터베이스를 조회하여 데이터 존재 여부(원소 포함 여부)를 판단할 수 있기 때문에, 시스템 전체적으로는 항상 정해를 도출할 수 있습니다.
  • 이런 특성 때문에 Bloom Filter는 단독으로 사용하는 것보다는 확률적인 방법이 아닌 다른 방법을 보조하는 역할로 사용하는 것이 적합

  • Bloom Filter의 주목적은 ‘데이터베이스가, 원소(키)가 존재하지 않는다는 것을 파악하는 데 소모되는 자원의 낭비를 줄이는 것’이다.

  • 간략 내용
    • bit배열 V가 있다. (0 ~ m-1까지의 index를 가진다)
    • A라는 데이터가 있다
    • 여러개(k개)의 hash함수가 있다.
    • A라는 데이터를 k개의 hash 함수에 의해 나오는 k개의 결과가 bit배열 V의 index가 된다.
    • hash를 통해 나오는 결과는 0 ~ (m-1) 까지의 숫자가 되겠다.
    • bit배열 V에서 해당 index에 맞는 자리에 비트가 1로 지정된다.
    • 추후 데이터 A가 있는지 검사하기 위해 k개의 hash함수를 통과시키고 나오는 결과 k개를 가지고 bit배열 V에 해당 index가 1인지 살펴본다.
    • 배열V의 index 자리 비트가 모두 1이라면 A라는 데이터가 존재한다. (true를 반환)
  • 많은 비트를 할당할수록 성능은 좋을 수 있으나 많은 메모리가 필요,
  • 해싱 함수를 늘리게 되면 연산이 많아지게 되어 성능은 느리나 메모리를 덜 차지하게 되는 trade-off 관계가 존재한다.


B-tree란?

  • 참고 - 자료구조 :: B-트리(블로그 포스팅)
  • Balanced Tree로 균형을 유지하는 트리를 말한다.
  • B 트리는 자식을 두개만 가질 수 잇는 Binary Search Tree 를 확장하여 더 많은 자식을 가질 수 있게 고안한 것
  • 오라클과 같은 상용 DB에서 많이 사용하는 자료구조
  • 외부 검색(주 저장장치인 메모리 외의 저장장치에서의 검색)에 유용하다.
  • Binary Tree같은 경우 한 쪽으로 치우치는 구조가 되면 연산의 시간복잡도가 O(NxLogN) 최악의경우 -> O(NxN) 이 나온다 (데이터가 Sorting되어 입력될 경우 밸런스가 안 맞음)
  • 하나의 노드가 여러 데이터를 가진다.
  • 한 노드에 최대 M개의 자료가 배치될 수 있으면 M차 B트리라고 한다.
  • 노드내의 데이터는 반드시 정렬된 상태여야 한다.
  • 노드의 데이터 왼쪽에 연결된 노드에 있는 모든 데이터는 더 작다. 오른쪽에 연결된 노드에 있는 모든 데이터는 더 크다.
  • 하나의 노드가 가지는 데이터 갯수가 많을 수록 트리의 높이가 낮아진다. 탐색 시간이 줄어든다.
  • 항상 O(logm N)의 성능을 보장한다



쓰기 구조 (How is data written)

  • Coordinator 노드 : 요청을 받게 되는 최초의 노드
    • (참고) - http://meetup.toast.com/posts/60
    • Coordinator는 해당 데이터의 Row key를 hashing하여 어느 노드들에 데이터를 Write해야 하는지 확인합니다.
    • 해당 쿼리에 지정된 Consistency Level에 따라 몇 개의 노드에 Write해야하는지 참고하여 현재의 데이터를 Write해야 할 노드들의 status가 정상인지를 확인
    • 특정 노드의 status가 정상이 아니라면 Consistency Level에 따라 hint hand off라는 로컬 임시 저장공간에 Write 할 데이터를 저장
    • hint hand off에 데이터를 백업했다면, Coordinator 노드는 Cassandra의 topology를 확인하여 어느 데이터 센터의 어느 렉에 있는 노드에 먼저 접근 할 것인지 결정하여 데이터와 함께 Write를 요청
  • 실제로 데이터 저장하게 될 노드 내에서는,
    • Write 요청이 오면 혹시 모를 장애에 대비하여, CommitLog라고 불리는 로컬 디스크의 파일에 기록
    • 그 다음 MemTable이라는 이름의 메모리 저장공간에 데이터를 Write한 뒤, 성공 메시지를 돌려줌으로써 Write 요청에 대한 동작은 마무리
    • (MemTable은 임시저장공간입니다.)
    • MemTable에 데이터가 충분히 쌓이면 디스크 버전의 MemTable이라고 할 수 있는 SSTable에 데이터를 Flush합니다.
    • (SSTable은 Immutable 합니다.)
  • 공식 Document (Datastax)


Logging writes and memtable storage

  • 카산드라는 write 할 때 Memtable 이라는 memory structure에 저장한다.
  • 그리고 configurable durability 를 제고하기위해 disk 의 commit log 에 write operation을 추가한다.
  • commit log 는 카산드라 노드에 요청되는 모든 write을 기록한다.
  • 이 durable writes 는 전원이 다운되더라도 영구적으로 유지된다.
  • The memtable is a write-back cache of data partitions that Cassandra looks up by key.
  • Memtable은 (configurable) limit에 달할때 까지 writes이 정렬되어 저장된다.
  • limit에 꽉차면 SSTable로 flushed된다.
  • (참고) - Write back / Write through cache
  • Wirte-Through는 cache에 데이터를 쓰는 동시에 메모리에도 저장하는 방식 (안정적이지만 느리다)

  • Write-Back은 일단 cache만 데이터를 업데이트하고 추후 cache를 비워내면서 한 번에 메모리또는 디스크로 데이터를 저장한다. (빠르지만 무결성에 문제가 있을 위험).

  • (참고) - Durability
    • Durability 는 write이 완료되면 서버가 다운되더라도 영구적으로 유지되는 속성.
    • 이를 위한 방법은 매번 write이 일어날 때마다 permanent storage device 에 fsync 해주는 것인데, Physical Platter의 write location 에 쓰기 위해서는 disk가 random seek을 해야되기 때문에 매우 느리다. (각 seek 은 5-10ms 가 소요된다.)
    • 그래서 다른 modern system 과 마찬가지로 카산드라는, Commit log 에 먼저 write 을 추가하면서 Durability를 제공한다.
    • Commit log는 append only 이므로 seeking 이 필요없다.


Flushing data from the memtable

  • flush 과정에서 data가 Memtable에서 정렬된 그대로 (memtable-sorted order) disk에(SStable에) 쓰인다.
  • Token을 디스크의 위치에 매핑하는 partition index (디스크에 저장되는 자료구조) 도 함께 디스크에 생성된다.
  • 이 토큰을 말하는건지? - What-is-a-token-in-Cassandra
  • Commit log 공간이 설정한 용량을 초과하거나, memtable을 설정한 한계를 넘어서면 the memtable is put in a queue that is flushed to disk.
  • 커밋 로그(CommitLog)의 데이터는 memtable의 해당 데이터가 디스크의 SSTable로 플러시 된 후에 제거된다.


Storing data on disk in SSTables (Sorted String Table )

  • 테이블 마다 Memtables and SSTables가 유지된다.
  • Commit Log는 테이블간 공유된다.
  • SSTables는 변경 불가능하며, memtable이 플러시 된 후에 다시 쓰여지지 않습니다.
  • 결과적으로 Partition은 일반적으로 여러개의 SSTable에 저장된다.
  • 그리고 여러개의 Structure가 읽기(Read) 를 돕기 위해 존재한다.
    • 데이터 (Data.db): SSTable 데이터
    • Primary Index (Index.db) : 데이터 파일의 위치에 대한 포인터가있는 Row key 의 index
    • Bloom filter (Filter.db) : 디스크의 SSTables에 액세스하기 전에 Row데이터가 memtable(메모리)에 있는지 확인하는 메모리에 저장된 구조
    • Compression Information (CompressionInfo.db) : 압축되지 않은 데이터 길이, 청크 오프셋 및 기타 압축 정보에 대한 정보가 들어있는 파일
    • **Statistics (Statistics.db) **: SSTable의 내용에 대한 통계 메타 데이터
    • Digest (Digest.crc32, Digest.adler32, Digest.sha1) : 데이터 파일의 adler32 체크섬을 보관하는 파일
    • CRC (CRC.db); 압축되지 않은 파일에 청크 용 CRC32가 들어있는 파일입니다.
    • SSTable Index Summary (SUMMARY.db) : 메모리에 저장되어 있는 A sample of the partition index
    • SSTable Table of Contents (TOC.txt) : SSTable TOC의 모든 구성 요소 목록을 저장하는 파일
    • Secondary Index (SI_.*.db) : 기본 제공 보조 색인. SSTable 당 여러 개의 Secondary Index 가있을 수 있습니다.
  • SSTable은 디스크에 저장되는 File 이다.
  • data files은 data directory에 저장된다.
  • data directory 안에 Key-Space 마다 directory를 가지며 해당 directory에 각 table을 저장한다. 
    /data/data/keyspace1/table1-5be396077b811e3a3ab9dc4b9ac088d/la-1-big-Data.db
    • keyspace1 은 Keyspace name 이다.
    • A hexadecimal string, 5be396077b811e3a3ab9dc4b9ac088d in this example, is appended to table names to represent unique table IDs.
    • 카산드라는 각 테이블에 대하여 하위 디렉토리를 생성하여 [a chosen physical drive or data volume] 에 테이블을 Symlink할 수 있다.



데이터 유지(How is data maintained? )

  • 참고 - (Datastax, Compaction과정이 설명되어 있다. )
  • Write을 할 때 SSTables 라고 불리는 file에 데이터를 저장한다.
  • SSTables are immutable.
  • inserts or updates로 기존에 존재하는 row에 overwrite 하는 대신, 카산드라는 새로운 timestampe를 가지는 버전의 updated 데이터를 new SSTables에 추가한다.
  • 카산드라는 deleted 데이터를 제거하지 않고, Tombstone로 표시한다.
    • (Tombstone : A marker in a row that indicates a column was deleted. During compaction, marked columns are deleted.)
  • 이렇게 시간이 지남에 따라 카산드라는 여러 버전의 row를 추가하게 된다.
  • Each version may have a unique set of columns stored with a different timestamp.
  • SSTable이 누적될 때 마다, Complete row를 조회하기 위해서는 더 많은 SSTable에 분산된 데이터에 엑세스가 필요하다.
  • 데이터베이스를 정상적인 상태로 유지하기 위해 Cassandra는 주기적으로 SSTable을 병합하고 이전 데이터를 버립니다.
  • 이 프로세스를 Compaction 이라고합니다.


Compaction

  • Compaction은 ```SSTable`` 간에 일어납니다.
  • Compaction은 Unique Row에 대한 모든 version을 모두 모아서 하나의 Complete row로 assemble합니다.
  • 각 Row의 Column마다 갖고있는 timestamp를 이용해서 가장 최신버전의 것으로 말이죠.
  • merge process는 효율적입니다.
    • 왜냐면 각 row는 Partition key에 의해 각 SSTable에 정렬된 상태로 저장되어있고,
    • Merge 과정은 Random I/o를 사용하지 않기 때문이죠.
  • 이렇게 새로운 version의 Row가 조합되어 새로운 SSTable에 저장됩니다.
  • Old version의 row들은 old SSTable에 남아있고,
  • pending reads(이전에 요청되어 처리중인?대기중인? read 작업을 말하는 것 같음)가 완료되자마자 모두 삭제됩니다.
  • 이과정은 일시적으로 Disk space usage 와 disk I/O에 Spike를 발생시킵니다.

  • merge가 완료되자마자 old version의 SSTable 가 차지하던 공간을 확보합니다.

  • 모든 Compaction 과정이 끝나기 전이라도, Cassandra는 기다리지 않고 새로운 SSTable에서 read를 할 수 있습니다.
  • As Cassandra processes writes and reads, it replaces the old SSTables with new SSTables in the page cache
  • The process of caching the new SSTable, while directing reads away from the old one, is incremental it does not cause a the dramatic cache miss.



삭제 구조 (How is data deleted)

  • 카산드라는 delete를 insert로 간주합니다.
  • DELETE 명령어로 추가된 데이터는 Tombstone 이라고 불리는 deletion marker이다.
  • Write과 같은 방식으로 SSTable 에 추가된다.
  • tombstone은 Built-in expiration data/time을 가진다.
    • expiration 기간이 만기되면 SSTable의 Normal compaction process 과정에서 삭제된다.
  • Cassandra record(row또는 Column)를 TTL(time) value를 설정할 수 있다.
    • 지정해둔 시간이 끝나면 tombstone 마크가 record에 표시된다.
    • 이 역시 compaction과정에서 삭제된다.
  • 멀티노드 클러스터에서 카산드라는 replica를 다른 노드에 저장이 가능하다.
  • 이는 데이터 손실을 예방하지만, Delete를 복잡하게한다.



읽기 구조 (How is data read)

  • Read 요청이 들어오면 먼저 key 갑을 이용해서 생성된 Hash값을 기반으로 Cluster Ring 내에 데이터가 저장된 노드를 찾습니다.
  • 데이터를 해당 노드로부터 읽어옵니다.
  • 복제된 다른 노드로 부터도 데이타를 읽어 옵니다.
  • 각 레플리케이션에서 읽어온 값들을 비교합니다.
  • 그리고 그 값이 다르다면 최신 값을 반환해줍니다.
  • 노드 내에서는
    • MemTable에 데이터가 있으면 바로 리턴
    • MemTable에 없으면 디스크의 SSTable 을 확인
    • SSTable내의 Bloom Filter 에서 해당 데이터의 유무 정보를 얻을 수 있다.
    • Bloom Filter 가 해당 데이터의 존재를 알려주면 Index File 에서 그 위치를 얻고
    • Data File에서 해당 위치의 데이터를 읽어서 반환한다.

  • Read 요청에 대해 카산드라는 Active Memtable의 결과와 여러개의 SSTable(디스크)의 결과를 합칩니다.

  • Memtable부터 SSTable까지 몇 단계를 거쳐서 데이터를 읽는 과정을 거칩니다.
    • Memtable 을 먼저 체크합니다.
    • row cache를 확인합니다. (if enabled)
    • Bloom filter를 체크합니다.
    • partition key cache를 확인합니다.( if enabled)
    • partition key cache 에서 partition key를 찾으면 compression offset map으로 갑니다.
    • partition key를 못 찾았다면, partition summary(memory)를 확인해봅니다.
    • 그리고 나서 partition index(disk)를 거쳐서 compression offset map(memory) 으로 갑니다.
    • compression offset map을 이용해서 디스크에 데이터가 위치한 곳으로 접근합니다.
    • 해당 SSTable로부터 데이터를 리턴합니다.




각 컴포넌트에 대해 좀 더 자세히 알아보자.


memtable

  • memtable 에 데이터가 있으면 가져와서 SSTable에서 가져온 데이터와 merge된다.


Row Cache

  • Read는 대부분의 in-demand 데이터가 메모리에 위치할 때 가장 빠르다.
  • row cache는 95%의 load가 read 인 read-intensive operation에서 성능향상을 제공한다.
  • row cache가 enable 되어있을 경우 SSTable의 partition data의 일부분(subset)을 메모리에 저장합니다.
  • Off-heap에 저장되어 JVM의 garbage collection 의 관리대상이 아닙니다.
  • 캐쉬가 가득차면 Row Cache는 LRU (least-recently-used) Eviction을 수행하여 메모리공간을 확보합니다.
  • Row cache 사이즈와 row 갯수는 설정가능합니다
  • Row Cache가 enable 되어 있으면 원하는 데이터는 row cache로 부터 read 합니다.
  • Row cache에 저장되는 row는 자주 엑세스 되는 row입니다. SSTable에 엑세스 될 때 merge되어 저장된 것들 입니다.
  • 데이터가 row cache에 저장된 후, 이후의 쿼리에 의해 또 접근될 수 있습니다.
  • row cache는 write-through 가 아닙니다.
  • 해당 row에 대해서 write 요청이 들어오면 해당 row에 대한 cache는 유효하지 않습니다.
  • 그리고row가 다음 read가 될때까지 캐쉬되지 않습니다.
  • 마찬가지로 partition이 업데이트 되면 partion 전체가 cache에서 제거됩니다.
  • 원하는 데이터가 Row Cache에 없으면 bloom filter를 확인하는 단계가 진행됩니다.


Boom Filter

  • 먼저, Cassandra는 Bloom 필터를 검사하여 어떤 SSTables가 요청 데이터를 가질 가능성이 있는지를 확인합니다.
  • Boom Filter는 off-heap memory 에 저장됩니다.
  • 각각의 SSTable에 연관된 bloom filter가 있습니다.
  • Bloom 필터는 확률 적 기능이기 false positive 가 발생할 수 있습니다. (없는데 있다고 함)
  • If the Bloom filter does not rule out an SSTable, Cassandra checks the partition key cache


Partition Key Cache

  • Partition Key Cache 가 enable 되어 있으면 off-heap memory에 partition index를 캐쉬에 저장합니다.
  • Key Cache 는 작은 공간을 차지합니다.
  • Partition Key가 Partition Key Cache에 있으면 compression offset map 으로 바로 가서 데이터가 저장되있는 디스크 Compressed Block을 찾아봅니다.
  • Partition Key를 Partition Key Cache에서 못 찾으면 partition summary 로 갑니다.


Partition Summary

  • Partition Summary는 off-heap in-memory structure 입니다.
  • sampling of the partition index 를 저장합니다.
  • 디스크의 partition index는 모든 partition key를 포함하는 반면, Partition Summary는 모든 X key를 샘플링하고, X번째 key의 위치를 index file 에 매핑합니다.
  • 만약 Partion Summary가 every 20 keys를 샘플링하도록 설정되었다면, 첫 번째 키의 위치를 SSTable 파일의 시작부분으로 저장합니다. 그리고 20번째 key를 ….뭔소린지 모르겠따…
  • Partition key의 위치를 ​​아는 것만큼 정확하지는 않지만, Partition Summary는 데이터 위치를 찾기 위한 검색을 단축 할 수 있습니다.
  • 고정 된 양의 메모리는 index_summary_capacity_in_mb 를 사용하여 설정 할 수 있으며 Default는 힙 크기의 5 %입니다.


Partition Index

  • Partition Index 는 디스크에 있으며, Offset에 매핑되는 모든 Partition Key의 인덱스를 저장합니다.
  • 원하는 데이터의 인덱스를 찾으면 compression offset map 으로가서 디스크의 데이터가 저장된 compressed block 을 찾습니다.
  • 이렇게 Partition Index 를 거치는 경우 Disk Seek 이 두 번 일어나게 된다.


Compression offset map

  • Compression offset map 은 데이터가 저장되어있는 디스크의 정확한 위치를 저장하고 있습니다.
  • off-heap memory 에 저장되어 있습니다.
  • partition key cache 또는 the partition index 에 의해 엑세스 됩니다.
  • Compression offset map 에서 디스크의 정확한 위치를 찾으면 올바른 correct SSTable(s) 에서 원하는 데이터를 가져옵니다.
  • The compression offset map grows to 1-3 GB per terabyte compressed
  • compression offset map이 CPU리소스를 소모하더라도 Compression 은 Default로 enable 되어있다.
  • 이는 page cache 를 효율을 높인다.

Udate / Delete

  • SSTable 은 Immutable 하다.
  • 그래서 변경이나 삭제가 불가능
  • Delete의 경우 tombstom 이라는 marking 방식을 이용.
  • 해당 record에 Delete Mark를 True로 표기해서 insert한다.
  • 그럼 기존의 동일한 record도 남아있고, 해당 record랑 같은 값을 가지면서 Delete Mark 표시된 녀석이 또 하나 추가된 것.

  • timestamp를 보고 최신 것이 delete mark 가 돼있다면 해당 record는 삭제된 것으로 간주.

  • 그럼 이것들이 계속 쌓이는 건가!? 저장공간을 차지하는 건가?

  • Compaction
    • 카산드라는 두 개의 SSTable을 병합하면서 삭제된 레코드는 빼고 새로운 SSTable을 생성한다.
    • 이렇게 Compaction 후에는 Delete mark 가 표시된 record는 존재하지 않는다.
    • SSTable은 sort된 상태이기 때문에 병합이 빠르다고 한다.



참고