[25 Computer Papers] 4. Cassandra - A Decentralized Structured Storage System

https://www.cs.cornell.edu/projects/ladis2009/papers/lakshman-ladis2009.pdf

 

 

1 introduction

Cassandra는 확장성과 가용성을 달성하기 위해 잘 알려진 기술을 종합적으로 사용합니다. Cassandra는 페이스북의 편지함 검색 기능의 스토리지 요구 사항을 충족하도록 설계되었습니다.

-매우 높은 쓰기 처리량, 하루 수십억 건의 쓰기 작업

-사용자 수에 따른 확장성

 

 

2 Related Work

성능, 가용성, 내구성을 위한 데이터 분산은 파일 시스템과 데이터베이스 커뮤니티에서 널리 연구되어 왔습니다. Cassandra에 영향을 준 기존 시스템에 대해 이야기해 보겠습니다.

-Ficus와 Coda는 일관성을 희생하는 대신 고가용성을 위해 파일을 복제하는 파일 시스템입니다. 업데이트 충돌은 일반적으로 특수한 충돌 해결 절차를 사용하여 관리됩니다.

-Farsite는 중앙 집중식 서버를 사용하지 않는 분산형 파일 시스템입니다. 복제를 사용하여 고가용성과 확장성을 달성합니다.

-GFS(Google 파일 시스템)는 전체 메타데이터를 호스팅하기 위해 단일 마스터 서버를 사용하고 데이터가 청크로 분할되어 청크 서버에 저장되는 분산 파일 시스템입니다. 하지만 이제 GFS 마스터는 Chubby를 사용하여 내결함성을 갖추게 되었습니다.

-Bayou는 분산 관계형 데이터베이스 시스템으로, 단절된 작업을 허용하고 궁극적인 데이터 일관성을 제공합니다. Bayou, Coda, Ficus는 단절된 운영을 허용하며 네트워크 파티션 및 중단과 같은 문제에 탄력적으로 대응할 수 있습니다.

-Dynamo는 네트워크 파티션 중에도 읽기 및 쓰기 작업을 계속할 수 있으며 다양한 충돌 해결 메커니즘을 사용하여 업데이트 충돌을 해결합니다.

-Bigtable은 구조와 데이터 배포를 제공하지만 내구성을 위해 분산 파일 시스템에 의존합니다.

 

 

3 .data model

Cassandra에서 데이터 기본 모델

• Cassandra의 테이블은 키로 인덱싱된 분산형 다차원 맵
• 테이블의 행 키는 크기 제한이 없는 문자열
• 값은 고도로 구조화된 객체
• columns은 columns families라는 집합으로 그룹화

 

단일 행 키 아래의 모든 작업은 원자 단위입니다. 애플리케이션은 슈퍼 컬럼 또는 단순 컬럼 패밀리 내에서 컬럼의 정렬 순서를 지정할 수 있습니다.

 

 

 

4 System Architecture

Partitioning

데이터를 분할하는 방법에는 여러 가지가 있습니다. 그 중 하나가 해시 기반 파티션입니다. 데이터를 해시하고 해시된 값을 사용해 파티션을 결정하는 개념입니다.

Cassandra는 일관된 해싱 기반 파티셔닝을 사용하여 클러스터 전체에서 데이터를 파티션합니다.

• 해시 함수의 출력 범위는 고정된 원형 공간 또는 링으로 취급됩니다(즉, 가장 큰 해시 값이 가장 작은 해시 값으로 감싸는 방식).
• 시스템의 각 노드에는 이 공간 내에서 링에서의 위치를 나타내는 임의의 값이 할당
• 먼저 키를 해싱하여 링에서의 위치를 산출
• 그런 다음 링을 시계 방향으로 이동하여 해당 항목의 위치보다 큰 위치를 가진 첫 번째 노드를 찾는다.

이러한 방식으로 각 노드는 링에서 자신과 링의 이전 노드 사이의 영역을 책임지게 됩니다. 일관된 해싱의 주요 장점은 노드의 출발 또는 도착이 바로 인접한 노드에만 영향을 미친다는 것입니다.

일관된 해싱에는 두 가지 문제가 있습니다.

1. 링의 각 노드에 무작위로 위치를 할당하면 데이터와 부하가 균일하지 않게 분산
2. 알고리즘이 노드 성능의 heterogeneity(이질성)을 활용하지 못함

카산드라는 링의 부하 정보를 분석하여 부하가 적은 노드를 링에서 이동시켜 부하가 많은 노드의 부하를 완화합니다.

 

Replication

Cassandra는 복제를 사용하여 고가용성과 내구성을 달성합니다.

각 데이터 항목은 N(구성 가능한) 호스트에 복제됩니다.

각 키는 코디네이터 노드에 할당됩니다.

코디네이터는 자신의 키 범위에 있는 데이터 항목을 복제할 책임이 있습니다.

Cassandra는 Zookeeper를 사용해 노드 중에서 리더를 선출합니다. 모든 노드는 클러스터에 가입할 때 리더에게 연락하여 자신이 어느 범위의 복제본인지 알려줍니다.

리더는 링에서 N-1 개 이상의 범위를 담당하는 노드가 없다는 불변성을 유지합니다.

키 범위를 노드에 매핑하는 메타데이터는 각 노드에 로컬로 캐시되며, 내결함성 방식으로 Zookeeper 내부에 저장됩니다. 이러한 방식으로 Cassandra는 Dynamo의 키 범위 개념에 대한 기본 설정 목록을 사용합니다.

 

 

Bootstrapping

노드가 처음 시작할 때, 노드는 일관된 해싱 링에서 자신의 위치를 위해 임의의 토큰을 선택합니다. 이 정보는 Zookeeper의 로컬 디스크에 유지되며 클러스터 전체에 가십으로 전달됩니다. 이를 통해 모든 노드는 키에 대한 요청을 클러스터의 올바른 노드로 라우팅할 수 있습니다.

부트스트랩의 경우, 노드는 시드 노드로부터 키 범위 매핑을 구축합니다.

Cassandra에는 Cassandra 인스턴스에서 노드의 추가 및 제거를 시작하는 명시적인 메커니즘이 있습니다. 이 백서에서는 다음과 같이 언급합니다:

관리자는 명령줄 도구 또는 브라우저를 사용하여 Cassandra 노드에 연결하고 클러스터에 가입하거나 탈퇴하기 위해 멤버십 변경을 실행합니다.

 

 

 

Local Persistence(로컬 지속성)

Cassandra 시스템은 데이터 지속성을 위해 로컬 파일 시스템에 의존합니다.

일반적인 쓰기 작업은 두 단계로 이루어집니다:

1. 내구성과 복구 가능성을 위해 커밋 로그에 쓰기
2. 이전 쓰기가 성공한 경우에만 인메모리 데이터 구조에 쓰기

Cassandra는 각 머신에 커밋 로그를 위한 전용 디스크가 있습니다. 인메모리 데이터 구조가 데이터 크기와 개체 수에 따라 계산된 특정 임계값을 초과하면 여러 상용 디스크 중 하나에 덤프됩니다.

여기에는 몇 가지 중요한 사항이 있습니다:

1. 모든 쓰기는 디스크에 순차적으로 이루어집니다.
2. 쓰기는 행 키를 기반으로 효율적인 조회를 위한 인덱스를 생성합니다.
3. 인덱스는 데이터 파일에 저장됩니다.

일반적인 읽기는 다음과 같이 작동합니다:

1. 쿼리는 인메모리 데이터 구조에 대해 실행됩니다.
2. 데이터를 찾을 수 없는 경우 디스크의 파일을 최신에서 오래된 순서로 살펴봅니다.

디스크의 많은 데이터 파일에서 키를 조회해야 할 수 있습니다. 이 조회 프로세스를 신속하게 처리하기 위해 Cassandra는 블룸 필터를 사용합니다. 어떤 요소가 집합의 멤버인지 여부를 테스트하는 데 사용되는 데이터 구조입니다. 또한 오탐 결과를 생성하지 않으며 공간 효율성이 매우 높다

Cassandra는 블룸 필터를 디스크와 인메모리 데이터 구조에 저장합니다. 열 패밀리의 키에는 여러 개의 열이 있을 수 있습니다. 디스크의 모든 열을 스캔하는 것을 방지하기 위해 Cassandra는 열 인덱스를 유지합니다.

 

 

Implementation Details

Cassandra에는 다음과 같은 기본 모듈이 있습니다:

1. 파티셔닝 모듈
2. 클러스터 멤버십 및 장애 감지 모듈
3. 스토리지 엔진 모듈

각 모듈은 메시지 처리 파이프라인과 작업 파이프라인이 여러 단계로 분할되는 이벤트 중심 아키텍처에 의존합니다. 이는 SEDA(Staged Event-Driven Architecture) 아키텍처를 따릅니다.

클러스터 멤버십 및 장애 감지 모듈은 non-blocking I/O를 사용하는 네트워크 계층에 구축됩니다.

모든 시스템 제어 메시지는 UDP에 의존합니다. 그리고 복제 및 요청 라우팅을 위한 애플리케이션 관련 메시지는 TCP에 의존합니다.

요청 라우팅 모듈은 상태 머신을 사용하여 구현됩니다. 읽기/쓰기 요청은 다음 상태를 통해 상태 머신을 변형시킵니다:

(i) 키에 대한 데이터를 소유한 노드를 식별합니다.

(ii) 요청을 노드에 라우팅하고 응답이 도착할 때까지 기다립니다.

(iii) 설정된 시간 초과 값 내에 응답이 도착하지 않으면 요청을 실패하고 클라이언트로 돌아갑니다.

(iv) 타임스탬프를 기준으로 최신 응답을 파악합니다.

(v) 최신 데이터가 없는 경우 모든 복제본에서 데이터 복구 일정을 잡습니다.

 

Cassandra는 동기식 또는 비동기식 쓰기를 수행하도록 구성할 수 있습니다. Cassandra에서는 이전 커밋 로그가 구성 가능한 특정 크기를 초과하면 커밋 로그가 롤아웃됩니다.

인메모리 데이터 구조와 데이터 파일은 모두 열 제품군별로 생성됩니다. 특정 columns families에 대한 인메모리 데이터 구조가 디스크에 덤프될 때마다 Cassandra는 커밋 로그에 해당 비트를 설정하여 이 columns families가 디스크에 성공적으로 지속되었음을 나타냅니다.

Cassandra의 시스템은 기본 키를 기준으로 모든 데이터를 인덱싱합니다. 디스크의 데이터 파일은 일련의 블록으로 나뉩니다. 각 블록에는 최대 128개의 키가 포함되며 블록 인덱스로 구분됩니다.

Cassandra는 빅테이블 시스템과 같이 여러 파일을 하나로 병합하는 압축 프로세스를 수행합니다.

 

 

Conclusion

Cassandra는 확장성, 고성능, 폭넓은 적용성을 제공하는 스토리지 시스템으로 구축, 구현, 운영됩니다. Cassandra는 매우 높은 업데이트 처리량을 지원하면서도 지연 시간을 낮출 수 있습니다. 압축, 키 전반의 원자성 지원 기능, 보조 인덱스 지원은 다음에 구축될 기능입니다.