BigTable

From Big Data Analytics Lab

Bigtable: A Distributed Storage System for Structured Data

Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Michael Burrows, Tushar Chandra, Andrew Fikes, Robert E. Gruber: Bigtable: A Distributed Storage System for Structured Data. ACM Trans. Comput. Syst. 26(2): (2008)
Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Michael Burrows, Tushar Chandra, Andrew Fikes, Robert Gruber: Bigtable: A Distributed Storage System for Structured Data (Awarded Best Paper!). OSDI 2006: 205-218

Introduction

  • 2003년 후반부터 개발
  • Design goals: wide applicability, scalability, high performance, high availability
  • throughput 위주의 batch processing 부터 latency-sensitive한 data 처리까지 다양한 workload를 요하는 여러 Google product에서 사용.
  • database와의 차이점
    • full relational data model을 지원하지 않음. data layout과 format에 대한 dynamic control이 가능한 simple model.
    • client가 storage에서 제공하는 locality 성질을 고려하도록 허용.
    • data는 string인 row와 column 이름으로 인덱스됨. data는 uninterpreted string으로 처리.
  • 스키마 파라미터로 데이터를 디스크에서 serve할지 메모리에서 serve할지 dynamic control 가능

Data Model

  • cluster: Bigtable SW를 실행하는 프로세스들의 집합. table의 집합을 serving.
  • table: sparse, distributed, persistent multidimensional sorted map
  • cell: row key, column key, timestamp로 reference되는 storage
    • (row:string, column:string, time:int64) -> string
  • row들은 묶여서 load balancing의 단위가 됨. column들은 묶여서 access control과 resource accounting의 단위가 됨.
  • 예로 사용할 Webtable

A slice of an example table that stores Web pages

Rows

  • key: 임의의 string. 보통 10-100bytes. 64KB까지 가능.
  • single row key 하에 있는 데이터의 read/write 는 atomic. (column 수와 무관)
  • Bigtable은 row key를 lexicographic order로 정렬하여 데이터를 유지.
  • 한 table의 row range는 동적으로 partition됨.
  • tablet: 각 row range를 가리킴. distribution과 load balancing의 단위가 됨.
    • short row range에 대한 read는 적은 수의 머신과만 통신하게 되므로 효율적.
    • 이런 성질을 잘 이용하게끔 row key를 선택하면 효과적이다.
      • e.g., Webtable에서 URL의 hostname component를 뒤집어서 저장. (maps.google.com -> com.google.maps)
      • 이렇게 하면 같은 도메인(*.google.com)에 속한 row들이 모여 있게 되므로 효과적.

Implementation

Compactions

Compactions

  • minor compaction: memtable의 크기가 threshold를 넘으면 새 memtable을 만들고 기존 것은 frozen memtable로 만든 뒤 SSTable로 변환하여 GFS에 write.
    • tablet 서버의 메모리 사용량을 줄이고, recovery time을 짧게 하는 효과.
  • merging compaction: background로 주기적으로 여러 개의 SSTable이 있으면 merge를 수행.
    • read operation이 읽을때 merge하는 오버헤드를 없앰.
  • major compaction: 모든 SSTable들을 하나의 SSTable로 rewrite하는 것. 지워진 데이터 및 정보가 없는 SSTable을 만든다. 정기적으로 모든 tablet을 돌면서 수행.
    • 지워진 데이터의 resource 반환. sensitive data를 남기지 않고 완전히 지우는 효과.
  • GFS 서버와 Bigtable tablet 서버가 같이 떠 있는 경우 locality optimization. 자신의 노드에 있는 SSTable을 compaction.