Introduction? 簡介

Data Model? 數據模型

Rows? 行

Column Families? 列族

Timestamps? 時間戳

Bigtable數據模型知識整理

Bigtable架構

---

前言

最近在看Bigtable的論文，其中的數據模型這部分一直沒有很好的理解。現在先將論文中的部分原文展示出來，并附上中文翻譯。之后是自己對Bigtable數據模型知識的整理。

?

Introduction? 簡介

In many ways, Bigtable resembles a database: it shares?many implementation strategies with databases. Parallel databases?and main-memory databases have?achieved scalability and high performance, but Bigtable?provides a different interface than such systems. Bigtable?does not support a full relational data model; instead, it?provides clients with a simple data model that supports?dynamic control over data layout and format, and allows clients to reason about the locality properties of the?data represented in the underlying storage.?Data is indexed using row and column names that can be arbitrary?strings. Bigtable also treats data as uninterpreted strings,although clients often serialize various forms of structured and semi-structured data?into these strings. Clients?can control the locality of their data through careful?choices in their schemas. Finally, Bigtable schema parameters let clients dynamically control whether to serve?data out of memory or from disk.

在很多方面，Bigtable和數據庫很類似：它使用了很多數據庫的實現策略。并行數據庫和內存數據庫已經具備可擴展性和很高的性能，但是Bigtable提供了一個和這些系統完全不同的接口。Bigtable不支持完整的關系數據模型；與之相反，Bigtable為客戶提供了簡單的數據模型，利用這個模型，客戶可以動態控制數據的分布和格式，用戶也可以自己推測底層存儲數據的位置相關性。數據的下標是行和列的名字，名字可以是任意的字符串。Bigtable將存儲的數據都視為字符串，但是Bigtable本身不去解析這些字符串，客戶程序通常會在把各種結構化或者半結構化的數據串行化到這些字符串里。通過仔細選擇數據的模式，客戶可以控制數據的位置相關性。最后，可以通過Bigtable的模式參數來控制數據是存放在內存中、還是硬盤上。

?

Data Model? 數據模型

A Bigtable is a sparse, distributed, persistent multidimensional sorted map.?The map is indexed by a row?key, column key, and a timestamp;?each value in the map?is an uninterpreted array of bytes。(row:string, column:string, time:int64) → string

Bigtable是一個稀疏的、分布式的、持久化存儲的多維度排序Map。Map的索引是行關鍵字、列關鍵字以及時間戳；Map中的每個value都是一個未經解析的字符串。(row:string, column:string,time:int64)->string

We settled on this data model after examining a variety?of potential uses of a Bigtable-like system. As one concrete example that drove some of our design decisions,suppose we want to keep a copy of a large collection of?web pages and related information that could be used by?many?different projects; let us call this particular table?the Webtable. In Webtable, we would use URLs as row?keys, various aspects of web pages as column names, and?store the contents of the web pages in the contents: column under the timestamps when they were fetched, as?illustrated in Figure 1.

我們仔細分析了一個類似Bigtable的系統的種種潛在用途之后，決定使用這個數據模型。先舉個具體的例子，這個例子促使我們做了很多設計決策；假設我們想要存儲海量的網頁及相關信息，這些數據可以用于很多不同的項目中，我們稱這個特殊的表為Webtable。在Webtable里，我們使用URL作為行關鍵字，使用網頁的某些屬性作為列名，網頁的內容存在"contents:"列中，并用獲取該網頁的時間戳作為標識，如圖一所示。

Figure 1: A slice of an example table that stores Web pages. The row name is a reversed URL. The contents column family contains the page contents, and the anchor column family contains the text of any anchors that reference the page. CNN’s home page?is referenced by both the Sports Illustrated and the MY-look home pages, so the row contains columns named anchor:cnnsi.com?and anchor:my.look.ca. Each anchor cell has one version; the contents column has three versions, at timestamps t3, t5, and t6。

圖一：Webtable例子中的片斷。行名是一個反向URL。contents列族存放的是網頁的內容，anchor列族存放引用該網頁的錨鏈接文本。CNN的主頁被Sports Illustrater和MY-look的主頁引用，因此該行包含了名為"anchor:cnnsi.com"和 "anchor:my.look.ca"的列。每個錨鏈接只有一個版本（時間戳標識了列的版本，t9和t8分別標識了兩個錨鏈接的版本）；而contents列則有三個版本，分別由時間戳t3，t5，和t6標識。

?

Rows? 行

The row keys in a table are arbitrary strings (currently up?to 64KB in size, although 10-100 bytes is a typical size?for most of our users). Every read or write of data under?a single row key is atomic (regardless of the number of?different columns being read or written in the row), a?design decision that makes it easier for clients to reason?about the system’s behavior in the presence of concurrent?updates to the same row.

Bigtable maintains data in lexicographic order by row?key. The row range for a table is dynamically partitioned.Each row range is called a tablet, which is the unit of distribution and load balancing.?As a result, reads of short?row ranges are efficient and typically require communication with only a small number of machines. Clients?can exploit this property by selecting their row keys so?that they get good locality for their data accesses. For?example, in Webtable, pages in the same domain are?grouped?together into contiguous rows by reversing the?hostname components of the URLs. For example, we?store data for maps.google.com/index.html under the key com.google.maps/index.html. Storing pages from?the same domain near each other makes some host and?domain analyses more efficient.

表中的行關鍵字可以是任意的字符串（目前支持最大64KB的字符串，但是對大多數用戶，10-100個字節就足夠了）。對同一個行關鍵字的讀或者寫操作都是原子的（不管讀或者寫這一行里多少個不同列），這個設計決策能夠使用戶很容易的理解程序在對同一個行進行并發更新操作時的行為。

Bigtable通過行關鍵字的字典順序來組織數據。表中的每個行都可以動態分區。每個分區叫做一個"Tablet"， Tablet是數據分布和負載均衡調整的最小單位。這樣做的結果是，當操作只讀取行中很少幾列的數據時效率很高，通常只需要很少幾次機器間的通信即可完成。用戶可以通過選擇合適的行關鍵字，在數據訪問時有效利用數據的位置相關性，從而更好的利用這個特性。舉例來說，在Webtable里，通過反轉URL中主機名的方式，可以把同一個域名下的網頁聚集起來組織成連續的行。具體來說，我們可以把maps.google.com/index.html的數據存放在關鍵字com.google.maps/index.html下。把相同的域中的網頁存儲在連續的區域可以讓基于主機和域名的分析更加有效。

?

Column Families? 列族

Column keys are grouped into sets called column families, which form the basic unit of access control. All data?stored in a column family is usually of the same type (we?compress data in the same column family together). A?column family must be created before data can be stored?under any column key in that family; after a family has?been created, any column key within the family can be?used. It is our intent that the number of distinct column families in a table be small (in the hundreds at most), and?that families rarely change during operation. In contrast,a table may have an unbounded number of columns.

A column key is named using the following syntax:family:qualifier. Column family names must be printable, but?qualifiers may be arbitrary strings. An example column family for the Webtable is language, which?stores the language in which a web page was written. We?use only one column key in the language family, and it?stores each web page’s language ID. Another useful column family for this table is anchor; each column key in?this family represents a single anchor, as shown in Figure 1. The qualifier is the name of the referring site; the?cell contents is the link text.

Access control and both disk and memory accounting are performed at the column-family level. In our?Webtable example, these controls allow us to manage?several different types of applications: some that add new base data, some that read the base data and create derived?column families, and some that are only allowed to view?existing data (and possibly not even to view all of the?existing families for privacy reasons).

列關鍵字組成的集合叫做"列族"，列族是訪問控制的基本單位。存放在同一列族下的所有數據通常都屬于同一個類型（我們可以把同一個列族下的數據壓縮在一起）。列族在使用之前必須先創建，然后才能在列族中的任何一列關鍵字下存放數據；列族創建后，其中的任何一個列關鍵字下都可以存放數據。根據我們的設計意圖，一張表中的列族不能太多（最多幾百個），并且列族在運行期間很少改變。與之相對應的，一張表可以有無限多個列。

列關鍵字的命名語法如下：列族：限定詞。?列族的名字必須是可打印的字符串，而限定詞的名字可以是任意的字符串。比如，Webtable有個列族language，language列族用來存放撰寫網頁的語言。我們在language列族中只使用一個列關鍵字，用來存放每個網頁的語言標識ID。Webtable中另一個有用的列族是anchor；這個列族的每一個列關鍵字代表一個錨鏈接，如圖一所示。Anchor列族的限定詞是引用該網頁的站點名；Anchor列族每列的數據項存放的是鏈接文本。

訪問控制、磁盤和內存的使用統計都是在列族層面進行的。在我們的Webtable的例子中，上述的控制權限能幫助我們管理不同類型的應用：我們允許一些應用可以添加新的基本數據、一些應用可以讀取基本數據并創建繼承的列族、一些應用則只允許瀏覽數據（甚至可能因為隱私的原因不能瀏覽所有數據）。

?

Timestamps? 時間戳

Each cell in a Bigtable can contain multiple versions of?the same data; these versions are indexed by timestamp.Bigtable timestamps are 64-bit integers. They can be assigned by Bigtable, in which case they represent "real?time" in microseconds, or be explicitly assigned by client?applications. Applications that need to avoid collisions?must generate unique timestamps themselves. Different?versions of a cell are stored in decreasing timestamp order, so that the most recent versions can be read first.

To make the management of versioned data less onerous, we support two per-column-family settings that tell?Bigtable to garbage-collect cell versions automatically.The client can specify either that only the last n versions?of a cell be kept, or that only new-enough versions be?kept (e.g., only keep values that were written in the last?seven days).

In our Webtable example, we set the timestamps of?the crawled pages stored in the contents: column to?the times at which these page versions were actually?crawled. The garbage-collection mechanism described?above lets us keep only the most recent three versions of?every page.

在Bigtable中，表的每一個數據項都可以包含同一份數據的不同版本；不同版本的數據通過時間戳來索引。Bigtable時間戳的類型是64位整型。Bigtable可以用精確到毫秒的"實時"時間給時間戳賦值；用戶程序也可以給時間戳賦值。如果應用程序需要避免數據版本沖突，那么它必須自己生成具有唯一性的時間戳。數據項中，不同版本的數據按照時間戳倒序排序，即最新的數據排在最前面。

為了減輕多個版本數據的管理負擔，我們對每一個列族配有兩個設置參數，Bigtable通過這兩個參數可以對廢棄版本的數據自動進行垃圾收集。用戶可以指定只保存最后n個版本的數據，或者只保存“足夠新”的版本的數據（比如，只保存最近7天的內容寫入的數據）。

在Webtable的例子里，contents:列存儲的時間戳信息是網絡爬蟲抓取一個頁面的時間。上面提及的垃圾收集機制可以讓我們只保留最近三個版本的網頁數據。

?

Bigtable數據模型知識整理

Bigtable不是關系型數據庫，但是卻沿用了很多關系型數據庫的術語，像table（表）、row（行）、column（列）等。Bigtable用于存儲關系較為復雜的半結構化數據。數據大致可以分為以下三類：

非結構化數據：包括所有格式的辦公文檔、文本、圖片、圖像、音頻和視頻信息等。

結構化數據：一般存儲在關系數據庫中，可以用二維關系表結構來表示。結構化數據的模式(Schema，包括屬性、數據類型以及數據之間的聯系)和內容是分開的，數據的模式需要預先定義。

半結構化數據：介于非結構化數據和結構化數據之間，HTML文檔就屬于半結構化數據。它一般是自描述的，與結構化數據最大的區別在于，半結構化數據的模式結構和內容混在一起，沒有明顯的區分，也不需要預先定義數據的模式結構。

本質上說，Bigtable是一個鍵值（key-value）映射。按作者的說法，Bigtable是一個稀疏的，分布式的，持久化的，多維的排序映射。Bigtable的鍵有三維，分別是行鍵（row key）、列鍵（column key）和時間戳（timestamp），行鍵和列鍵都是字節串，時間戳是64位整型；而值是一個字節串。

與二維關系表結構不同的是，Bigtable的鍵是三維的。二維表就像日常生活中遇到的普通表格或數據庫中的表格，根據行列就能找到信息，而且行列唯一確定一條信息。三維結構更像圖書館里的一個書架，行列可以確定書架上的一個空間(圖書館的書架上相鄰空間放的都是一類書，由上文可知，在Bigtable里，"類似的"數據也是放的很近的)，而不能唯一的確定某一本書。時間戳給用戶介紹了這些書的"順序"，用戶可以根據順序拿到自己想要的那本書。例如，圖一的t5就可以理解成從左至右第5本書。

行鍵可以是任意字節串，行的讀寫都是原子性的。Bigtable按照行鍵的字典序存儲數據。Bigtable的表會根據行鍵自動劃分為片（tablet），片是負載均衡的單元。最初表都只有一個片，但隨著表不斷增大，片會自動分裂，片的大小控制在100-200MB。Bigtable將多個列組織成列族，這樣，列名由兩個部分組成：(column family，qualifier)。列族是Bigtable中訪問控制的基本單元，也就是說，訪問權限的設置是在列族這一級別上進行的。Bigtable中的列族在創建表格的時候需要預先定義好，個數也不允許過多；然而，每個列族包含哪些qualifier是不需要預先定義的。

在看Bigtable相關的知識時，最先讓我感到奇怪的就是Bigtable三維結構的鍵。因為我們一般使用的Map存儲一維的數據，就算是數據庫里的表也只有二維而已。這種多維的結構讓我想起了操作系統中的多級頁表(建立索引，優點是不用占據內存太多空間，也能管理足夠多的數據，也不用盲目地順序查找頁表項)。

由Bigtable的定義可知，它的行、列和時間戳都是索引。行是表的第一級索引，可以把該行的列、時間戳和value看成一個整體(結構1)，簡化為一維鍵值映射，類似于：

table{"11111" : {結構1},//行1"aaaaa" : {結構1},//行2"bbbbb" : {結構1},//行3"asdaa" : {結構1},//行4"zzzzz" : {結構1} //行5 }

?

列是第二級索引，每行擁有的列是不受限制的，可以隨時增加減少。特點：一個列族里的列一般存儲相同類型的數據。一行的列族很少變化，但是列族里的列可以隨意添加刪除。列鍵按照family:qualifier格式命名。這次將列拿出來，將時間和value看成一個整體(結構2)，簡化為二維鍵值映射，類似于：

table{// ..."aaaaa" : { //行1"A:foo" : {結構2},//列1，列族名為A，列名是foo"A:bar" : {結構2},//列2，列族名為A，列名是bar"B:" : {結構2} //列3，列族名為B，但列名是空字串}，"bbbbb" : { //行2"A:foo" : {結構2},//列1，列族名為A，列名是foo"B:asd" : {結構2} //列2，列族名為B，列名是asd}，// ... }

?

時間戳是第三級索引。Bigtable允許保存數據的多個版本，版本區分的依據就是時間戳。數據的不同版本按照時間戳降序存儲，因此先讀到的是最新版本的數據。加入時間戳后，就得到了Bigtable的完整數據模型，類似于：

table{// ..."aaaaa" : { //行"A:foo" : { //列16 : "y", //版本15 : "m" //版本2},"A:bar" : { //列215 : "d", //版本1},"B:" : { //列312 : "w"， //版本110 : "o"， //版本29 : "w" //版本3}},// ... }

查詢時，如果只給出行列，那么返回的是最新版本的數據；如果給出了行列時間戳，那么返回的是時間小于或等于時間戳的數據。比如，我們查詢 "aaaaa"/"A:foo"/6，返回的值是 "y"；查詢 "aaaaa"/"A:foo"/5，返回的結果就是 "m"；查詢 "aaaaa"/"A:foo"/2，返回的結果是空。圖 1 中 "contents:" 列下保存了網頁的三個版本，我們可以用 ("com.cnn.www", "contents:", t5) 來找到 CNN 主頁在 t5 時刻的內容。

?

Bigtable架構

Bigtable 構建在 GFS 之上，為文件系統增加了一層分布式索引層。另外，Bigtable 依賴 Google 的 Chubby (分布式鎖服務)進行服務器選舉及全局信息維護。

如圖，Bigtable 將大表劃分為大小在 100-200MB 的子表(tablet)，每個子表對應一個連續的數據范圍。Bigtable 主要由三個部分組成：客戶端程序庫(Client)、一個主控服務器(Master)和多個子表服務器(Tablet Server)。

客戶端程序庫(Client)：提供 Bigtable 到應用程序的接口，應用程序通過客戶端程序庫對表格的數據單元進行增、刪、查、改等操作。客戶端通過 Chubby 鎖服務獲取一些控制信息，但所有表格的數據內容都在客戶端與子表服務器之間直接傳送；

主控服務器(Master)：管理所有的子表服務器，包括分配子表給子表服務器，指導子表服務器實現子表的合并，接受來自子表服務器的子表分裂消息，監控子表服務器，在子表服務器之間進行負載均衡并實現子表服務器的故障恢復等。

子表服務器(Tablet Server)：實現子表的裝載/卸出、表格內容的讀和寫，子表的合并和分裂。Table Server 服務的數據包括操作日志以及每個子表上的 Sstable 數據，這些數據存儲在底層的 GFS 中。

Bigtable 依賴于 Chubby 鎖服務完成如下功能：

(1) 選取并保證同一時間內只有一個主控服務器；

(2) 存儲 Bigtable 系統引導信息；

(3) 用于配合主控服務器發現子表服務器加入和下線；

(4) 獲取 Bigtable 表格的 schema 信息及訪問控制信息。

Chubby 是一個分布式鎖服務，底層的核心算法為 Paxos。Paxos 算法的實現過程需要一個 "多數派"?就某個值達成一致，進而才能得到一個分布式一致性狀態。也就是說，只要一半以上的節點不發生故障，Chubby 就能夠正常提供服務。Chubby 服務部署在多個數據中心，典型的部署為兩地三數據中心五副本，同城的兩個數據中心分別部署兩個副本，異地的數據中心部署一個副本，任何一個數據中心整體發生故障都不影響正常服務。

Bigtable 包含三種類型的表格：用戶表、元數據表和根表。其中，用戶表存儲用戶實際數據；元數據表存儲用戶表的元數據；如子表位置信息、Sstable 及操作日志文件編號、日志回放點等，根表用來存儲元數據表的元數據；根表的元數據，也就是根表的位置信息，又稱為 Bigtable 引導信息，存放在 Chubby 系統中。客戶端、主控服務器以及子表服務器執行過程中都需要依賴 Chubby 服務，如果 Chubby 發生故障，Bigtable 系統整體不可用。

?

參考：

《大規模分布式存儲系統》

Bigtable論文：A Distributed Storage System for Structured Data

Bigtable論文翻譯：https://blog.csdn.net/qq_38289815/article/details/89959074

總結

以上是生活随笔為你收集整理的Bigtable数据模型和架构的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。