Bigtable/Data Model

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

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

데이터 저장 형식은 3차원 테이블형태. 행(row key), 열(column), 깊이(timestamp)
태블릿을 모두 합병하면 테이블이 된다.

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

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

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

1. split 허용

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

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

1. SSTABLE 명?
   
   1. 태블릿Id
      
   2. + 마지막 row key
      
2. 데이터 블록과 인덱스 블록
   
   1. 데이터 블록
      
   2. 인덱스 블록
      
      1. 약 64KB마다 존재하는 row key를 블록의 인덱스로 한다.
         
      2. 블록의 인덱스와 실제 파일의 주소를
         
3. 다수의 태블릿이 하나의 SSTable을 참조할 때의 문제점?
   
   1. 여러 태블릿이 하나의 SSTable을 참조해도 블럭들을 오프셋으로 참조하므로 같은 부분을 참조하는 일이 없다.
      
   2. 각 태블릿의 majorCompaction시 태블릿별로 SSTable들이 나누어지므로 결국 SSTable은 하나의 태블릿에 피참조된다.
      

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

1. 메모리에 할당되어있다.
1. 태블릿당 한개
1. 쓰기밖에 안됨.
1. 데이터 블럭과 인덱스 블럭으로 나누어짐

1. 크기
   
   1. 데이터 블럭 크기 : 32MB
      
   2. 인덱스 블럭은 크기제한 없다.
      
2. 데이터
   
   1. 데이터 블럭 : 키:값을 쓴다.
      
   2. 인덱스 블럭 : 태블릿이 참조하고 있는 SSTable의 블럭 인덱스들 merge
      

1. 할당된 메모리 크기가 다 차서 더이상 쓸 수 없을 때 SSTABLE로 저장한다.
1. SSTABLE들의 인덱스를 가진다

1. 인덱스는 어떻게?
   

특정 컬럼을 가지는 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. 카탈로그 전용 파일 필요?? SSTable 하나를 할당받아 다 쓸때까지 해제하지 않는건 어떨까?
      
4. ISSUE
   
   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#