google-bigtable.md

구글 빅테이블

빅테이블이란?

• 구조화된 데이터를 담는 분산 스토리지 시스템
  • 구조화 되지 않은 데이터: 오디오, 비디오 파일
  • 반만 구조화된 데이터: JSON
  • 구조화 데이터: 엑셀, RDBMS의 데이터
• 페타 바이트의 데이터를 여러 서버에 나눠서 저장할 수 있게 설계됨
  • 분산 == 수평 확장
  • 기존 RDBMS는 수직확장에 용이하지만 수평확장에는 약함
  • 수직확장은 더 좋은 부품을 써야해서 비싸고 한계도 있음
  • 수평확장은 저렴한 서버 여러 개를 사용하면 되므로 효율적임

빅테이블의 목표

• 넓은 적용성
  • 한 서비스에 매몰되지 않고 여러 서비스에서도 사용할 수 있음
• 확장성
  • 저렴한 서버 추가로 더 많은 데이터를 저장할 수 있음
• 고성능
  • 다루는 데이터 크기가 커도 괜찮음
• 고가용성
  • 다운타임이 없어야함

RDBMS와 비슷한 점

• 구조화된 데이터를 저장함
• 테이블 형식으로 데이터를 저장함
• SQL 같은 Sawzall 스크립트 언어 제공
  • 하지만 SQL보다 능력이 제한됨

RDBMS와 차이점

• 인터페이스가 다름
• 스키마가 유동적
• 데이터 레이아웃과 포맷 수정 가능
• 데이터가 Row + Column 이름으로 인덱싱됨
• 인 메모리 저장소 제공
• 스키마 선택으로 데이터의 Locality를 조절할 수 있음
  • Locality: 데이터가 어떻게 나눠져서 보관될 지

데이터 모델의 특징

• 희소성(Sparse)
  • 테이블의 모든 칼럼 키가 값을 가질 필요 없음
• 분산성
  • 데이터가 타블릿 서버 여러 개에 나눠져 있음
• 영속성
  • 구글 파일 시스템에 저장됨
• 다차원적
• 정렬된 맵
  • Row 키 기반으로 정렬돼서 저장됨

데이터 모델 예시

• Row 키, Column 패밀리 키, Column 키, 타임스탬프로 데이터 접근 가능

• 키와 시간에 따라 여러 버전의 데이터가 저장됨 == 다차원적 특성

Row

• Row 키는 64KB 이하의 랜덤 문자열
• Row 키로 하는 모든 읽기/쓰기는 원자적임
• Row 키의 사전 순서에 따라 테이블이 저장됨
• Row 집합 == Tablet
• Row 키를 잘 선택해야 데이터의 Locality를 활용할 수 있음

Column 패밀리

• Column 키들을 Column 패밀리들로 묶음
• Column 패밀리가 같은 Column은 타입도 같음
• 그래서 Column 패밀리끼리 압축을 효율적으로 할 수 있음
• Column 키를 저장하기 전에 Column 패밀리를 생성해야함
• 한 테이블에 특정 개수(≈ 100) 이상의 Column 패밀리를 만들 수 없음
• 한 테이블이 가질 수 있는 Column 키는 개수 제한 없음
• ACL(Access Control List)은 Column 패밀리 레벨에서 적용할 수 있음

타임스탬프

• 64비트 정수
• 빅테이블은 마이크로초 단위의 실제 시간으로 타임스탬프를 저장함
• 사용자가 임의로 타임스탬프를 설정해서 충돌을 막을 수 있음
• 데이터 버전은 내림차순으로 저장돼서 최근 버전을 가장 처음 읽음
• 버전 개수 제한은 Column 패밀리 레벨에서 설정가능하고 이를 넘으면 가비지 수집됨

사용자 API

사용자가 사용할 수 있는 API

• 테이블, Column 패밀리 생성, 삭제
• 클러스터, 테이블, Column 패밀리 메타데이터(ex, ACL) 업데이트
• Row 원자적 변경과 필터링하기
• Row 키 간 트랜잭션은 지원하지 않음
• Join 없음, 테이블이 한 개 뿐이므로.
• Sawzall 스크립트 언어(SQL과 비슷)
• 스크립트 언어는 변형, 필터링, 요약만 지원하고 변경은 지원하지 않음. grep과 비슷함

구성요소

• GFS를 사용해 로그와 데이터 파일을 저장함
• 빅테이블 프로세서는 다른 앱들과 서버 풀을 공유함
• 빅테이블 데이터는 SSTable(Sorted String Table) 파일 형식으로 디스크에 저장됨
• Chubby라는 고가용성, 영속성, 분산성을 지닌 락 서비스에 의존함

Chubby

• 고가용성, 영속성, 분산성을 지닌 락 서비스
• 복제본 5개를 사용하고, 그 중 선출된 마스터 하나로 요청을 처리함
• 복제본 중 3개 이상 작동해야 서비스가 살아있다고 봄
• 작동실패 시 Paxos 알고리즘을 사용해서 복제본을 유지함

Chubby 서비스

• 디렉터리와 작은 파일들을 포함하는 네임스페이스를 제공함
• 각 파일과 디렉터리를 락 단위로 사용할 수 있고 읽기/쓰기가 원자적임
• Chubby 클라이언트 라이브러리는 Chubby 파일 캐싱 기능을 제공함
• 클라이언트의 세션을 유지함
• 세션은 클라이언트나 파일에 따라 만료됨
• 파일, 디렉터리 변경과 세션 만료에 따른 Callback 등록 가능

Chubby 내 빅테이블 의존성

• 항상 마스터는 단 한 개만 작동하도록함
• 빅테이블 데이터의 부트스트랩 위치를 저장함
• Tablet 서버를 발견하고 Tablet 서버 다운을 판별함
• 테이블 스키마와 ACL 정보를 저장함

빅테이블이 Chubby 서비스에 과도하게 의존하므로, Chubby 서비스 다운 시 빅테이블도 작동 정지됨

구현

세 가지 구성요소

• 클라이언트 라이브러리
• 마스터 서버 하나
• Tablet 서버 여러 개

Tablet 서버는 어플리케이션의 필요에 따라 동적으로 추가/삭제됨

마스터가 하는 일

• Tablet 서버에 Tablet 할당
• 새 Tablet 서버 추가와 기존 Tablet 서버만료를 발견하기
• Tablet 서버 로드 밸런싱
• GFS의 파일 가비지 수집
• 테이블 스키마 변경

Tablet 서버가 하는 일

• Tablet 집합 관리(10 ~ 1000개)
• 읽기/쓰기 요청 처리
• 크기가 큰 Tablet 나누기 (Tablet 당 100 ~ 200MB)

클라이언트는 Tablet 서버 위치가 캐싱하므로 마스터와 직접 정보를 주고 받을 일 없음. 대신에 클라이언트는 Tablet 서버와 직접 연결되어 빅테이블을 읽고 씀. 마스터로 부하가 가지 않음.

Tablet 위치

Tablet 위치 계층은 B+ 트리 형태로 저장됨

Tablet 할당

• 각 Tablet은 항상 Tablet 서버 1개에만 할당됨
• 마스터가 Tablet 서버의 상태와 그 안의 Tablet들을 계속 파악함
• 미할당된 Tablet을 찾아서 공간이 충분한 Tablet 서버에 할당함
• 마스터는 Chubby를 사용해서 Tablet 서버를 추적함

마스터 재시작

클러스터 관리 시스템이 마스터를 재시작(or 시작)하면 다음의 단계를 거침

• 마스터 서버가 Chubby의 유니크한 마스터 락을 잡아서 여러 개의 마스터가 동작하는 것을 막음
• 마스터가 Chubby의 서버 디렉터리를 스캔해서 살아있는 Tablet 서버를 찾음
• 마스터가 각 Tablet 서버와 정보를 교환해서 각 서버에 있는 Tablet을 찾음
• 마스터가 Tablet들의 메타데이터 테이블을 스캔하고 미할당된 Tablet이 있으면 이를 미할당 Tablet 리스트에 추가함

Tablet 요청 처리(Serving)

Tablet 서버의 쓰기 요청 처리

쓰기 연산 요청이 Tablet 서버에 도착했을 때

• 요청 형식을 검증함
  • 요청이 테이블 스키마의 구조와 동일한 지 확인
• 유저의 변경 권한을 Chubby 파일의 ACL을 사용해서 검증함
• 위 두 개 조건이 만족되면, 변경 사항이 로그에 기록됨
• 변경 사항이 로그에 기록되면 요청 내용이 MemTable에 쓰여짐

Tablet 서버의 읽기 요청 처리

읽기 연산 요청이 Tablet 서버에 도착했을 때

• 요청 형식을 검증함
• 유저의 변경 권한을 Chubby 파일의 ACL을 사용해서 검증함
• 위 두 조건이 만족되면, MemTable과 SSTable을 합친 결과를 반환함

압축

MemTable의 크기가 커지고 한계점을 넘으면, MemTable은 동결되고 새 MemTable이 생성된다. 동결된 MemTable은 SSTable로 변환돼서 GFS에 쓰인다.

이를 마이너 압축이라고 한다.

마이너 압축

마이너 압축의 목적

• Tablet 서버의 메모리 사용량을 줄인다.
• 복구 시 커밋 로그에서 읽어야 할 데이터양을 줄인다.

마이너 테이블은 계속 SSTable을 생성해서 테이블의 수가 크게 증가한다.

이를 가만히 두면 읽기 연산 시 합쳐야 하는 SSTable의 수가 감당이 안 될 수도 있다.

메이저 압축

• 모든 SSTable들을 하나의 SSTable로 합치는 것
• 마스터 프로세스가 백그라운드에서 주기적으로 실행함
• 메이저 압축으로 생성된 SSTable은 삭제된 데이터를 포함하지 않음
  • 마이너 압축으로 생성된 SSTable이 삭제된 데이터를 포함할 수도 있는 것과 대조됨
• 삭제된 데이터가 차지하던 자원을 회수(가비지 수집)
• 주기적으로 민감한 정보를 확실히 지울 수 있게함

Locality 그룹

• Column 패밀리 여러 개 합친 것 == Locality 그룹
• 각 SSTable은 각 Tablet의 Locality 그룹에 생성됨
• 자주 같이 접근되는 데이터를 Locality 그룹으로 묶으면 읽기 성능이 향상됨
• Locality 그룹 저장 위치를 메모리나 디스크로 설정할 수 있음
  • 메모리 저장 시 성능이 크게 향상됨
  • 작고 자주 접근되는 데이터는 메모리에 저장하는 게 나음

압축

• Locality 그룹용 SSTable도 압축할 수 있음
• 앱 요구사항에 따라 압축 방법 선택 가능
• 보통 벤틀리-맥클로이 알고리즘으로 2패스 압축을 함
  • gzip은 1/4 수준인 반면, 이 알고리즘은 1/10 수준으로 압축함

캐싱으로 읽기 속도 증가시키기

읽기 속도 증대를 위해 Tablet 서버는 2단계 캐싱을 구현함

1. 스캔 캐시

SSTable이 반환하는 키/값 쌍을 캐싱함. 같은 데이터를 여러 번 읽는 응용 프로그램에 적합함

2. 블록 캐시

GFS에서 읽는 SSTable 블록을 캐싱함. 자주 접근하는 Row 내 Locality 그룹은 같지만 Column이 다른 순차/랜덤 읽기를 하는 응용 프로그램에 적합함.

블룸 필터

읽기 연산은 Tablet의 SSTable을 전부 읽는데, SSTable이 메모리에 없으면 디스크 접근이 많아서 읽기 비용이 커짐.

Row/Column 쌍의 데이터가 SSTable에 들어있는지 블룸 필터로 확인할 수 있음.

블룸 필터가 Tablet 서버의 메모리를 약간 차지하지만, 디스크 탐색 수를 줄여서 읽기 성능을 향상시킴.

커밋 로그 구현

커밋 로그를 남길 때 두 가지 방법이 있음

1. Tablet 당 커밋 로그 하나

• 디스크 용량을 많이 차지함

2. Tablet 서버 당 커밋 로그 하나

• 용량은 덜 차지하지만, Tablet의 상태를 복원할 때 문제가 발생할 수 있음
• 이를 방지하기 위해 커밋 로그를 키 순서대로 정렬하면 읽기 문제가 줄어듦
• 커밋 로그 정렬은 마스터 서버에 의해 병렬화 및 조절됨-
• Tablet 서버가 커밋 로그에서 변경 사항을 복원할 때 커밋 로그 정렬이 시작됨

Tablet 복원 속도 높이기

Tablet 로딩 시, 커밋 로그의 모든 데이터를 Tablet 서버에 넣는게 시간이 많이 듦

마스터 서버가 한 Tablet을 다른 Tablet 서버로 옮기기 전에, 기존 Tablet 서버는 압축을 실행함

압축을 통해 압축되지 않은 커밋 로그의 데이터양을 줄일 수 있음

새 Tablet 서버는 Tablet을 불러올 때, 커밋 로그에서 데이터를 복원할 필요가 없으므로 Tablet 복원 속도가 빨라짐

SSTable의 불변성이 주는 이점

• 파일 시스템 간 동기화가 필요 없으므로, Row에 대한 동시성 제어가 효율적임
• Tablet을 빠르게 나눌 수 있음
  • 한편, 오래된 데이터를 제거할 때 문제가 생기지만 이는 메이저 압축 때 해결됨
• MemTable만 가변 자료 구조임
  • MemTable 읽기 시 경쟁을 줄이기 위해, 각 Row 생성 시 쓰기 시 복사(copy-on-write) 방법을 사용해 병렬로 읽고 쓸 수 있음

성능 평가