# 7-1 Bigtable: A Distributed Storage System for Structured Data

## Introduction
:::info
Bigtable的目標:
* wide applicability
* scalibility
* high performance
* high availability
:::

* Bigtable使用在Goolge使用產品及專案上
* Google Analytics
* Google Finance
* Orkut
* Personalized Search
* Writely
* Google Earth
* Bigtable不支援全關聯式資料模型，而是提供簡單的資料模型，來動態的對資料布局和格式進行控制，也允許client推斷底層存儲中表示的資料的局部性屬性
* 其Schema能讓client動態控制從記憶體還是磁碟來提供資料

## Data Model
* Bigtable是一個spare, distributed, persistent multi-dimensional sorted map
* **透過row key, coloumn key, timestamp來做索引的**
* 每個值都是未解釋的array of bytes
* e.g. (row:string, column:string, time:int64) → string
* 以下圖範例簡稱Webtable, table中會用URL做row key, 使用網頁的各部分作為column name, 來儲存網頁的content
* 
### Row
* row key是任意字串，目前大小限制是64KB
* **對於一個row key下的讀寫都是原子性操作**
* 表格中的row範圍是動態劃分的，每個row範圍稱為tablet，為一個分配和負載均衡的單位
### Column Families
* **column keys會被分組到column family的集合中，是一個基本的訪問控制單元**
* 每個column family的數據類型相同
* 必須在儲存column key下的數據前創建column family
* 希望table中column family數量少(最多數百個)，且在操作期間很少改變，相對的一個table裡面則可以有無限量的column
### Timestamps
* **Bigtable中每個單位格中可以包含很多版本的相同數據，版本透過timestamp來索引**
* timestamp型態為int64，必須唯一
* 單元格會透過timestamp降序排序，優先讀取最新版本
* 為避免數據管理負擔，會自動丟掉舊的版本，用戶可以指定只保留最新的n個版本
* Webtable範例中contents則只保留最新的三種版本
## API
* 提供新增刪除table和column family，也提供更換cluster, table, column family metadata
* client可以寫入或刪除Bigtable中的值，透過rows來查值，或者迭代table中的某一部分
* e.g.
* 
* 此範例對webtable加入一個anchor到www.cnn.com再刪除一個anchor
* 使用者可以迭代很多個column family，也具有很多機制可以限制rows, columns, timestamp
* e.g.
* 
* 此範例透過Scanner來迭代特定row的所有anchors
* Bigtable也支援很多feature讓client更複雜的操控數據
* single-row transaction，對於單個row key下做原子性的操作
* counter，允許單元格作為整數的計數器使用
* client-supplied script: 可執行client提供的腳本
* Bigtable可以和MapReduce集成一起使用
## Building Blocks
* Google File System:
* Bigtable使用Google File System(GFS)來儲存log和data files
* SSTable:
* Bigtable內部使用Google SSTable文件格式來儲存數據
* SSTable是一個持久，有序的不可變map from keys to value，key和value都是任意byte strings
* 查找操作可以通過一次disk查找完成: 會先在memory的index中透過binary search找到區塊，再從disk讀取該區塊
* Chubby
* Bigtable使用high-available的persistent distributed lock服務Chubby
* Chubby由五個活躍replica組成，其中一個被選為master來處理請求
* Chubby使用Paxos來保持一致性
* **Chubby的任務:**
* 確保最多一個master
* 儲存Bigtable data的啟動位置
* 發現tablet server和finalize table server死亡
* 儲存Bigtable schema
* 儲存訪問控制列表
* 如果Chubby長時間無法使用，Bigtable也將不可用
## Implementation
:::info
主要組件
* client library
* 一個master server
* 多個tablet server
* Tablet伺服器可以動態添加或移除以適應工作負載的變化
:::
* 職責:
* master server:
* 分配tablets給tablet server
* 檢測和重新分配失效的tablet server
* load balancce
* 管理架構變更(如table和column family的創建)
* tablet server:
* 處理tablet讀寫請求
* 分割過大的tablets
* client和server之間直接通訊，master server不會參與
* 一個table由多個tablet組成，每個tablet包含row範圍內所有數據
* table增長時會自動切割為多個tablet
### Table location
* 三層結構來儲存tablet位置訊息，可能要地回查找
* root tablet位置存在Chubby中
### Table assignment
* 每個tablet分配給一個tablet server
* master server監控和分配tablet，檢測並處理tablet server的失效
### Tablet serving
* Tablet狀態存在GFS中，更新到commit log，最近的更新會在memtable，較舊的會在SSTable中
* write檢查格式和授權後會寫入commit log，並插入memtable
* read會在合併SSTables和memtable視圖中執行
* 
### Compactions
* 當memtable到達一個threshold後，會轉換成SSTable並寫入GFS
* 定期進行合併壓縮，將多個SSTable和memtable合併為一個新的SSTable
## Refinements
* Locality Groups
* 將相關column family分組，提高讀取效率
* 可設定為在memory中來提高讀取效率
* Compression
* 雙重壓縮方案（Bentley和McIlroy算法+快速壓縮）提高壓縮比
* Webtable中壓縮比可達10:1
* Caching for Read Performance
* 使用兩個cache: Scan Cache和Block Cache
* 提升重複讀取和相鄰數據讀取的效率
* Bloom Filter
* 使用此fileter減少disk讀取次數
* Commit-log implementation
* 將所有變更紀錄在一個commit log
* Speeding up tablet recovery
* 移動tablet前進行壓縮，減少恢復時間
* Exploiting Immutability
* SSTable不可變，簡化併發控制和垃圾回收
## Performance Evaluation
:::info
* 透過實驗，Bigtalbe展現了很好的性能和擴展性，能夠有效處理不同的讀寫操作
* 隨著server數量增加，性能明顯提升，但會受到網路bandwidth和CPU限制
:::
## Conclusions
* Bigtable用於管理結構化數據，目標擴展到PB數據級別和數千台機器上
* 用戶反饋喜歡Bigtable的性能和高可用性
* 但新用戶會不熟悉於Bigtable介面
* Bigtable優勢:
* 自行設計和實作具有很大的靈活性
* 能夠控制Bigtable的實作及依賴其他的Google基礎服務，在瓶頸和低效出現時進行優化和改建
* future work: 支持二級index，將bigtable部署為服務