Bigtable

[[pagelist(^Bigtable/)]]

• 구글의 분산 데이터베이스 Bigtable 분석하고 설계하기
• http://nforge.zeropage.org/projects/bigtablet
  • 아 잘못만들었네

기능

태블릿 할당 ★★★★★ B+ 트리 유지 ★★★★★ 마스터 SCAN ★★★★ 클라이언트의 요청 ★★★★ TS 등록 ★★★ 커밋로그에 쓰기 ★★★ SSTABLE Compaction ★★★ 태블릿 복구 ★★ 태블릿 Split ★★ 클라이언트 에러코드 ★★ heartbeat ★ 만기 ★

태블릿 할당 ★★★★★

기능명세

로드 밸런싱(TS <-> TS)

가장 load가 적은 TS에게 가장 load가 많은 TS의 태블릿을 할당. 신규 TS에 태블릿 할당하기도 같음.

1. 트리거
   1. 태블릿 개수, cpu rate, 메모리 사용량의 비율을 계산해서
   2. ISSUE : 평균 ? 일정 수치이상?

• 마스터 역할

1. 1. 가장load가 큰 TS(source)와 가장load가 적은 TS(target)와의 차이가 일정수준 이상일때
   2. source 에게 target의 ip와 전달할 태블릿의 개수를 전달

• TS 역할

1. 1. 소스 TS
   2. 해당 태블릿의 SSTABLE들을 minor compaction
   3. source는 target에게 정해진 갯수만큼의 태블릿을 리스트로 이름전달 ( 연속된 태블릿을 전달한다)
   4. 자신의 태블릿 리스트에서 전달한 태블릿들을 삭제
   5. target에게서 제대로 전달받았는지 확인 (ISSUE. target이 제대로 전달받았는지 어떻게 알지?)
   6. 마스터에게 전달 성공 메세지 보냄
   7. 타겟 TS
   8. 전달받은 태블릿 리스트로 태블릿들을 읽어온다
   9. 소스 TS에게 성공 메세지 보냄
   10. 소스 TS
   11. 마스터에게 성공 메세지 전달(마스터 업데이트)

• 마스터 역할

1. 1. b+ 트리(메타태블릿) 갱신

• ISSUE

1. 1. 클러스터의 로드가 적어서 하나의 TS가 커버할 수 있는 정도도 로드 밸런싱이 필요한가?
   2. target이 제대로 전달받았는지 어떻게 알지?
   3. target이 직접 마스터에게 자신의 태블릿 리스트를 전달하고 마스터가 target의 이전 태블릿 리스트와 현재 태블릿 리스트를 비교해 밸런싱이 잘 되었는지 확인.
   4. 더 나은 로드밸런싱 정책필요
   5. 로드밸런싱시 전송할 태블릿 개수 어떻게?

TS 복구(마스터 <-> TS)

TS가 다운되면 해당 TS가 가지고 있던 태블릿들을 다른 TS에 분산해 나누어준다.

• 마스터

1. 1. 마스터는 주기적으로 TS들에게서 heartbeat를 받는다
   2. 마스터는 주기적으로 TS들의 태블릿 리스트를 스캔한다.
   3. 스캔한 태블릿 리스트들과 메타태블릿(루트태블릿이었나?)과 비교해 누락된 태블릿 리스트가 있는지 검사
      1. 누락된 태블릿 리스트가 있다면 해당 태블릿 리스트를 가지고 있는 TS가 만기된 것임.(<- 만기가 되지 않았다면?)
      2. 해당 태블릿 리스트를 다른 TS들에게 할당해야함.
      3. target들을 정한다. (어떤 기준으로? 몇개나?)
      4. traget들에게 직접 태블릿 리스트를 전달한다.

• TS

1. 1. 읽기 성공시 마스터에게 성공 메세지 전달 (마스터 업데이트)

• ISSUE

1. 1. 태블릿 분산시 어떤 정책을 쓸까?
   2. 평균?
   3. 개수?

ISSUE

• 메타데이터 태블릿 갱신

1. 1. 갱신 : 마스터가
   2. 언제 : 마스터 업데이트 후
   3. 마스터 업데이트 : target이 태블릿 리스트를 전달받고 GFS에서 태블릿 읽기에 성공하면 source에게 성공 메세지 전달.
   4. source는 target에게 성공 메세지를 받으면 자신의 태블릿 리스트에서 전달한 태블릿들을 삭제한다.
   5. source는 마스터에게 성공 메세지를 보내 마스터를 업데이트한다.
   6. 마스터는 메타태블릿을 업데이트한다.
2. 로드 밸런싱 중간에 target이 다운된다면 : 마스터는 로드밸런싱을 위해 다른 target을 선택. 이후 TS 복구를 한다.
3. 로드 밸런싱 중간에 source가 다운된다면? : TS 복구
4. 소스TS는 전달할 태블릿을 어떻게 정할 것인가 : 태블릿 리스트에서 앞에서부터 연속되는 태블릿 N개
5. GFS에서 태블릿 읽기 실패시 대처
   1. 무한 읽기 시도 -> GFS 부하 증가
   2. 읽기 실패한 태블릿 삭제요청 -> 정보 손실

B+ 트리 유지 ★★★★★

태블릿의 삽입(혹은 split)이 있을 때마다 마스터(또는 TS 스스로)가 b+ 트리를 갱신한다. client는 b+ 트리를 이용해 row key 탐색을 할 수 있다.

마스터 SCAN ★★★★★

마스터의 스캔요청에 대한 응답. TS가 관리중인 모든 태블릿의 리스트를 마스터에게 전달한다.

1. 마스터의 스캔요청
2. TS가 자신이 관리하고 있는 태블릿의 리스트들을 전달한다.

클라이언트의 요청 ★★★★

• 캐싱 필요

기능명세

read

• 클라이언트 역할

1. 1. B+트리에서 원하는 row를 가지고 있는 TS를 탐색

• TS역할

1. 1. 클라이언트의 ROW의 읽기 요청이 들어온다 (ISSUE 6. 클라이언트는 어떤 형식으로 TS에게 ROW를 요청할 것인가)
   2. TS는 자신이 가진 태블릿들에서 요청받은 ROW를 검색
   3. 검색결과들을 merge한다.
   4. merge결과를 String의 리스트로 클라이언트에게 돌려준다

write

• 클라이언트 역할

1. 1. (태블릿은 같은 ROW를 담고 있으므로 클라이언트는 트리탐색을 통해 TS를 할당받는다)

• TS 역할

1. 1. 클라이언트에게 요청받은 row는 먼저 커밋로그에 기록 후 memtable에 쓴다.

커밋로그에 쓰기 ★★★

쓰기(write) 연산시에만 기록됨 크기 제한(2GB) 필요 원형 자료구조를 사용해 공간의 재활용필요 -> 한바퀴 돌아서 공간이 없어지면 memtable들의 minor compaction이 필요하다. 그러나 compaction시에는 모든 수정작업이 중지되므로 로그는 적절히 커야한다.

기능명세

기록

1. memtable에 쓰기를 하기 전
2. 커밋로그에 sstable명과 쓰려는 값 기록

말소

1. memtable이 copaction으로 sstable이 되면 해당 sstable의 로그는 삭제되어야 한다.

비기능 명세

1. 커밋로그는 GFS에 있다.
2. TS당 한개.

TS 등록 ★★★

신규 TS는 chubby에 자신의 정보를 등록한다 chubby는 잠금파일을 이용해 TS를 관리한다.

기능명세

1. chubby에 자신의 정보를 등록한다
   1. 자신의 ip
   2. port
   3. 그 외의 시스템 전체가 공유해야 하는 정보는?

클라이언트 에러코드 ★★

클라이언트의 요청이 제대로 수행되지 않았을 때 TS에게 받은 응답메세지별로 다른 시도를 할 수 있다.

비기능명세

1. TS 시작시에 등록한다. 등록에 성공하지 못하면 다시 시도한다.
2. 재시도할 때 마다 시간간격 늘림
3. 일정횟수 이상시 멈춤(chubby의 부하 고려)

SSTABLE Compaction ★★★

마스터는 태블릿의 SSTABLE 리스트도 알고있어야 하나?

Minor Compaction

memtable에 더이상 쓰기 연산을 수행할 수 없을 때 SSTABLE로 변환. GFS에 쓴다.

1. memtable에게 할당된 메모리를 다 사용해서 더 이상 쓰기를 할 수 없을 때
2. 커밋로그에게 할당된 용량을 다 사용해서 더 이상 쓰기를 할 수 없을 때

Major Compaction

SSTABLE들을 합병하여 최근 기록만을 남긴다. client의 읽기 요청 응답시에 효율이 좋음

• ISSUE

1. 1. SSTABLE 합병 시기?
   2. major compaction을 하면 SSTABLE이 항상 1개가되나?

태블릿 Split ★★

태블릿의 크기가 일정 수준 이상 커지면 두개로 나눈다.

기능명세

1. 태블릿의 크기가 200MB를 넘으면 major compaction
   1. 태블릿 split시 키는 반드시 sort되어 있어야 한다.
2. 후 split한다
3. SSTABLE은 논리적으로 분할된다
   1. 여러 태블릿이 하나의 SSTABLE을 참조할 수 있다.
   2. ISSUE : merge compaction등으로 두개의 sstable만들면 sstable의 복수참조를 막을 수 있다.

태블릿 복구 ★★

커밋로그에서 로그를 읽어와 memtable 복구하는 것

기능명세

1. map&reduce 연산으로 TS별 정렬이 필요하다.
2. 정렬된 로그에서 특정 TS만의 로그를 재실행(redo)한다.

heartbeat ★

TS가 마스터(또는 chubby)에 일정 간격마다 지속적으로 전송하는 더미 패킷. TS가 활성화중임을 알린다.

만기 ★

유닛들은 스스로를 파기하지 않는다. TS에 장애가 생겨 기능을 하지 못하게 되었을 때 만기(expired) 되었다고 한다.

기능명세

X

비기능명세

1. 1. 만기/실패시 복구