应用程序不可避免地需要随时间而变化，在演化过程中，需要不断地添加或修改功能。在大多数情况下，更改应用程序功能时，也需要更改其存储的数据: 可能需要捕获新的字段或记录类型，或者需要以新的方式呈现已有数据。 当数据格式发生变化时，经常需要对应用程序代码进行相应的调整(例如，向记录中添加新字段，然后应用程序代码开始读取和写入该字段) 。然而，对于一个大型应用系统，代码更迭往往并非易事。 服务器端程序，可能需要滚动升级，每次将新版本部署到少数几个节点，之后再逐步推广到所有节点。 对于客户端应用程序，用户可能不会在一段时间内马上更新软件 这意为着新旧版本的代码，以及新旧数据格式，可能同时在系统中共存，所以保证数据的双向兼容性至关重要 数据兼容性 向后兼容性较新的代码可以读取由旧代码编写的数据 向前兼容性较旧的代码可以读取新代码编写的数据 向后兼容通常不难实现：只需要清楚旧代码所编写的数据格式，就可以比较明确的处理这些数据，对于向前兼容性，旧的代码需要忽略新版本代码中所做的添加 在本文中，将介绍多种编码数据的格式，包括JSON、XML、Protocol Buffers、Thrift。特别 ...

对于数据库来说，向它插入数据，它就保存数据，向它查询，它就返回那些数据，根据上文，当确定数据库的数据格式(文档模型，关系模型，图状模型)以及对应的查询语言(SQL、命令式查询)之后，本文将从数据库的角度来探索如何存入数据以及在受到查询时，如何找到数据。 数据库核心123456789#!/bin/bashdb_set () { echo "$1,$2" >> database}db_get () { grep "^$1," database | sed -e "s/^$1,//" | tail -n 1} 这两个函数实现了一个 KV 存储，当调用 db_set key value,将在 database 中保存 key value, 调用 db_get key ,会返回 key 对应的 value 它底层的存储格式其实非常简单 : 一个纯文本文件。其中每行包含一个key-value对，用逗号分隔 (大致像一个CSV文件，忽略转义问题) 。每次调用db_set即 ...

背景数据模型可能是开发软件最重要的部分，它们不仅对软件的编写方式，而且还对如何解决问题都有深远的影响。 大多数应用程序是通过一层一层叠加数据模型来构建的。每一层都面临的关键问题是: 如何将其用下一层来表示? 例如： 作为一名应用程序开发人员，通过实际要求，创建对应的对象以及数据结构。 当需要存储这些数据结构时，可以采用通用数据模型 (例如JSON或XML文档、关系数据库中的表或图模型) 来表示。 数据库工程师接着决定用何种内存、磁盘或网络的字节格式来表示上述JSON/XML/关系/图形数据。数据表示需要支持多种方式的查询、搜索、操作和处理数据。 在更下一层，硬件工程师则需要考虑用电流、光脉冲、磁场等来表示字节。 复杂的应用程序可能会有更多的中间层，基于底层API来构建上层API，但是基本思想相同: 每层都通过提供一个简洁的数据模型来隐藏下层的复杂性。 下文将介绍一系列用于数据存储和查询的通用数据模型，我们将比较关系异型、文档模型和一些基于图的数据模型。我们还将讨论多种查询语言并比较它们的使用场景。 关系模型与文档模型SQL现在最著名的数据模型可能是 ...

背景当今许多新型应用都属于数据密集型 (data-intensive) ，而不是计算密集型(compute-intensive) 。对于这些类型应用，CPU的处理能力往往不是第一限制性因素，关键在于数据量、数据的复杂度及数据的快速多变性。 数据密集型应用通常也是基于标准模块构建而成，每个模块负责单一的常用功能。例如，许多应用系统都包含以下模块： 数据库: 用以存储数据，这样之后应用可以再次访问。 高速缓存: 缓存那些复杂或操作代价昂贵的结果，以加快下一次访问。 索引: 用户可以按关键字搜索数据并支持各种过着。 流式处理: 持续发送消息至另一个进程，处理采用异步方式。 批处理: 定期处理大量的累积数据。 越来越多的应用系统需求广泛，单个组件往往无法满足所有数据处理与存储需求。因而需要将任务分解，每个组件负责高效完成其中一部分，多个组件依靠应用层代码驱动有机衔接起来。 设计原则设计数据系统或数据服务时，一定会碰到很多环手的问题。例如，当统内出现了局部失效时，如何确保数据的正确性与完整性?当发生系统降级 (degrade) 时，该如何为客户提供一致的良好表现?负载增加时，系统如何扩 ...

背景紧接上篇，通过 PickCompaction 确定了 需要 Compaction 的层级 level 及文件 确定了 level + 1 层文件 确定了 level + 2 层文件 接下来，我们来分析后续的 Compaction 操作 分析leveldb 并不是之间直接将 level 与 level + 1 层进行进行 Compaction ，而是有一个优化：根据所选文件进行判断这是否是一次简单的压缩 123456789// c 代表上一次 PickCompaction 操作是否有需要 Compaction 的文件// c == nullptr 代表当前无文件需要处理if (c == nullptr) { // Nothing to do } else if (!is_manual && c->IsTrivialMove()) { ... } else { ... } is_manual 是前文提到过的：是否是通过 leveldb 对外接口手动触发 Compaction ，默认是 ...

背景leveldb 是一个写效率十分高的存储引擎, 一次写操作只需要顺序写日志(WAL)，内存跳表插入(logn) 但是如此以来读性能就有所下降，在最差的情况下可能需要查找以下所有文件 1MemTable --> Immutable MemTable --> Level 0 files --> Level 1 files -->Level 2 files ......-->Level 6 files 所以引入 Compaction 可以带来如下好处 平衡读写差异，将相关文件进行合并 删除过时数据，减少数据量 分析Compaction 是通过后台线程调用 BackgroundCompaction 来触发，上一章中我们分析了如何触发 Compaction 并分析了当中的 Minor Compaction ，本文将关注当中的 Major Compaction (SSTable 当中的 Compaction) BackgroundCompaction 主要有两个部分组成 Minor Compaction1234if (imm_ != nullptr) & ...

背景 图片来自于SmartKeyerror 此图为 SSTable 的总览图，如图所示主要由下面几个模块构成 Data Block ： 具体的数据块，存储 (key value)，并在存储时通过前缀压缩等方法进行优化 Meta Block ： 为了方便查询所建立的过滤块，leveldb中使用的是布隆过滤器，该过滤块可以快速判断 key 是否存在 Metaindex Block ： 对 Meta Block 块的索引块，默认 Meta Block 为 4K 大小 Index Block ：对 Data Block 块的索引块 Footer ：存储 Metaindex Block 与 Index Block 的偏移地址 分析触发 Compaction接下来我们将从 leveldb 的源码部分看看一个 SSTable 究竟是如何产生的 首先是一个大致的调用逻辑: leveldb 会在对外接口 open 中去调用 MaybeScheduleCompaction 函数，从名字中得知，此函数应该是调度触发压缩(Compaction)，为什么是Maybe呢？ 12345678910111 ...

背景一般来说，哈希表的实现是通过两个部分实现的 12hash = hashfunc(key)index = hash % table_size 使用求模来减少存储空间，所以必然会导致不同的数据离散到相同的索引下标处，此时就发生了哈希冲突。 解决方案主要分为两大类 链式法 （Separate Chaining） 开放地址法（Open Addressing） 链接技术将采用额外的数据节点来处理冲突。当冲突发生时，在冲突位置建立链表，通过链表串联起离散到相同下标的节点。在最坏的状况下，会退化为单链表，性能损失严重，哈希攻击便是采用这种形式。 开放地址就是开放哈希表中的所有地址，不使用额外的空间。如果遇到冲突，寻找其他位置存储。 开放地址法线性探测如果哈希到索引为 x 处，如果此处有元素，则查看 x + 1 处，如果没有则放在这里，如果有，则以此类推查看 x + 2，x + 3, … 二次探查这是线性探测的改进，每次的步长变为平方倍数。 Double hashing另一种改进的开放寻址法称为重哈希(Double hashing)或者叫二度哈希（Rehashing） 而在 LevelD ...

背景Bloom Filter 是一种空间效率很高的随机数据结构，它利用位数组表示一个集合，并能判断一个元素是否属于这个集合。 Bloom Filter 的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。 leveldb 中利用布隆过滤器判断指定的 key 值是否存在于 sstable 中，若过滤器表示不存在，则该 key 一定不存在，由此加快了查找的效率。 优劣相对于其他表示数据集的数据结构，如平衡二叉搜索树、Trie 树、哈希表，甚至更简单的数组或者链表。大都需要对数据项本身存储。但是 Bloom Filter 并不存储数据项本身，而是用高效紧凑的位数组来存。 如此设计，使得 Bloom Filter 的大小与数据项本身大小（如字符串的长短）无关。可以理解为在哈希表基础上，忽略了冲突处理，从而省下了额外开销。 对于 Bloom Filter ，其误判率应该和以下参数有关： 哈希函数的个数 k 底层位数组的长度 m 数据集大小 n 当 k = ln2 * (m/n) ...

背景LRU （Last Recent Used）是一个重要的缓存替换算法，常用于缓存场景,一般的实现是使用一个哈希表（unordered_map）和一个双向链表，哈希表解决索引问题，双向链表维护访问顺序。 内部实现LevelDB的LRUCache设计有4个数据结构，是依次递进的关系，分别是： LRUHandle HandleTable LRUCache ShardedLRUCache LRUHandle 是 LRUCache 中的数据节点，HandleTable 是 LRUCache 为了实现可扩展哈希性而自定义的哈希桶，LRUCache 便是核心类，内部维护了一条冷数据双向链表，一条热数据双向链表，以及 HandleTable来索引节点，此时LRU的缓存管理数据结构已经实现。而 ShardedLRUCache 是为了在多线程访问时提升效率，内部有16个LRUCache，查找key的时候，先计算属于哪一个LRUCache，然后在相应的LRUCache中上锁查找。 模块分析首先是 LevelDB 的导出接口 Cache 123456789101112131415161718192 ...