Bigtable/DataModel

[[pagelist(^Bigtable)]]

구조

테이블 -> 태블릿 -> SSTABLE -> block

1. 테이블은 태블릿들의 논리적인 집합.
2. 태블릿은 SSTABLE들의 집합으로 구성되어있으며 SSTABLE들의 리스트를 저장하고 있다.
3. SSTABLE은 block의 집합이며 block들의 주소와 오프셋으로 구성되어있다.

테이블

1. Key - value
2. row key : url(또는 데이터값의 대표, 제목등)
3. column family : column 종류
   1. 앵커
   2. 콘텐츠(제목?) <- 컬럼의 값이 value
   3. Title
4. timestamp는 별도
5. value : 해당 사이트/키와 매핑되는 구조화된 데이터값

태블릿

태블릿을 모두 합병하면 테이블이 된다. 태블릿은 SSTABLE들의 집합으로 구성되어있으며 SSTABLE들의 리스트를 저장하고 있다.

1. 태블릿의 이름은 : 마지막 키 -> 카탈로그에 매핑필요
2. 마지막 키는 카탈로그에서 shorten id와 매핑되어있다.
3. 태블릿은 하나 이상의 row로 구성됨.
4. 태블릿은 SSTABLE의 이름+오프셋을 리스트를 저장하고 있다.

SPLIT

1. split 허용
2. 트리거 : 태블릿 크기가 200MB 이상일때
3. row는 하나 이상의 태블릿에 존재할 수 있다.

SSTABLE

SSTABLE은 하나의 memtable과 block의 시작주소와 오프셋들로 이루어져있다. DFS 최소 파일 단위 List 사용

1. SSTABLE 명?
   1. 태블릿Id
   2. + ???
   3. ISSUE : 여러 태블릿이 참조하는 경우는 어떻게 하지?
2. 인덱스
   1. 파일의 한 라인을 하나의 인덱스로?

• ISSUE

1. 1. 다수의 태블릿이 하나의 SSTABLE을 참조할 때의 문제점

블록

1. 블록은 64KB내외의 암시적인 자료구조이다.
   1. SSTABLE의 주소와 오프셋으로 블록들이 구분된다.
2. 명시적인 자료구조가 아니라 SSTable에서 row key들로 구분되어진 범위이다.
   1. 블록 인덱스로 선택된 row key부터 다음 블록 인덱스로 선택된 row key가 나올 때 까지를 하나의 블록 단위로 한다.
   2. 반드시 64KB가 되지는 않음

memtable

배열

1. 메모리에 할당되어있다.
2. 태블릿당 한개
3. 쓰기밖에 안됨.
4. 할당된 메모리 크기가 다 차서 더이상 쓸 수 없을 때 SSTABLE로 저장한다.

• issue

1. 1. 메모리 크기는 : 64MB의 배수로
2. SSTABLE들의 인덱스를 가진다
3. 인덱스는 어떻게?

로컬리티 그룹

특정 컬럼을 가지는 row들을 별도의 태블릿에 저장한 것. ex) 타이틀

1. TS의 메모리에 존재한다.
2. 특정 컬럼 종류만을 가진다. ex) title

커밋로그

1. 태블릿의 ID + 쓰려는 키:밸류
   1. 태블릿의 ID은 태블릿의 가장 마지막 키를 이용해 만든다.
   2. 태블릿의 ID은 매핑테이블(카탈로그)에서 짧은 ID으로 대체됨.
2. 저장공간의 재사용 : 커밋로그는 원형 자료구조를 사용하여 자동으로 공간을 재사용하도록 한다.
   1. 커밋로그의 가장 마지막 타임스탬프와 memtable의 가장 오래된 타임스탬프와 비교하여 memtable의 타임스탬프가 더 최신이라면 로그삭제가능
   2. memtable의 T/S가 더 최신이 아니라면 minor compaction을 하여 로그를 비운다.

카탈로그

1. 카탈로그의 주소는 Locker에 등록되어있다. (client의 접근을 위해 Locker에 등록)
2. 카탈로그 또한 태블릿. TS가 관리한다.
3. 카탈로그에 필요한 것
   1. 태블릿 ID 매핑 테이블
   2. 컬럼 패밀리 개수
   3. 또?

• ISSUE

1. 1. 카탈로그에 언제 접근할 것인가?

태블릿 컴색 트리/ 태블릿 트래커

루트태블릿, 메타데이터 태블릿, 유저태블릿으로 구성됨. 일반 태블릿과 마찬가지로 SSTABLE로 이루어져있으며 write only임. 자료구조 : B+-트리 -- 배열(루트, 메타태블릿) + 리스트(유저태블릿) --

1. 루트 태블릿
   1. Locker에 위치가 기록된다
   2. 메타태블릿이 분할될 때(또는 삽입될 때) 갱신됨.
   3. 루트태블릿의 원소 하나는 메타데이터 태블릿과 매칭된다.
2. 메타데이터 태블릿
   1. 유저태블릿이 분할될 때(또는 삽입될 때) 갱신됨
3. 유저 태블릿
   1. 태블릿 ID(row key)와 태블릿 서버 매핑해줌.
   2. 태블릿이 어디에 저장되어있는지 알 수 있음.
4. 저장 데이터
   1. key : 태블릿 ID(row key)

 value : IP+port#