Bigtable 논문 분석

이번 글은 Google에서 발표한 Bigtable 문서를 읽고 정리한 내용이다.

bigtable-osdi06.pdf (216.0 KB)

개인적인 이해 수준으로 작성된 문서이기 때문에 틀린 부분도 많이 있을 수 있다는 것을 미리 밝혀둔다.

1. Bigtable 개요

  • BigTable : 분산파일시스템(Google File System)에서 운영되는 구조화된 데이터 저장소, 일종의 DBMS(Database Management System)
    수천 대 이상의 서버들로부터 데이터 접근을 허용하며 Petabyte 단위의 데이터를 처리

  • Goal : Wide applicability, Scalability, High performance

  • 현재 60개 이상의 Google project에서 사용 중 : Google Analytics, Google Finance, Oekut, Personalized Search, Writely, Google Earth…

  • 배치 업무부터 real-time data 제공 서비스 까지 다양하게 사용

  • BigTable Idea
    • 여러 종류의 데이터베이스로부터 개념 혼합
    • Parallel DBMS, main-menory DBMS
    • Full Relational data model은 지원하지 않음
    • But, 여러 가지 유연성 제공
    • Data layout과 format을 동적으로 제어


2. Data Model
  • Multi-dimensional sorted map
    • - Index : Row key, column key, timestamp




  • Row
    • String type, Row key는 최대 64KB까지 가능
    • Row key에 의미 있는 값을 사용했을 때 장점은? : 좀 더 연구 대상
    • 하나의 row에 대한 Read, write 작업은 atomic
    • Row Key를 이용하여 사전처럼 row를 정렬
      - Table을 여러 개의 tablet로 분리하기 쉽다.
      - Tablet로 분리할 경우 인접한 row에 대한 접근 시 여러 Server에 접속할 필요가 없다.

  • Column Families
    • Column key는 그룹으로 column family에 속한다.
    • Column Key를 생성하기 전에 반드시 column family를 먼저 생성해야 한다.
    • 데이터에 대한 접근 단위는 column family이다.
    • 하나의 테이블에는 수십 ~ 수백 개의 column family가 존재하지만 column key은 무수히 많다.




    • Column family에 대한 변경은 거의 발생하지 않지만 column key는 계속 변경되고 제한이 없다.
      . RDBMS에서의 master-detail 관계는 두 개의 테이블로 구성하지 않고 column family -- column key로 구성한 것으로 생각됨-추측




    • Column Family 단위로 접근 제어(access control)


  • Timestamps
    • cell은 timestamp로 index된 여러 버전의 데이터 저장
    • Timestamp는 자동 생성 또는 client에 의한 생성 가능
    • Descending order 로 저장 → 가장 최근 data가 우선 read
    • Garbage Collection 기능 제공
      . 오래된 데이터에 대한 삭제
      . Column family에 대해 적용
      . 두 가지 방법 제공 : 최신 버전부터 n개만 유지하는 방법, 최근 몇 일 이내의 버전만 유지하는 방법(예: crawler는 페이지에 대해 최근 3개만 유지)



3.API
  • SQL이 아닌 별도의 API 제공
    • Table manipulation, Data management
    • Tablet management in cluster

  • Single-row transaction
    • Atomic read-modify-writer

  • Support client-supplied script
    • Server내에서 client에 의해 만들어진 script를 실행(Stored procedure의 개념?)
    • Write는 not yet, data 가공용도로 활용

  • Sawzall
    • Google 만든 script 언어
    • Aggregation 관련 처리를 병렬로 쉽게 해주는 기능
    • DB용 Map&Reduce API ??
    • MapReduce의 input, output target으로 사용
    • C++ Sample code


    • Sawzall Sample code



4.Building Blocks
  • Google File System
    • Data, log 파일 저장

  • Cluster Management System
    • 다른 Application이 수행되는 서버에서도 수행

  • SSTable
    • Bigtable이 저장되는 file format
    • Data 조회를 위해 Single disk access 처리를 위해 design
    • ordered immutable map
      Immutable : 한번 저장된 값은 변경되지 않는다. 삭제는 가능, Read only와는 다른 개념
      Map : key, value 쌍으로 저장. Key를 이용하여 value 조회
    • SSTable은 여러 개의 block으로 구성(64KB)
      block index 정보는 SSTable의 마지막에 저장
      SSTable이 open 될 때 block index가 메모리로 로딩


  • Chubby
    • Distributed Lock Service
    • 5개의 active한 replica 운영, 1개만 실제 서비스(Failure에 대비해서 sync를 맞추는 것은 Paxos 알고리즘 사용)
    • File과 directory에 대한 namespace 제공, 이 파일을 이용하여 lock service 제공
    • Chubby Server는 client와 session 메커니즘을 이용
      Session expire 시 해당 client가 소유한 모든 lock은 해제
      Client는 server에 특정 lock event에 대한 callback 등록 가능
    • Bigtable에서의 활용
      Bigtable master가 여러 개 수행되는 것을 방지
      Bigtable data의 bootstrap 정보를 저장
      Tablet server를 찾거나 Tablet server의 death를 결정
      Bigtable의 schema 정보를 저장
    • Chubby Service가 일정 시간 이상 unavailable 시 Bigtable 역시 unavailable

  • Bigtable 관련 구성요소




5.Implementation
  • Tablet
    • 큰 테이블을 row를 경계로 해서 분리한 것
    • 하나의 Tablet 내에 있는 row는 일관된 순서를 가진다.
    • Tablet하나의 사이즈는 100 ~ 200 MB


  • Bigtable 구성
    • Client library, one master server, many tablet servers

  • Master server
    • Tablet Server에서 관리할 Tablet을 할당
    • 새로 추가되거나 expire 된 tablet server 탐색
    • Tablet server에 대한 로드 밸런싱
    • GFS내 있는 파일(SSTable)의 Garbage Collection 수행
    • Schema change 관리

  • Tablet Server
    • 하나의 tablet server가 10 ~ 수천 개의 tablet 관리
    • 데이터에 대한 read/write operation 수행
    • Tablet split 수행
    • Client는 데이터 처리를 위해 master를 경유하지 않는다

  • Tablet location
    • client는 tablet을 서비스 하고 있는 tablet server를 lookup.
    • Client tablet server의 location에 대해 cache를 가지고 있다.
      cache에 존재하지 않을 경우 max 3번 통신
      cache miss인 경우 max 6번 통신
    • METADATA는 모두 memory에 로딩
    • METADATA Tablet에 event log 정보도 같이 기록




  • Tablet Assignment하나의 tablet은 하나의 tablet server에 할당
    (tablet server의 down time 동안에는 어떻게 서비스 하는가?
    Tablet 재 할당에는 어느정도 시간 소요?)
  • Master는 active한 tablet server의 목록, tablet server-tablet 정보, 할당되지 않은 tablet 정보를 관리
    할당되지 않는 tablet은 여유가 있는 tablet server에 할당
    Tablet server의 정보를 관리하기 위해 Chubby 이용
  • Tablet Server, Master Server 모두 chubby Server에 접근하지 못할 경우 자신을 kill
    Tablet Server의 down을 감지한 master server는 tablet을 다른 tablet server에 할당
    Tablet Server가 새로 시작된 경우 Master Server는 이를 감지하여 tablet server에 tablet 할당
    Cluster Management System이 master server를 재 시작
    Master server가 down되도 data service에는 문제 없음

  • 전체 구성


  • 운영중 상태



  • Tablet Serving & Compaction


    • ※ memtable에 정해진 크기가 만큼 데이터가 쌓이면 다음과 같은 순서로 SSTable 생성(minor comapction)
    - 기존 memtable lock
    - 새로운 memtable 생성
    - 새로운 memtable로 계속 서비스
    - 기존 memtable의 정보를 SSTable에 저장(백그라운드)
    - 기존 memtable 메모리에서 제거

    - server 복구 시 빠른 복구
    - SSTable 생성 시에도 계속 서비스
    - 메모리 절약

    ※ major compaction
    - minor compaction에서 생성된 많은 SSTable을 하나의 SSTable로 합치는 작업
    - 너무 많은 SSTable은 Read OP시 merge 작업이 복잡
    - 삭제된 정보까지 SSTable에 포함 → 이때 GC 수행


6.Refinements
  • Locality group
    • 같이 사용되는 정보끼리 묶어서 관리

  • 효율적인 data read
    • 자주 사용되는 데이터는 memory에 로딩되도록 구성(예: METADATA tablet)

  • Compression
    • 특정 locality group에는 데이터 압축 적용
    • SSTable의 block 단위로 압축을 적용할 수 있다.
    • Google의 경우 WebTable의 Web Page content를 압축하여 사용
    • Caching for read performance
      Tablet servers use 2 level cache
      - Scan Cache : Tablet Server ↔ SSTable
      - Block Cache : SSTable block↔ GFS

  • Bloom filters
    • SSTable이 메모리에 없는 경우 read시 많은 disk access 발생
    • Bloom filter는 메모리 내에서 SSTable이 client가 원하는 정보를 가지고 있는지를 확인해준다.

  • Commit-log implementation
      Commit-log는 tablet의 write op시 저장
    • Tablet Server에 하나의 commit-log 파일만 관리
      Tablet별로 commit-log 파일이 필요
      Commit-log 파일은 GFS 상에 저장되기 때문에 많은 commit-log 파일 관리를 위해서는 여러 파일 서버를 거쳐야 한다.
      여러 tablet에 걸쳐 있는 group commit 처리 시 속도 저하
    • 하나의 Commit-log 파일을 이용한 복구
      Tablet server 장애 시 서비스 중인 많은 tablet이 다른 tablet server에 할당
      할당된 tablet server 모두 commit-log 파일 필요(비 효율적)
      Commit-log 파일 내에서 sorted 된 형태로 저장(어떻게??)
    • tablet server는 commit-log 파일 저장을 위해 두 개의 thread 운영
      GFS latency 발생에 대비.
      하나의 thread에 latency 발생 시 다른 thread가 수행

  • Speeding up tablet recovery
    • Master가 tablet을 다른 tablet에서 할당할 경우 빠른 recovery 보장 방법
      Source tablet server는 minor compaction을 수행, Commit-log 파일을 이용한 redo 작업을 수행하지 않게 한다.
      Source tablet server는 tablet service를 중지하기 전에 한번 더 minor compaction을 수행한다.
      앞에서의 minor compaction 수행 후 발생한 변경 분에 대해서만 수행
      Target tablet server에 할당

  • Exploiting immutability
  • SSTable은 immutable이기 때문에 시스템 구성을 간단하게 할 수 있다.
    동기화 문제 등을 쉽게 해결
  • Memtable만 유일하게 conflict 상황 발생
    Copy-on-write를 통해 write 중에 read 가능


크리에이티브 커먼즈 라이센스
Creative Commons License

Posted by 김형준

Response
No Trackback , 4 Comments

Trackback URL : http://www.jaso.co.kr/trackback/107

Comments List

  1. typos 2006/09/21 14:04 # M/D Reply Permalink

    찾아보기 힘들 글을 봅니다. 잘 볼께요..

  2. 고감자 2006/10/27 00:33 # M/D Reply Permalink

    오늘 세미나 잘 들었습니다. ^^
    정리하고 피드백 꼭 해드리겠습니다.

    1. 김형준 2006/10/27 08:11 # M/D Permalink

      도움이 되었다니 다행입니다.
      앞으로 계속 좋은 자리 만들었으면 합니다.

  3. 비밀방문자 2006/10/27 09:42 # M/D Reply Permalink

    관리자만 볼 수 있는 댓글입니다.

Leave a comment
« Previous : 1 : ... 267 : 268 : 269 : 270 : 271 : 272 : 273 : 274 : 275 : ... 347 : Next »