imported>rabierre |
imported>rabierre |
| (10 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| __TOC__
| | 구글 빅테이블 |
| [[pagelist(^Bigtable/)]]
| |
| * 구글의 분산 데이터베이스 Bigtable 분석하고 설계하기
| |
| * http://nforge.zeropage.org/projects/bigtablet
| |
| ** 아 잘못만들었네
| |
| == 기능 ==
| |
| 태블릿 할당 ★★★★★
| |
| 3 B+ 트리 갱신 ★★★★★
| |
| 4 마스터 SCAN ★★★★★
| |
| 5 클라이언트의 요청 ★★★★
| |
| 6 커밋로그에 쓰기 ★★★
| |
| 7 TS 등록 ★★★
| |
| 8 클라이언트 에러코드 ★★
| |
| 9 SSTABLE Compaction ★★★
| |
| 10 태블릿 Split ★★
| |
| 11 태블릿 복구 ★★
| |
| 12 마스터 복구 ★★
| |
| heartbeat ★
| |
| 만기 ★
| |
| | |
| == 로드 밸런싱 ★★★★★ ==
| |
| 가장 load가 적은 TS에게 가장 load가 많은 TS의 태블릿을 할당.
| |
| TS와 TS간의 태블릿 할당
| |
| 신규 TS에 태블릿 할당하기도 같음.
| |
| === 기능명세 ===
| |
| # 트리거
| |
| ## 태블릿 개수, cpu rate, 메모리 사용량의 비율을 계산해서
| |
| ## ISSUE : 평균+일정 수치를 이용한 계산식 필요
| |
| ## 평균으로 트리거를 결정하지만 값이 일정 수치보다 작다면 로드 밸런싱은 일어나지 않는다.
| |
| * 마스터 역할
| |
| ## 가장load가 큰 TS(source)와 가장load가 적은 TS(target)와의 차이가 일정수준 이상일때
| |
| ## source 에게 target의 ip와 전달할 태블릿의 개수를 전달
| |
| * TS 역할
| |
| ## 소스 TS
| |
| ## 해당 태블릿의 SSTABLE들을 minor compaction
| |
| ## source는 target에게 정해진 갯수만큼의 태블릿을 리스트로 이름전달 ( 연속된 태블릿을 전달한다)
| |
| ## 자신의 태블릿 리스트에서 전달한 태블릿들을 삭제
| |
| ## target에게서 제대로 전달받았는지 확인
| |
| ## 타겟 TS
| |
| ## 전달받은 태블릿 리스트로 태블릿들을 읽어온다
| |
| ## 소스 TS에게 성공 메세지 보냄
| |
| ## 소스 TS
| |
| ## 마스터에게 성공 메세지 전달(마스터 업데이트)
| |
| * 마스터 역할
| |
| ## b+ 트리(메타태블릿) 갱신
| |
| * ISSUE
| |
| ## 클러스터의 로드가 적어서 하나의 TS가 커버할 수 있는 정도도 로드 밸런싱이 필요한가?
| |
| ## target이 제대로 전달받았는지 어떻게 알지?
| |
| ## target이 직접 마스터에게 자신의 태블릿 리스트를 전달하고 마스터가 target의 이전 태블릿 리스트와 현재 태블릿 리스트를 비교해 밸런싱이 잘 되었는지 확인.
| |
| ## 더 나은 로드밸런싱 정책필요
| |
| ## 로드밸런싱시 전송할 태블릿 개수 어떻게?
| |
| == TS 복구 ★★★★★ ==
| |
| TS가 다운되면 해당 TS가 가지고 있던 태블릿들을 다른 TS에 분산해 나누어준다.
| |
| 마스터와 TS사이의 로드밸런싱
| |
| === 기능명세 ===
| |
| * 마스터
| |
| ## 마스터는 주기적으로 TS들에게서 heartbeat를 받는다
| |
| ## 마스터는 주기적으로 TS들의 태블릿 리스트를 스캔한다.
| |
| ## 스캔한 태블릿 리스트들과 메타태블릿(루트태블릿이었나?)과 비교해 누락된 태블릿 리스트가 있는지 검사
| |
| ### 누락된 태블릿 리스트가 있다면 해당 태블릿 리스트를 가지고 있는 TS가 만기된 것임.(<- 만기가 되지 않았다면?)
| |
| ### 해당 태블릿 리스트를 다른 TS들에게 할당해야함.
| |
| ### target들을 정한다. (어떤 기준으로? 몇개나?)
| |
| ### traget들에게 직접 태블릿 리스트를 전달한다.
| |
| * TS
| |
| ## 읽기 성공시 마스터에게 성공 메세지 전달 (마스터 업데이트)
| |
| * ISSUE
| |
| ## 태블릿 분산시 어떤 정책을 쓸까?
| |
| ## 평균?
| |
| ## 개수?
| |
| === ISSUE ===
| |
| * 메타데이터 태블릿 갱신 (B+ 트리 갱신)
| |
| ## 갱신 : 마스터가
| |
| ## 언제 : 마스터 업데이트 후
| |
| ## 마스터 업데이트 : target이 태블릿 리스트를 전달받고 DFS에서 태블릿 읽기에 성공하면 source에게 성공 메세지 전달.
| |
| ## source는 target에게 성공 메세지를 받으면 자신의 태블릿 리스트에서 전달한 태블릿들을 삭제한다.
| |
| ## source는 마스터에게 성공 메세지를 보내 마스터를 업데이트한다.
| |
| ## 마스터는 메타태블릿을 업데이트한다.
| |
| # 로드 밸런싱 중간에 target이 다운된다면 : 마스터는 로드밸런싱을 위해 다른 target을 선택. 이후 TS 복구를 한다.
| |
| # 로드 밸런싱 중간에 source가 다운된다면? : TS 복구
| |
| # 소스TS는 전달할 태블릿을 어떻게 정할 것인가 : 태블릿 리스트에서 앞에서부터 연속되는 태블릿 N개
| |
| # DFS에서 태블릿 읽기 실패시 대처
| |
| ## 무한 읽기 시도 -> DFS 부하 증가
| |
| ## 읽기 실패한 태블릿 삭제요청 -> 정보 손실
| |
| == B+ 트리 갱신 ★★★★★ ==
| |
| 태블릿의 삽입(혹은 split)이 있을 때마다 마스터(또는 TS 스스로)가 b+ 트리를 갱신한다.
| |
| client는 b+ 트리를 이용해 row key 탐색을 할 수 있다.
| |
| == 마스터 SCAN ★★★★★ ==
| |
| 마스터의 스캔요청에 대한 응답. TS가 관리중인 모든 태블릿의 리스트를 마스터에게 전달한다.
| |
| # 마스터의 스캔요청
| |
| # TS가 자신이 관리하고 있는 태블릿의 리스트들을 전달한다.
| |
| === 기능명세 ===
| |
| == 클라이언트의 요청 ★★★★ ==
| |
| * 캐싱 필요
| |
| === 기능명세 ===
| |
| ==== read ====
| |
| * 클라이언트 역할
| |
| ## B+트리에서 원하는 row를 가지고 있는 TS를 탐색
| |
| * TS역할
| |
| ## 클라이언트의 ROW의 읽기 요청이 들어온다 (ISSUE 6. 클라이언트는 어떤 형식으로 TS에게 ROW를 요청할 것인가)
| |
| ## TS는 자신이 가진 태블릿들에서 요청받은 ROW를 검색
| |
| ## 검색결과들을 '''merge'''한다.
| |
| ## merge결과를 String의 리스트로 클라이언트에게 돌려준다
| |
| ==== write ====
| |
| * 클라이언트 역할
| |
| ## (태블릿은 같은 ROW를 담고 있으므로 클라이언트는 트리탐색을 통해 TS를 할당받는다)
| |
| * TS 역할
| |
| ## 클라이언트에게 요청받은 row는 먼저 커밋로그에 기록 후 memtable에 쓴다.
| |
| == 커밋로그에 쓰기 ★★★ ==
| |
| 쓰기(write) 연산시에만 기록됨
| |
| 크기 제한(2GB) 필요
| |
| 원형 자료구조를 사용해 공간의 재활용필요 -> 한바퀴 돌아서 공간이 없어지면 memtable들의 minor compaction이 필요하다.
| |
| 그러나 compaction시에는 모든 수정작업이 중지되므로 로그는 적절히 커야한다.
| |
| === 기능명세 ===
| |
| ==== 기록 ====
| |
| # memtable에 쓰기를 하기 전
| |
| # 커밋로그에 sstable명과 쓰려는 값 기록
| |
| ==== 말소 ====
| |
| # memtable이 copaction으로 sstable이 되면 해당 sstable의 로그는 삭제되어야 한다.
| |
| # 로그의 삭제도 쓰기연산
| |
| ## 플래그를 이용해 삭제됨을 명시
| |
| === 비기능 명세 ===
| |
| # 커밋로그는 DFS에 있다.
| |
| # TS당 한개.
| |
| == TS 등록 ★★★ ==
| |
| 신규 TS는 Locker에 자신의 정보를 등록한다
| |
| Locker는 잠금파일을 이용해 TS를 관리한다.
| |
| === 기능명세 ===
| |
| # Locker에 자신의 정보를 등록한다
| |
| ## 자신의 ip
| |
| ## port
| |
| ## 그 외의 시스템 전체가 공유해야 하는 정보는?
| |
| # Locker는 해당 ip와 port#로 파일을 생성하며 해당 TS에게만 수정권한을 준다.
| |
| == 클라이언트 에러코드 ★★ ==
| |
| 클라이언트의 요청이 제대로 수행되지 않았을 때 TS에게 받은 응답메세지별로 다른 시도를 할 수 있다.
| |
| === 비기능명세 ===
| |
| # TS 시작시에 등록한다. 등록에 성공하지 못하면 다시 시도한다.
| |
| # 재시도할 때 마다 시간간격 늘림
| |
| # 일정횟수 이상시 멈춤(Locker의 부하 고려)
| |
| == SSTABLE Compaction ★★★ ==
| |
| 마스터는 태블릿의 SSTABLE 리스트도 알고있어야 하나?
| |
| === Minor Compaction ===
| |
| memtable에 더이상 쓰기 연산을 수행할 수 없을 때 SSTABLE로 변환. 파일형태로 DFS에 쓴다.
| |
| # 트리거
| |
| ## memtable에게 할당된 메모리를 다 사용해서 더 이상 쓰기를 할 수 없을 때
| |
| ## 커밋로그에게 할당된 용량을 다 사용해서 더 이상 쓰기를 할 수 없을 때
| |
| === Major Compaction ===
| |
| SSTABLE들을 합병하여 최근 기록만을 남긴다.
| |
| client의 읽기 요청 응답시에 효율이 좋음
| |
| * ISSUE
| |
| ## SSTABLE 합병 시기?
| |
| ## major compaction을 하면 SSTABLE이 항상 1개가되나?
| |
| == 태블릿 Split ★★ ==
| |
| 태블릿의 크기가 일정 수준 이상 커지면 두개로 나눈다.
| |
| === 기능명세 ===
| |
| # 태블릿의 크기가 200MB를 넘으면 major compaction
| |
| ## 태블릿 split시 키는 반드시 sort되어 있어야 한다.
| |
| # 후 split한다
| |
| # SSTABLE은 논리적으로 분할된다
| |
| ## 여러 태블릿이 하나의 SSTABLE을 참조할 수 있다.
| |
| ## '''ISSUE''' : merge compaction등으로 두개의 sstable만들면 sstable의 복수참조를 막을 수 있다.
| |
| === ISSUE ===
| |
| == 태블릿 복구 ★★ ==
| |
| 커밋로그에서 로그를 읽어와 memtable 복구하는 것
| |
| === 기능명세 ===
| |
| # map&reduce 연산으로 TS별 정렬이 필요하다.
| |
| # 정렬된 로그에서 특정 TS의 로그를 재실행(redo)한다.
| |
| == 마스터 복구 ★★ ==
| |
| 마스터 서버 다운시 복구
| |
| === 기능명세 ===
| |
| # 마스터가 다운되었음을 감지하는 즉시 ?는 새로운 마스터를 결정한다.
| |
| ## ISSUE
| |
| ## 마스터의 다운을 어떻게 감지하지?
| |
| ## 누가 새로운 마스터를 결정하지?
| |
| # 새로운 마스터의 시작을 알린다
| |
| ## ISSUE : 누가 마스터를 알리지?
| |
| ## 마스터가? TS가?
| |
| # 마스터는 Locker에서 TS리스트를 읽어온다.
| |
| # 마스터는 Locker에서 루트태블릿의 정보를 읽어온다.
| |
| # 마스터는 TS들에게서 태블릿 리스트를 스캔한다.
| |
| == heartbeat ★ ==
| |
| TS가 마스터(또는 Locker)에 일정 간격마다 지속적으로 전송하는 더미 패킷.
| |
| TS가 활성화중임을 알린다.
| |
| | |
| * ISSUE
| |
| ## heartbeat에 응답을 해야하나?
| |
| ## 장 : 마스터 실패를 TS가 감지할 수 있다.
| |
| ## 단 : 마스터의 부하 증가
| |
| == 만기 ★ ==
| |
| 유닛들은 스스로를 파기하지 않는다.
| |
| 서버에 장애가 생겨 기능을 하지 못하게 되었을 때 만기(expired) 되었다고 한다.
| |
| === 기능명세 ===
| |
| # TS 복구
| |
| # 마스터 복구
| |
| # Locker와 DFS의 복구는 논외로 한다.
| |
| === 비기능명세 ===
| |
| ## 만기/실패시 복구
| |
|
| |
|
