& &&Bigtable&是一个用来管理结构化数据的分布式存储系统，具有很好的伸缩性，能够在几千台应用服务器上处理PB数量级数据。谷歌有许多项目都把数据存储在Bigtable中，包括web indexing,Google Earth, and Google Finance. 这些应用对Bigtable的侧重点不同，但是他们都是海量数据和实时性的应用。尽管需求变化多端，Bigtable很好的提供了一个灵活多变，高性能额解决方案。
INTRODUCTION
& &&在很多方面Bigtable都与数据库类似：他们有同样的实现策略。并行数据库和主存数据库都具有高伸缩性和高性能的特点。但是Bigtable提供了一种不同的接个口。Bigtable不支持完全的关系数据模型；相反，它给客户端提供了一种简单的数据模型，这种数据模型支持对数据分布和格式的动态控制，并且允许客户端推出底层存储中数据的分布特性。Bigtable的数据可以使用任意字符的行列进行索引，Bigtable也把数据当作不可解释的字符串（uninterpreted strings），尽管客户端常常把不同形式的结构化、半结构化的数据序列化形成这些字符。客户端可以控制通过进行选择模式控制数据的位置。最后一点，调整Bigtable的模式参数能让客户端动态控制是从内存还是硬盘提供数据。
& &&2.&DATA MODEL
& &&一个Bigtable 集群是一系列运行Bigtable软件的进程。每一个集群都有一组tables。Bigtable中的表是稀疏的、分布式、持久的多维有序map。其数据有三个维度：行、列、时间戳。
(row:string, column:string, time:int64) & string
& & 我们称由一个特定行键、列键、时间戳指定的部分为一个单元(cell)。多行组合起来形成负载平衡的基本单元，多列组合起来形成访问控制和资源分配的基本单元。
& 考虑这样一个具体的列子：一个大量网页和相关信息的集合，该集合会被大量不同的应用利用。假设我们称此表为Webtable。在Webtable中，URL为行键，网页的不同方面成为列键，存储网页的内容。时间戳指的是网页被获取的时间。如下图所示
& & Rows. Bigtable以行键的字典序存储数据，而表中的行键是任意的字符串（目前能达到64KB，尽管对于大部分用户来说10-100字节就够了）。单行数据的读写是串行的（无论该行数据有多少不同的列正被读或者写），这种设计使得客户端能够在对某行数据进行并行更新的时候很容易知道系统的行为。换句话说，行是Bigtable控制事务一致性的基本单元，也就是意味着他不支持跨行事务。
& & 具有连续键值的行组合成tablets，这是数据分布和负载平衡的基本单元。这样的好处是读取很少的行范围内的数是高效并且一般仅仅需要和少量的机器交互。客户端可以利用这个数据局部性实现高效的数据访问。例如：在Webtable中，相同域名的网页分成一组分布在相邻（contiguous）行，存储的时候把URL的主机部分逆向存储。/index.html会以com.google.maps/index.html作为键存储。把相同域名的网页临近存放使得某些域名和主机分析更加高效。
& & Columns. 列键放在一起称为列家族，它是访问控制的基本单元。在一个列族中存放的数据通常是相同类型的。在数据用key存储之前必须显式创建列族。在列族创建完成之后，该族任意的列键都可以使用：数据可以在不影响表模式的前提下存储在这样的列键中。我们的想法是让不同列族数比较少（最多上百），并且这样的列族在操作过程中几本不会改变；这种限制控制了共享元数据的大小。但是其对列数是没有任何限制的。
& & 改变一个表模式可能会删掉所有的列族，在这种情况下，该族任意列键存储的数据都将被删掉。由于Bigtable并不支持跨行事务，如果数据被存储在多行，特定的列键被删除，其对应的数据可能不会被删掉。
& & 列键是用如下的语法命名的：族：标识符。列族的名字必须是可打印的，但是标识符没有限制。关于Webtable的一个列族例子是网页编写的语言。在语言族中我们仅使用一个列键和一个空的标识符来存储每个网页的语言ID。该表另一个有用的列族是anchor；该族中的每一个列键都代表一个anchor。标识符就是所指向网址的名字。单元（cell）则包含与链接相关的文本。
& & 访问控制以及磁盘内存分配调度都使在列族层次上的。在Webtable例子中，这些控制允许我们控制几种不同类型的应用：有些应用新增底层数据，有些则读取底层数据和创建新建的列族，有些仅仅允许访问已存在的数据（甚至由于隐私的原因，不允许访问所有存在的族的数据）
& & TimeStamps. 表中不同单元格可以包含同样数据的不同版本，版本是通过timestamp索引的。Bigtable的时间戳是64位整数。他们可以被Bigtable隐式赋值，这种情况是&实时的&，精确到毫秒级，或者可以被客户端显式赋值。应用程序必须产生唯一的时间戳来避免冲突。不同版本的单元格以降序存储，这样最新版本会被最先读取。
& & 为了简化版本管理，我们支持两个per-column-family 告诉Bigtable自动进行垃圾版本回收。客户端既可以选择保存最近的几个版本，也可以选择保存足够新的版本（例如，仅保存最近七天写入的）
& & 在Webtable例子中，我们可以把时间戳存储在扒取网页的内容中：这列意味着这些网页版本实际扒取的时间。上面描述的垃圾回收机制使得Bigtable仅保存每个网页的最近三个版本。
&&&&3. API
& &&Bigtable的API提供了创建和删除表和列族的函数。同样也提供了改变集群、表和列族元数据的函数，例如访问控制权限。
& & 客户端程序可以删除Bigtable中的值或者向Bigtable中写入数据，从单行中检索数据，或者对表中数据子集进行迭代。
图2描述了C++代码使用RowMutation抽象进行一系列更新操作。（无关细节略去了）调用Apply执行对Webtable的原子操作：向增加了一个anchor，同时删除了一个不同的anchor。
& & 图3 描述了C++使用一个Scanner抽象对某一个特定row的所有anchor进行迭代。客户机可以在不同的列族进行迭代，不过也有一些机制来限制scan可以遍历的行、列、时间戳。例如：我们可以限制让scan仅仅扫描那些匹配正则表达式的列，或者对时间戳进行限制来选择。
& &&Bigtable支持不同的特性让用户能够以复杂多变的方式操作数据。首先，Bigtable支持单行事务，这个特性使得对单行数据可以执行原子的读写序列。Bigtable目前还不迟滞跨行事务，尽管其给客户机提供了一个接口可以跨行批量写入。第二，Bigtable允许单元格充当整数计数器。第三，Bigtable支持客户端提供的脚本在服务器地址空间中执行。
& & 4.&BUILDING BLOCKS
& &&Bigtable 是基于其他几个Google基本结构的。一个Bigtable集群通常在运行各种各样分布式应用程序的共享机器上运行。Bigtable依赖于谷歌的集群管理系统来调度任务，管理资源，监控机器状态，处理异常机器。Bigtable进程与其他应用程序进程共享机器。如图4所示，一个Bigtable服务器可能与MapReduce、应用服务器、GFS服务器等运行在同一个机器
& & Bigtable 使用GFS来存储日志和数据文件。GFS是一个分布式文件系统，可以保存每个文件的多个备份以提高可靠性和易用性。
& &&Bigtable使用Google SSTable不变文件格式存储Bigtable数据文件。一个SSTable提供了一个持久的有序不变的从key到values的map。用户可以通过指定的key查找关联的value，也可以对指定的key范围内数据迭代。每一个SSTable都包含了连续的几个块（默认情况下，每个块64KB，但是大小是可以配置的）块索引（存放在SSTable的最后）是用来定位块的；当SStable打开时索引就被加载进内存。这样查询只需要一次磁盘寻道:首先通过对内存索引进行二分查找找到对应的块。根据实际情况，一个SSTable可以完全被映射到内存，从而在执行查找和扫描是无需访问硬盘。
& & Bigtable依赖一个高易用性、持久化的分布式锁机制&&Chubby。一个Chubby服务由五个活动的副本组成，其中一个被选为主要的用来处理请求。当大部分副本都处于运行状态并且相通信时Chubby处于活动状态，Chubby使用Paxos算法来保证在遇到问题时副本之间的一致性。Chubby还提供了一个由目录和小文件组成的名字空间。每一个目录或文件都可以当作锁，读写文件都是原子操作。Chubby客户端库都提供了对Chubby文件的一致映射。每一个Chubby客户端都和Chubby服务维持一个会话（session）.当客户端session不能够在到期之前续期就会失效，当session失效后，它将失去所有的锁。Chubby客户端可以对文件或目录注册一个回调函数以便在session超期或发生改变时接受通知。
& & Bigtable的Chubby可以处理不同的任务：保证任何时候之多只有一个master；存储Bigtable数据的启动位置（见5.1）；寻找tablet服务器以及确定tablet服务器的死亡（见5.2）；存储Bigtable模式（见5.5）。如果Chubby服务在一段时间内不可用，Bigtable就会不可用
& & 5.IMPLEMENTATION
& &&Bigtable的实现主要包括三哥主要部分：一个链接到每个客户端的库，一个master服务器，许多tablet服务器。Tablet 服务器可动态添加到集群（或删除）以适应不同的负载。
& & master服务器负责把tablets分配到tablet服务器上，检测tablet服务器的增加和超期，平衡tablet服务器负载，对GFS进行垃圾收集。此外，还能处理模式改变，例如列族的创建和删除。
& & 每一个tablet服务器都管理一组tablets(一般每个tablet服务器上有10-1000个tablets)。tablet服务器处理对该服务器上tablets的读写请求，也能够将特别大的tablets分成几个。
& & 像许多单master的分布式存储系统一样，客户端的数据不会移动到master上：客户端直接与tablet服务器进行读写交互。因为Bigtable客户端无需通过master知道tablet的位置信息，大部分client从来都不喝master交互。这样，在实际中，master的负载就会特别小。
& & 一个Bigtable集群存储了大量的tables。每一个表都由一组tablets构成，每一个tablet包含一个行范围内的数据。初始情况下，每个表仅包含一个tablet。随着表大小的增长，它会自动分裂成多个tablets，默认每个表可以达到1GB。
& & 尽管，我们的模型支持任意大小的数据，但是目前的Bigtable的实现还不能非常大的数据。下面的部分江介绍Bigtable实现的细节情况。
& & 5.1&Tablet Location
& &&我们使用一个类似于B+树的三层结构存储位置信息。第一层是存储在Chubby中的文件，该文件包含root tablet的位置信息。root tablet包含一个特殊METADATA table所有teblets的位置信息.每一个tablet包含许多用户tablets的位置信息。root tablet和其他tablet有所不同&&从来不会分裂&&这种特性使得tablet位置层次结构不会超过三层。
& & METADATA表用一行存储一个tablet的位置信息，位置信息包括tablet表标识符的编码和末行号。每一个METADATA行大约占用1KB的内存。而每个METADATA表的上限是128MB，这样我们三层结构能够处理
2^34的tablets。
& & 客户端库遍历位置层次结构定位tablets，并且缓存寻找到的tablet的位置。如果client不知道一个tablet的位置，或者它发现它缓存的信息是错误的，那么它将第贵的在位置层次结构中移动。如果客户端缓存是空的，这种寻找算法需要三次来回传递消息，包括一次从Chubby中读取。如果客户端缓存中的信息过时了，这中算法需要6次来回消息传递才能找到某一个tablet，由于过时的缓存项只有在miss的情况下才会发现。尽管tablet位置信息存储在内存中，无需GFS访问，我们通过客户端库预取tablet位置信息进一步减少这种通常情况下的开销：不管什么时候客户端读取METADATA表时多读取几个tablet的metadata。
& & 我们同样在METADATA表中存储了耳机信息，包括与每一个tablet相关的所有事件的日志（如服务器向其提供服务的时间）这种信息对调试和性能分析的作用是很大的。
& & 5.2&Tablet Assignment
&&&&& &&每一个tablet一次至多只能分配给一个tablet服务器。master服务器跟踪这些活动的tablet 服务器以及当前正被分配给tablet 服务器的tablet，包括违背分配的tablets.当一个tablet是未分配的，tablet server 有足够的空间容纳一个tablet，master就会通过向tablet server发送一个tablet装载请求给tablet分配服务器。分配只有在一个master的失效备援工作之前tablet装载请求还没有收到：因为tablet server 仅接受当前master的装载请求。因此当一个master服务器发送了一个装载请求，它可以假设这个tablet被赋给了某个tablet服务器知道该服务器死亡，或者该tablet服务器通知master它已经卸载了该tablet.
&&&&& & Bigtable使用Chubby跟踪这些tablet服务器，当一个tablet服务器启动时，在一个特定的Chubby目录下，对一个唯一名字的文件创建一个排它锁。master监测此目录来发现tablet服务器。当tablet失去排它锁时，就会停止对其上的tablets提供服务。例如：网络中断可能导致服务器失去和Chubby的会话。tablet服务尝试重新获取一文件的排它锁只要它的文件依旧存在。如果它的文件不存在了，服务器将不能提供任何服务，它就会终结它自己。不论什么时候tablet服务器终止，它将尝试释放自己的锁，以便master可以更快的给它的tablets分配新的服务器。
&&&&& & master负责检测tablet服务器不再向tablets提供服务的情形，尽可能快的重新分配这些tablets。为了检测一个tablet 服务器不再向tablet提供服务，master周期性询问每一个tablet服务器的锁的状态。如果某个tablet服务器告诉master它丢失了它的锁，或者master几经尝试都不能够到达一个tablet服务器.master就会尝试获取服务器文件排它锁。如果master能够获取该锁，这说明chubby正常并且tablet服务器要么终结了要么不能够到达Chubby.master将会通过删除它的服务器文件保证该tablet服务器永远都不能够再提供服务。一旦一个服务器文件被删除，master就会将之前分配给他的tablets重新变成未分配的。为了确保master和Chubby之间不易受到网络问题的影响，master终结自己当它与Chubby之间的会话插旗。master失败并不会影响tablets分配。
& & 当一个master被集群管理系统启动时，在改变tablet分配之前，它需要知道当前的tablet分配情况。在启动时，master会执行以下的步骤：
& & （1）首先master会在Chubby中获取一个为一个master lock,此锁可以避免并行的master实例
& & （2）master扫描Chubby的servers目录发现活动的tablet 服务器
& & （3）master与每一个活动的tablet server交互发现那些tablets已经分配到每一个服务器，更新当前master所了解到的信息（任何之前masters发送的tablet装载请求都会被拒绝)
& & （4）master扫描METADATA表知道有哪些tablets.不论什么时候扫描到一个没有被分配的tablet,master把这个tablet放到未分配tablet集合中，这样可以是得tablet分配更加方便。
&&&&& & 一个比较复杂的事情是只有当METADATA tablets已经被分配之后才能够扫描METADATA表。因此，在开始扫描之前（第四步），master把root tablet加到未分配tablet集合中如果在第三步中没有对root tablet进行分配。这会保证root tablet会被分配。因为root tablet包含所有的METADATA表的名字，master在扫描完root tablet之后就会知道所有的METADATA表的名字。
&&&&& & 这些tablets集合只有在表创建或删除的时候、俩个tablets合并成一个更大的tablet,或者一个tablet分裂成俩个更小的tablets时才会改变。master能够跟踪这些改变因为除了最后一个操作，其他操作都是由master初始化的。对于tablets分裂需要特殊对待，因为这个操作是由tablet servers启动的。tablet server&分裂过程是这样的，在METADATA表中记录新的tablet server的信息。在执行分裂之后，tablet server通知master.如果分裂通知丢失（由于tablet server或者master死亡）。master会发现该新的tablet当其要求tablet server加载已经分裂的tablet的时候。tablet server会告知master关于该分裂，因为master发现在METADATA表中的tablet项仅能描述它要求加载tablet的一部分信息。
& & 5.3&Tablet Serving
&&&&& &&tablet的持久化信息被存储在GFS中，如图6所示
&&&&& & 更新信息都被提交到一个存储恢复记录的commit log中。最近提交的信息都被存储在内存中的一个叫做memtable的有序缓冲中。一个memtable保存了row-by-row basis的更新，每一行都通过写时复制来保证行层次的一致性。更早的更新存储在一系列的SSTables中（不可改变）
&&&&& & 为了恢复一个tablet，tablet server从METADATA表中读取元数据。这些元素据包括组成tablet和一系列的还原点的SSTables，这些元数据可能包含tablet数据的提交日志的指针。server把SSTables的索引读进内存，通过还原点中更新记录重构memetable。
&&&&& & 当tablet server接受到一个写操作请求，server检查该请求是否是良定义的，发送者是否有权限执行该操作。检查权限是通过Chubby文件中一个允许写的列表（该文件在CHubby客户端缓存中，几乎每次都能命中）。合法的改变都会写入到提交日志中。批量提交小的改变可以提高系统吞吐量。当写操作提交之后，内容就被插入到memtable总。
&&&&& & 当tablet server接收到一个读操作时，同样先检查其形式和权限。
&&&&& & 当tablets正在分裂或者合并的时候读写操作仍然可以继续。当tablets在被压缩时，读写操作仍然可以进行。
& & 5.4&Compactions
&&&&& & 当执行写操作时，memtable大小增加。当memtable大小达到阈值时memtable就会被冻结，一个新的memtable会被创建，冻结的memtable会被转换成SSTable并被写入到GFS中。这种小型压缩过程有两个目的：减少tablet server的内存消耗，减少在server死亡情况下恢复过程中需要从commit log中读取的数据量
&&&&& & 每一次微小压缩（minor compaction）都会创建一个新的SSTable。如果这种行为不受约束，读操作可能需要合并任意数量的SSTable中的更新记录。相反，如果我们限制了这些文件的数目通过在后台周期性执行一个合并压缩。合并压缩读取几个SSTable和memtable的内容，写入到一个新的SStable中。当压缩完成后，输入SSTables和memtable可以被丢弃掉。
&&&&& & 把所有SSTables中的内容写入到一个SSTable的合并操作称之为大的合并。由小型压缩产生的SSTables可以包含特殊的删除项，该删除项可以限制在比较老的SStable中仍然存活着的数据。另一方面，大的压缩产生的SSTable不包含任何删除信息或数据。Bigtable周期性的检测所有的tablets并且周期性应用大的压缩。这些大的压缩让Bigtable回首被删除数据使用的水资源，同时也能保证让需删除的数据机试从系统中小时，这一点对于存储敏感数据的服务很重要。
&&&&& & Bigtable读性能得以与GFS的局部性优化。当文件被写入时，GFS尝试把数据的副本放在写者的机器上。当读取GFS文件时，读取的数据来源于最近可用的副本中。因此，在tablet servers与GFS servers共享机器时，tablet servers会压缩到在硬盘上有副本的SStables中，这样可以在处理连续的读请求时快速访问这些SSTables
& & 5.5模式管理
&&&&& & BigTable的模式存储在Chubby中。Chubby给Bigtable模式提供了一个搞笑的交流基质，它提供了对整个文件原子写操作和小文件的一致性缓存。列入，假设一个客户端程序想要删除表中的某些列族。master执行访问控制检查，验证结果模式是梁定义的，然后向Chubby中重写相应的模式来安装新的模式。不论什么时候tablet servers需要决定那些列族存在，仅需要读取Chubby中相应的模式，这在Chubby的客户端缓存中常常是存在的。因为Chubby缓存是一致的，tablet servers 一定能够看到对那个文件的所有改变。
& & & & 参考资料：
　　　　Bigtable: A Distributed Storage System&for Structured Data
阅读(...) 评论()BigTable简单翻译
BigTable简单翻译
发布时间： 3:02:50
编辑：www.fx114.net
本篇文章主要介绍了"BigTable简单翻译"，主要涉及到BigTable简单翻译方面的内容，对于BigTable简单翻译感兴趣的同学可以参考一下。
Bigtable: A Distributed Storage System for StructuredData
简述：Google的很多产品在进行数据存储的时候都用到了Bigtable，例如网页检索、Google地图和Google Finance。这些应用对Bigtable有各异的要求，包括：数据的大小（简单的网页URL到卫星数据级别的数据）和时延要求（后端处理到实时数据服务）。尽管要求众多，但是Bigtable能够提供统一的易扩展、高性能的解决方案。
1 Data model
Bigtable是一个稀疏的、分布式永久存储的排序多维度关联图。这个关联图中的索引有行关键字、列关键字和时间戳组成；在关联图中的每个值都是未解释的字节数组。
（row:string,column:string, time:int64）--&string
举例：在一个叫webtable中的某一行存储了CNN被引用的几个地方。其行关键字是CNN的web网址，这个网址是倒转的，即：n.www。在列关键字上有多个，例如有和anchor:my.look.ca，通过行关键字和列关键字，定位到一系列有时间戳的内容上。整个webtable的解释就是，cnn网站被列上的网站索引（anchor）时间戳显示的内容可以查找到。
&& 行关键字是二进制字符串，目前最大支持64KB，一般用的大小为1-100字节。Bigtable中的行顺序按照行关键字的字典顺序进行排序，每行叫做一个tablet，作为分发和负载均衡的单位。在例子中webtable，通过把web地址逆序，把相同域的放在连续行，这样提高素具访问速度。
&&& 列关键将table分为了列族，每族列作为访问控制的基本单元。每族列上的数据都是同一种类型，必须在数据存储前创建。列的数目不会太多，一般不会超过百，列的修改很少在操作的时候被修改，但是还是允许列数量的改变。
一个列关键字可以定义为如下语义：列族：条件。就是说在列族中，可以通过条件进行排序和筛选。在上面的webtable中，假设有一列上为语言，那么对于列族可以通过语言进行条件筛选，比如通过给语言设置ID，可以快速筛选；上面提到的anchor，也能够进行筛选。
&& 在Bigtable中通过行关键字和列关键字找到的内容，可以针对同样数据有不同版本；不同的版本依靠时间戳来标记。时间戳是一个64位的整数，由应用程序进行实时的标记，精确到微秒。应用程序要负责产生独一无二的时间戳，不同版本的排序是按照时间戳下降排序，保证访问的时候，最新版本在前面。
Bigtable目前允许对单行进行读写和修改的操作，不支持同时对多行的操作；但是允许对多行在客户端进行打包。Goolge还为操作Bigtable开发了语言Sawzal。
Bigtable是基于Google的基础设施的，其中的数据和日志文件存储时在GFS中。在Goolge中，利用SSTable文件来存储Bigtable数据。在SSTable中，提供一个排序的不可修改的从关键字到值的关联图，并且关键字和值都是二进制字符串。可以通过关键字搜索到相应的值，并进行遍历。每个SSTable文件由块构成（一般是64KB，这个可以配置）；块的索引存在在SSTable的末尾。通过块索引能够定位块；当SSTable被打开的时候，将该索引加载到内存中。在单个硬盘中查找：首先在内存中的块索引定位合适的块，然后从硬盘读取相应的块。有的时候，可以将整个SSTable文件加载到内存中，这样就不用读取硬盘了。
Bigtable中使用了该可以用性和持久性的锁服务Chubby。Chubby服务中包含了五个活跃的副本服务器，其中一个作为主服务器响应请求。只要副本服务器能够运行，它们之间能够通信，Chubby服务就能执行。Chubby服务中采用了Paxos算法来保证副本一致性。每个目录或者文件都可以看作是一个锁。Chubby客户端和Chubby服务之间建立session，当用户的session在期限内没有更新session的租赁时间，那么session将会过期。当用户的session过期，那么他获得的锁将会被解除。
Bigtable中利用Chubby有如下作用：保证只有一个活跃的主服务器；保存Bigtable数据的启动位置；发现tablet服务器，终结死忙的tablet服务器；存储Bigtable的模式信息；存储访问控制列表（ACL）。
3 运行的Bigtable
Bigtable实例中包含三个主要部分：一个和所有客户端连接的库、一个主服务器和多个tablet服务器。tablet服务器可以根据负载的变化动态增加。
主服务器负责分配tablets到tablet服务器，发现新增的和过期的tablet服务器，对tablet服务器进行负载均衡，搜集在GFS中的文件。此外，还要处理模式的改变。
每个tablet服务器管理一系列的tablets。每个tablet服务器处理对tablets的读和写，当tablet过大的时候，还需要对其进行分割。
每个用户有多个table，每个table包含多个tablets，每个tablet包含了一行中的所有相关数据。初始的时候，一个table中只包含了一个tablet，随着table的增长，会进行分割。
Tablet的定位
采用三层结构构建成B+树来存储tablet的位置信息。Chubbyfile—&Root tablet(1st metadata tablet)--&Other metadata tablet---&table1 … table N。
第一层存储在Chubby中的文件，包含了根tablet。根tablet包含了所有tablet的特殊metadata表。其中每个metadatatablet包含了用户一部分tablet的位置信息。其实根tablet就是metadata tablet中的第一个tablet，但是改tablet不会被分割。
一般metadata tablet的数量限制在128MB左右，加上tablet的大小在64KB，那么通过该三层结构可以寻址到234个tablet。
在用户库中缓存了tablet位置信息。如果用户不知道某个tablet的位置，或者缓存的talet位置信息部准确，会递归通过三层结构搜寻。如果用户缓存为空，在定位的时候就需要进行三次的往返，包括从Chubby读取文件；如果用户缓存过时，那么久需要六次往返，过期的缓存只能通过tablet的未命中来判定。
3.1 Tablet的分配
每个tablet服务器都一次只分配了一个tablet。主服务器需要跟踪这些有效的tablet服务器，并将tablet分配到这些服务器上。当一个tablet服务器启动的时候，它会创建并获得对在Chubby目录中一个唯一命名文件的独立锁。主服务器通过监控这个目录，来发现tablet服务器。主服务器需要发现down掉的tablet服务器，然后马上重新分配tablet。为了发现不再服务的tablet服务器，主服务器周期性的询问tablet服务器的锁状态。如果tablet服务器告知其锁丢失或者主服务器不能联系到该服务器，主服务器就会获得对该服务器文件的锁；在主服务器获得锁后，Chubby正常运行下，会将tablet服务器上的文件删除；待其上文件被删除，主服务器会重新分配tablet。
主服务器发现当前的tablet分配情况，过程如下：1.获得在Chubby中的master锁 2.主服务器浏览Chubby目录来发现活跃的服务器3.主服务器和每个活跃的服务器进行通信，得到已经在活跃服务器上的tablet信息4.主服务器浏览Metadata表（由各个tablets构成）知道所有tablets，如果发现有tablet尚未分配就会进行分配。
用户可以将一些列组合为本地组。为每个tablet的本地组分配一个单独的SSTable。这样可以更加高效的读取数据。例如在webtable中，网页的元数据（例如语言）在一个本地组，网页内容在一个不同的组；当应用想要读取元数据时，就不用读取网页内容了。
两种压缩方式：Bentley和McIlroy模式，该模式通过一个窗口对常见的长串进行压缩；第二种压缩算法，利用16KB大小窗口寻找重复的串。
3.Bloom Filter
利用该过滤器来查找SSTable中是否包含了指定row/column对。
版权声明：本文为博主原创文章，未经博主允许不得转载。
一、不得利用本站危害国家安全、泄露国家秘密，不得侵犯国家社会集体的和公民的合法权益，不得利用本站制作、复制和传播不法有害信息！
二、互相尊重，对自己的言论和行为负责。
本文标题：
本页链接：