随意的世界 - 数据库
type: channel
link: https://www.nasuiyile.cn/数据库/
items: CMU-数据库导论-3
items: CMU-数据库导论-2
items: CMU数据库导论-1
items: 那些底层使用了Rocksdb的项目
items: LSM基础
items: Faster笔记
items: Megastore: Providing Scalable, Highly Available Storage for Interactive Services（1）
items: Dynamo：亚马逊的高可用键值对存储
items: Cassandra 一个去中心化的结构化存储
items: Percolator

CMU-数据库导论-3
type: item
date: 2026-07-23T17:23:00+08:00
description: CMU-数据库导论-3数据库日志ACID的最后一块拼图是持久性。持久性代表回复外界时，数据就要保证不能丢失。恢复算法分为俩个部分，为了应对可能发生的故障，在事务运行期间，我们需要采取额外的措施。准备失败。另一个是当我们从故障恢复后，要弄清楚崩溃发生时的系统状态。处理失败。为了实现这一目标，我们需要俩个关键操作，undo和redo。undo是一出未完成的事务的更改或影响。因为系统自身终止系统崩溃，或者由于俩阶段锁定或者OCC机制限制无法提交。该事务被认为未提交，redo是对于已提交的事务确保在系统恢复后，保留其所有更改。我们需要确保每个已提交的事务的更改都已写入。我们如何进行undo和redo操作，将取决于缓冲池管理器能为我们提供什么支持。我们实际上需要对它进行一些更改，使其能够更智能地处理系统中的各个情况。我们可以进行俩种策略不窃取（No-Steal）：只有事务提交后，其脏页才能落盘。这要求缓冲区为每个活跃事务保留足够的空间，如果一个长事务修改了大量页面，可能会撑爆缓冲区。窃取（Steal）：即使事务未提交，其脏页也可以被刷写回磁盘。这解决了缓冲区空间被未提交事务占满的问题，允许缓冲池更灵活地换入换出页面。预写日志read-ahread logging将使用窃取策略。因为允许从尚未提交的事务中驱逐页面，缓冲池 管理器的替换策略（LRU-K）就能有更多可释放帧的选择。如果不适用窃取策略，那么一个事务修改的所有内容都需要保留在内存中。这意味着如果事务修改的页面超过了你可用的内存，那么就糟了，因为你无法逐出任何内容。另外一种策略：force（强制）：当一个事务已经提交时，在告知外界事务已经提交前，需要将所有的脏写更改写回并刷新到磁盘。no-force（非强制）：事务提交不需要将脏数据刷新到磁盘。即：Steal / No-Steal 解决的是：事务未提交时，它的脏数据能否被挤出内存写到磁盘？Force / No-Force 解决的是：事务提交时，它的脏数据是否必须强制写到磁盘？force会让提交速度便慢。影子分页假设 这里采用no-steal、force策略。如果我们有ABC三个数据在同一个页面上。比如我们T1读取A页面被加载到了缓存中，T2读取并修改了B。然后提交了事务。当事务提交，根据force策略，就必须将脏数据刷回磁盘。这里就产生了冲突问题，因为根据no-steal策略，我们不允许写出来自尚未提交的任何脏页或任何未提交的修改。因此解决这个问题的方法是，在缓冲区中复制这个页面，但是只包含自己已提交事务的更改。然后就可以把数据回写。这样一来当回到T1时，T1的回滚操作就会变得非常简单。因为实际上没有修改任何东西，任何修改的东西都没有被写入磁盘。很明显上述方案非常糟糕。如果更新10亿个页面呢？那么需要复制10亿个页面才能删除不需要的内容。高并发系统中有成千上万个事务同时运行，我需要跟踪所有事务修改过的页面。还需要制作这些页面的副本。因此没有任何系统用这种做法，这种做法实际上也会加速硬件老化，SSD的擦写次数是有限的。这就是shadow paging 影子分页。是一种no-steal，force策略 。它避免了每次都复制整个数据库。这是IBM在System R项目初期发明的。在影子分页中，不允许多个事务同时更新一个页面。因此，将数据刷新到磁盘的时候，就不需要剔除未提交事务的部分了。其中主版本用于存放已经提交的事务更改，影子副本用于存放未提交事务的更改。当事务提交时，我们会将所有脏页从影子表刷新到磁盘。然后用一个指针来指向当前的主页表。这基本上就是写时复制的工作原理。它在处理并发时表现不佳。影子分页还会导致数据不再连续存储。undo：移除影子页。保留主页面和数据库根指针不动。redo：不需要任何操作Sqlite（2010之后）sqlite有一种叫做回滚的机制。sqlite第一个版本的实现类似影子分页。（2010年后处于性能考虑，添加了WAL）sqlite最开始的做法是，页面在内存中，数据库在磁盘上，此外还有一个额外的文件叫做日志文件（journal file）。当事务想要修改一个页面时，你会从磁盘读取它，加载到缓存中，然后在你做任何更改之前，将更改复制到日志文件中。现在就可以在内存中进行修改了。此时更改page2，然后是page3。但是更改page2的时候崩溃了，page的一部分写入了磁盘，在写入page3之前崩溃了，此时你就会知道这个事务没有提交。在这里内存中的缓存区会被清除。在恢复时，首先查找日志文件。然后将这些页面复制回内存，因为你知道这些页面时事务开始之前的原始版本。然后直接将他们复制回磁盘，因为你知道任何事务运行并更改之前，这些页面是数据库的正确版本。sqlite使用但写线程，因此无需担心多个事务并发修改页面的问题。当事务提交…

CMU-数据库导论-2
type: item
date: 2026-07-19T14:10:00+08:00
description: CMU-数据库导论-2Query Execution处理模型当关系型数据库接收到SQL查询时，会将其转化为执行计划。理想情况下，你希望查询计划是一个有向无环图，directed acyclic graph，也就是DAG。大多数系统是将其实现为树。理论上DAG是更优的结构，因为树不能重用一些输出，除非使用特殊的技巧。管道是操作符的合计，数据库在这些操作符之间连续传递，无需阻塞或等待更多数据。管道中断器（pipeline breaker）本质上是管道的边界，除非在查询中执行另一个操作（另一个管道），否则无法继续处理当前管道中的任何元组。管道的核心思想是，定义了一个边界，在这个边界内，我们可以执行一系列操作符，而无需将结果物化到中间存储。处理模型定义了数据库将如何执行查询计划，以及如何将数据从一个操作符移动到另一个操作符。这里有些操作方式适合OLAP有些适合OLTP。控制流（control flow）是只是数据库系统用来下一步要运行哪个操作符的机制。它可以是一个管道或者一系列运算符。数据流则决定了操作符发送的位置和方式。在迭代器模型中控制流和数据流的界限实际上会变的模糊。在迭代器模型中，表示数据已足够，停止运行的方式，和指示其完全停止的方式是相同的。一个操作符的输出会取决于我们想要使用的处理模型。常见的三种方法是iterator model：最常见，pg，mysql，oracle，db2都是用这个。materialization model：少见vectorized/batch model：常见，OLAP系统中用的多。迭代模型这是最常见的实现方式，尤其在行存储系统中。查询计划中的每个算子都要实现系统提供的API，这个API包含三个基本的函数。其中next函数会发出指令，算子会生成下一个元组，这个元组成为正在处理数据的输出结果。父算子会不断在其子算子上重复调用next函数，直到子算子没有更多元组能够返回。它会返回空指针和一个文件结束标记。因此，如果一个算子有一个子算子，其并不关心子算子实际上是如何生成数据的。只需要调用子算子的next函数，不需要关心是来自网络，还是来自索引。我们可以维护一些关于算子状态的元数据。所以我们必须要open和close函数。当调用索引扫描算子的open函数式，就像为B+树创建迭代器一样，实例化迭代器，移动它生成一个元组。先open，调用next直到eof，最后调用close清理迭代器。当顶层的算子调用child.next时，会发生阻塞，然后执行流程会跳转到下层算子。（不设置的情况下，数据库默认使用的是inner join）管道之间存在依赖关系，R没有执行完毕之前，S是不能执行的。父级不在乎子级真正调用next时干了什么，可以是实际去查询一条数据，也可以时将查询好的数据直接返回。这种方式几乎被用了所有的DBMS中。这种方法的另一个优点是容易控制输出，如果有一个limit语句只要10条数据，那么只需要在获取10个元组后停止调用getNext即可。这就是之前说的，控制流和数据流在某种程度上是混合在一起的。物化模型物化模型中仍然有一种next函数，它实际上就像，给我一切。因此不再是每次调用操作符时生成一个元组，而是直接获取该操作符产生的所有元组。这项技术，20世纪90年代名为monadb的项目，Duckdb实际上是mongnadb的嵌入式版本。获取S中的所有元组，添加到输出缓冲区，然后现在传递给这个运算符，它会扫描数据并应用谓词。但是如果有一百万条记录，谓词只会匹配其中俩条，显然是不合理的。因此这个领域里一个非常常见的优化方式是算子融合。基本思想是，将同意流水线的不同算子内联，或者组合起来，从而避免不必要的复杂操作。在上述例子中，扫描R表，应用谓词，如果满足条件就将其放入输出缓冲区。物化模型更适合OLTP，因为查询只访问小部分的元组。更少的执行和协调开销，更少的函数掉用。对于OLAP，调用next会很昂贵，因为必须要扫描10亿个元组的场景存在。而且我们不想一次性物化所有的数据，因为我们希望分解处理流程并将其并行化，而不必担心耗尽所有内存，只需要生成运算符的之间结果即可。一个显而易见的方式是在俩者之间做一些事情向量化模型向量化模型类似迭代器模型，当调用next时，得到的不是一个元组，而是一批元组。现在获得该批元组的运算符将处理这批元组，在整个批上面处理。操作符的一次内部循环处理多一个元组批的大小可以基于精简和查询资源如果知道某个列中的属性和元组返回相同的值，可以使用类似游程编码的方式来进行。Duckdb底层就会进行类似的操作。和之前的例子类似，但是这次不再是传递单个元组，而是传递一个向量。该模型在Clickhouse，oracle，sql server，duckdb中均有使用。这是2006,2007年才提出的概念，最…

CMU数据库导论-1
type: item
date: 2026-07-12T14:14:29+08:00
description: CMU数据库导论-1关系模型关系型数据库（Relational Database，RDB）是一种基于关系模型（Relational Model）来组织和管理数据的数据库。它由Edgar F. Codd于 1970 年提出，其核心思想是将数据组织成二维表（Table），并利用数学中的关系代数来操作数据。但是论文中的表述是完全数学化的。IBM发明了第一个查询语言叫做SQUARE，但是这种语言写起来很怪，没有人真正实现它。然后SEQUEL被发明了，由于版权原因被改名为了SQL。SQL在86年就被标准化了，但是规范仍然会不停的更新。这些变化是为了适应人们编写应用的方式，以及对查询语言需求的变化。XML在90年代末20年代初很火，所以增加了XML的支持，Json在2010年火，所以增加了JSON。2023年增加了对图查询的支持，因此neo4j，可以通过SQL，在表的基础上进行图的遍历。如今要构建一个新系统，只少需要支持SQL92，它支持了常见的功能，比如select，from，group by，聚合函数等。平均每10年都有人说SQL要死了，但是它们从未发生。SQL分为DML，DDL，DCL。数据存储文件数据库可以分为多层查询计划-操作执行-访问方法-缓存管理-磁盘管理这一章讨论磁盘管理我们数据库会假设，在数据库管理系统中，数据主要存储在非易失性存储上。系统本质上是在协调数据在非易失性存储和内存上移动。磁盘数据需要加载到内存中才能提取答案。中间这条线以上的任何存储都是按照字节寻址的。按字节寻址意味着，每一个内存地址对应1Byte的数据。地址 数据0x1000 0x110x1001 0x220x1002 0x330x1003 0x44地址0x1000保存1个字节，地址0x1001保存1个字节，地址0x1002保存1个字节。。。。这里和操作系统的位数不同32位CPUCPU寄存器宽度、指针宽度、地址宽度主要为32位64位CPUCPU寄存器宽度、指针宽度、地址宽度主要为64位32位操作系统运行在32位架构上，使用32位指针和地址空间64位操作系统运行在64位架构上，使用64位指针和地址空间在non-volatile上存储的数据都是按块存储的。我们必须以块为单位访问整个页面，通常4KB。现代的存储设备，普遍采用4KB作为物理扇区，以前的硬盘很多是512byte现在通常是4096bytes。如果物理社区大小为4KB每个数据块需要刚好都落在4KB扇区内。如果一条数据跨越了俩个物理扇区，则需要进行多一次的内存读写。这就是为什么需要4k对齐。这将决定我们使用什么数据结构和算法。但是现代计算机中这些界限正在变模糊。现在SSD和HDD中出现了fast network storage，不存储在本地，但可以进行快速的访问，而且它是持久的。此外傲腾其实介于内存和磁盘之间。然而2022年傲腾被砍掉了。傲腾是一种特殊的硬件，向dram一样插在DIMM插槽中，但是如果拔掉电源可以保存存储的内容。如果intel没有砍掉它，很多课程中的内容将会消失，因为我们不再需要DRAM和磁盘之间来回移动数据了。现在替代傲腾的CXL3，是一种字节寻址的内存，它可能并不在你本地的物理机上。三星会售卖这种插在PCIE插槽上的设备，它就像是扩展了DRAM插槽的数量。它就像扩展了DRAM插槽的数量。CXL本身也不能解决断点数据保存。NVDIMM，运行时和普通内存一样，断电时电池继续供电，然后将数据写入磁盘，但是其也没有得到广泛的使用，在部分细分市场。随机访问通常比顺序访问来的慢。即便是SSD，真正读写的是page，顺序访问可以充分利用并行性，现代SSD内部其实有很多Flash芯片，多个channel同时工作，顺序读取几乎能跑满PCIE贷款。随机访问很难形成连续流水，假设读取4KB，可能在chip0,7,3。控制器需要查FTL，找到物理地址，发送命令，等待Flash响应，每一次都有固定的延迟。这意味着我们在设计数据库系统时，劲量选择顺序算法，因为顺序写入比随机写入块。我们假设系统运行在现成的文件系统上，并且我们只是在读取和操作这些文件。页在数据库系统和计算机中，实际上有三种页面概念在最低级别，有一个硬件页面，这是硬件公开的，实际可以执行的原子写入操作的最大大小，通常是4KB原子写入：要么写入完成，要么写入全部失败，不会出现中间状态。OS层级页会有page的概念，以为这是x86在80年代的做法。默认是4kb，在更新的版本中可以使用巨页（huge page）是2mb甚至1GB。在数据库中，基于操作系统页面，我们可以使用不同大小的页面。页面大小因数据库而异。sqlite、oracle、IMBDB2、rocksdb、wiredtiger（mongodb的默认存储引擎）都是4kb。sqlserver，pgsq…

那些底层使用了Rocksdb的项目
type: item
date: 2026-03-20T15:25:00+08:00
description: 那些底层使用了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基础
type: item
date: 2025-08-01T12:46:19+08:00
description: 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的并行写入特性。相较于机械硬盘，随机读取与顺序读取的性能在固态上没有那么显著。意味着过分追求顺序读取而进行…

Faster笔记
type: item
date: 2025-07-07T16:51:00+08:00
description: 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值的条…

Megastore: Providing Scalable, Highly Available Storage for Interactive Services（1）
type: item
date: 2025-05-23T13:28:40+08:00
description: 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 i…

Dynamo：亚马逊的高可用键值对存储
type: item
date: 2024-12-02T16:39:00+08:00
description: Dynamo：亚马逊的高可用键值对存储概要在大规模下的可靠性是我们在亚马逊一个大的挑战，一个世界上最大的电商系统。即便是轻微的中断也会明显的财务影响并且影响了客户的信任。亚马逊平台提供了给世界尺度的很多网站提供服务，在成千上万台基础设施上实现的，并且网络组件位于许多遍布世界的数据中心。在这个规模下，小或者大的组件连续不断的故障，面对这些故障时管理持久化状态的方式驱动了可靠的可扩展的软件系统。这个paper提出了设计和Dynamo的实现，一个高可用的键值对存储系统，亚马逊的一些核心服务就是用它来提供永远的在线体验的。为了达到这种级别的可用性，Dynamo牺牲了在某些故障场景下的一致性。它以一种为开发人员提供新颖接口的方式，广泛使用了对象版本控制应用辅助的冲突解决，1 介绍亚马逊运行着世界范围的电商平台，在高峰时段为数以千万的客户提供服务，使用上万台服务器位于世界的许多数据中心。在亚马逊平台上的操作对于性能，可靠性，有效性方面有严格的要求，为了支持持续增长，平台需要具有高度可扩展性。可靠性是一个最重要的需求，因为即便是小的中断也会导致明显的经济后果和影响客户的信任。此外，为了支持持续的增长平台徐亚高扩展性。我们团队组织从运营亚马逊平台中学到的经验之一，系统的可靠性可扩展性依赖于如何管理应用程序状态。亚马逊使用了高度去中心化的，松耦合的，面向服务体系结构，由数百个服务组成。在这个环境特别需要强大的永远可用的存储技术。例如客户有能查看和添加项目到购物车即便磁盘故障。网络线路不稳定，数据中心被龙卷风摧毁。因此，服务负责管理购物车他可以永远被读取和写入在数据存储，数据需要跨多个数据中心高可用。处理由百万个组件组成的基础设施中的故障是我们标注的操作模式；总会有几个小的但是显著数量的服务和网络组件在一些给定时间内故障。因此亚马逊软件系统需要构建一种方式，他将异常视为正常情况而不影响可用性和性能。为了应对可靠性和扩展性需求，亚马逊开发了几个存储技术，其中Amazon Simple storage Service (也可以在亚马逊之外访问到，被称为Amazon S3)，可能是最有名的。这篇论文提出了Dynamo的实现和设计。在亚马逊平台上构建的另一种高可用的可靠的可扩展的分布式数据存储。Dynamo被用来管理服务状态，它们对可靠性的需求非常高并且需要严格的控制，可用性，一致性成本效益和性能。amazon平台有非常多样的应用在不同的存储需求。选择一组应用需要一种存储技术，他足够弹性，以让应用设计人员根据这些权衡适当的配置数据存储以实现高可用，使用最划算的方式保证性能 。许多在亚马逊平台上的服务他们只需要键值对访问。对于许多服务，比如提供畅销排行榜的，购物车，客户偏好，会话管理，销售排名和产品目录，使用关系型数据库的常见模式会导致低效率以及限制了规模和可用性。Dynamo提供了简单的键值对接口，以应对这些应用的需要。Dynamo使用了一些工作的良好的技术综合以达到可扩展性和可靠性：数据被通过一致性哈希进行分区和复制。通过在更新期间保持副本的一致性通过法定人数技术和去中心化的复制同步协议。Dynamo使用了基于gossip的故障探测和成员协议。Dynamo是一个完全去中心化的系统并且最小化手动管理的需求。存储节点可以在Dynamo添加或者删除而不需要任何手动分区或者重分布。在过去的一年中，Dynamo已经成为了亚马逊贸易平台中的几个核心服务的底层存储技术。它能够在节假日扩展到极端的峰值负载而无需任何停机时间。例如，维护购物车的服务服务于数千万的请求在同一天就有超过300万的结账，管理会话状态的服务处理数十万的活动会话。这项工作对于学术届的主要贡献是评估了如何结合不同的技术来提供单一的高可用性系统。他展示了最终一致性的存储系统可以被用在对于有着高要求的应用。他也提供了对这些技术调优的深入理解以应对生产系统非常严苛的性能需求。背景亚马逊的电商平台由几百项服务组成，这些协同功能从推荐到订单履行到欺诈检测的各种功能。每个服务都通过良好定义的接口进行暴露可通过网络访问。这些服务被托管于由上万个服务谓语世界范围内的数据中心。其中的一些服务是无状态的（服务聚合从其他服务的影响）一些是有状态的（即服务在他存储在持久化系统的状态上执行业务逻辑，生成它的相应）。传统的生成系统存储他们的状态在关系型数据库中。然而， 对于许多常见的状态持久化的使用模式，关系系数据库是非理想的解决方案。他么中的大部分服务只存储并检索数据，不需要关系型数据库管理系统提供的功能复杂的查询和管理。这种多余的功能需要昂贵的硬件和高技能的操作人员，这是一个非常低效的方案。此外，可用的复制技术是有限的，通常选择一致性而不是可用性。虽然尽管近年来取得了许多进展，横向扩展数据库依然不简单，或者使用智能的分区模…

Cassandra 一个去中心化的结构化存储
type: item
date: 2024-11-13T14:45:00+08:00
description: 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 时，它会把自己的向量时钟一并发送过去。接收到更新的节点会更新自己的时钟，确保自己的向量时钟包含其他节点的历史修改。检测冲突：向量时钟的核心在于它…

Percolator
type: item
date: 2024-10-31T19:30:00+08:00
description: 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其实…