Cassandra

Cassandra 는 데이터를 서버 여러 대에 나눠 담아 한 대가 멈춰도 계속 읽고 쓰게 해 주는 데이터베이스입니다. 대표 서버를 두지 않아서 어느 서버에 물어도 답을 받습니다. 대신 방금 쓴 값이 모든 서버에 곧바로 보이지는 않습니다.

상세

Cassandra 는 서버 여러 대를 한 무리로 묶어 굴리는 분산 데이터베이스입니다. 내려받아 여러 대에 띄우면 그 대들이 서로 소식을 주고받습니다. 그렇게 한 덩어리처럼 움직입니다. 담는 것은 활동 기록, 시계열 측정값, 메시지 이력처럼 계속 쌓이고 한 대에 안 들어가는 데이터입니다.

설계는 앞서 나온 분산 저장소 둘에서 갈라져 나왔습니다. 데이터를 어느 서버에 두고 사본을 어떻게 맞출지는 Dynamo 에서, 디스크에 쌓아 두는 저장 방식은 Bigtable 에서 물려받았습니다.

여러 대에 나눠 담는 까닭

관계형 데이터베이스는 대개 한 대가 데이터를 전부 들고 있습니다. 데이터가 늘면 그 기계를 더 큰 것으로 바꿔 버팁니다. 한 대를 키우는 이 방법이 수직 확장입니다.

이 방법에는 끝이 있습니다. 제일 큰 기계에 안 들어가는 양이 되면 갈 곳이 없습니다.

그래서 여러 대에 나눠 담습니다. 나눠 담는 것이 샤딩입니다. 대수를 늘려 버티는 것이 수평 확장입니다.

나눠 담으면 이번에는 다른 문제가 생깁니다. 어느 데이터가 어느 대에 있는지 관리해야 합니다. 한 대가 죽으면 그 대가 맡은 데이터를 못 읽습니다.

Cassandra 는 이 관리를 제품 안에 넣어 둔 데이터베이스입니다. 데이터를 어느 대에 둘지 스스로 정합니다. 같은 데이터를 여러 대에 복사도 해 둡니다. 운영하는 사람은 서버를 몇 대 띄울지와 사본을 몇 벌 둘지를 정합니다.

데이터를 서버에 나눠 두는 방법

Cassandra 의 표에서 한 행은 파티션 키를 갖습니다. 파티션 키는 그 행을 어느 서버에 둘지 정하는 값입니다. 이 값을 해시 함수에 넣으면 숫자 하나가 나옵니다. 그 숫자가 토큰입니다.

서버 한 대를 노드라고 부릅니다. 노드들은 토큰이 가질 수 있는 범위를 잘라 나눠 갖습니다. 범위의 끝은 처음으로 이어져 원 모양이 됩니다. 이 원이 링입니다.

flowchart TD
    subgraph 링["링 · 토큰 0~99 를 노드 넷이 나눠 갖는다"]
        direction TB
        N1["노드 1 · 0~24"] --> N2["노드 2 · 25~49"]
        N2 --> N3["노드 3 · 50~74"]
        N3 --> N4["노드 4 · 75~99"]
        N4 -->|끝에서 처음으로| N1
    end

토큰이 어느 구간에 떨어지느냐로 담당 노드가 정해집니다. 원 위에서 담당을 이렇게 나누는 방법을 일관성 해싱이라고 부릅니다.

담당 노드 한 대만 데이터를 들고 있으면 그 대가 죽을 때 못 읽습니다. 그래서 담당 노드부터 링을 따라 다음 노드들에 사본을 더 둡니다. 몇 벌을 둘지는 복제 계수로 정합니다. 복제 계수가 셋이면 데이터마다 사본이 셋입니다.

flowchart TD
    K["파티션 키 u42"] --> H["해시 함수"]
    H --> T["토큰 62"]
    T --> N3["노드 3 · 50~74 를 맡는다 · 사본 1"]
    N3 -.->|링의 다음 노드| N4["노드 4 · 사본 2"]
    N4 -.->|링의 다음 노드| N1["노드 1 · 사본 3"]

실선은 값이 어디로 가는지를, 점선은 링에서 다음 차례가 누구인지를 가리킵니다. 사본 셋은 담당 노드가 넘겨주는 것이 아니라 코디네이터가 한꺼번에 적습니다. 그 진행은 아래 「일관성 수준」에서 봅니다.

노드를 새로 넣거나 빼면 그 노드가 맡은 구간만 옮겨 갑니다. 나머지 데이터는 제자리에 남습니다.

flowchart TD
    subgraph 그대로["구간이 안 바뀌는 노드"]
        A1["노드 1 · 0~24"]
        A2["노드 2 · 25~49"]
        A4["노드 4 · 75~99"]
    end
    subgraph 갈림["노드 5 가 들어온 구간"]
        B0["노드 3 이 맡던 50~74"] --> B3["노드 3 · 50~62"]
        B0 --> B5["노드 5 · 63~74"]
    end

대표 없이 요청을 받는 구조

많은 데이터베이스는 쓰기를 받는 대표 한 대를 둡니다. 나머지는 대표가 적은 것을 따라 적습니다. 대표가 죽으면 새 대표를 뽑는 동안 쓰기가 멈춥니다.

Cassandra 에는 대표가 없습니다. 모든 노드가 같은 일을 할 수 있어서 클라이언트는 아무 노드에나 요청을 보냅니다. 요청을 받은 노드는 그 데이터의 사본을 들고 있는 노드들에 일을 돌리고 답을 모읍니다. 이렇게 한 요청의 진행을 맡은 노드가 코디네이터입니다.

flowchart TD
    subgraph L["대표를 둔 구조"]
        C1["클라이언트"] --> LD["대표 · 쓰기를 받는 한 대"]
        LD --> F1["팔로워 1"]
        LD --> F2["팔로워 2"]
    end
    subgraph S["Cassandra"]
        C2["클라이언트"] --> CO["요청을 받은 아무 노드 · 코디네이터"]
        CO --> R1["사본 1"]
        CO --> R2["사본 2"]
        CO --> R3["사본 3"]
    end

코디네이터는 못 박힌 역할이 아닙니다. 요청마다 그 요청을 받은 노드가 코디네이터가 됩니다. 노드들은 서로 살아 있는지와 어느 구간을 맡았는지를 가십이라는 방식으로 주고받습니다. 가십은 노드가 아는 소식을 가끔 이웃 하나에게 전하고 그 이웃이 또 전하는 식으로 퍼뜨리는 방법입니다.

일관성 수준

읽고 쓸 때마다 사본 몇 대의 답을 기다릴지 고릅니다. 이 고르는 값이 일관성 수준입니다. 자주 쓰는 값은 셋입니다.

ONE 은 답이 일찍 돌아오는 대신 방금 쓴 값을 못 읽을 수 있습니다. 쓰기가 사본 하나에만 닿은 사이에 다른 사본에서 읽으면 옛 값이 나옵니다. ALL 은 그런 일이 없는 대신 사본 한 대만 멈춰도 요청이 실패합니다.

QUORUM 은 그 사이입니다. 쓰기도 과반, 읽기도 과반을 기다리면 두 과반은 반드시 한 대 이상 겹칩니다. 겹친 그 한 대가 방금 쓴 값을 들고 있어서 읽기가 그 값을 봅니다. 이 과반을 정족수라고도 합니다.

flowchart TD
    subgraph W["쓰기 정족수 · 둘이 적으면 끝"]
        WN1["노드 1"]
        WN3["노드 3"]
    end
    subgraph R["읽기 정족수 · 둘이 답하면 끝"]
        RN3["노드 3"]
        RN4["노드 4"]
    end
    WN3 -.->|겹치는 한 대| RN3

사본이 셋일 때 과반은 둘입니다. 한 대가 멈춰 있어도 읽기와 쓰기가 됩니다. 쓰기 쪽 둘과 읽기 쪽 둘을 어떻게 고르든 같은 노드가 최소 한 대는 양쪽에 들어갑니다.

sequenceDiagram
    participant 앱 as 클라이언트
    participant 코디 as 노드 1 · 코디네이터 겸 사본
    participant N3 as 노드 3 · 사본
    participant N4 as 노드 4 · 사본
    앱->>코디: u42 행을 써라 · QUORUM
    코디->>코디: 자기 사본에 적는다
    코디->>N3: 이 값을 적어라
    코디->>N4: 이 값을 적어라
    N3-->>코디: 적었다
    Note over 코디,N3: 셋 중 둘이 적었다 · 과반이다
    코디-->>앱: 성공
    N4-->>코디: 늦게 적었다

노드 4 의 답을 안 기다리고 성공이 돌아갔습니다. 셋 중 둘이 과반이라 조건이 이미 채워졌기 때문입니다. 답이 늦는 노드 한 대가 쓰기 전체를 붙잡지 않습니다.

어긋난 사본을 맞추는 법

QUORUM 으로 썼다면 사본 하나는 아직 옛 값을 들고 있습니다. 놓친 사본을 그냥 두면 계속 옛 값을 돌려줍니다. Cassandra 는 이 어긋남을 세 가지 방법으로 메웁니다.

첫째는 힌티드 핸드오프입니다. 사본 한 대가 꺼져 있으면 코디네이터가 그 대에 갈 값을 적어 들고 있습니다. 그 대가 돌아오면 넘겨줍니다. 적어 둔 그 쪽지가 힌트입니다.

sequenceDiagram
    participant 앱 as 클라이언트
    participant 코디 as 코디네이터
    participant 사본 as 꺼진 사본
    앱->>코디: 값을 써라
    코디->>사본: 이 값을 적어라
    Note over 코디,사본: 꺼져 있어 안 닿는다
    Note over 코디: 그 대에 갈 값을 힌트로 적어 둔다
    사본->>코디: 돌아왔다
    코디->>사본: 들고 있던 힌트를 넘긴다

둘째는 읽기 복구입니다. 읽기를 하다가 사본들이 서로 다른 값을 내놓으면 최신 값을 골라 돌려줍니다. 뒤처진 사본에는 그 값을 써 넣습니다. 읽는 김에 고치는 방식이라 자주 읽는 데이터일수록 잘 맞습니다.

셋째는 반-엔트로피 복구입니다. 어긋남이 쌓이는 것을 거꾸로 되돌린다는 뜻으로 반-엔트로피라고 부릅니다.

운영자가 시켜서 도는 작업입니다. 사본끼리 들고 있는 데이터를 전부 견줍니다. 데이터를 전부 주고받으면 양이 많습니다. 요약본인 머클 트리를 먼저 견주고 다른 가지만 내려갑니다.

쓰기가 디스크에 닿는 길

Cassandra 의 저장 엔진은 LSM 트리(Log-Structured Merge tree, 로그 구조 병합 트리) 방식입니다. 디스크의 같은 곳을 고쳐 쓰지 않고 새로 쓰기만 하는 방식입니다.

쓰기가 들어오면 두 곳에 적습니다. 하나는 커밋 로그로, 디스크에 순서대로 덧붙이기만 하는 기록입니다. 다른 하나는 memtable 로, 메모리 안에서 키 순서로 들고 있는 표입니다. 두 곳에 적히면 그 쓰기는 끝난 것으로 봅니다.

메모리의 표가 정해진 크기를 넘으면 그대로 디스크 파일 하나로 내려 굳힙니다. 굳은 이 파일이 SSTable 입니다. 한 번 쓰이면 고치지 않습니다. 값을 바꾸거나 지울 때도 이 파일은 손대지 않고 새 파일이 하나 더 생깁니다.

파일이 자꾸 늘면 읽기가 뒤져야 할 곳이 많아집니다. 쌓인 파일을 하나로 합치고 옛 파일을 버리는 컴팩션이 뒤에서 돕니다.

flowchart TD
    W["쓰기 한 건"] --> C["커밋 로그 · 디스크에 덧붙인다"]
    W --> M["memtable · 메모리에 키 순서로 쌓인다"]
    M -->|가득 차면| S1["SSTable · 고치지 않는 파일"]
    S1 --> K["컴팩션 · 쌓인 파일을 합친다"]
    K --> S2["새 SSTable · 옛 파일은 버린다"]

커밋 로그와 memtable 로 갈라지는 두 줄이 한 번의 쓰기입니다. 커밋 로그는 서버가 갑자기 죽었을 때 메모리에 있던 것을 되살리는 데 씁니다. memtable 이 파일로 내려간 뒤에는 그만큼의 커밋 로그가 필요 없어집니다.

읽기는 memtable 과 SSTable 여러 개를 겹쳐 봅니다. 어느 파일에 그 키가 없다는 것을 파일을 열지 않고 걸러 내려고 블룸 필터를 파일마다 함께 둡니다. 블룸 필터는 「없다」는 확실히 답하고 「있다」는 틀릴 수 있는 요약본입니다.

flowchart TD
    RD["읽기 한 건"] --> MM["memtable 을 본다"]
    MM --> BF["SSTable 마다 블룸 필터에 묻는다"]
    BF -->|없다| SKIP["그 파일은 안 연다"]
    BF -->|있다고 한다| OPEN["그 파일을 열어 본다"]
    SKIP --> PICK["모은 값 가운데 최신을 고른다"]
    OPEN --> PICK

지운 값에 남는 표시

Cassandra 는 값을 지울 때 그 행을 바로 없애지 않습니다. 「지워졌다」는 표시를 하나 써 넣습니다. 이 표시를 툼스톤이라고 부릅니다.

왜 바로 안 지우는지는 사본을 생각하면 드러납니다. 사본 한 대가 꺼진 사이에 삭제가 일어났다고 해 봅시다. 그 대가 돌아왔을 때 자기만 옛 행을 들고 있으면, 사본을 맞추는 과정에서 그 행이 되살아납니다. 삭제를 값처럼 적어 두어야 「지워진 것이 최신」이라고 판정할 수 있습니다.

툼스톤은 정해진 기간이 지난 뒤 컴팩션 때 걷힙니다. 그 기간 안에 꺼져 있던 노드가 돌아오지 않으면 지운 데이터가 되살아날 수 있습니다. 반대로 지웠다 썼다를 되풀이하는 데이터는 툼스톤이 쌓여 읽기가 무거워집니다.

stateDiagram-v2
    state "값이 있다" as V
    state "툼스톤이 붙었다" as T
    state "사본이 전부 삭제를 안다" as C
    state "행이 없어졌다" as G
    state "옛 행이 되살아난다" as Z
    [*] --> V
    V --> T: 삭제
    T --> C: 기간 안에 꺼진 노드가 돌아온다
    C --> G: 컴팩션
    T --> Z: 기간을 넘겨 돌아온다

미리 낸 길로만 도는 질의

Cassandra 에 질의를 보내는 언어는 CQL(Cassandra Query Language, 카산드라 질의 언어)입니다. 생김새가 SQL(Structured Query Language, 구조화 질의 언어)과 닮아서 표를 만들고 행을 넣고 고르는 문장이 비슷합니다. 닮은 것은 생김새고 할 수 있는 일은 다릅니다.

표를 만들 때 기본 키를 정합니다. 기본 키의 첫 칸이 파티션 키입니다. 그 뒤 칸들은 클러스터링 키입니다.

파티션 키는 그 행이 어느 노드로 갈지를 정합니다. 클러스터링 키는 한 노드 안에서 행들이 어떤 순서로 줄지을지를 정합니다.

CREATE TABLE orders (
  user_id text,
  ordered_at timestamp,
  amount int,
  PRIMARY KEY (user_id, ordered_at)
);

user_id 가 파티션 키라 한 사용자의 주문이 전부 같은 노드에 모입니다. ordered_at 이 클러스터링 키라 그 안에서 주문들이 시각 순으로 줄지어 놓입니다.

flowchart TD
    subgraph ND3["노드 3"]
        subgraph P42["파티션 u42"]
            O1["01-03 · amount 1200"]
            O2["02-11 · amount 300"]
            O3["02-28 · amount 900"]
            O1 -->|ordered_at 순| O2
            O2 -->|ordered_at 순| O3
        end
    end
    subgraph ND1["노드 1"]
        P77["파티션 u77 · 키가 달라 다른 노드로 간다"]
    end

파티션 키가 다르면 같은 표의 행이라도 다른 노드로 갑니다. 이 표에 던질 수 있는 질의와 던질 수 없는 질의는 이렇게 갈립니다.

-- 파티션 키로 찾는다
SELECT * FROM orders
 WHERE user_id = 'u42';   -- 시각 순으로 나온다

-- 키가 아닌 칸으로 찾는다
SELECT * FROM orders
 WHERE amount > 1000;     -- 거부된다

뒤 질의가 거부되는 까닭은 amount 가 행의 위치를 정하는 값이 아니기 때문입니다. 이 조건에 맞는 행을 찾으려면 모든 노드의 모든 행을 훑어야 합니다. Cassandra 는 그런 질의를 기본으로 막습니다. ALLOW FILTERING 을 붙여 훑겠다고 밝혀야 받습니다.

표를 짜는 순서도 뒤집힙니다. 관계형 데이터베이스에서는 데이터의 모양을 먼저 정하고 질의를 나중에 만듭니다. Cassandra 에서는 어떤 질의를 쓸지 먼저 정하고 그 질의에 맞는 표를 만듭니다. 같은 데이터를 두 가지로 찾아야 하면 표를 둘 만들어 양쪽에 넣기도 합니다.

포기한 것

Cassandra 는 여러 대에 흩어 놓고도 멈추지 않는 것을 얻으려고 몇 가지를 내려놓았습니다.

Cassandra 는 계좌 이체처럼 여러 행을 한 번에 맞춰 바꿔야 하는 데이터에는 쓰지 않습니다. 사용자 활동 기록, 센서 측정값, 메시지 이력처럼 한 번 쓰고 잘 안 고치며 계속 쌓이는 데이터가 Cassandra 가 노린 몫입니다.

관련 항목

Cassandra 가 데이터를 노드에 나눠 두는 방법

일관성 해싱 · 파티션 키 · 토큰 · 샤딩 · 복제 계수 · 복제 · 수평 확장 · 수직 확장 · 파티셔닝 · 노드 · 클러스터

Cassandra 가 사본을 맞추는 방법

코디네이터 · 일관성 수준 · 정족수 · 느슨한 정족수 · 힌티드 핸드오프 · 읽기 복구 · 반-엔트로피 · 머클 트리 · 가십 · 충돌 해소 · 결과적 일관성

Cassandra 의 저장 엔진을 이루는 구성 요소

LSM 트리 · SSTable · memtable · 커밋 로그 · 컴팩션 · 툼스톤 · 블룸 필터 · 쓰기 증폭 · WAL

Cassandra 에 질의를 보내고 표를 짜는 수단

CQL · 기본 키 · 클러스터링 키 · SQL · 데이터 모델링 · 비정규화 · 경량 트랜잭션 · 구체화 뷰

Cassandra 와 같은 역할을 두고 겨루는 데이터베이스

ScyllaDB · HBase · DynamoDB · Riak KV · MongoDB · Bigtable · Dynamo

Cassandra 가 맞바꾼 성질

고가용성 · CAP · 분단 · 일관성 · 선형화 가능성 · 가용성

Cassandra 가 속하는 상위 분류

분산 시스템 · 데이터베이스 · NoSQL · 와이드 칼럼 저장소 · 관계형 데이터베이스 · 키-값 저장소