那些底层使用了Rocksdb的项目元数据使用了RocksDB的框架kafka：的streams默认将持久化状态的中间计算结果Pulsar的底层存储，也就是Bookkeeper：的默认存储实现中，Rocksdb用来维护Ledger元数据索引rocketmq：RocketMQ 在 broker 端通过 RocksDB 来保存 消费偏移量、订阅组管理/配置、认证授权数据等元数据Ceph：使用Rocksdb来管理对象映射和磁盘分配记录。Doris在后端BE存储中使用了rocksdb保存元数据的键值对。主要状态数据使用RocksDBMySQL/MariaDB中存在innodb的另一个存储引擎选择，MyRocks，底层使用了rocksdb作为存储引擎。顺序批量写入性能更高，但是查询延迟稍高。Kvrocks，pikiwidb，Tendis他们都兼容Redis协议，并且底层使用rocksdb作为主要的持久化协议存储。tidb：底层使用的tikv的内部使用了rocksdb作为存储实现。Flink：Checkpoint可以选择，通过使用rocksdb存储到本机。ClickHouse 提供了一个叫 EmbeddedRocksDB 的表引擎，可以让用户把一个表的数据存放在一个 RocksDB 实例中，并通过 ClickHouse SQL 访问它。Nacos等这些底层依赖sofa-jraft的框架底层都采用rocksdb作为存储，不过也允许切换为其他存储实现。MongoDB提供了rocksdb存储引擎插件，优化高写入场景
LSM‍‌‌‍⁠‌‬⁠⁠‍‍‬‌﻿‌⁠⁠‬‌‌‍‬‬‍‌‬‍⁠wiscKey论文精读 - 飞书云文档经典LSM实现-LevelDB适合磁盘索引的结构通常有俩中，一种是就地更新B+，一种是就地更新LSM。B+树读取性能更好，B+树随机写入很差，LSM写入性能更好。接下来内容都讨论LSM Tree。最直观的想法是将随机写入改成顺序写入，最简答的方法就是假设一个无限大小的文件，每次kv为一组，一直向后追加。这样会引出几个问题。同一个key可能被写入多次，更早的key就无效了，会浪费磁盘空间。读取的性能是不可接受的，读取一个数据可能要扫描全部文件。一个简单的优化想法就是合并这个无限大的文件，将被覆盖的key清理掉，只保留最新的key，但这样就不能在一个文件中操作（不能将压缩过程变成更新，类似GC），因此需要将文件分段。每次合并本质上就是一个归并排序的过程（为了支持范围查询，以及空间压缩），那么就需要找到所有分段文件中有重合范围的文件，进行合并。而且不能合并一个正在写入的文件。为了降低读取的复杂度，第一个想法就是使用内存，将最近新写入的kv存储在内存数据结构中，红黑树，跳表等。那么问题是合适将数据结构dump到磁盘？最简单的是根据其大小的区别，然而在dump之前我们不能继续向其中写数据。为了更好的确定内存中的数据结构什么时候应该被写入，我们应该在内存中维护一个不变内存表和活跃内存表，周期性的将不变内存表dump到内存中形成一个文件。这些都没有解决最先写入且从未更新的key尧都区全量数据的问题，为解决这个问题LSM结构引入了分层的思想。由于我们区分了不变内存，因此从内存dump到磁盘的文件一定是有序的。L0中每个文件内是不会出现重复的现象，但是文件之间可能是乱序的。从L1开始，每个层级内的SSTable文件必须保证Key范围有序且不重叠。这是通过compaction实现的。我们假设直接从内存写入磁盘的文件为第0层，从第0层合并数据到第二层。那么从c1-ck层，他们的数据只会出现一次。而c1-ck是发生过合并的文件。由于ci+1 是ci中具有重叠部分的文件合并的产物，因此可以说在同一层内是不存在重叠key的，因为重叠key已经在其上一层被合并了。那么只有c0层是可能存在重叠的文件的。所以当要读取磁盘上的数据时，最坏情况下只需要读取c0的所有文件以及c1-ck每一层中的一个文件即c0+k个文件即可找到key的位置，分层合并思想使得非就地更新索引在常数次的IO中读取数据。L1 的每个文件负责的 Key 范围是 由 Compaction 动态划分的，而非预先固定。例如：如果 L0 和 L1 的合并数据覆盖 [a, z]，Compaction 可能将其拆分为多个文件（如 [a, g]、[h, m]、[n, z]），每个文件大小接近 target_file_size（默认 2MB）。LSM tree中，文件更新完全通过原子替换实现。L1和L2的归并步骤选择 L1 层的所有 SSTable 文件选择 L2 层中与 L1 层有键范围重叠的 SSTable 文件对这些文件进行多路归并排序生成新的 L2 层 SSTable 文件删除旧的 L1 和 L2 层参与合并的文件leveldb最多有8层，假设第0层最多6个文件，我们只需要读取14个文件就能找到一个key。用户在读取同一个key的时候，只要读取最上面的最新版本即可。简单来说，同一层只有一个相同的key，但是不同层可能有多个相同的key的（不同版本）。在一个巨大的日志文件中找一个key也是很难的，leveldb中有三个模块，元数据区，索引区，数据表。元数据区存在布隆过滤器，可以直接判断key是不是在当前文件。布隆过滤器存在假阳，当假阳发生时，需要读取索引块。这个索引存储了key和对应value的偏移量，可以直接在内存中进行二分查找。实际上存储数据的结构叫做sstable。为了标记哪些SStable属于哪一层，因此要存在一个sstable的元数据管理文件，在levelDB中叫做MANIFEST文件。其中存储每一个sstable的文件名，所属的级别，最大与最小的key的前缀。LSM树中，一层有多个文件，这允许多个文件进行并行写入操作，小文件可以独立合并，避免每次合并都要重写整个层的数据。小规模更新对系统影响小，且每个层都可以维护自己的布隆过滤器。LSM tree优化方向LSM 是牺牲读取性能和空间利用率为代价，换取写入性能的。因此，对LSM的结构优化目标就是想办法提高读取性能和空间录用率。KV分离对SSD的优化SSD上引用LSM技术带来俩个问题，第一写放大缩短了SSD寿命，第二传统LSM无法充分发挥SSD的并行写入特性。相较于机械硬盘，随机读取与顺序读取的性能在固态上没有那么显著。意味着过分追求顺序读取而进行的激进优化是没有必要的。其中最明显的就是将key和value放在一个文件内（sstable），在机械硬盘上这种结构能保证一次读取就获得数据，减少了磁头的寻道次数，而对于固态哟安这样会导致合并压缩过程中，对同意kv进行多次写入与移动，从而降低了SSD的寿命。虽然也是读取一次但对于固态硬盘来说两次读取也要快于机械硬盘一次读取，而为了有效的减少LSM造成的读写放大，wisckey中将key与value分离存储，value仅存储在vlog中以仅追加的方式，而key存储在之前的lsm tree结构中。专业带来了俩个好处。不需要频繁的移动value的值，所以写放大减少，LSM存储固定大小的key使得其存储占用变小，在内存中可以同时存储更多的key进而提高了key的数据量，间接降低了读放大问题。对于范围查询，由于真正的value都存储在vLog中因此是无序的，所以进行范围查询就是需要进行随机读取（先从LSM顺序读key再随机读value），这必然会造成性能的下降，传统的随机读取是串行的难以发生固态并行随机读取的特性，因此在wisckey中根据迭代器方法调用prev，next来排序号lsm中读取一定的key到内存中，加速 随机的范围查询性能，这种读取是异步进行的，充分发挥固态硬盘的并行读取性能。实现细节工程优化kv分离带来的挑战kv分离会导致vLog文件不断增大，那么就需要合并，如何合并才能保证对性能的影响最小化？同时由于移动了value的位置，LSM结构中维护的value的位置信息也需要更新。数据具体如何布局？VLog日志如何拆分？Wisckey崩溃后如何才能保证数据一致性在sstable文件中数据布局: <key, addr(vlogName,offset,size)>在vlog文件中的数据布局: <keySize,valueSize,key,Value>这里的key是一个固定大小的字符串，addr是一个地址指针应该是一个64或者128的int值。value log中存储了 key大小（确定读取程度）值大小，key和value的具体值。这里再将key存放一遍是为了故障恢复需要使用。随机点查：先访问内存表是否命中key，如果找到地址信息判断是在内存中还是磁盘中(LRU缓存)在内存中被缓存了value则直接返回，否则去磁盘中查找，根据vlog的名字找到具体的vlog文件然后根据offset定位字节的首地址，根据size读取内容并返回基于一定策略将整个vlog涉及的bolck缓存下来范围查询，会返回一个迭代器。根据迭代器 next 还是 prev判断 是在游标之前读还是之后读，预先读取一定的key，交由底层的线程池异步的取ssd中获取数据将异步结果缓存在内存中 等到迭代器的调用随机、顺序写入将set写操作写入vlog日志中（存储key的作用之一就是即作为预写日志，又作为值日志）将返回的地址信息写入LSM中返回写入返回成功合并压缩head是最后写的，tail是最早写的其中合并后得到的新value log文件，可能在之后仍需要被再次合并Vlog分为多个文件，其中存在一个活跃vlog文件，用于写入数据最为head地址。（有些类似kafka，会又活跃的vlog）最先写入的日志在最后（早）的vlog中，存在tail地址。多个写入线程在head地址出追加日志而只有一个后台执行收集运行在尾部每次选择一个vlog文件的内容去lsm结构中随机查询（可并行化）将没有失效的key重新写回到head地址出重新追加到vlog中。然后更新lsm中这些key的新地址并释放老的vlog文件这一过程中需要先将数据写入新的vlog文件后，刷新到固态硬盘后一步更新索引。最后扇出老文件，保证次过程中进程崩溃不会造成数据丢失。故障恢复wisckey的设计中预写日志就是值日志因此引擎进程只需要定时保存head和tail的地址即可数据库恢复时需要获取崩溃前最新的地址然后从tail到head将日志进行redo即可（会有检查点的操作）同时为了保证一致性查询，在查询key时要做一些必要的一致性就爱你差当前key如果在tail预head索引范围外则忽略当前位置上的值具有key预查询的key不匹配则忽略当发生上述情况时，引擎直接返回错误信息。改进和优化写缓冲区，为减少写入的系统调用次数，多个小key的写入会被缓存在内存中回去在一起同意的写入lsm的sstable中，但会优先写入vlog中当做预写日志处理。空间放大率：数据的实际大小预逻辑上的大小比值用来衡量空间放大情况，对于固态硬盘来说，价格昂贵，降低空间放大率会节省成本在线垃圾收集：GC过程会造成引擎的性能尖刺，通过并发的在线分批次进行的GC操作来对前台读写行的影响。小value的存储：经过论文测试value大于4kb时读取性能才会有极大的提升，incid可以设置一个阈值，当value大于次阈值时才进行kb分离，而再次之前用传统lsm tree的格式。
Faster笔记Epochepoch框架Faster是基于一个关键的设计原则，旨在实现可伸缩性：避免在线程和公共的访问路径之间的昂贵协调开销。更快的线程在大多数情况下独立执行操作，不需要同步。与此同时，他们需要就共享系统整天同步的通用机制达成一致。为了实现这个目标我们扩展了多线程访问 epoch安全到一个框架中在任意全局操作上启用异步延迟。Epoch basics是Faster用于协调多线程并发访问的轻量级同步机制。以下是核心组件线程记作$T$全局当前epoch（E）一个原子计数器，由系统维护，记为当前的epoch。线程本地epoch$E_T$：每个线程维护自己本地版本的E，线程会定期刷新本地的E。安全epoch$E_s$：全局变量，表示所有线程以观察到的最小epoch值。即本地所有线程的epoch大于$E_s$时，$E_s$才会更新为那个新值。所有线程本地的$E_T$被存储在epoch table中每个线程占用一个缓存行（应该是为了防止缓存行伪共享）。对于任意的epoch $c$如果所有的线程本地的epoch都大于$c$，那么这个c就是安全的。系统保持对于任意的$T$, $E_s<E_T \leq E$Trigger action当把当前的线程从$c$增加到$c+1$,线程可以额外关联一个操作这个操作在将来系统epoch$c$为安全时进行触发。这是通过drain-list实现的，一个<epoch,action>pairs的列表，其中的action是回调代码。这通过使用小的数组来实现的，每当$E_s$更新时，该数组会被扫描以寻找触发的动作。我们在数组上使用原子的比较并交换来确保每个操作只被执行一次。使用epoch框架我们使用四个操作来暴露epoch保护框架，它可以被任意线程调用。Acquire：为$T$保留一个条目并且设置$E_T$为$E$。Refresh：更新$E_T$为$E$, $E_s$更新为当前最大的安全epoch并且触发在drain-list中就绪的操作。BumpEpoch(Action)：将计数器E从当前值c增加到c+1，并且添加到drain-list当中。Release：从epoch table中删除T。具有延迟触发动作的epoch可用于简化并行系统中的延迟同步。考虑一个典型案例，当共享变量状态更新为active时，必须调用active-now函数。线程将自动的将状态更新为active，并以active-now作为触发动作来触发epoch。并不是所有线程都会立即观察到状态的变化。然而他们都保证在刷新它们的epoch的时候观察到它，（由于使用内存屏障的顺序内存一致性）因此active-now只有在所有线程看到状态为活动状态后才会被调用，因此是安全的。我们使用epoch框架在faster中协调系统操作，比如内存安全的垃圾收集，索引改变，循环缓冲维护和页刷新，共享日志页边界维护和检查点。同时在短时间内为用户操作（如读取和更新提供更快的线程不收锁限制地访问共享内存位置）。Faster线程的生命周期我们使用faster实现了一个计数器存储（counter store），其中一组faster用户线程会传递与传入请求关联的计数器。线程首先调用Acquire向epoch机制注册自身，随后发起一系列的用户操作，并定期调用Refresh（例如没256次操作调用一次）以将线程移至当前epoch，同时调用completePending（例如没64K操作调用一次）来处理所有先前待处理操作。最后线程调用release来注销Faster的调用。Faster的哈希索引Faster的关键构建块是哈希索引，一个并发的无延迟可扩展以及可变的基于哈希的索引。为了便于说明，我们假设一个64位的机器，有64个字节的缓存行。在大的架构中我们期望有更大的原子操作，从而允许我们的设计可扩展。在4,5,6章中，我们把这个索引与不同的分配器配对，以创建功能不断增强的键值对存储。3.1 索引组织faster索引是一个缓存对其的$2^k$大小的哈希桶，其中每个桶的大小和缓存行对其（图2）。因此，一个64字节的同由7个8字节的哈希桶项和一个8字节的条目。每个溢出的桶（每个桶包含7个条目+1个溢出指针）也具有缓存行的大小和对其方式，并使用内存分配器按需分配。选择8字节的条目是关键的，因为它允许我们使用64位原子比较并交换操作对条目进行无锁操作。在64位机器上，物理地址通常占用不到64位，例如因特尔机器通常使用48位指针。因此我们可以偷窃这些额外的比特来进行索引操作（Faster至少需要一个bit）。在本文的其余部分中，我们使用48位指针，但请注意，我们可以支持63位长度的指针。每个哈希桶（图2）包含了三个部分：tag（15bit），tentative bit和地址。0值的条目代表着空槽位。在一个有$2^k$个哈希桶的索引中，tag用来将索引的有效散列分辨率从k位增加到k+15位。这通过减少哈希碰撞来提升性能。对于哈希值位h的键，其对应的哈希桶先通过h的前k位（成为h的偏移量，offset）来定位。h后面的15位被称为h的标签（tag）。标签只用于增加哈希分辨率，根据地址的大小，标签可能更小，或者完全被删除。试探性钻头是插入所必需的，稍后将介绍3.2索引操作Faster的索引是基于不变的每个(offset,tag) 有唯一的索引项，该索引项指向一组记录，这些记录的散列指向相同的偏移量和标签。在支持并发无锁读取、插入和删除索引条目的同时，确保这种不变性是一种挑战。这里的k取决于哈希表的大小。文中都是在说如何解决一个哈希桶中7个条目遇到冲突的情况。可以简单的理解为，为了缓存行对其，一个链表中存放了7个条目，图中的next Bucket address就是指向下一个的指针。其中每个条目都是一个链表。这里的tag可以将哈希分辨率提升到k+15位，15就是tag的固定大小。比如在查找时如果一个桶中有许多元素，可以先比较tag，来排除一部分，而不需要直接比较俩个key本身（如string的比较代价是高昂的）。查找和删除一个条目。定位一个条目对应的key是直接的：我们使用k哈希bit，扫描存储桶以找到标记的条目。从索引条目中删除条目也很容易：我们使用比较交换将匹配项（如果有的话）替换为0。插入一个条目：考虑一个例子，当一个tag没有存在于bucket中，并且必须插入一个新条目。一个简单的方法是查找空条目并使用比较并交换插入标记。但是俩个线程可以并发地在bucket中的俩个不同的空槽中插入相同的标记，从而破坏我们的不变量。作为一种变通，考虑一个解决方案，每个线程从左到右扫描bucket，并确定地选择一个空条目作为目标。他们将使用比较并交换来竞争插入，并且只有一个会成功。这里给的例子意思是一个哈希桶中出现了一模一样的重复的key即使是这种方法在存在删除操作时也会违反不变性条件，如图3a所示。一个线程$T_1$从左到右扫描桶，并且选择槽5来插入tag$g_5$。另一个线程$T_2$从相同桶中的slot3中删除$g_3$，然后尝试插入具有相同tag的$g_5$.从左到右扫描将会导致线程$T_2$为这个tag选择第一个空的条目3。可以证明，对于任何独立选择槽并直接插入的算法都存在这个问题：要了解原因，请注意，就在线程$T_1$执行比较并交换之前，它可能会被交换出去，数据库状态可能会任意更改，包括具有相同tag的另一个槽。简单来说就是插入之后重新跑一遍检查看看有没有值被修改过，如果被修改过了。说明发生竞争了，需要重新执行。但是一个桶内发生竞争的概率很小。因此，锁定桶是一个必要（但是沉重）的解决方案。Faster使用latch-free俩阶段插入算法这使用了tentative bit条目。一个线程找到一个空槽并插入了含有tentative bit 记录。然后我们重新扫描桶（注意，它已经存在于我们的缓存中）来检查是否另一个tentative条目在同一个tag中。如果是回退进行重试。否则我们重置暂定位以完成插入。因为每个线程都遵循这个俩阶段提交方法，因此每个线程都保证稳定的不变性。图3b展示了俩个线程的操作顺序：不存在任何并发交错（interleaving）会导致重复的非暂定（non-tentative）tag。3.3 扩容和索引检查点对于键数可能随时变化很大的应用程序，我们支持动态调整索引大小。我们利用epoch保护盒阶段状态机降低开销执行大小。有趣的是，即使存在并发操作，使用无锁存操作也总是将索引保持在一致状态。这允许我们在不获得读锁的情况下执行索引的异步模糊检查点，从而大大简化了恢复。内存键值对存储我们现在构建了完整的内存键值对存储使用上述的hash index，搭配在内存中的入jemalloc分配器。具有相同(offset,tag)的记录被组织为反向单链表。哈希桶入口指向链表尾部（最近的一条记录）尾部指向前一条记录，以此类推。每个记录可以是固定大小或可变大小，由64位记录头、键和值组成。记录头如图2所示。除了前面的指针之外，我们还使用一些位（invalid和tombstone）来跟踪日志结构分配器所需的信息（参见第5节和第6节）。这些位作为地址字的一部分存储，但如果需要，也可以单独存储。内存分配中的操作fetch-and-add是什么？fetch-and-add 是一种原子操作（atomic operation），用于在多线程环境下安全地修改共享变量的值。它的核心特点是原子性（不可分割），即在执行过程中不会被其他线程中断，从而避免竞态条件（race condition）。在faster中，用户在epoch保护的安全下线程读取和修改记录值，使用用户的读取或更新逻辑处理记录级并发。例如可以对计数器级别使用fetch-and-add，采用记录级别的锁，或者利用用户级别的分区只是来进行无锁更新。下面描述对于存储的操作。读取，我们从3.2节中描述的索引中找到匹配的标记条目，然后遍历该条目的链表以找到具有匹配键的记录。更新和插入。盲更新（upsert）和rmw更新都是从查找键的哈希桶条目开始的。如果条目不存在，我们使用3.2中描述的俩阶段算法来插入标记和新纪录的地址到散列桶的空槽之中。如果条目已存在，我们扫描链表来找到一个匹配键的记录。如果存在这样的记录，我们就地执行操作。线程保证访问记录的内存位置，只要它不刷新它的epoch。此属性允许线程在不担心线程安全的情况下就地更新值。如果这样的记录不存在，我们使用比较-交换将新记录拼接到列表的尾部。在我们的计数存储示例中，我们增加现有键的计数器值，使用fetch-and-increment或普通的in-place increment（如果key是分割的）。插入新键的初始值设置为0删除操作。我们通过原子性地将记录从链表中移除来实现删除，具体方式是对记录头或哈希桶条目（针对首条记录）执行比较并交换操作。当从单例链表中删除记录时，该条目会被置为0，从而允许后续插入操作重新使用该位置。由于同一内存地址可能存在并发更新，被删除的记录无法立即归还给内存分配器。为此我们采用基于epoch的保护机制：每个线程维护一个线程本地（避免并发瓶颈）的(epoch, 地址)配对空闲列表。当相关epoch进入安全状态后，即可将这些内存安全地归还给分配器。
Megastore: Providing Scalable, Highly Available Storage for Interactive Services（1）
Megastore: Providing Scalable, Highly Available Storage for Interactive ServicesMegastore.pdfINTRODUCTIONMegastore Blends the scalability of a NOSQL data storage with the convenience of a traditional RDBMS. It uses synchronous replication to achieve high availability and a consistent view of data. It provide fully serializable ACID semantics over distant replicas with low enough latencies to support iterative application.We accomplish this by taking a middle ground in the RDBMS vs. NoSQL design space: we partition the data-store and replicate each partition separately, providing full ACID semantics within partitions, but only limited consistency guarantees across them. We believe that megastore is the largest system deployed that uses Paxos to replicate primary user data across datacenters on every write. Megastore has been widely deployed within Google for several years. It handles more than three billion write and 20 billion read transactions daily and stores nearly a petabyte of primary data across many global datacenters.The key contribution of this paper are:the design of a data model and storage system that allows rapid development of interactive applications where high availability and scalability are built-in from the start;an implementation of the Paxos replication and consensus algorithm optimized for low-latency operation across geographically distributed datacenters to provide high availability for the system;a report on our experience with a large-scale deployment of Megastore at Google.2 Toward Availability and scalefor availability, we implemented a synchronous ,fault-tolerant log replicator optimized for long distance-links.for scale, we partitioned data into a vast space of small databases, each with its own replicated log stored in a per-replica NoSQL datastore.2.1common strategies for with-area replication:Asynchronous Master/slave: a master node replicates write-ahead log entries to at least one slave. Log appends are acknowledged at the master in parallel with transmission to slaves. The master can support fast ACID transactions but risks downtime or data loss during failover to a slave. a consensus protocol is required to mediate mastership.Synchronous master/slave a master waits for changes to be mirrored to slaves before acknowledging them allowing failover without datal loss. Master and slave failures need timely detection by an external systemOptimistic replication any member of a homogeneous replica group can accept mutations, which are asynchronously propagated through the group. availability and latency are excellent. However, the global mutation ordering is not known at commit time, so transactions are impossible.2.2 Partitioning and locality2.2.1 Entity groupsTo scale throughput and localize outages, we partition our data into a collection of entity groups, eah independently and synchronously replicated over a wide area. The underlying data is stored in scalable NoSQL datastore in each datacenter(see Figure 1).Entities within an entity group are mutated with single phase ACID transactions(for which the commit record is replicated via Paxos). Operations across entity group could rely on expensive two-phase commits, but typically leverage Megastore's asynchronous messaging. A transaction in a sending entity group places one or more messages in a queue; transactions in receiving entity groups atomically consume those message and apply ensuring mutations.Note that we use asynchronous message between logically distant entity groups, not physically distant replicas. All network traffic between datacenters is from replicated operations, which are synchronous and consistent.Index local to an entity group obey ACID semantics; those across entity group have looser consistency. See Figure 2 for the vraious operation on and between entity groups.2.2.2 Selecting Entity Group boundariesThe entity group defines the a priori grouping of data for fast operations. Boundaries that are too fine-grained force excessive cross-group operations, but placing to much unrelated data in a single group serializes unrelated writes, which degrades throughput, but placing too much unrelated data in a single group serializes unrelated writes, which degrades throughput.The following examples show ways applications can work within these constraintsEmailBlogsMapsphysical layoutWe use Google's Bigtable for scalable fault-tolerant storage within a single datacenter, allowing us to support arbitrary read and write throughput by spreading operations across multiple rows.We minimize latency and maximize throughput by letting applications control the placement of data: through the selection of Bigtable instances and specification of locality within an instance.To minimize latency, application try to keep data near users and replicas near each other. They assign each entity group to the region or continent from which it is accessed most. Within that region they assign a triplet or quintuplet of replicas to datacenters with isolated failure domains.A tour of megastoreMegastore map this architecture onto a feature set carefully chosen to encourage rapid development of scalable applications. This section motivates the tradeoffs and describes the developer-facing features that result.3.1 Api design philosophyACID transactions simplify reasoning about correctness, but it is equally important to be able to reason about performance. Megastore emphasizes cost-transparent API with runtime costs that match application developers' intuitions.Normalized relational schemas rely on join at query time to service user operations. This is not the right model for Megastore applications for several resons:High-volume interactive workload benefit more from predictable performance than from an expressive query language.read dominate writes in our target applications, so it pays to move work from read time to write time.Storing and querying hierarchical data is straightforward in key-value stores like Bigtable.With this in mind, we designed a data model and schema language to offer fine-grained control over physical locality. Hierarchical layouts and declarative denormalization help eliminate the need for most joins. Queries specify scans or lookups against particular table and indexes.Join, when required, are implemented in application code. We provide an implementation of merge phase of the merge join algorithm, in which the user provides multiple queries that return primary key for the same table in the same order; we then return the intersection of keys for all the provided queries.We also have applications that implement outer joins with parallel queries. This typically involves an index lookup followed by parallel index lookups using the results of the initial lookup. We have found that when the secondary index lookups are done in parallel and the number of results from the first lookup is reasonably small, this provides an effective stand-in for SQL-style join.3.2 data modelMegastore defines a data model that lies between the abstract tuples of an RDBMS and the concrete row-column storage of NoSQL. ASs in an RDBMS, the data model is declared in schema and is strongly typed. Each schema has a set of tables, each containing a set of entities, which in turn contain a set of properties a set of entities. properties are named and typed values. The types can be strings, various flavors of numbers, or Google's protocol Buffers. They can be required, optional, or repeated(allowing a list of values in a single property). All entities in a table have the same set of allowable properties. All entities in a table have the same set of allowable properties. A sequence of properties is used to form the primary key of the entity, and the primary keys must be unique with in the table. Figure 3 shows an example schema for a simple photo storage application.Megastore tables are either entity group root tables or child tables. Each child table must declare a single distinguished foreign key referencing a root table, illustrated by the ENTITY group KEY annotation in Figure3. Thus each child entity references a particular entity in its root table(called the root entity). An entity group consists of a root entity along with all entities in child tables that reference it. A megastore instance can have several root tables, resulting in different classes of entity groups.In the example schema of Figure 3, each user's photo collection is a separate entity group. The root entity is the User, and the photos are child entities. Note the photo. tag field is repeated, allowing multiple tags per photo without the need for a sub-table.3.2.1 pre-joining with KeysWhile traditional relational modeling recommend that all primary keys take surrogate value, Megastore keys are chosen to cluster entities that will be read together. Each entity is mapped into a single Bigtable row; the primary key values are concatenated to form the Bigtable row key, and each remaining property occupies its own Bigtable column.Note how the Photo and User tables in figure 3 share a common user_id key prefix. The IN TABLE USER directive instructs Megastore to colocate these two tables into the same Bigtable, and the key ordering ensures that Photo entities are stored adjacent to the corresponding User. This mechanism can be applied recursively to speed queries along arbitrary join depths. Thus, users can force hierarchical layout by manipulating the key order.Schemas declare keys to be sorted ascending or descending, or avert sorting altogether: the scatter attribute instructs Megastore to prepend a two-byte hash to each key. Encoding monotonically increasing keys this way prevents hotsots in large data set that span Bigtable servers.3.2.2 IndexesSecondary indexes can be declared on any list of entity properties, as well as fields with in protocol buffers. We distinguish between two high-level classes of indexes: local and global (see Figure2). A local index is treated as separete indexes for each entity group. It is used to find data within an entity group. In Figure3, PhitiByTime is an example of a local index. The index entries are stored in the entity group and are updated atomically and consistently with the primary entity data.a global index spans entity groups. It is used to find entities without knowing in advance the entity groups that contain them. The phitisByTag index in Figure 3 is global and enables discovery of photos marked with a given tag, regardless of owner. Global index scans can read data owned by many entity groups but are not guaranteed to reflect all recent updates.Megastore offer additional indexing features:storing clause(物化视图)repeated indexesInline Indexes.3.2.3 mapping to BigtableThe Bigtable column name is a concatenation of the megastore table name and property name, allowing entities from different Megastore to be mapped in to the same Bigtable row without collision. Figure 4 show how data from the example photo application might look in Bigtable.Within the Bigtable row for a root entity, we store the transaction and replication metadata for the entity group, including the transaction log. Storing all metadata in a single Bigtable row allows us to update it atomically through a single Bigtable transaction.Each index entry is represented as a single Bigtable row; the row key of the cell is constructed using the indexed property values concatenated with the primary key of the indexed entity. For example, the photosByTime index row keys would be the tuple(user_id,time,primary key) for each photo. Indexing repeated fields produces one index entry per repeated element. For example, the primary key for a photo with three tags would appear in the photosByTag index thrice.3.3 Transactions and concurrency contorlEach Megastore entity group functions as a mini-database that provides serializable ACID semantics. A transaction writes its mutations into entity group's write-ahead log, then the mutations are applied to the data.Bigtable provides the ability to store multiple values in the same row/column pair with different timestamps. We use this feature to implement multiversion concurrency control(MVCC): when mutations within a transaction are applied, the values are written at the timestamp of their transaction. Readers use the timestamp of the last fully applied transaction to avoid seeing partial updates. Readers and writers don't block each other, and reads are isolated from writes for the duration of a transaction.3.1.1 queuesQueues provides transactional messaging between entity groups. They can be used for cross-group operations, to batch multiple update into a single transaction, or to defer work. A transaction on an entity group can atomically send or receive multiple message in addition to updating its entities. Each message has a single sending and receiving entity group; if they differ ,delivery is asynchronous.(See figure 2)Queues offer a way to perform operation that affect many entity groups. For example, consider a calendar application in which each calendar has a distinct entity group, and we want to send an invitation to a group of calendars. A single transaction can atomically send invitation queue messages to many distinct calendars. Each calendar receiving the messages will process the invitation in its own transaction which updates the invitee's state and deletes the message.There is a long history of message queues in full-featured RDBMSs. Our support is notable for its scale: declaring a queue automatically create an inbox on each entity group, giving us millions of endpoints.3.3.2 two-phase commitMegastore supports two-phase commit for atomic updates across entity groups. Since these transactions have much higher latency and increase the risk of contention, we generally discourage application from using the feature in favor of queues. Nevertheless, they can be useful in simplifying application code for unique secondary key enforcement.
Dynamo：亚马逊的高可用键值对存储概要在大规模下的可靠性是我们在亚马逊一个大的挑战，一个世界上最大的电商系统。即便是轻微的中断也会明显的财务影响并且影响了客户的信任。亚马逊平台提供了给世界尺度的很多网站提供服务，在成千上万台基础设施上实现的，并且网络组件位于许多遍布世界的数据中心。在这个规模下，小或者大的组件连续不断的故障，面对这些故障时管理持久化状态的方式驱动了可靠的可扩展的软件系统。这个paper提出了设计和Dynamo的实现，一个高可用的键值对存储系统，亚马逊的一些核心服务就是用它来提供永远的在线体验的。为了达到这种级别的可用性，Dynamo牺牲了在某些故障场景下的一致性。它以一种为开发人员提供新颖接口的方式，广泛使用了对象版本控制应用辅助的冲突解决，1 介绍亚马逊运行着世界范围的电商平台，在高峰时段为数以千万的客户提供服务，使用上万台服务器位于世界的许多数据中心。在亚马逊平台上的操作对于性能，可靠性，有效性方面有严格的要求，为了支持持续增长，平台需要具有高度可扩展性。可靠性是一个最重要的需求，因为即便是小的中断也会导致明显的经济后果和影响客户的信任。此外，为了支持持续的增长平台徐亚高扩展性。我们团队组织从运营亚马逊平台中学到的经验之一，系统的可靠性可扩展性依赖于如何管理应用程序状态。亚马逊使用了高度去中心化的，松耦合的，面向服务体系结构，由数百个服务组成。在这个环境特别需要强大的永远可用的存储技术。例如客户有能查看和添加项目到购物车即便磁盘故障。网络线路不稳定，数据中心被龙卷风摧毁。因此，服务负责管理购物车他可以永远被读取和写入在数据存储，数据需要跨多个数据中心高可用。处理由百万个组件组成的基础设施中的故障是我们标注的操作模式；总会有几个小的但是显著数量的服务和网络组件在一些给定时间内故障。因此亚马逊软件系统需要构建一种方式，他将异常视为正常情况而不影响可用性和性能。为了应对可靠性和扩展性需求，亚马逊开发了几个存储技术，其中Amazon Simple storage Service (也可以在亚马逊之外访问到，被称为Amazon S3)，可能是最有名的。这篇论文提出了Dynamo的实现和设计。在亚马逊平台上构建的另一种高可用的可靠的可扩展的分布式数据存储。Dynamo被用来管理服务状态，它们对可靠性的需求非常高并且需要严格的控制，可用性，一致性成本效益和性能。amazon平台有非常多样的应用在不同的存储需求。选择一组应用需要一种存储技术，他足够弹性，以让应用设计人员根据这些权衡适当的配置数据存储以实现高可用，使用最划算的方式保证性能 。许多在亚马逊平台上的服务他们只需要键值对访问。对于许多服务，比如提供畅销排行榜的，购物车，客户偏好，会话管理，销售排名和产品目录，使用关系型数据库的常见模式会导致低效率以及限制了规模和可用性。Dynamo提供了简单的键值对接口，以应对这些应用的需要。Dynamo使用了一些工作的良好的技术综合以达到可扩展性和可靠性：数据被通过一致性哈希进行分区和复制。通过在更新期间保持副本的一致性通过法定人数技术和去中心化的复制同步协议。Dynamo使用了基于gossip的故障探测和成员协议。Dynamo是一个完全去中心化的系统并且最小化手动管理的需求。存储节点可以在Dynamo添加或者删除而不需要任何手动分区或者重分布。在过去的一年中，Dynamo已经成为了亚马逊贸易平台中的几个核心服务的底层存储技术。它能够在节假日扩展到极端的峰值负载而无需任何停机时间。例如，维护购物车的服务服务于数千万的请求在同一天就有超过300万的结账，管理会话状态的服务处理数十万的活动会话。这项工作对于学术届的主要贡献是评估了如何结合不同的技术来提供单一的高可用性系统。他展示了最终一致性的存储系统可以被用在对于有着高要求的应用。他也提供了对这些技术调优的深入理解以应对生产系统非常严苛的性能需求。背景亚马逊的电商平台由几百项服务组成，这些协同功能从推荐到订单履行到欺诈检测的各种功能。每个服务都通过良好定义的接口进行暴露可通过网络访问。这些服务被托管于由上万个服务谓语世界范围内的数据中心。其中的一些服务是无状态的（服务聚合从其他服务的影响）一些是有状态的（即服务在他存储在持久化系统的状态上执行业务逻辑，生成它的相应）。传统的生成系统存储他们的状态在关系型数据库中。然而， 对于许多常见的状态持久化的使用模式，关系系数据库是非理想的解决方案。他么中的大部分服务只存储并检索数据，不需要关系型数据库管理系统提供的功能复杂的查询和管理。这种多余的功能需要昂贵的硬件和高技能的操作人员，这是一个非常低效的方案。此外，可用的复制技术是有限的，通常选择一致性而不是可用性。虽然尽管近年来取得了许多进展，横向扩展数据库依然不简单，或者使用智能的分区模式以负载均衡。这篇论文描述了Dynamo，一个高可用的数据存储技术解决了这些重要类型的服务的需求。Dynamo有简单的键值对接口，他具有明确定义的一致性窗口的高可用，在资源存储中是有效的，并且有一个简单的扩展方案来解决数据集大小或请求率的增长。每个使用Dynamo运行自己的Dynamo实例。2.1 系统假设和需求此类业务对存储系统的要求如下：查询模型：简单的读取和写入操作到到数据条目，她被通过key唯一进行标识。状态就像二进制对象一样被存储（blobs）被唯一的key定义。没有跨多个数据项的操作，也不需要关系模式。这个需求基于一个显著的观察，亚马逊的服务可以在简单的查询模型下工作，并且不需要任何关联模式。Dynamo目标一样需要存储的对象通常小于1MB。ACID属性 ：ACID（atomicity，consistency，isolation，durability）是一组保证数据库事务处理可靠性的资源。在数据库文本中，单一逻辑的操作被叫做事务。在亚马逊用的经验已经展示了提供事务的数据存储提供了差的可用性。这已经被机构和学界所认可。Dynamo 目标一样他操作是弱一致性的（ACID中的C）如果这导致高可用性。DynamoDynamo不提供任何的隔离性保证，许可只有单个键更新的时候。有效性：系统需要功能谓语通用的硬件基建之上。在亚马逊平台，服务有很明显的延迟要求，通常在分部99.9%处测量。鉴于状态访问在服务中扮演了重要的决策，存储系统必须能够面对这样严苛的SLA。服务必须能够配置Dynamo，这样他就能始终如一的达到延迟和吞吐量。成本效益，可用性和持久性保证之间做出权衡。其他假设：Dynamo被用来亚马逊内部的服务。他的操作环境被假设为非敌对的，不存在认证授权等安全相关需求，此外，因为每个服务使用了Dynamo的不同实例，它最初的设计模板是多大数百台存储主机的规模。我们将会讨论Dynamo可靠性限制并且可扩展性和相关的扩展在之后讨论。2.2 服务水平的协议（SLA）为了保证应用可以在有限的时间内交付它的功能。平台中的每个依赖项都需要在更严格的范围内交付其他功能。客户和服务签订服务水平协议（SLA），正式协商的合同，其中客户端和服务就系统的几个特征达成一致，其中最突出的是包括客户端的预期的特定API的请求率分布以及这些条件下预期的服务延迟。一个简单的SLA的例子是服务保证了他在300ms内提供响应百分之99.99%的请求在峰值时客户端每秒负载500个请求。在亚马逊去中心化导向的基建，SLA扮演了重要的角色。例如，一页的请求达到一个电商网站通常需要呈现引擎构造其相应，通过调用超过150个服务。这些服务通常由多个依赖，这些经常是其他的服务，因此程序调用图有多个级别并不罕见。为了确保页面呈现擎可以维护明确的界限，调用链中的每个服务都必须遵守其性能契约。图1：亚马逊平台上面向服务的架构图1展示了亚马逊平台的抽象架构图，其中动态的web内容被页面呈现组件，这些组件反过来查询许多其他的服务。一个服务可以使用不同的数据存储来管理他的状态，这些数据存储是只能在他的服务边界内访问。一些服务的行为像聚合器，通过使用几个其他的服务生成复合响应。通常聚合器服务是无状态的，虽然他们使用了庞大的缓存。业界形成面向性能的SLA的常用方法是使用均值，中值和期望变量来描述它。在亚马逊我们发现了这些指标不足够好，如果想要构建一个系统让所有的用户有良好的体验，而不只是大多数。例如，如果使用广泛的个性化技术，那么具有较长历史的用户需要更多的处理，这会影响分布上端的分布性能。用中指或者均值响应时间表示SLA不能解决这一部分客户群体的表现。为了解决这个问题，在亚马逊中，SLA表达和衡量的是第99.9百分位的分布。这个选择对于99.9%或者更高的百分位已经基于成本效益分析得出，展示了提高性能成本的显著增加。亚马逊的生产环境系统已经表明，与那些满足基于平均值或中位数定义的SLA的系统相比，这种方法提供了更好的整体体验。在这个paper中很多次提到了分布中的99.9百分位，这反应了亚马逊工程师持续的站在客户经验的角度专注于性能。许多论文都上报了平均值，所以当在有意义的情况下这些会被包含进来用于比较。然而亚马逊工程师和优化工作并不聚焦于平均值。几个技术，比如负载均衡选择了协调者，是完全具有针对性的在控制性能在99.9的百分位上存储系统通常在建立一个服务的SLA中扮演了重要的角色，特别是业务逻辑相对轻量级的时候，亚马逊的许多其他服务器也是如此。一个主要设计的考虑是因为Dynamo是让服务控制它们的属性，比如持久性和一致性，并且让服务在功能性和性能和成本效应之间做权衡。2.3 设计考虑商业系统中的数据复制算法传统上执行同步副本协调以提供强大的一致性数据访问接口。为了达到这个级别的一致性，这些算法聚焦于在特定的故障场景做权衡。例如，与其处理答案是否正确的不确定性，不如让些数据是绝对正确的否则不能使用这些数据。在一个非常早起的复制数据库工作，当处理可能的网络故障时，强一致性和高可用性不可能被同时达到，这一点广为人知。这些系统和应用需要知道哪个属性可以在哪个条件下被达到。对于容易出现网络故障的系统，通过优化复制技术可以增加可用性，允许将改变传播到后台的副本，并且允许并发的，断开连接的工作。这些方法带来的挑战可能必须检测和解决相互冲突的更改。这个冲突解决的过程导致了俩个问题：什么时候解决他们以及谁来解决它们。Dynamo被设计为最终一致性的数据存储；也就是说所有的更新最终会达到副本。一个重要的设计考量是决定什么时候执行解决更新冲突的处理，即是否应该在读写期间解决冲突。一些传统的数据存储执行冲突解决在写入的时候并且保持读取的复杂性较低。在这样的系统中，如果数据存储不能达到所有的（或者大多数）节点在给定时间中，写入可能会被拒绝。另一方面，Dynamo的目标是“始终可写”数据存储的设计空间（即：数据存储对于写入高可用）。对于一些亚马逊的服务，拒绝客户的更新会导致糟糕的客户体验。举个例子，购物车服务必须允许用户添加或者删除购物车的项目。即便网络出现故障的情况下也是如此。这一需求强迫我们推动冲突解决的复杂性到读取去却把写入永远不会被拒绝。下一个设计选择了谁来执行这个冲突决议。这个可以通过数据存储或者应用来完成。如果冲突决议被数据存储完成，他的选择非常有限。在这个例子中数据存储只能使用简单的策略，比如最后写入的得胜以解决冲突更新。另一方面因为应用知道数据冲突的模式他可以决策冲突决议方法，这对于客户端的体验来说是非常合适的。例如，那些管理客户购物车冲突的应用可以选择合并冲突的版本并且返回一个一致的购物车。即便有这种特性，一些应用开发者可能不想编写自己的冲突解决机制，并选择将其下推到数据存储中，这样反过来又选择了一个简单的策略，比如因为最后一次写为获胜。设计中包含的其他关键原则是：增量可扩展性：Dynamo应该能过横向扩展（之后称作节点）在一个时间，并且最小化对于系统操作和系统本身的影响。对称性：每一个节点在Dynamo中应该和对等节点有相同的指责；没有特殊角色的节点或者有额外特殊职责的节点。在我们的经验中，对称性简化了系统的配置和维护过程。去中心化：一个对称性的延伸，设计应该偏好于去中心化的p2p技术不受中心化的控制。在过去，中心化的结果导致了停机，我们的目的是尽量避免它们。这导致了简单的，可扩展的和更可靠的系统。异质性：系统需要能够利用跑在基础设施上的异质。即工作分布必须与单个服务器的能力成比例。这是非常重要的对于添加新的高容量的节点，而无需对所有主机位进行升级。3 相关工作4 系统架构存储系统需要的操作在生产环境是复杂的。除了真正的数据持久性组件，系统需要扩展和健壮解决负载均衡，成员和故障探测，复制同步，过载处理，状态转换，一致性和工作调度，请求整理，请求路由，系统监控和报警以及配置管理。描述每个解决方案是不可能的，这篇论文聚焦于核心的分布式系统技术在Dynamo中的使用：分区，复制，版本管理，成员，失败处理和扩展。4.1 系统接口Dynamo通过相关联的键使用简单的接口；他暴露出来了俩个操作，get()和put()。get(key)操作定位对象副本在存储系统中和key的关联，并返回冲突版本的单个对象或者对象列表以及上下文。put(key,context,object)根据关联键放置对象副本的位置，并且写入副本到磁盘。context编码了系统关于对象的元数据，他们对于调用者来说是不透明的比如对象版本等信息。上下文信息与对象一起存储，以便系统可以验证放置请求中提供的上下文对象的有效性。Dynamo同时处理调用者提供的键并且都将对象视为不透明的数组。他使用MD5哈希来生成128位的标识符，这杯用来确定服务这个key的存储节点。4.2 分区算法一个对于Dynamo关键的设计是它必须逐渐的扩展。这需要机制来动态的分区数据在整个节点的集合上在系统中。Dynamo的分区模式依赖于一致性哈希以分布负载穿过多个存储主机。在一致性哈希中，哈希的函数的输出范围如同一个固定的圆空间或者环（即从最大的环绕到最小的哈希值）。系统中的每个节点指派一个在空间中的随机值他表示环上的位置。每个由键标识的数据项通过散列数据项的键来获得其在环上的位置，从而分配给节点，然后顺时针遍历环，找到一个位置大于项目位置的节点。因此每个节点都负责他在环上和前一个节点之间的区域。一致性哈希的主要优点是一个节点离开或者只到达影响它的邻近，其他节点维持不受影响。基础的一致性哈希算法提出了一些挑战。首先环上各个节点随机位置分配导致了负载分布的不均衡。其次基础算法忽略了节点性能之间的异质性。为了解决这个问题，Dynamo使用了一致性哈希的变体：不是将节点映射到环中的单个点，每个节点分配到环中的多个点。为了这个目的，Dynamo使用虚拟节点。一个虚拟节点就像在系统中的单个节点，但是节点可以负责超过一个的虚拟节点。实际上，当新的节点添加到系统中，它指派多个位置（之后叫做token）在环中。Dynamo分区方案的微调过程将在第6节中讨论。使用虚拟节点有如下的优势：如果一个节点不可用（由于失败或者日常维修），这个节点上处理的负载均匀的分布在剩下的可用节点上当一个节点再次可用，或者新的节点被添加到系统中，新的可用节点接受和其他可用节点大致相等的负载。节点负责的虚拟节点的数量可以根据节点的容量来进行确定，考虑到物理基础设施的异质性。4.3 复制为了实现高可用性和耐用性，Dynamo复制它的数据到多个主机上。每个数据项被复制到n个主机上，其中n是每个实例可以配置的参数。每个键k分配一个给协调器节点（在前一张描述）。协调者负责复制其范围内的数据项。除了本地存储范围内的每个键之外，协调器复制这些键在环中n-1个顺时针的后继者节点。这导致了在系统中每个节点负则它和在它之前的第n个环区域。在图2中，节点B复制在c和d上的的键key，并将其存储在本地。节点D存储落在范围(A, B], (B, C], and (C, D].中的数据。负责存储特定键的节点列表被叫做preference偏好列表。系统的设计将会在4.8章进行解释，所以系统中的每个节点可以决定对于特定的键，哪个节点应该在列表中。为了考虑节点故障，偏好列表维护了n个节点。注意通过使用虚拟节点，对于特定键的前n个节点可能被小于n个物理节点持有（即节点可能保存前N个位置中的多个位置）。为了解决这个问题，键的偏好列表通过跳过环中的位置来进行构建以确保列表只包含不同的物理节点。4.4 数据版本Dynamo提供了最终一致性，这允许更新异步的传播到所有的副本。put() 调用可能在更新尚未应用到所有副本之前就返回给调用者，这可能导致后续的 get() 操作返回一个没有最新更新的对象。如果没有失败，更新的传播时间会有边界。然而，在不确定失败的场景下（即，服务退出或者网络分区），更新可能在很长的时间内不能到达所有副本。亚马逊平台的一类应用类型可以忍受这种不一致，并且可以在这个条件下构建操作。例如，购物车应用程序要求永远不能忘记或拒绝添加购物车操作。如果最新状态不可用，并且用户对购物车的旧版本进行了更改，这种变化是有意义的，应该被保留。但是与此同时，它不应该取代购物车不可用的状态，它本身可能包含应该被保留的变化。记住无论是添加购物车还是删除购物车操作都会被翻译为put请求到Dynamo。当用户想要添加一个项目（或者删除）到购物车最后的版本是不可用的，该项目天极爱（或者从中删除）就的版本不同的版本应该在之后被调和。为了提供这种保证，Dynamo处理每次修改的结果作为一个新的不可变的数据版本。它允许对象的多个版本在系统的不同时间被提出。大部分时候，新的版本包含了老的版本并且系统本身可以授权版本（语义调和）。然而版本可能会出现分歧，在存在故障和伴随着并发冲突更新的情况下，导致对象版本的冲突。在这个例子中，系统无法协调同一个对象的多个版本，客户端必须进行调和将数据演化的多个分支合并为一个（语义复制）。一个典型的合并操作的例子是merge客户购物车的不同版本。使用调和机制，添加到购物车操作不会丢失，然而，删除项目可能重新出现。这对于理解特定的故障模型可能导致系统有俩个但是不同版本的相同数据很关键。在网络存在分区时和节点故障时的更新可能潜在的导致了具有不同版本子历史对象，系统将会在未来对这些进行调和。这就要求我们在设计应用程序时明确承认同一数据存在多个版本的可能性（以不丢失任何的更新）。Dynamo使用了向量时钟以补货不同版本对于相同对象的因果关系。向量时钟是一个有效的(node，counter)对列表。一个向量时钟与每个对象的版本相关联。通过检查向量向量时钟，可以确定一个对象的俩个版本是在平行分支上还是有因果顺序，如果第一个对象的计数器是小于或者等于第二个时钟的所有节点，那么前者是后者的祖先可以被遗忘。否则，俩个变化被认为是冲突的需要调和。在Dynamo中，当一个节点希望更新一个对象，他必须指名要更新的版本。这是通过 传递从先前读取的上下文来实现的，它结合了向量时钟的信息。在处理读请求时，如果Dynamo访问了多个分支，这在语义上是无法调和的，它会返回所有叶子上的对象，以及在上下文中对应的版本信息。使用此上下文的更新被认为已经调和了不同的版本，分支被折叠成单个新版本。为了演示向量时钟的使用，让我们来考虑一个例子如图3所示。一个客户端写入新的对象。节点（Sx）处理这个键的写操作以增加它的序列号，并且创建了数据向量时钟。系统现在有对象D1和相关的时钟[(Sx,1)]。客户端更新对象。假设相同的节点处理这个请求。系统现在有对象D2和它相关联的时钟[(Sx, 2)]。D2从D1位置下降因此替代D1，然而可能在尚未看到D2的节点上存在D1的副本。让我们假设相同的客户端再一次更新对象并且不同的服务（Sy）处理请求。系统现在有数据D3和它相关联的时钟[(Sx, 2), (Sy, 1)]。下面假设不同的客户端读取D2，并且尝试更新它，另一个节点（Sz）进行写入。系统现在有D4（D2的后代）它的版本时钟是[(Sx, 2), (Sz, 1)]。D1或D2的节点可以在接受时确定D4和它的时钟，D1和D2被新的数据覆盖，可以被垃圾收集。一个节点知道D3并且接收D4将会发现它们之间没有因果关系。换句话说，D3和D4的变化没有相互反应。必须保持俩个版本数据并呈现给客户（在读取时）以进行语义协调。现在假设一些客户机读取了D3和D4（上下文将反应俩个值都是由read找到的）。读取的上下文是D3和D4的总结，即 [(Sx, 2), (Sy, 1), (Sz, 1)]。如果客户端执行调和，并且节点Sx协调了些操作，Sx将会更新它在时钟中的序号[(Sx, 3), (Sy, 1), (Sz, 1)]。向量时钟的一个问题是向量时钟可能会增加许多服务协调写入到对象的大小。在现实中这是不可能的，因为些通常在头n个偏好列表的节点中的一个进行写入。在网络分区的例子或者多个节点失败的例子中，写入请求可能被不在topn个偏好列表中的节点进行处理导致向量时钟的增长。在这个情况下，最好限制向量时钟的大小。为此，Dynamo使用了以下的时钟截断方案：为每个（节点，计数器）对，Dynamo存储一个时间戳，它代表了节点更新数据项最后的时间。当（节点，计数器）对的数量在向量时钟达到了预制（比如10），最后的对见会被从时钟中移除。这种截断模式可能导致调和的低效后台的关系不能被准确交付。然而这个问题还没在生产环境中出现，因此还没有得到彻底的调查。4.5 执行get()和put()操作Dynamo中存储任何节点都有资格接受针对客户端任何秘钥的get和put操作。在这一章节中为了简单我们描述了这些操作如何在无故障的环境下进行执行，在之后的章节我们讨论操作在有故障的时候进行执行。get和put操作执行都是通过HTTTP在亚马逊的特定基础设施处理框架调用的。客户端可以使用俩中策略来查找节点。通过一般的负载均衡器路由请求它们会给予负载信息来选择节点。使用了解分区的客户端库它直接路由请求到合适的协调者节点。第一种方法的优点是，客户端不必在其应用程序中链接任何特定于Dynamo的代码，第二个策略可以达到低延迟因为它跳过了潜在的转发步骤。一个节点处理读取和写入操作的节点称之为协调器，一般这是选项列表前N个节点的第一个。如果请求是通过负载均衡器接受的，请求节点可以路由到环中的任意一个节点。如果节点不在请求键首选列表的前N位，在这个情况下，接收请求的节点将不会协调。相反，该节点吧请求转发给首选项列表中的第一个。在偏好列表中，读取和写入操作相关的前N个健康的节点，跳过那些已经下线的或者无法访问的。当所有节点都运行正常时，将访问键首选项列表中的前N个节点。当节点故障或者网络分区，访问优先级列表中排名较低的节点。为了保持副本之间的一致性，Dynamo使用了一致性协议类似于法定人数系统所使用的。该协议有俩个可配置的键值：R和W。R是必须参加成功读取操作的节点最小数量。W是必须成功写入操作的节点数量。设置R和W 使得R+W>N产生一个类法定人数的系统。在这个模型中，get(或者put)操作的延迟依赖于最慢的R和W副本。处于这个原因R和W通常被配置为小于N已提供更好的延迟。在接收到对key的put请求时，协调者生成一个新版本号的向量时钟，并且本地写入新版本。协调者之后发送新的版本（以及新的向量时钟）到N个最高的排行的可达节点。如果只少有w-1个节点响应了，那么写入被视为成功。类似的，对于get()请求，协调器从首选列表中排名最高N个可达节点中请求该键所有现有版本的数据，然后等待R个响应，然后将结果数据返回给客户端。如果协调器收集了多个版本的数据，它返回所有它认为没有因果关系的版本。然后对不同的版本进行协调，并将取代当前版本的协调版本写回来。4.6 处理故障：提示转交在Dynamo中传统的法定人数方法在服务故障和分区期间，即便在最简单的失效条件下也会降低耐久性。为了解决这个问题，它不强制的执行法定人数成员作为替代使用sloppy quorum（草率法定人数）；所有的读取和写入操作在偏好列表中前N个健康的节点上执行；这可能不总是在遍历一致性哈希环遇到的前N个节点。考虑一个Dynamo配置在图2中让N为3的例子。在这个例子中，如果节点A临时下线下线或者在写入操作中不可达，然后通常存在于节点A上的副本被发送到了节点B。这样做是为了维护所需的可用性和持久性保证。发送给D的副本将会在元数据中有提示，这表明了那个节点是预期的接受者（这个例子中的A）。接受到提示副本的节点将会吧他们保持在独立的本地数据库，并定期扫描，一旦A已经回复，D会尝试将副本交付给A。一旦转换成功，D可以删除来自本地存储的对象，而不需要减少系统中副本的总数。使用提示转交（hinted handoff），Dynamo确保了读取和写入操作不会因为节点的临时故障而写入失败。需要最高级可用性的应用可以将w设置为1，这确保了只要一个节点在系统中持久的写入键到它的本地存储，系统就可以接受写入。因此只有系统中的所有节点都不可用时写入才会被拒绝。然而，现实中亚马逊服务大部分都在生产环境中设置更高的w以面对所需的持久性水平。我们将在第6章详细的讨论配置N、R和W。高可用的存储有能力去处理数据中心级别的故障是非常重要的。数据中心故障可能会由于店里供应散热失效，网络故障和自然灾害。Dynamo是可以配置为每个对象都被付出在多个数据中心。本质上键的首选项列表的构造使得存储节点分布在多个数据中心。这些数据中心通过告诉的网络连接起来。这种跨多个数据中心的复制方案允许我们处理整个数据中心的故障，而不会造成数据中断。4.7 处理永久性故障 ：副本同步如果系统成员流失率很低并且节点故障很短暂，暗示着切换状态最好。在某些情况下，副本返回到原始副本节点之前变得不可用。为了处理这个和其他耐久性的威胁，Dynamo实现了反熵（副本同步）协议已保持副本同步。为了快速和最小传输数据的代价，探测副本之间的不一致。Dynamo使用了merkle tree。Merkle tree是一个哈希树，其叶子是单独key的哈希值。树中较高的父节点的其他它子节点的哈希值。Merkle tree的主要优点是，每个树的树干可以单独的被检查，而不需要节点下载整个树或者数据集。此外，Merkle tree帮助减少了需要传输的数据量，同时检查不同数据副本的不一致。例如，如果俩个根节点的哈希值相同，叶子节点在树中是相同的，此时节点不需要同步。如果不是，这意味着一些副本的值是不同的。在这种情况下，节点可能会交换子节点的哈希值，这个过程一直持续到到达树的叶子，此时主机可以识别出“不同步”的键。Merkle树最小化了需要为同步传输的数据量，并且减少了磁盘读取执行在反熵过程中的次数。Dynamo使用merkle树进行反熵如下：每个节点维护他托管key范围的merkle树（虚拟节点覆盖的键集合）。这允许节点比较，范围内的键是否是最新的。在这个模式下，俩个节点交换他们共同托管的对应键范围内的merkle树的根。随后使用树遍历之前描述的确定节点，如果有任何不同就执行同步操作。这个模式的缺点是，当节点加入或者离开系统许多键的范围会改变，因此需要重新计算树。这个问题已经通过精致的分区被解决，在6.2章中进行描述。4.8 成员和失败探测4.8.1 环成员在亚马逊中节点听起（由于失败和维护任务）通常是转瞬即逝的，但可能会持续很长的间隔。节点中断很少意味着永久的离开，因此不会导致分区作业的不平衡或者副本不可达。类似的手动的错误可能导致无意识的启动新的Dynamo节点。因为这个原因，使用显示的机制来初始化添加或者删除Dynamo中的节点是合适的。管理员使用命令行工具或者浏览器以连接到Dynamo节点并且发出成员改变加入节点到环中或者删除环中的节点。节点服务于请求写入成员改变，并且他持久化存储发送时间。历史的成员改变来自历史，因为节点可以删除或者添加可以来回多次。一个基于gossip协议传播成员的改变并且维护最终一致性的成员视图。每个节点的联系人是在随机时刻被对等的选择，并且节点有效的调和成员在历史中的冲突。当节点在第一时间启动， 他选择它的token集合（一致性哈希空间的虚拟节点）并且映射节点到他代表的token集上。映射在磁盘上持久化，初始化只包含本地节点和token集合。存储在不同节点上的映射在同一通信之间被协调，这个协调了成员之间的修改历史。因此，分区和防止信息也通过gossip协议传播，并且每个存储节点知道他对等节点处理的token的范围。这允许每个节点转发键的读取写入操作到直接到正确的节点。4.8.2 外部发现上面的机制可能暂时导致Dynamo环中的分区。例如，管理员可能联系节点A将A加入到环中，联系节点B将B加入到环中。在这个场景下，节点A和B每个都认为自己是环中的一员，然而双方都不会立刻意识到对方。为了维护逻辑分区，一些Dynamo节点扮演者种子的角色。种子是通过外部机制发现，并且被所有节点知道的节点。因为所有节点最终都用一个种子来调和他们成员的关系，因此逻辑分区是非常不可能的。种子可以在静态配置文件或者配置服务中得到。通常，种子在Dynamo中是彻底的功能性节点。4.8.3 故障探测故障探测在Dynamo中被用来避免，当传输分区时暗示副本，在不平衡的节点中的在get和put操作时的尝试通信，故障检测纯粹的局部性概念是完全足够的：如果节点B不响应节点A的信息，节点B考虑出现故障（即便节点B响应节点C的信息）。在Dynamo环中客户端请求在节点通信之间产生的稳定速率存在时，当节点B失败的回复信息，一个节点快速的发现节点B是没有反应的。之后节点A使用备份节点来处理服务请求映射到B的分区；A定期重试B以检查后者的恢复情况。在缺乏客户端节点请求驱动俩个节点之间的流量时，俩个节点都不需要知道另一个节点是可达还是不可达的。去中心化的故障探测使用了简单的gossip风格的协议，他允许系统中的每个节点学习如何到达（或者离开）另一个节点。有关分散故障检测器和影响其精度的参数的详细信息，请参阅有兴趣的读者。更早的Dynamo的设计使用了去中心化的故障探测已维护故障视图的全局一致性。后来确定，显式节点加入或者离开方法消除了故障状态全局视图的需要。这是因为节点会收到永久性节点添加的通知，通过显式的加入节点加入和离开进行删除，当与其他节点沟通失败，通过独立的节点进行探测（同事转发请求）。4.9 添加和删除存储节点当一个新的节点（如X）加入了系统，他得到指派的token编号 ，这个编号在环上是随机分散的。对于每个指派给x的键的范围，可能存在多个节点（小于或者等于N），它们负责处理范围内的秘钥。由于将秘钥的范围分配给X，一些已经存在的节点不长期持有键并且这些节点传输他们的键到X。让我们来考虑简单的启动场景，其中接地那X被添加如图2所示的环中，在A和B之间。当X被添加到系统中，他负责存储范围(F, G], (G, A] 和(A, X]的秘钥。作为结果，节点B，C和D补偿器存储这个表示的范围。因此，节点B，C和D将会提供并且在确认后转移适当的秘钥。当节点在系统中删除，秘钥的再分配发生在相反的过程中。秘钥的重新分配发生在相反的过程中。操作经历已经展示了这个方法分发键的负载一致的穿过存储节点，他对于应对延迟的徐亚和确保快速启动非常重要。最后通过在资源和目标之间添加配置圆，他确保了目标节点对一给定的key范围不会接受任何重复读传输。5 实现在Dynamo中每个存储节点有是哪个主要的软件组件：请求协调，成员与故障探测，以及本地持久化引擎。 所有的这些组件都是用java实现的。Dynamo的本地持久化组件允许不同的存储引擎插入。Berkeley 数据库（BDB），传统数据存储，BDBJAVA版本，MYSQL。设计一个可插拔的持久化组件的主要原因是为了选择最适合应用访问模式的存储引擎。例如，BDB可以处理典型的十几KB大小的对象，而MySql可以处理更大的对象。应用基于他的对象大小的分布，选择Dynamo的本地持久化引擎。Dynamo大部分的生产实力使用了BDB事务数据存储。SEDA（Staged Event-Driven Architecture，分阶段事件驱动架构）是一种高性能、可伸缩的系统架构设计模型，旨在更好地管理复杂和高并发的应用程序。SEDA 最初由 Matt Welsh 在其博士论文中提出，用于解决传统线程池模型和事件驱动模型在高负载条件下的不足。请求协调者组件是在事件驱动的消息传递底层之上构建的。其中消息处理流水线被切分到多个状态类似于SEDA架构。所有的沟通使用Java的NIO管道进行实现。协调者通过收集一个或多个的执行读取和写入请求在客户代理上（在读取的例子中），或者存储数据在一个或者多个节点上（为写入）。在客户端请求的节点上，每一个客户端请求都会创建一个状态机。状态机包含了所有的定义节点对哪些key负责的逻辑，发送请求，等待响应，可能的进行重试，处理回复并且打包响应到客户端。每个状态机实例只处理一个客户端请求。例如，一个读取操作实现了以下的状态机发送读取请求到节点等待需要响应的最小数量如果在给定时间范围内回复的太少，让请求失败否则手收集所有的数据版本并且确定要返回的版本如果版本可用，执行语法的调和并且生成不透明的写入上下文，他包含了持有剩余版本的向量时钟。为了简洁，故障处理和重试状态在读取响应给调用者后，状态机等待一小段时间以接受任何未完成的响应。如果过期的版本已经在任何的响应中返回了，协调者更新这些节点最后的版本。这个操作被叫做read repair（读取修理），因为它在一个合适的时机修复哪些错过更新的副本，从而减少了反熵协议的负担，不必由它来完成修复工作。如前所述，写请求通过偏好列表中的头N个节点进行协调。尽管他总是希望前N个节点中的第一个节点来协调写操作，从而在单个位置序列化所有写操作，这个方法会导致负载不均，从而违反SLA。这是因为请求负载在是不一致的分布在不同的对象之间。为了解决这个问题，允许偏好列表的前N个节点中的任何一个进行这个操作。特别地，由于每次写入通常是在一次读取操作之后进行的，因此写入的协调节点被选择为对先前读取操作响应最快的节点，该信息存储在请求的上下文信息中。这个优化允许我们选择在之前的读取操作已经写入数据的节点，从而增加“读你写的”一致性。他也减少了请求处理性能的变化，提高了99.9百分位的性能。6 经验教训7 结论在这篇paper中描述了Dynamo，一个高可用的可扩展的数据存储，用来存储Amazon.com电商平台的核心服务的持久化状态。Dynamo已经提出了可用性和性能的渴望即便，并且成功的处理服务失败，数据故障和网络分区。Dynamo是增量可扩展的并且允许服务拥有者基于当前的负载扩展和下调。Dynamo允许服务拥有者，通过允许它们去调整参数N,R和W去定制存储系统以应对他需要的性能，持久性和一致性SLA。最近几年Dynamo的成功已经展示了，去中心化的技术可以联合以提供一个高可用的系统。在最具挑战性的应用环境他成功的展示了，最终一致性存储系统可以发布高可用的应用块。
Cassandra 一个去中心化的结构化存储概要cassandra是一个分布式存储系统已管理大量的结构化数据分布在许多商用服务器上，同时允许在单点故障的情况下提供高可用。Cassandra的目标是运行在上百台节点的基础设施之上（可能分割到不同的数据中心）。在这个尺度下，大的和小的组件故障连续不断。Cassandra在面对这些故障管理持久状态的方式驱动了一来该软件服务的软件系统的可靠性和伸缩性。在很多封面Cassandra类似一个数据库，并与之贡献很多实现策略Cassandra不知此完全的关系模型；作为替代他提供给客户端一个简单的数据模型以支持对数据布局和格式的动态控制。Cassandra的系统被设计为运行在廉价的通用硬件。在处理高吞吐量的同时不影响读取的效率。1 介绍Facebook运行最大的社交网络平台，服务于上亿的用户在峰值时段使用上万台服务器其遍布整个世界。这是一个严格的操作要求facebook的平台的性能，可靠性，有效性有严格的要求，并且支持持续的增长，平台需要高可缩放性。处理包括上千个组件的故障是我们标准运作模式。总会有小的但是明显的服务和网络组件在给定的事件故障。因此，软件系统需要结构化的管理者将失败视为日常而不是意外。为了应对上述的可用性和可缩放需求facebook开发了Cassandra。Cassandra总和使用了知名的技术一达到可缩放和可用性。Cassandra被设计为实现Inbox serch 问题。Inbox是一项功能允许用户搜索他们的facebook收件箱。在facebook中这意味着系统需要处理非常高的写入量，每天上百万的写入，并且随着用户数量的扩大。由于用户从地理分布的数据中心获得服务，允许副本数据穿过数据中心是保证低延迟的关键。Inbox 查询在2008年6月启动服务于大约1亿用户如今我们有超过2.5亿的用户，并且Cassandra还在保持增长。Cassandra现在被部署在后端存储系统为facebook的多个服务服务。2 相关工作分布式数据的可靠性可用性和持久性在文件系统和数据库已经有了广泛的研究。对于只支持平面空间的p2p存储，分布式文件系统特别支持了分级的命名空间。文件系统类似Ficus和Coda 以牺牲一致性为代价来获得高可用性。更新冲突通常使用专门 打冲突解决程序进行管理。Farsite是一个分布式文件系统他不使用任何中心化服务。Farsite使用复制达到了高可用和可缩放。GFS是另一个文件系统以托管谷歌内部的应用状态。GFS使用了简单的单个主设计以托管整个元数据，其数据被切分为chunk并且存储在chunk服务上。然而，GFSmaster使用Chubby的抽象处理容错。Bayou是一个分布式关系型数据库允许不连贯的操作并且提供数据的最终一致性。在这些系统中，Coda和Ficus 允许断开操作并对网络分区和中断问题具有弹性。这些系统在解决冲突上的过程有所不同。例如coda和Ficus执行文件级别的冲突决议，Bayou允许应用级别的解决。然而，他们都保证最终一致性，Dynamo允许读取和写入操作连续，即便是在网络分区的情况下别去使用不同的由客户端驱动的冲突解决机制来解决冲突。传统的复制的关系数据聚焦于保证副本数据的强一致性。虽然强一致性提供了应用写入方便的模型，这写系统限制了可缩放性和可用性。这些系统没有处理网络分区的能力，因为他通常提供强一致性保证。向量时钟（Vector Clock）是一种用于解决分布式系统中并发更新冲突的问题的机制。它通过记录每个节点（或副本）在某个数据项上的修改历史，来追踪这些数据项的状态变化，以便在多个副本并行修改时能够检测到哪些修改是冲突的。在分布式系统中，通常会有多个节点（或副本）处理同一数据项的不同副本。为了确保数据一致性，需要一种机制来判断这些副本是否有冲突，尤其是在它们的更新是并行进行的情况下。向量时钟就提供了一种解决方法。每个节点有一个时钟：系统中的每个节点维护一个向量，记录该节点对数据项的修改历史。向量中的每个元素对应一个节点的时钟，通常是一个整数，表示该节点的修改次数。例如，系统中有三个节点 A、B 和 C，那么每个节点会维护一个三维向量 [A, B, C]，每个维度的值代表该节点对数据项的修改次数。每次修改都会更新时钟：当某个节点修改数据时，它会增加自己的时钟值，同时将这个更新传播到其他节点。例如，假设节点 A 修改了数据，它的向量时钟会变成 [1, 0, 0]（假设初始时钟为 [0, 0, 0]），表示节点 A 对数据进行了第一次修改。向量时钟的传播：当节点 A 将数据更新发送给节点 B 和节点 C 时，它会把自己的向量时钟一并发送过去。接收到更新的节点会更新自己的时钟，确保自己的向量时钟包含其他节点的历史修改。检测冲突：向量时钟的核心在于它能帮助系统识别冲突。例如：如果两个节点同时修改了同一数据项，但修改的顺序无法确定，或者修改的内容互相冲突，则这两个版本会被标记为冲突。如果两个节点的向量时钟不相等，并且没有完全包含对方的历史时钟，那么这两个修改就是并行的，意味着可能会发生冲突，需要进一步处理。向量时钟的核心方案是通过维护每个节点的历史修改来检测分布式系统中是否存在更新或者冲突。Dynamo是一个存储系统他被亚马逊用来存储和检索用户购物车。Dynamo的基于成员的算法帮助每个节点维护其他节点的信息。Dynamo可以定义为一个结构化的覆盖网络，最多有一跳路由请求。Dynamo使用矢量时钟的方案检测冲突，但是更偏好于客户端测解决冲突。Dynamo的写操作也需要执行读取操作来管理矢量时间戳。在系统处理非常高的写吞吐量的环境中，这可能是非常有用的。Bigtable提供了结构和数据分布，但是他的持久性依赖于分布式文件系统。3 数据模式Cassandra中的表是由键缩阴丹分布式多维映射。值是一个高度结构化的对象。行键（row key）在表中是一个字符串但是允许16-36的字节长度。每个操作对每个副本都是原子的，无论读取或写入多少列。列被分组到一起加入一个叫做列族的集合，这与bigtable非常类似。Cassandra暴露了俩种列组，简单和超级列族。超级列族可以被抽象为列族的列族。此外，应用可以指定列的顺序使用超级列族或者是普通列族。系统 允许列变得有序通过时间或者名字。类似iInbox 查询这样的应用利用了列的时间排序，结果总是按顺时间排序的顺序显示。在一个列族（column family）内的任何列都可以通过以下方式访问：column_family : column，任何类型为超级的列都可以通过column_family:super_column:column进行访问。一个关于超级列抽象能力的非常航的例子在6.1。应用程序通常使用专用的Cassandra集群，并将其作为服务的一部分进行管理。虽然系统提供了多个表的概念，但是所有的部署模式只有一个表。4 APICassandra API包含了如下的三个简单方法。insert(table, key, rowMutation)get(table, key, columnName)delete(table, key, columnName)columnName用来指定的列，列族， 超级列族或者超级列中的列。5 系统架构需要在生产环境中运行的系统架构是很复杂的。除了实际的数据存储组件之外，系统须有如下的特性；可缩放和健壮的环境一应对负载均衡成员和故障检，失败回复，复制同步，过载处理，状态转换，实时工作调度，请求编组，请求路由，系统监控和警报与配置管理。描述解决方案的每个细节超出了这个论文的范围，所以我们关注于cassandra使用的核心系统分局技术，分区，复制，成员，故障和缩放。所有的这些模块同步处理负载请求。通常，对于key的读写请求被路由到cassandra的任何节点。节点之后确定特定key的复制。对于写入，系统路由请求到副本并且等待副本的法定数量来确认写操作的完成。对于读取，基于通过客户端对一致性保证的需要，系统要么路由到最近的副本要么路由请求到所有副本并且等待法定人数的响应。5.1 分区cassandra的一个设计的关键特性是增量扩展的能力。这需要在集群中的节点集（即存储主机）上动态划分数据。cassandra使用一致性哈希分区数据跨越集群，但是使用了一个保持顺序的哈希函数。在一致性哈希中，哈希函数的数范围被视为一个固定圆形空间形成的环（即最大的哈希值到最小的哈希值）。每个节点在信息系统中被分配一个随机值，代表它在环上位置。由key标识的每个数据项通过哈希分给每一个节点，数据项的键以获得其在环上的位置，然后顺时钟遍历找到位置大于该数据项的第一个节点。这个节点被视为此键的协调器。应用程序指定此键，并且cassandra使用它路由请求。因此，每个节点负责环中该区域，并且处理环上的节点。一致性哈希的一个主要优点是，一个节点的离开或者到达只影响它的近邻，其他节点仍然不受影响。首先随机的位置指派到圆上的每个节点导致数据和载荷分布不均。通常解决这个方法由俩个问题：一个方法是将节点分配到圆中的多个位置（类似Dynamo），第二是分析圆上的负载信息并且稍微调整环上节点的移动减轻过载节点。cassandra选择了后者因为他的视线非常容易处理并且有助于做出关于负载均衡非常确定的选择。5.2 复制不同的策略就是为了就近复制。在复制速度和可靠性做取舍。复制的越远，越不容易一起崩溃。cassandra使用复制以保证高可用性和持久性。每个数据项被复制到n个节点其中n是复制因子被每个实例配置。每个键k被分配到对应节点（在之前的章节描述的）。协调器负责其数据范围内的数据项。除了本地存储范围内的每个键之外，协调器在环中的N-1个节点复制这些键。Cassandra为客户端提供了各种复制数据的选项。Cassandra提供了多种复制策略比如Rack Unaware和Rack Aware（在数据中心中）以及Datacenter Aware（在数据中心）。副本的选择基于应用的复制策略。如果中心应用选择了Rack Unaware复制策略，那么非协调器的副本将通过选择协调器后续的N-1个节点来确定。Cassandra系统选举leader使用了一个叫做Zookeeper的系统。所有加入集群的节点与leader联系，告诉它们复制的范围是什么，并且leader会协调维护不变性，没有节点负责超过n-1个范围。关于节点范围的元数据在本地缓存在每个节点上并且在Zookeeper中保证容错性。通过这种方式崩溃和恢复的节点知道它的范围。我们借用了Dynamo的说法，将负责给定范围的节点称为该范围的偏好列表（preference list）。如5.1章的例子一样，每个节点都知道系统中的其他节点和他们负责 的范围。Cassandra通过5.2章中描述的仲裁要求，在节点故障和网络分区存在的情况下保证持久性。数据中心的故障 是由于断点，散热失效，网络故障和自然灾害。Cassandra被配置为在数据中心复制每个行。本质上，构造了键的首选项列表，因此存储节点扩展跨越多个数据中心。这些数据中心使用告诉网络进行连接。跨越多个数据中心的复制方案允许我们处理整个数据中心的故障无论是否停电。5.3 成员Cassandra的客户端成员是基于Scuttlebutt的，一个非常有效的基于Gossip的逆熵机制。Scuttlebutt的一个突出的特性是非常有效的CPU利用率以及非常有效的利用了gossip通道。在Cassandra系统内部，gossip不仅用于成员，还用于传播系统的相关控制状态。5.3.1 失败探测Accrual Failure Detector 是一种用于分布式系统中的故障检测机制，旨在通过累积的信息来逐渐确定某个节点是否发生故障。与传统的故障检测机制（如心跳或超时检测）不同，Accrual Failure Detector 提供了一个更为渐进的失败判定过程，使得系统能够在不同情况下适应不同的故障检测需求。每个节点都会定期发送心跳消息，以便其他节点检测它的存活状态。接收节点根据这些消息来计算发送节点失效的概率。通过累积收到的心跳信息，节点估算出发送节点失败的可能性，这个概率随着时间的推移逐渐增加，直到某个阈值被触发，从而确定节点已经失败。系统会设定一个阈值（通常是一个概率值），当某个节点的失败概率超过这个阈值时，系统就会认为该节点发生了故障。这个阈值通常是动态调整的，根据实际的网络状况和节点的健康状态来修改。失败探测是一个机制，如果有任何系统中的节点上线或者下线，节点可以本地进行确定。在Cassandra中失败探测也被用来避免在各种操作中与不可达的节点通信。Cassandra使用修改版本的$\Phi$累计故障检测器。累计故障检测器的思想是故障探测模块，不会我发出一个布尔值来表示节点是up还是down。相反。故障检测模块发出一个值，表示每个监视节点怀疑的级别。这个值的定义如同$\Phi$。其基本的思想是动态调整的尺度上表示$\Phi$的值，以反映被监视节点的网络负载和条件。$\Phi$遵循以下机制，给定一些阈值$\Phi$，并且假设我们在$\Phi$的时候怀疑节点，然后是我们犯错的可能性（即，这个决定会在未来被延迟的心跳推翻）约为10%。当$\Phi$=2概率是1%,$\Phi$=3概率是0.1.以此类推。系统中的每个节点都维护一个滑动窗口，显示来自集群中其他节点的gossip信息的间隔到达时间。这些到达间隔的时间是确定的，并且由$\Phi$计算出来。虽然原论文认为分布式近似高斯的，我们发现指数分布是一个更好的近似。因为gossip通道的性质和对延迟的影响。据我们所知，我们的是使用gossip实现累计故障检测同类中的第一个。累计故障检测对于准确性和速度都非常好，他能很好的适应网络环境和服务负载条件。5.4 启动在一个节点启动的第一时间，他选择一个随机token已定位环上的位置，为了容错，映射被持久化到本地磁盘和Zookeeper中。token信息之后会被gossip环绕到集群。这就是我们如何知道所有节点在圆上的位置。这允许所有节点为key进行请求路由到合适的集群中的节中。在启动案例中，当一个节点需要加入集群他读取配置文件，其中包含了了几个接触点的列表。我们叫这个初始化点为集群的种子。种子也来自配置服务比如Zookeeper。在facebook环境节点停机时（由于异常和维修任务）通常是短暂的，但是也可能遗留较长时间。故障可以是多种形式，比如磁盘故障，CPU损坏等我。节点停机很少意味着永久离开，因此不会导致分区作业重平衡或者修复无法访问的副本。类似的手动的错误可能会导致无意中启动新的Cassandra节点。每条信息都是这样包括每个Cassandra实例的节点名。因为这个原因，它被认为是合适的：使用显示的机制初始化Cassandra实例中的节点添加和删除。管理者使用命令行工具或者浏览器连接到Cassandra节点并且发送成员修改已加入或者离开集群。5.5 缩放集群当新的节点添加到系统中，他被分配一个token，这样就可以减轻负载过重的节点。这导致了新节点拆分其他节点之前负责的范围。操作员使用命令行或者Cassandra web仪表盘，Cassandra启动算法从系统中的任何其他的节点上初始化。放弃数据的节点使用核-核复制技术将数据传输到新节点。运行经验表明，数据可以在40MB/s的速度在单个节点传输。我们正在努力改进这一点，通过多个副本参与启动传输，从而并行化工作，类似于Bittorrent。5.6 本地持久化Cassandra系统信任本地文件系统以进行持久化。数据在磁盘上的表示使用使用有效的数据检索方式。写操作包括写入提交日志用于持久性和可恢复性并且更新内存的数据结构。写入到内存的数据结构只有在成功的写入提交日志之后才会执行。我们在每个机器上有专用的磁盘用于提交日志因此所有写入提交日志是连续的，因此我们最大化磁盘的吞吐量。当内存中的数据结构超过特定的阈值（基于数据大小和对象数量计算的），它将自己存储到磁盘。这个写操作是在机器所配备的许多商品磁盘上上的一个进行的。所有写操作都是顺序写入磁盘的，并且还生成一个索引，一遍根据row key高效的进行查找。这些索引页随着文件数据一起被持久化。随着时间推移，许多这样的文件可能存在于磁盘上，并且归并程序在背景中运行以核对文件的不同合并到一个树中 。这个过程非常类似bigtable系统中的压缩过程。一个典型的读取操作在查看磁盘文件之前，首先查询内存中的数据结构。这些文件是按照从新到旧的顺序来进行查看的。当进行磁盘查找时，我们可以查找多个磁盘上文件的一个key。为了防止查找到不包含键的文件，一个bloom过滤器，总结文件中的键，他存储在每个数据文件中也存储在内存中。首先要查看bloom过滤器，以检查正在查找的键是否存在于给定的文件中。列族中的键可能有多列。需要一些特殊的索引来检查离键较远的列。为了防止扫描磁盘上的每一列，我们维护索引，使我们能能跳转到磁盘上正确的快进行检索。当给定键被序列化并且写到磁盘时，我们在256K区块的边界生成索引。这个参数是可配置的，但是256K对于我们生产环境工作的很好。5.7 实现细节SEDA（Staged event-driven architecture）事件驱动架构是一种为高并发和高可扩展性系统设计的架构模型阶段（Stage）： 每个阶段是一个独立的处理单元，通常有自己的线程池、任务队列和资源管理机制。一个阶段只负责执行特定的功能，比如接受请求、解析请求、处理数据、返回响应等。这样可以避免系统出现“瓶颈”或者某个阶段过载的问题。事件驱动： 各个阶段通过事件传递任务，即每个阶段完成任务后，会生成一个事件，并将其放入下一个阶段的队列中，从而实现任务的分布式处理。通过事件驱动机制，SEDA能够在负载较大时有效缓解系统压力，并通过异步非阻塞方式提升性能。资源管理： 每个阶段的线程池和任务队列可以动态调整，系统可以根据负载自动调节阶段资源，避免因单个阶段过载影响整体系统性能。这样，SEDA可以灵活地应对负载的变化。流控： 通过对每个阶段的任务队列进行监控，SEDA可以动态调整资源分配和处理速度。当一个阶段的负载过高时，可以通过减少进入该阶段的任务数量来缓解压力，从而保证系统的平稳运行。Cassandra的进程在单个机器上主要由以下的抽象构成：分区模块，集群成员和失败探测模块以及存储引擎模块。每个模块都依赖于事件驱动的基层，其中消息处理管道和任务管道沿着SEDA架构的路线分成多个阶段。这些模块都是使用java从头开始实现的。集群成员和故障检测模块，构建在网络层的上方，它使用nio。系统控制消息基于UDP的消息传递，而用于复制和请求路由相关的应用信息依赖于TCP。请求和路由模块使用特定的状态机进行实现。当读写请求到到达集群中的任何节点，集群中的状态机通过以下几种变化 1 定义拥有key数据的节点 2 路由请求到节点并且等待响应等待的到来 3 如果响应没有在配置的超时内到达，请求返回失败并返回到客户端 4 根据时间戳找出最近的响应 5 如果没有找到最新的数据片，则安排对数据的修复。为了说明我们不讨论失败的场景。系统可以配置执行同步或者异步操作。对于确定需要高吞吐量的系统，我们依赖于异步的复制。在这里进入系统的写操作远远大于进入系统的读操作。在同步案例中，在返回给客户端之前，我们等待响应的法定人数 。在任何日志系统中，需要存在一种清楚日志条目的机制。在Cassandra中我们使用滚动提交日志其中当旧的日志提交超过特定的可配置大小时，就会生成一个新的提交日志。我们发现在生产环境中滚动提交日志大小设置在128MB能工作的非常好。每个提交日志都有一个header，他基本上是一个位向量，通常比系统处理的列组数量要多。在我们的实现中，我们有一个内存中的数据结构和一个按列族生成的数据文件。每次将特定内存中数据结构存储到磁盘时，我们都会提交日志中设置它的位，表示该列组已经成功持久化到磁盘。这表示信息片已经提交了。这些位向量是每个提交日志，也保存在内存中，每次滚动提交日志的所有向量。如果认为所有数据都成功持久化到磁盘啧删除这些提交日志。写入提交日志的操作可以是正常模式也可以是快速同步模式。在快速同步模式中对提交日志写操作将被缓冲。在这种模式下，我们还以缓冲的方式将内存中的数据结构转储到磁盘。传统的数据库不是为处理特别高的写入吞吐而设计的。传统的数据库不是为了高吞吐量而设计的。由于转储到磁盘的文件永远不会发生变化，因此在读取它们时不需要加锁。因此，我们不需要处理或处理存在于基于B-Tree的数据库实现中的并发问题。Cassandra系统基于主键索引索引所有的数据。磁盘上的数据文件被分解成一系列的块。每个块包含了最多128个key，通过块索引进行切分。块索引捕获到块中的相关key的偏移和数据的大小。当将内存中的数据结构转储到磁盘时，将生成一个块索引，并将其偏移量作为索引写入磁盘。这个索引维在内存中以进行快速访问。一个典型的读取操作总是第一步查阅在内存中的数据。如果发现数据就返回给应用，因为内存中包含任何键的新数据。如果没有找到，那么我们执行相反的事件顺序对磁盘上的所有数据进行io。因为我们总是找寻最新的数据，如果我们找到了 数据就返回。数据文件的数量将会随着时间增长。我们执行压缩过程，非常类似Bigtable系统，他合并多个文件为一个；本质是对已经排序的文件进行归并排序。系统总是对相似的大小的文件进行压缩。也就是说永远不会出现一个100GB的文件被压缩为小于50gb的文件。定期的运行一个主要的亚索过程我，将所有的相关的数据文件压缩成一个大文件。这个压缩过程是一个磁盘密集型操作。可以进行很多优化不影响即将到来的读请求。6 实践7 结论我们已经构建和运行了一个强大的系统，他提供可缩放，高性能，广泛的应用能力。我们可以通过经验证明可以提供低延迟的同时支持非常高的更新吞吐量。未来的工作包括增加压缩， 支持跨键原子性的支持和二级索引。
Percolator思考Google的三驾马车提供了Google的搜索引擎功能。建立网页我过程如下爬取互联网的内容进行解析提取出关键字确认反向索引对反向索引的URL进行整理形成了搜索引擎所需的网页引擎在构建网页索引的过程中，我们初始状态是由大量URL到页面内容这个键值对。我们把它处理成从关键字到URL这样一个反向的键值对（倒排索引）。reduce函数合并共同的反向索引。如果多个URL的内容一样，那么只有pageRank高的网页才会进行展示。但是一旦有网页更新，新的网页产生。我们需要更新到索引库中。网页之间的关系非常复杂。加入在新URL产生后需要内容去重然后重新pagerank。但是MapReduce这套生成网页索引的机制是全量的。没办法单独为新增的网页跑一套这个流程。MapReduce只能权利生成不能增量更新。Google长期采用的方法是通过MapReduce批处理过程，定期重新生成一个新的索引库。假设原来索引库索引了1000个页面，这时候五个页面新加入。MapReduce需要重新处理10005个页面才能得到新索引库。那么能不能只处理5个新增页面通过一个增量的更新呢？其实增量这个操作就是select+insert/update的过程。还需要保证整个过程的一致性和隔离性。如果这个索引库支持事务就能解决我们的问题了。那么如何让Bigtable支持事务呢？我们需要一个支持事务的DBMS来索引存储库。因此出现了percolator，在Bigtable上面做了一层封装。支持事务解决了问题并成为了分布式数据库。也就是newSQL的雏形。原论文中说：percolator是专门为了增量处理而构建的，并不是为了取代大多数数据任务处理的解决方案，MapReduce可以更好地处理无法将结果分解为小更新。此外计算应该有强烈的一致性要求不然Bigtable就足够了。计算在某些维度上应该非常大。传统的DBMS可以处理不适合Mapreduce或Bigtable的较小计算。但后续的Spanner到现在的各种newsql数据库已经在现有的解决方案商越走越远了。在性能差异不大的情况下，NewSQL能支持近乎无限容量的数据。提供强大的扩展性，又能弥补原有分布式的种种限制。（变得all in one）基本原理percolator是基于俩阶段提交的改进版本。prepare阶段：协调器向各个节点发送paepare消息，各节点决定该节点事务部分是提交还是中止。commit阶段：协调者收到各节点的ready或不能提交响应。所有节点都ready则提交成功，任一阶段无法提交就回滚。俩阶段提交的特点是强一致性失去了并发能力：不能使用MVCC需要一个特殊实现的协调者，这个协调者需要单独实现并存储一些日志和锁内容。（这个协调者是脱离bigtable的，所以更难控制）需要付出更大的性能。percolator基于此做了最核心的俩个改造提交过程中的第一个参与者设计为一个类似俩阶段提交协调者的角色，整个事务的原子性状态也以它为准。由此，借用Bigtable的高可用存储能力，免去了特殊设计协调者的麻烦和风险。percolator采用全局授时机制，通过全局时间戳实现多版本的管理，从而实现了snapshot isolation（快照隔离），具有一定的并发能力和first-commiter-win的特性。percolator存储了四个列：key，data，lock（锁状态），write（提交状态）字段前5或6是时间戳（我们用一个简单的自增整数来代替，时间戳由Bigtable负责存储）write下时间戳为data@5表示时间戳为5已经提交data字段的写入不表示这个事务已经提交了，没有提交的数据是不可以读的。读的流程为先查询write字段，找到最近的一个提交记录。再按照这个时间戳找到已提交的数据进行读取。接下里Bob给Joe转账7元。我们首先扣除Bob账户的7元。并在Bob账户上加锁。因为这是分布式事务的第一把锁，所以我们设定它为primary锁。这里最新的write字段还是时间戳6，只能查询到时间戳5的数据。所以现在Bob的余额还是10（MVCC）然后给Joe账户增加7元，余额变为9，并在Joe的账户上加锁。因为这是分布式事务的第二把锁，它指向primary锁的位置。这是为了让分布式事务的提交与成功有一个原子性的标志。一个事务中除了第一个锁是Primary锁其他的锁都是secondary锁。这样我们的prepare阶段就完成。事务进入commit阶段，事务释放掉primary锁，并申请时间戳8，在时间戳8写入write列。时间戳8就是这个事务的提交时间戳。底层实现我们可以简单把Bigtable当做一个整体来看待，Bigtable上面就是运行percolator程序的服务器了。percolator其实是作为Bigtable的client来调用Bigtable的接口的。在这里percolator在系统中的角色非常像一个中间件。可以看做是一个proxy代理。percolator需要在保证持久化的部分都借用Bigtable高可用的能力。因此他们都是无状态的，因此在考虑后续流程的情况下我们需要考虑proxy节点宕机的情况。先是事务的执行阶段写入根据start_ts前最后一个快照进行修改，并且只写入proxy本地缓存，无任何持久化和上锁操作（proxy挂掉了就丢掉）（强一致性读取）先要校验读取在start_ts之前是否有锁，如果有所要尝试清理掉这个锁。（因为proxy可能在俩阶段提交的过程中崩溃，这里是lazy清理。）如果是primary锁直接清理掉如果是secondary锁，那么找的哦啊primary锁的位置。根据primary锁的状态判断释放与否；如果token的时间戳很旧，大概率是之前的事务出问题了。那么可以清理锁如果没锁，就去找到start_ts前最后write的一个字段，再根据这个write字段指向的时间戳去读取数据。来看prepare阶段在自己修改的快照之后又新的事务提交，也就是write列写了信值在自己修改的行上有锁，也就是lock列写了新制没发生1,2的情况就成功上锁写入data和lock。其中1和2俩中情况都意味着在当前事务读取和prepare之间进行了prepare和commit。因此根据first-commoter-win这个特性，当前事务就必然要回滚了。最后来看commit阶段依次校验锁是否都加上了再获取提交时间戳commit再一次提交各行数据，提交过程就是清理锁，并写入write字段的过程。percolator使用全局时间戳实现快照隔离级别。percolator通过一台机器的时间接口统一给出全局递增的时间戳。percolator采用的是乐观事务模型
Bigtable解读基本Bigtable 是在GFS上的结构化的系统。很多人也把它称之为分布式表格系统。Bigtable在GFS和Chubby的基础上首次实现了可用的LSM树。bigtable的key由三部分组成，关键字，列关键字+时间戳(row:string,column:string,time:int64)->string它的key由三部分组成，行关键字+列关键字+时间戳。它的value是一个bute数组。分别对应行主键，列名。value从业务角度理解可以是一个未解析的byte数组。在谷歌给出的例子中url就是行关键字，anchor和内容就是列关键字。url 列名时间戳形成了多个键值对，比如途中就有6个k-v对其中t是数据版本。为什么要把各列的值拆成多个k-v对呢？而不是一整行数据放在一起呢。因为对于网页索引来说网页内容非常大，读取也比较慢。而对于anchor这样的小字段读取就非常的快。并且俩者的查询往往不是一个业务场景。常见的是先用anchor索引确定网页后在读取完整的页面内容。这样吧他们放在一起对于读取anchor的场景就非常不利了。所以虽然他们有相同的url但还是分开存储好。然后谷歌还提出了列族的概念，就是吧一些有共性的字段整合到一起，在存储访问等方面统一管理。API：bigtable提供的功能包括建表、删表DDL对单行数据增删查功能，不支持修改范围扫描功能（弱化的where）。bigtable只支持单行的事务。因此bigtable只能用在宽松的场景。结构在最底层bigtable把数据按照字典序排列之后以range划分。bigtable把这样一个range的数据称为一个tablet一个tablet对应一个GFS中的文件。有一个全局唯一的文件名。并且一个tablet相当于一个LSM树。要注意GFS支持append不支持update。而LSM树的所有操作都是append操作。对于Bigtable来说只需要一个tablet的文件名就可以直接从GFS中进行读写了。但是这里我们需要一个手段把我们要查询的key值和tablet文件名联系起来。为了解决这个问题Bigtable设计了三层的类似B+树结构的结构来存储tablet的位置信息。这里的三层结构是存储位置信息不要和存储具体kv的lsm树搞混。LSM树是一个tablet内部的概念。Chubby file，负责选择出Root tabletroot tablet 包含一个特殊的METADATA表；记录METADATA例所有的TABLET位置信息METADATA，其中的每个tablet包含了一个usertablet的集合多个usertablet存储数据的最终项。经过计算能存储2048PB的数据整个bigtable还需要client来提供服务。为了避免tablet服务器出现宕机的情况需要master服务器来检测各tablet服务器的状态。查找流程为通过client项chubby查找key访问到chubby指向的tablet开始。逐层向下找到自自己要找到tablet在找到tablet的lsm树中进行查找每次都进行这样的流程会有些慢，可以加上路径缓存。把路径上第一层的RootTablet，第二层的MetaDATA和第三层的Tablet位置都加入缓存。Bigtable把这个缓存存储在客户端称为客户端缓存。
Bigtable：面向结构化数据的分布式存储系统
Bigtable：面向结构化数据的分布式存储系统概要Bigtable是一个面向管理结构化数据的分布式存储系统，它是被设计为非常大的尺寸：TB的数据在上千个通用服务器。许多项目在Google上将数据存到Bigtable中包括了网站索引，谷歌地图和谷歌财经。这些应用对Bigtable提出了许多不同的要求，包括在数据大小（从URL到网站页面到卫星图像）与延迟要求（从后端批量处理到实时数据服务）。尽管他们有不同的需求，Bigtable很成功的提供了弹性， 高性能解决方案给所有的这些谷歌项目。在这个论文中我们描述Bigtable提供的简单数据模型，它使客户端能够动态控制数据布局和格式，并且我们描述Bigtable的设计和实现。1介绍在过去的俩年半里我们设计实现和开发了分布式存储系统以管理结构化的数据，在谷歌我们叫做Bigtable。Bigtable在谷歌被设计为可靠的的扩展到PB级别的数据和上千台的机器。Bigtable已经达到了几个目标：广泛的应用范围，可扩展性，高性能和高可用性。Bigtable被用在超过60个谷歌的产品和项目上，包括了规格分析，谷歌财经，Orkut，个性化搜索，Writely和规格地球。这些项目使用Bigtable以应对需求多变的工作负载。其范围从吞吐量为导向的批处理工作，到最终用户提供提供延迟敏感的数据服务。在许多方面，Bigtable类似于数据库：他们共享许多数据库的存储策略。并行的数据库和内存数据库已经达到了高可用，但是Bigtable提供了与这些系统不同的接口。Bigtable不支持完整的关系模型；相反，它给客户端提供了简单的数据模型，它支持动态控制数据布局和格式，允许客户端推断底层存储中表示的数据的局部属性。数据索引使用可以为仍以字符串的行名和列名。Bigtable还将数据视作未解释的字符串，尽管客户端经常将各种结构化和半结构化的数据序列化到这些字符串中。通过仔细的选择模式，客户端可以控制数据的位置。最后Bigtable的模式参数让客户端动态控制无论是在磁盘还是内存提供数据。章节2更详细的描述了数据模型，章节3提供了客户端API的总览。章节4描述了谷歌文件系统底层的结构。章节5描述了Bigtable实现的基本原理，章节6描述了一些让我们Bigtable性能提升的改进。章7提供了Bigtable的性能指标。在章节8中我们描述了几个不同的Bigtable在Google中使用的例子。在章节9讨论我们设计和支持Bigtable时学习到的一些经验。最后，章节10描述了相关工作，章节11提出了我们的结论。Bigtable是一个稀疏的，分布式的、持久的多维排序图。这个图通过行和列的key，时间戳进行索引；图中的每个值都是一个为解释的字节数组（行：string，列：string，time：int64）-->string2数据模型我们在检验了多重潜在的使用类似Bigtable的系统，选择了这个数据模型。作为一个确实的例子，它驱动了我们的一些设计决策，假设我们需要保证网页上大量数据和相关数据集的拷贝，这可能被用于许多不同的项目；让我们把这些的表叫做Webtable。在Webtable中，我们可能使用url作为行的键，网页的不同方面作为列名，在内容中存储web页面的内容：在获取的时间戳下面有一列，如图1所示。图1：一个示例表的切片，它存储了web页面。它的行名是倒过来的url。content列族包含了页面内容，锚列族包含了引用该列的任何锚文本。《体育画报》和MY-look主页都引用了CNN的主页，因此，该行包含名为anchor:cnnsi.com和anchor:my.look.ca的列。每个锚单元格都有一个版本；内容列有3个版本，时间戳为t3、t5和t6。在bigtable中表的组成分为行行列key在表中是一个随机字符串（目前最大可达64KB，尽管10-100字节是我们大部分用户的典型大小），每一个对于单行的读和写操作都是原子的（无论在行中读取或写入的不同列的数量如何），在对同一个记录进行更新时，使客户端更容易推断系统行为的设计决策。Bigtable按字典顺序维护数据。表的行范围是动态分区的。每个行的范围被叫做tablet，它是一个分布和负载均衡的单元格。因此，读取短行的范围通常是高效的，通常只修要与几个小数量的机器进行交流。客户端可以通过查询这些行的key来利用这个特性，这样他们就能得更号的数据访问的局部性。例如在Webtable中，通过翻转url的主机名组件将同一域中的页面分组到连续的行中。举个例子，我们将maps.google.com/index.html数据存储到键com.google.maps/index.html下面。将来自同一域的页面存储在彼此相邻的位置，让一些主机和域分析更加有效。列族列键被分组为集合，称为列族它是访问控制的基本单元格。所有的数据被存储在列族中，他们通常是一个类型（我们将同一列族的数据压缩）。在数据可以被存储在列族的任何列键下之前，列族组必须被创建；在列族被创建之后，任何列族中的键都可以使用。我们希望表中不同列族的数量劲量少，并且列族很少在操作途中修改。作为对比，一个表可以有无限多的列。一个列键使用以下语法命名：family:qualifier。列族名必须是可打印的，但是限定名可以是任意字符串。Webtable的一个列族是 language，它存储了编写网页采用的语言。我们在语言族中只使用一个列键，并且它存储了每个网页的语言ID。这个表另一个有用的列族是anchor；在这个家族中的每个列键代表一个锚，如图1所示。推荐语是引用网站的名称；单元格内容是连接文本。访问控制和磁盘内存统计在列族级别执行。在我们的Webtable例子中，这些控制允许我们管理几个不同类型的应用：其中一些添加新的基础数据，其中一些读取基本数据并创建派生列族，还有一些只允许查看现有数据（处于隐私原因甚至不会查看所有的族）时间戳每个在Bigtable中的单元格可以包含多个版本；这个版本是根据时间索引的。Bigtable的时间戳是64位的整数。它可以通过Bigtable进行指定，在这个例子中它代表以微妙为单位的实时，或者通过客户端应用进行清晰的指派。为了避免冲突，应用自生必须生成独一无二的时间戳。一个单元格的不同版本是按照时间戳降序的，所以大部分最近的版本可以被第一个读取到。为了让数据的管理更加简单，我们支持俩个列族的设置，告诉Bigtable自动对单元格版本进行垃圾收集。客户端可以指定只有最后的单元格n个版本被持有，或者只有一个足够新的版本被保留（即保留最后7天的值）在我们的Webtable例子中，我们设置存储内容在抓取页面的时间戳。列中显式了这些页面版本实际被抓取的时间。上面描述的垃圾收集机制允许我们只保留每个页面的最近三个版本。3 APIBigtable API提供了函数以创建和删除表以及列族。它也提供了函数以改变集群，表和列族元数据，例如访问控制权限。// Open the table Table *T = OpenOrDie("/bigtable/web/webtable"); // Write a new anchor and delete an old anchor RowMutation r1(T, "com.cnn.www"); r1.Set("anchor:www.c-span.org", "CNN"); r1.Delete("anchor:www.abc.com"); Operation op; Apply(&op, &r1);图2：写Bigtable客户端应用可以写入或者删除Bigtable中的值。从各自的行中查找值，或者迭代表中的数据子集。图2展示了C++代码使用RowMutation抽象来执行一系列的更新（不相关的细节被取消了以保证例子的简短）。调用Apply对Webtable执行原子性改变：它添加一个锚到www.cmm.com，并且删除不同的锚。Scanner scanner(T); ScanStream *stream; stream = scanner.FetchColumnFamily("anchor"); stream->SetReturnAllVersions(); scanner.Lookup("com.cnn.www"); for (; !stream->Done(); stream->Next()) { printf("%s %s %lld %s\n", scanner.RowName(), stream->ColumnName(), stream->MicroTimestamp(), stream->Value()); }图3：从Bigtable中尽显读取图3展示了C++代码，使用scanner抽象在特定的行中迭代所有的锚。客户端可以迭代多个列族，客户机可以遍历多个列族，并且有几种机制可以限制扫描产生的行、列和时间戳。例如，我们可以将上面的扫描限制为只生成其列与正则表达式anchor:*.cnn.com匹配的锚，或者只生产那些时间戳在当前十点之前的锚。Bigtable支持几个其他的特性，这允许用户以更复杂的方式随意操作数据。受限GFS支持单行的处理，它可以被用作在单行键下的数据存储执行原子读-修改-写序列。Bigtable目前不支持跨行键的事务，虽然它提供了客户端在不同行键之间批量写的接口。第二，Bigtable允许单元格用作证书计数。最后，Bigtable支持在服务的地址空间中执行客户端提供的脚本。这个脚本是通过谷歌开发的用于加工数据的语言Sawzall写的。 现在基于Sawzall的API不允许客户端脚本写回Bigtable。但是它的确允许各种形式的数据转换，基于任意表达的过滤，并通过各种运算进行总结。Bigtable可以和MapReduce一起使用，一个由谷歌开发被用于运行大规模并行计算的框架。我们已经写了一套包装，它允许Bigtable作为MapReduce的输入数据源，也可以作为输出目标。4构建模块Bigtable是构建在几个谷歌其他基础设施上的。Bigtable使用了分布式的谷歌文件系统来存储日志和数据文件。Bigtable集群通常在共享的机器池进行操作，机器池广泛运行着各种分布式应用程序，Bigtable进程通常和其他的应用进程共享同一个机器。Bigtable依赖于集群管理系统进行任务的调度，管理共享机器的资源，处理机器故障和监控机器状态。SSTable（Sorted String Table）是一种用于存储已排序数据的文件格式，它被多种数据库系统所采用，包括但不限于Google的Bigtable、Apache Cassandra 和 Apache HBase。Google SSTable文件格式在内部使用并存储Bigtable的数据。SSTable提供了持久化有序不可变的从key到value的映射，其中的键和值都是任意字节的字符串。提供操作以查找与指定的键相关的值，并且迭代所有规定范围内的键值对。在内部每个SSTable包含一个块序列（通常每个块是64KB，不过这是可配置的）。块索引（存储在SSTable的结尾）被用来确定块。当SSTable被打开时，index索引被装载到内存中。查找可以通过简单的磁盘检索来执行：我们首先在内存索引中执行二分查找来找到合适的块，然后从磁盘中读取合适的块。可选的，SSTable可以完全映射到内存中，它允许我们进行查找和扫描而不需要接触磁盘。Bigtable以来高可用和叫做Chubby的持久分布式锁服务。Chubby服务包含了五个活动副本，其中一个被选为主副本并主动处理请求。当主要的副本正在运行并且能和其他的副本交流时，服务器就是存活的。Chubby使用了Paxos算法以保持它副本面对失败时保持一致。Chubby提供了命名空间，它包含了由目录和小文件组成的命名空间。每个目录或者文件可以使用一个锁，并原子性的读写文件。Chubby的客户端库提供了Chubby文件的一致的缓存。每个客户端维护维护一个与Chubby服务的会话。如果在租约到期的时间之间不能重新租约，那么客户端的会话将会到期。当客户端会话到期，它丢失了任何锁并打开句柄。Chubby客户端还可以在Chubby文件和目录上注册回调，以通知更改或会话到期。Bigtable使用Chubby来进行多种任务：以保证它在任何时间只有一个活动的主；来存储Bigtable数据的引导位置（见章节5.1）；来发现tablet服务并判决tablet服务的死亡（见5.2章）;来存储Bigtable的模式信息（每个表的列族信息）；存储访问控制列表。如果Chubby变得在很长一段时间不可用，Bigtable将会变得不可用。我们最近在跨越11个Chubby实例的14个Bigtable集群中测量了这个效果。由于Chubby不可用(由Chubby中断或网络问题引起)而导致Bigtable中存储的某些数据不可用的Bigtable服务器小时数的平均百分比为0.0047%。单个集群被Chubby的不可用最多的影响在0.0326%。5实现Bigtable实现了三个主要的组件：连接到所有客户端的库，一个主服务和几个Tablet服务。Tablet可以从集群中动态添加（或者删除）以适应工作负载的变化。主负责指派tablet到tablet服务上，探测添加的和到期的tablet服务，均衡tablet服务的负载，并在GFS中进行垃圾收集。此外，它还处理模式更改，例如表和列族的创建。每个tablet服务管理一组tablet（通常，我们每台tablet电脑服务器上有10到1000个tablet）。tablet服务处理读和写请求到已加载的tablet中，同时还拆分规模过大的tablet。就像单个主的分布式存储系统，客户端数据不通过主进行移动。客户端直接和其他tablet服务进行交流来和写。因为Bigtable的客户端不依赖于主来获取tablet的位置信息，大部分客户端从不与主交流。所以，主实际上只有很轻的负载。一个Bigtable集群存储许多表。每个表由tablet集构成，每个tablet包含了行范围相关的所有数据。最初每个表只有一个tablet。随着tablet的增长，它被自动切分乘多个tablet，默认大小为每个接近100-200MB。5.1 tablet位置我们使用我们使用三层级的类似B+树来存储tablet的地址信息。如图4图4：tablet的位置层级第一个级别是一个存储在Chubby中的文件，根节点在一个特殊的元数据表中包含所有tablet位置。每个元数据表包含了一组用户表的信息。根tablet表只是在元数据表中的第一个，但是收到特殊对待—它从不切分—以确保tablet位置层级没有更多的树形层级。元数据表将tablet的位置存储在行键下，行键是编码了tablet表的标识符和节数行。每个元数据行存储了接近1KB的数据在内存中。元数据tablet的限制是128MB的元数据，我们三层的地址模式足够处理$2^{32}$个tablet（或者在128MB的tablet中$2^{61}$字节）客户端库缓存了tablet的位置。如果客户端不知道tablet的地址，或者如果它们发现缓存的地址信息是错误的，那么递归向上移动tablet地址层级。如果客户端缓存为空，地址算法需要三次网络往返，包括了一次从Chubby中读取。如果客户端缓存已经失效，客户端算法可能需要进行六次往返，因为过期的缓存只有在命中时才被发现（假设元数据tablets不会移动的非常频繁）。虽然tablet的位置存储在内存中，因此不需要GFS访问，在一般情况下，我们通过让客户端预读取tablet位置来进一步降低成本：当它读取元数据表时，它读取多个tablet的元数据。我们也存储元数据表中次要的信息，包括了每个tablet的所有信息（例如当服务开始提供时）。这个信息有助于debug和性能分析。5.2tablet指派每个tablet一次指派给一个tablet服务在一个时间。主保持一组存活的tablet服务块以及分配给当前tablet服务的tablet吗，包括未分配的tablet。当tablet未被指派，并且tablet服务有足够大的空间可供tablet活动，主通过发送tablet负载请求到tablet以指派tablet。Bigtable使用Chubby以保持跟踪块服务。当tablet服务启动，它会在特定的Chubby目录中创建并获取一个唯一命名的文件的独占锁。主监视了这个目录（服务器目录）以发现tablet服务。如果它失去了独占锁，tablet服务停止为其提供服务：即由于网络分区导致了服务丢失其Chubby的会话。（Chubby提供了有效的机制来允许tablet服务检查它是否仍然持有锁，而不增加网络流量）。tablet服务企图再次得到文件的独占锁，只要文件仍然存在。如果该文件不再存在，那么tablet服务器将永远无法再次提供服务，因为它会自杀。当tablet服务停止时（即因为集群管理系统从及群众移出了tablet服务机器），它企图替换它的锁，以便主能够更快的重新分配tablet。主会检测合适tablet服务不再提供tablet，并且尽快的重新分配这些表。为了检测什么时候tablet服务不在服务它的tablet，主定时的询问每个tablet服务他们锁的状态。如果tablet服务上报它丢失了锁，或者如果主在最后几次尝试时不能访问服务，主会尝试持有服务文件上的独占锁。如果主能够获取到主，那么Chubby还活着，并且tablet服务服务还活着，那么tablet服务要么死了要么无妨访问Chubby，所以主通过删除这个服务文件确保tablet服务再也不能活动。一旦服务文件被删除，主可以将之前分配到那个服务的起的所有tablet移动到未分配的tablet中。为确保Bigtable集群不容易受到在主和Chubby之间网络问题的影响，如果Chubby的会话到期，主杀死自己。然而，如上所述，主的故障不会改变tablet的被分配到tablet服务上。当主被集群管理系统启动时，它需要在它能够修改他们之前发现当前的tablet指派。主在启动时执行以下步骤。主获在Chubby中取唯一的锁，它防止了主的并发实例化。主扫描Chubby中的服务目录以查找存活的服务。主链接其他的存活的tablet服务以发现哪些tablet已经被指派了master扫描元数据tablet以了解这组tablet。无论这次扫描是否遇到了还没有被分配的tablet，主添加tablet到一组未被指派的表中。这使得tablet有资格获得tablet的指派。一个复杂的问题是在元数据tablet在被指派之前，元数据表的扫描无法进行。因此在在启动这个扫描之前（步骤4），如果在步骤3中没有发现根tablet的指派，主添加跟tablet到一组未指派的tablet。这一层架保证了主根tablet将会被指派。因为主tablet包括了所有元数据tablet的名字，在扫描根tablet之后主知道他们所有人。一组已存在的tablet只有表被创建或者删除时才能被改变，或者现有的tablet被分为俩个tablet。主能够保持这些改变的块，因为除了最后一个其他都是启动的。tablet的切分是特殊处理的，因为它通过tablet服务初始化。tablet服务通过记录在元数据表中心的tablet的信息来提交切分。当切分被提交它通知主。如果被切分的通知丢失了（无论是因为tablet服务还是主的死亡），当它告诉tablet服务去加载现在被切分的tablet时，主会探测到新的tablet。tablet服务将通知主的分裂，因为它在元数据表中找到的tablet条目将只指定主机要求它加载的一部分。5.3tablet服务tablet的持久状态被存储在gfs 中，如图5所示，更新被提交重做记录的提交日志中。在这些更新中，最近的一次更新被存储在内存的缓冲区中被称为memtable；更老的更新被存储在SSTable序列中。为了回复tablet，tablet服务读取元数据表中的元数据。此元数据包含包含tablet和一组重做点的sstable列表，重做点是指向可能包含tablet数据的任何提交日志的指针。服务读取SSTable的索引到内存中，并且通过应用所有的自重做点以来的更新重建memtable。到写入操作到达tablet服务，服务检查它的格式是否完好，并且发送方被授权进行修改。授权是通过读取来自Chubby的文件的允许写入者列表进行的。一个有效的改变被写入到了提交日志中。分组提交用来增强大量的小型修改的吞吐量。在写操作提交之后，它的内容被插入到memtable中。当读取操作到达tablet服务端，它简单的检查和实现和适当的权限。在SSTable序列和memtable的合并试图上执行有效的读操作。因为SSTable和memtable是按字典序顺序排序的数据结构，合并后的试图可以有效的形成。当tablet被拆分的时候到来的读和写操作是可以连续的。5.4压缩在执行写操作时，memtable的大小增大。当memtable大小到达预制，memtable被冻结，一个新的memtable被创建，冻结的memtable被转换成SSTable并写入GFS。这个小的压缩操作有俩个目标：它收缩了tablet服务内存的使用，并且它减少了那些在恢复期间必须要进行读取的数据量（如果服务器死亡）。进来的读和写操作可以压缩操作同时发生。每次小的压缩都会创建一个新的SSTable。如果这个行为继续不受控制，读操作可能需要合并大量的来自任意SSTable数量的修改。相反，我们通过在后端定期执行合并压缩，限制了这类文件的数量。合并压缩读取几个SSTable和memtable的内容，并写一个新的SSTable。一旦压缩完成，输入的sstable和memtable就会被丢弃。将所有所有SSTable重写为一个SSTable的合并压缩被叫做主压缩（major compaction.）。通过非压缩产生的SSTable可能包含特殊的删除项，它阻止了旧的SSTable中存在的已删除数据。另一方面，一个主要的压缩，生成一个不包含输出数据的SSTable。Bigtable在所有的tablet上循环运行，并且定期对他们进行主要压缩。这些主要的压缩允许Bigtable去回收删除数据所使用的资源，并且也允许它确保删除数据在系统中即使的消失，它对于存储敏感的数据是非常重要的。6精炼前一章中描述的实现必须要许多的改进才能实现高性能，可用性和用户要求的可靠性。为了突出这部分改进，这一章更细节的描述的实现部分。局部性组客户端可以分组多个列族到局部性组。为每一个tablet的每个位置生成一个单独的SSTable。将不一起访问的列族分开到局部性组中可以提高读取效率。例如，page的元数据在WebTable中（例如语言和校验和）可以在一个局部性组，页的内容可以在不同的组中：需要读取元数据而不需要读通过所有的页内容的应用。此外，可以在每个位置组的基础上指定一些有用的调优参数。例如局部性组可以被声明为在内存中。内存中局部性组的SStable是懒加载到tablet服务的内存中的。一旦接受负载，列族列族根据这些局部性组可以直接读取而不需要访问磁盘。这个特性被用在访问频繁的小的数据片段上：我们在内部使用它以让局部性列族在元数据tablet中。压缩客户端可以控制局部性组的SStable是否压缩，如果是，使用哪种压缩格式。用户指定了用户指定了每一个SStable block所使用的压缩格式（这个大小可以通过局部性组明确的调优参数进行控制）。虽然我们通过压缩损失了一些空间，我们收益于SStable的一小部分可以在不解压整个文件的情况下实现读取。许多客户端使用双通道自定义压缩。第一次使用了Bentley 和McIlroy的模式，在大的窗口中压缩长而且普通的字符串。第二次使用了快速压缩算法在16KB大小的窗口中查找重复数据。俩个压缩步骤都非常快速它们编码100-200MB/s，解码在400-1000Mb/s在现代的机器上。即使我们在选择压缩算法的时候强调的是时间而不是空间，这俩个压缩方案都非常好。举个例子，在Webtable中，我们使用压缩模式存储Web页的内容。在一个实验中，我们将大量问的那个存储在压缩的局部性组中。为了实验目的，我们限制每个文档为一个版本，而不是存储所有可用的版本。该方案实现了10比1的空间缩减。这相比于常见的Gzip在html页面压缩3比1或者4比1要好的多：来自单个主机的所有页面都彼此靠近地存储。它通过Bentley-McIlroy压缩算法识别来自同一主机页面中的共享的大量共享样板文件。许多应用，不止是Webtable，选择他们的行名让相似的数据聚集在一起，一次实现非常好的压缩率。当我们存储相同值的多个版本在Bigtable中时，压缩率甚至还会更好。为了读取性能的缓存为了增加读性能，Tablet服务使用2级缓存。扫描缓存是高级缓存，它将SSTable接口返回的键值对缓存到tablet服务代码。Block缓存是第几缓存，它缓存了GFS中读取的SSTable block。块缓存是一个较低级的缓存，用于缓存从GFS读取的sstable块。扫描缓存对于倾向于重复读取相同数据的应用程序是最有用的。块缓存对于那些倾向于读取与它们最近读取的数据接近的数据的应用程序(例如，顺序读取，或者随机读取热行中的相同局部性组中的不同的列)是有用的。布隆过滤器如5.3描述的，读取操作必须从构成了tablet状态的所有的SSTable中读取。如果SSTable不在内存中，我们最终可能要做许多磁盘访问。我们通过客户端指定局部性组中SSTable创建的的布隆过滤器来减少访问次数。布隆过滤器允许我们询问SStable是否包含指定的行列对的数据。对于特定的应用，小的Tablet服务内存被使用在布隆管理器上，极大的减少了磁盘必须的访问。我们使用布隆过滤器也意味着，大部分对于不存在的行或者列的查找都不需要接触磁盘。提交日志实现我们保持每个tablet的操作日志在单独的日志文件中，大量的文件被并发写入了GFS中。根据每个GFS服务器上的底层文件系统实现，这些写入可能会导致大量磁盘寻道写入不同的物理日志文件。此外， 在每个tablet上使用单独的日志文件也会降低分组提交优化的有效性。为了弥补这个问题，我们将改变附加到每个tablet服务的单个提交日志中，在同一物理日志文件中对不同的tablet进行混合改变。在正常操作期间使用日志可以显著的提升性能。但是这会让恢复变得复杂。当tablet服务器死了，它所服务的tablet服务奖被转移到大量的其他tablet服务上：每个服务通常装在少量的原始服务的tablet。为了恢复tablet的状态，新的tablet需要重演那个被源tablet服务写入的提交日志的改变。然而，这个tablet的改变被混合到了同一个物理机中。一个方法是，每个新的tablet服务读取这个完整的提交日志文件，并且只应用它需要恢复的tablet所需的条目。然而，在这样的模式下，如果100台机器从一个故障的tablet服务器上分配一个tablet，那么日志文件将会被读取100次（每个服务一次）。我们通过受限按照键的顺序对提交日志进行排序来避免重复读取日志《表，列名，日志序号》。在排序后的输出中，所有特地tablet的改变是连续的，因此可以通过一次磁盘寻道和随后的顺序读来有效的读取。为了并发排序，我们将日志文件分割为64MB一个段，在不同的tablet服务上并行排序每个段。当tablet服务表明需要需要从一些日志文件中恢复改变，排序程序会通过主的协调进行开始。将提交日志写入GFS有啥好会由于各种原因导致性能中断（比如，涉及写的GFS服务机器崩溃，或者到达特定的三台GFS服务器的网络路径遇到网络拥塞，或者沉重的负载）。为了保护免受来自GFS延迟峰值的影响，每个tablet服务实际上有俩个日志写入线程，一个写入它自己的日志文件；在同一时间，这俩个线程中只有一个处于活动状态。如果活动日志文件的写性能很差，日志文件写入会切换到另一个线程，提交日志队列中的变化由新线程写入。日志条目包含了连续的数字以允许恢复进程省略由日志切换进程产生的重复的条目。加速tablet康复如果主将tablet从从一个tablet服务移动到另一个，源tablet服务首先会在这个tablet上进行少量压缩。这个压缩通过减少tablet服务中不紧凑的tablet提交日志的状态，减少了恢复时间。在这个压缩结束后tablet停止位这个tablet提供服务。在真正的卸载tablet之前，tablet服务执行另一个（通常是更快的）以消除在第一次小规模压缩执行期间到达的平板服务器日志中的任何未压缩状态。在第二次小的压缩完毕后，可以加载到另一个tablet服务器上，而不需要任何日志条目的恢复。利用不变性除了SSTable缓存，Bigtable系统的其他部分通过所有的SSTable我们生成之后就不会变动这个事实进行简化。例如我们不需要任何对文件系统的在读取时SSTable的访问进行同步。所以可以有效的进行并发控制。唯一一个可变的数据结构并且能够通过渡河写访问的是memtable。为了减少在读取memtable时的冲突，我们让每个memtable行写时拷贝（copy-on-write）并且允许读和写同时进行。因为SSTable是不可变的，所以永久删除数据被转换成了垃圾收集废弃掉的SSTable。每个tablet的SSTable都注册在元数据表中。主删除淘汰的SSTable就如同在SSTAble集合上进行标记清除垃圾收集算法，其中元数据表包括了跟集合。最终SSTable的不变性是我们更快速的分离tablet。而不是给每个子tablet生成新的SStable集合，我们让子tablet共享父tablet的SSTable性能评估下面的性能评估和使用场景b话有点多懒得翻译了
Mysql成本计算规则Optimizer tracemysql原理--optimizer trace表的神器功效-CSDN博客MySql5.6之前只能通过Explain语句查看到最后优化器决定使用的执行计划，却无法知道它们为什么做这个决策，在MySql5.6以及之后的版本mysql提出了Optimizer trace（优化跟踪）的功能，它可以让我们看到优化器生成执行计划的整个过程。如果想打开这个功能，必须首先把 enabled 的值改为 on ，就像这样： `SET optimizer_trace="enabled=on"然后我们就可以输入我们想要看优化查询过程的语句，当该语句执行完成后，就可以看到information_schema数据库下的optimizer_trace表中查看完整的优化过程。这个optimizer_trace表有4列，分别是。query：表示我们的查询语句tace表示优化过程的json文本missing_bytes_beyond_max_size：由于优化过程可能会输出很多，如果超过某个限时，多余的文本将会不显示，这个字段展示了被忽略的文本字节数insufficient_privileges：表示是否没有权限查看优化过程，默认值是0，止呕某些特殊情况下才会是1。在我们有一个搜索条件比较多的查询语句，它的执行计划如下：EXPLAIN SELECT * FROM t1 WHERE key1 > 'z' AND key2 < 1000000 AND key3 IN ('a', 'b', 'c') AND common_field = 'abc';可以看到该查询可能使用到的索引有3个，那么为什么优化器最终选择了 idx_key1 而不选择其他的索引或者直接全表扫描呢？这时候就可以通过 otpimzer trace 功能来查看优化器的具体工作过程：SET optimizer_trace="enabled=on";SELECT * FROM t1 WHERE key1 > 'z' AND key2 < 1000000 AND key3 IN ('a', 'b', 'c') AND common_field = 'abc';SELECT * FROM information_schema.OPTIMIZER_TRACEGQUERY: SELECT * FROM t1 WHERE key1 > 'z' AND key2 < 1000000 AND key3 IN ('a', 'b', 'c') AND common_field = 'abc' TRACE: { "steps": [ { "join_preparation": { "select#": 1, "steps": [ { "IN_uses_bisection": true }, { "expanded_query": "/* select#1 */ select `t1`.`id` AS `id`,`t1`.`key1` AS `key1`,`t1`.`key2` AS `key2`,`t1`.`key3` AS `key3`,`t1`.`key_part1` AS `key_part1`,`t1`.`key_part2` AS `key_part2`,`t1`.`key_part3` AS `key_part3`,`t1`.`common_field` AS `common_field` from `t1` where ((`t1`.`key1` > 'z') and (`t1`.`key2` < 1000000) and (`t1`.`key3` in ('a','b','c')) and (`t1`.`common_field` = 'abc'))" } ] } }, { "join_optimization": { "select#": 1, "steps": [ { "condition_processing": { "condition": "WHERE", "original_condition": "((`t1`.`key1` > 'z') and (`t1`.`key2` < 1000000) and (`t1`.`key3` in ('a','b','c')) and (`t1`.`common_field` = 'abc'))", "steps": [ { "transformation": "equality_propagation", "resulting_condition": "((`t1`.`key1` > 'z') and (`t1`.`key2` < 1000000) and (`t1`.`key3` in ('a','b','c')) and (`t1`.`common_field` = 'abc'))" }, { "transformation": "constant_propagation", "resulting_condition": "((`t1`.`key1` > 'z') and (`t1`.`key2` < 1000000) and (`t1`.`key3` in ('a','b','c')) and (`t1`.`common_field` = 'abc'))" }, { "transformation": "trivial_condition_removal", "resulting_condition": "((`t1`.`key1` > 'z') and (`t1`.`key2` < 1000000) and (`t1`.`key3` in ('a','b','c')) and (`t1`.`common_field` = 'abc'))" } ] } }, { "substitute_generated_columns": { } }, { "table_dependencies": [ { "table": "`t1`", "row_may_be_null": false, "map_bit": 0, "depends_on_map_bits": [ ] } ] }, { "ref_optimizer_key_uses": [ ] }, { "rows_estimation": [ { "table": "`t1`", "range_analysis": { "table_scan": { "rows": 3, "cost": 2.65 }, "potential_range_indexes": [ { "index": "PRIMARY", "usable": false, "cause": "not_applicable" }, { "index": "idx_key2", "usable": true, "key_parts": [ "key2" ] }, { "index": "idx_key1", "usable": true, "key_parts": [ "key1", "id" ] }, { "index": "idx_key3", "usable": true, "key_parts": [ "key3", "id" ] }, { "index": "idx_key_part", "usable": false, "cause": "not_applicable" } ], "setup_range_conditions": [ ], "group_index_range": { "chosen": false, "cause": "not_group_by_or_distinct" }, "skip_scan_range": { "potential_skip_scan_indexes": [ { "index": "idx_key2", "usable": false, "cause": "query_references_nonkey_column" }, { "index": "idx_key1", "usable": false, "cause": "query_references_nonkey_column" }, { "index": "idx_key3", "usable": false, "cause": "query_references_nonkey_column" } ] }, "analyzing_range_alternatives": { "range_scan_alternatives": [ { "index": "idx_key2", "ranges": [ "NULL < key2 < 1000000" ], "index_dives_for_eq_ranges": true, "rowid_ordered": false, "using_mrr": false, "index_only": false, "in_memory": 1, "rows": 3, "cost": 1.31, "chosen": true }, { "index": "idx_key1", "ranges": [ "'z' < key1" ], "index_dives_for_eq_ranges": true, "rowid_ordered": false, "using_mrr": false, "index_only": false, "in_memory": 1, "rows": 1, "cost": 0.61, "chosen": true }, { "index": "idx_key3", "ranges": [ "key3 = 'a'", "key3 = 'b'", "key3 = 'c'" ], "index_dives_for_eq_ranges": true, "rowid_ordered": false, "using_mrr": false, "index_only": false, "in_memory": 1, "rows": 3, "cost": 1.81, "chosen": false, "cause": "cost" } ], "analyzing_roworder_intersect": { "usable": false, "cause": "too_few_roworder_scans" } }, "chosen_range_access_summary": { "range_access_plan": { "type": "range_scan", "index": "idx_key1", "rows": 1, "ranges": [ "'z' < key1" ] }, "rows_for_plan": 1, "cost_for_plan": 0.61, "chosen": true } } } ] }, { "considered_execution_plans": [ { "plan_prefix": [ ], "table": "`t1`", "best_access_path": { "considered_access_paths": [ { "rows_to_scan": 1, "access_type": "range", "range_details": { "used_index": "idx_key1" }, "resulting_rows": 1, "cost": 0.71, "chosen": true } ] }, "condition_filtering_pct": 100, "rows_for_plan": 1, "cost_for_plan": 0.71, "chosen": true } ] }, { "attaching_conditions_to_tables": { "original_condition": "((`t1`.`key1` > 'z') and (`t1`.`key2` < 1000000) and (`t1`.`key3` in ('a','b','c')) and (`t1`.`common_field` = 'abc'))", "attached_conditions_computation": [ ], "attached_conditions_summary": [ { "table": "`t1`", "attached": "((`t1`.`key1` > 'z') and (`t1`.`key2` < 1000000) and (`t1`.`key3` in ('a','b','c')) and (`t1`.`common_field` = 'abc'))" } ] } }, { "finalizing_table_conditions": [ { "table": "`t1`", "original_table_condition": "((`t1`.`key1` > 'z') and (`t1`.`key2` < 1000000) and (`t1`.`key3` in ('a','b','c')) and (`t1`.`common_field` = 'abc'))", "final_table_condition ": "((`t1`.`key1` > 'z') and (`t1`.`key2` < 1000000) and (`t1`.`key3` in ('a','b','c')) and (`t1`.`common_field` = 'abc'))" } ] }, { "refine_plan": [ { "table": "`t1`", "pushed_index_condition": "(`t1`.`key1` > 'z')", "table_condition_attached": "((`t1`.`key2` < 1000000) and (`t1`.`key3` in ('a','b','c')) and (`t1`.`common_field` = 'abc'))" } ] } ] } }, { "join_execution": { "select#": 1, "steps": [ ] } } ] } MISSING_BYTES_BEYOND_MAX_MEM_SIZE: 0 INSUFFICIENT_PRIVILEGES: 0 优化过程大致分为了三个阶段prepare准备阶段optimize优化阶段execute执行阶段我们所说的基于成本的优化主要集中在 optimize 阶段，对于单表查询来说，我们主要关注 optimize 阶段的 “rows_estimation” 这个过程，这个过程深入分析了对单表查询的各种执行方案的成本；对于多表连接查询来说，我们更多需要关注 “considered_execution_plans” 这个过程，这个过程里会写明各种不同的连接方式所对应的成本。反正优化器最终会选择成本最低的那种方案来作为最终的执行计划，也就是我们使用 EXPLAIN 语句所展现出的那种方案。如果有小伙伴对使用 EXPLAIN 语句展示出的对某个查询的执行计划很不理解，大家可以尝试使用 optimizer trace 功能来详细了解每一种执行方案对应的成本，相信这个功能能让大家更深入的了解 MySQL 查询优化器。