一、Bigtable的设计目标
Bigtable是Google在2006年发表的分布式结构化存储系统论文中描述的系统。它不是一个关系型数据库，而是一个稀疏的、分布式的、持久化的多维有序映射（Sparse, Distributed, Persistent Multidimensional Sorted Map）。Google的许多核心产品都构建在Bigtable之上：Web索引（存储爬虫抓取的网页内容和链接关系）、Google Earth（卫星图像瓦片数据）、Google Analytics（用户行为统计数据）、Google Finance（股票历史数据）。
Bigtable的设计目标与关系型数据库截然不同。第一，它面向海量数据（PB级别）进行扩展，数据分布在数千台机器上。第二，它不支持完整的关系模型——没有连接操作（JOIN）、没有外键约束、没有多行事务（仅支持单行原子操作）。第三，它提供灵活的列式数据模型，允许每一行有不同的列，列可以在运行时动态创建。第四，数据按行键的字典序有序存储，相邻的行在物理上存储在一起，支持高效的范围扫描。
二、数据模型
Bigtable的数据模型是一个多维有序映射，可以用如下公式表达：
(row:string, column:string, timestamp:int64) -> string |
这三个维度的含义是：
行键（Row Key）：任意字符串，最大64KB。对同一行键的所有读写操作都是原子的（单行事务）。Bigtable按行键的字典序维护数据，行键范围被动态划分为Tablet（数据分片的基本单元）。行键的设计至关重要——良好的行键设计应当考虑访问模式，使得经常一起访问的数据在物理上相邻（如将域名反转后作为行键，com.google.www而不是www.google.com，这样同域名的页面会被分到相邻的行）。
列族（Column Family）：列被组织为列族，列族是访问控制和存储优化的基本单元。列族需要在创建表时预先声明，而列族中的列（称为限定符，Qualifier）可以动态创建。列族的命名语法是family:qualifier，如content:html。一个表通常只有少量的列族（通常不超过几十个），但每个列族可以有无限多个列限定符。同一列族的数据被存储在一起，通常具有相同的压缩和缓存策略。例如，网页表中content列族存储网页的原始HTML，使用Gzip压缩；anchor列族存储锚文本，使用不同的压缩策略；metadata列族存储爬取时间等信息。
时间戳（Timestamp）：Bigtable的每个单元格都可以存储同一数据的多个版本，每个版本由一个64位时间戳标识。时间戳可以由Bigtable自动分配（真实时间）或由客户端指定。数据按时间戳降序排列，最新版本最先被读取。表可以配置自动垃圾回收策略：仅保留最近N个版本，或者仅保留某个时间点之后的版本。
一个典型的网页表示例（实际存储表示）：
row: "com.cnn.www" |
这个例子中，contents:列的限定符为空（直接使用列族名），存储网页的HTML内容。anchor列族有多个限定符（每个引用源网站一个），存储其他网站指向该页面的锚文本。注意com.cnn.www是www.cnn.com的反转形式，使得同域名的页面在存储中相邻。
三、系统架构
Bigtable的架构建立在GFS和Chubby（分布式锁服务）之上：
Master：Bigtable集群有一台Master，负责将Tablet分配给Tablet Server，检测Tablet Server的新增和退出，均衡Tablet Server的负载，垃圾回收GFS上的孤儿文件，管理元数据的变更（如表和列族的创建）。Master不直接存储任何用户数据，也不处理任何客户端的读写请求。
Tablet Server：每个Tablet Server管理一组Tablet（通常十个到上千个）。Tablet Server处理其管理的Tablet的所有读写请求，并在Tablet变大时进行分裂。Tablet Server可以动态地从集群中添加或移除。
Tablet：一个Tablet是某个行键范围内的所有数据。初始时一个表只有一个Tablet，随着数据的增长，Tablet自动分裂——当Tablet的数据量超过阈值（默认约100到200MB），将其二分为两个Tablet。Tablet是负载均衡和数据迁移的基本单位。Master可以在Tablet Server之间迁移Tablet，以实现负载均衡或故障恢复。
Chubby：Chubby是Google的分布式锁服务，基于Paxos一致性算法。Bigtable使用Chubby来确保同一时间只有一台活跃的Master（Master选举）；存储Bigtable数据的自举位置（Root Tablet的位置）；发现Tablet Server并检测其存活性；存储Bigtable的Schema信息（列族定义）。
四、METADATA表与三层索引
Bigtable使用一个三层B+树结构来定位Tablet的位置信息：
第一层：Chubby文件。Chubby中的一个特定文件存储了Root Tablet的物理位置。这是整个定位链的入口，是硬编码在Chubby中的。
第二层：Root Tablet。Root Tablet是METADATA表中的第一个Tablet，存储了所有其他METADATA Tablet的位置。Root Tablet永远不分裂（保证三层结构的确定性）。
第三层：其他METADATA Tablet。每个METADATA Tablet存储了一组用户Tablet的位置信息，包括Tablet的行键范围端点（Start Key和End Key）和对应的Tablet Server地址。METADATA表的行键是table_id + end_row_key，使得查询某个table的某个行键所在的Tablet可以通过一次前缀扫描高效完成。
完整的查询流程：客户端查询行"com.cnn.www"的数据。首先从Chubby获取Root Tablet的位置；查询Root Tablet，获取包含该行范围元数据的METADATA Tablet位置；查询该METADATA Tablet，获取包含该行的用户Tablet的位置；最后，客户端将查询请求发送到该Tablet所在的Tablet Server。客户端会缓存Tablet的位置信息，大多数查询不需要访问METADATA表。如果缓存的地址失效（Tablet被迁移），客户端重新查询METADATA表。
五、底层存储：SSTable与LSM-Tree
Bigtable的底层存储基于SSTable（Sorted String Table）和LSM-Tree（Log-Structured Merge-Tree），这是其实现高写入吞吐量的核心。
SSTable：一个SSTable是一个持久化的、有序的、不可变的键值对文件。一旦写入完成，不再修改。SSTable内部包含一系列块（Block，默认64KB），每个块内存储了有序的键值对。文件末尾有一个块索引（Block Index），记录每个块的最后一个键及其在文件中的偏移量，用于快速定位键所在的块。当需要查找某个键时，将块索引加载到内存，二分查找确定键所在的块，然后将该块从磁盘读取到内存，在块内二分查找目标键。
MemTable：MemTable是Tablet Server内存中的一个可变的、有序的缓冲区。当写请求到达时，数据首先写入一个预写日志（Write-Ahead Log，WAL）——写入GFS（通过Group Commit批量提交），用于故障恢复。然后，数据写入MemTable。MemTable使用内存中的有序数据结构（Google使用跳表（SkipList），LevelDB/RocksDB也使用跳表），将数据按键排序。
Minor Compaction（小型压缩）：当MemTable的大小达到阈值（如64MB），将其冻结为一个不可变的SSTable，写入GFS，然后创建一个新的MemTable接收后续写入。这个操作非常快，因为只是将内存中的有序数据顺序写入磁盘。
Major Compaction（大型压缩）：随着Minor Compaction的不断执行，一个Tablet可能包含数百个SSTable。读取一个键需要检查MemTable以及所有SSTable（从新到旧），读取性能会随着SSTable数量的增加而下降。Major Compaction定期（或当SSTable数量达到阈值时）将MemTable和多个SSTable合并为一个（或少数几个）大的SSTable，在这个过程删除标记为已删除的数据和过期的版本，回收空间。Major Compaction是Bigtable系统中最消耗资源的操作，但它对读取性能和空间回收至关重要。
这种设计——追加写入、延迟合并——就是LSM-Tree的核心思想。LSM-Tree将随机写转化为顺序写（追加日志+顺序写SSTable），在HDD时代提供了远超B+树的写入性能。在SSD时代，虽然随机写性能大大提升，但LSM-Tree的写入放大问题（相同数据被写多次——WAL、MemTable刷写、多次Compaction）成为主要瓶颈。
六、布隆过滤器
Bigtable的读取需要检查所有SSTable以确定一个键是否存在，即使该键不存在于任何SSTable中。如果客户端频繁查询不存在的键，每次查询都需要读取所有SSTable（先从磁盘读取每个SSTable的块索引，再读取数据块），这被称为“读放大”问题。
布隆过滤器（Bloom Filter）解决这个问题。布隆过滤器是一个概率性数据结构，用于回答“某个元素是否在集合中”的问题——它可以确定地告诉你“键不存在”，或者大概率告诉你“键可能存在”（有一定误报率，但不会漏报）。Bigtable在每个SSTable文件上附带一个布隆过滤器。查询键时，先通过布隆过滤器快速判断该SSTable是否可能包含该键：如果布隆过滤器说“不在”，直接跳过该SSTable；如果“可能在”，再进行实际的磁盘读取。
布隆过滤器显著减少了不必要的磁盘I/O。典型的配置中，布隆过滤器的误报率设置为1%，内存开销约为每个键10比特（对应1%的误报率）。对于包含十亿个键的SSTable集合，布隆过滤器约需1.25GB内存（远小于加载所有SSTable的块索引所需的内存）。
七、单行事务与并发控制
Bigtable仅支持单行事务——对同一行键下的所有列的所有操作都是原子的。这大大简化了并发控制的设计。对于需要跨行原子性的应用场景，Google通常在应用层实现（如使用Percolator系统，它在Bigtable之上通过两阶段提交和分布式锁实现了跨行跨表的事务）。
Bigtable使用乐观并发控制（Optimistic Concurrency Control）处理读写冲突。每个Tablet Server维护每一行的读写锁，支持并发读取，写入需要获取行级别的排他锁。由于多数写入是向不同行写入，行级别的锁颗粒度足够细，冲突概率低。
时间戳维度的版本管理也在并发控制中扮演重要角色。客户端可以指定时间戳进行条件写入：“仅当该单元格的最新版本时间戳小于T时，才写入时间戳T的版本”。这类似于CAS（Compare-And-Swap）操作，允许实现简单的乐观锁模式。
八、Column Family与Locality Group
列族（Column Family）是Bigtable实现存储优化的关键抽象。一个表的多个列族可以分别配置不同的存储参数：
Locality Group（局部性组）：可以将多个列族绑定到同一个Locality Group，同一Group的列族数据在物理上存储在相同的SSTable文件中。这意味着访问某个列族时，不会引入其他无关联族的数据I/O。相反，如果两个列族总是一起被访问（如用户画像的多个维度），将它们放在同一个Locality Group中可以减少读取时的文件打开和索引查询次数。
压缩策略：不同的列族可以配置不同的压缩算法。如网页表中，contents列族存储HTML内容，压缩率高（通常5到10倍），可以配置Gzip压缩；language列族存储语言标签字符串（如”en”, “zh-CN”），单个值很短，压缩收益低，可以仅使用Snappy或不压缩。
缓存策略：可以为列族配置是否进行块缓存（Block Cache，缓存从磁盘读取的SSTable数据块）。经常一起顺序扫描的列族（如日志的raw_data）不需要块缓存，因为顺序扫描不会重复访问相同的数据块；而频繁点查的列族（如用户配置）需要块缓存。
In-Memory策略：对于元数据级别的列族（如Root Tablet和METADATA Tablet），可以设置为In-Memory，数据加载时就被全部加载到内存中，消除磁盘读取。
九、Bigtable的开源实现对比
HBase是Bigtable最直接的开源实现，构建在Hadoop生态之上（HDFS替代GFS、ZooKeeper替代Chubby）。HBase与Bigtable的设计基本一致，增加了Coprocessor（类似关系数据库的存储过程和触发器，允许用户在Tablet Server端执行自定义逻辑）、二级索引（通过Coprocessor实现）、Region Splitting策略的可定制化等增强。
Cassandra最初受Bigtable数据模型和Amazon Dynamo的P2P架构的共同影响。Cassandra放弃了Master/Slave架构，采用去中心化的Gossip协议进行节点发现和故障检测，使用一致性哈希进行数据分布。Cassandra的数据模型更接近Bigtable（宽列存储），但分布式架构更接近Dynamo（无Master、最终一致性、可调一致性级别）。Cassandra的写路径使用LSM-Tree（与Bigtable类似），但Compaction策略（Size-Tiered vs Leveled）比Bigtable更丰富。
LevelDB是Google的Jeff Dean和Sanjay Ghemawat开发的单机版LSM-Tree存储引擎，可以被视为Bigtable Tablet Server在单机上的实现。RocksDB是Facebook基于LevelDB的增强版，增加了多线程Compaction、列族支持、布隆过滤器策略优化等，被广泛用作现代分布式数据库（如TiDB、CockroachDB、YugabyteDB）的单节点存储引擎。
十、面试常见追问
问题一：Bigtable为什么选择LSM-Tree而不是B+Tree？
LSM-Tree的核心优势是将随机写转化为顺序写。在Bigtable设计的2004到2006年，主流存储设备是HDD，其随机写性能约为100到200次/秒（受限于寻道时间），而顺序写可达100MB/s以上。这意味着使用B+Tree处理海量随机写入时会严重受限于磁盘寻道。LSM-Tree通过追加写日志和批量刷入有序文件，将随机写全部变成了顺序写，写入吞吐量高出1到2个数量级。当然，LSM-Tree的代价是读放大（需要检查多个SSTable）和写放大（Compaction过程），以及Compaction时的I/O带宽消耗。但在Bigtable的使用场景中，写入吞吐比读取延迟更重要。
问题二：Bigtable如何处理Tablet Server故障？
当Master检测到Tablet Server宕机（通过Chubby的心跳会话超时），Master将该Tablet Server管理的所有Tablet重新分配到其他存活的Tablet Server上。由于Tablet的所有数据已经持久化在GFS上，数据不会丢失。唯一的恢复工作是重放该Tablet的预写日志（WAL）以恢复MemTable中尚未刷写到GFS的数据。Master将WAL文件按Tablet进行拆分和排序，分配给接管Tablet的各个Tablet Server，由它们各自重放相关的日志条目，重建MemTable。这个过程比传统数据库的恢复快得多，因为重放日志的工作被并行到多个Tablet Server上。
问题三：如何设计一个好的Bigtable行键？
行键设计决定了数据访问的效率。第一，避免顺序写入导致的热点——如果行键是单调递增的时间戳，所有新写入会集中在最后一个Tablet上，单个Tablet Server成为瓶颈。解决方案是将时间戳反转，或者使用哈希化的用户ID作为前缀，如user_id_hash + timestamp。第二，将经常一起访问的数据放在相邻的行中——如果经常按用户名查询，行键可以设计为user_id而非域名反转。第三，利用行键的字典序实现高效的扫描——如果经常按时间范围扫描某个用户的数据，行键设计为user_id + timestamp（用户ID在前，时间戳在后）。典型的场景如存储用户操作日志，user_id_1234567890的行键设计使得查询某个用户最近N天的操作只需要一次范围扫描。
