什么是LevelDB—-LevelDB日知录

一种单机持久化 K/V 数据库。其基于 LSM(LOG Structured Merge Tree) 实现，将所有的 Key/Value 按照 Key 的词法序有序地储存在文件中，具有很高的随机/顺序写性能，非常适用于写多读少的环境。

LevelDB 不是一个 SQL 数据库，它不支持关系数据模型，不支持 SQL 语言，也不支持索引。在同一时刻只允许单个进程（可以是多线程）访问数据库。

LevelDB具备以下特性：

1. Keys 和 Values 可以是任意的字节序列

2. 数据是按照 Key 排序的

3. 调用者可以提供一个定制的比较函数来决定 Keys 的排序方式。

4. 针对数据库的操作非常简单，i.e. Put, Get, Delete

5. 可以在一次原子的批处理中同时多次修改数据库

6. 用户可以创建 snapshot 保持对于数据视图的一致性

7. 这个数据结构提供前向和后向的迭代器 (iterator)

8. 数据可以自动经过 Snappy 算法压缩

9. 针对于操作系统文件的交互操作，LevelDB 提供给外部用户一个可以定制的虚拟的接口(Env)

写入流程

1. 每次写入一个 Key/Value 对时，首先将该数据追加到 log 中，然后再将其写入到内存的 memtable。memtable 是一个基于 SkipList 的有序的结构，每一个 Key 都会按序组织到 memtable 中。
2. 当 memtable 中的数据量达到一定的限制后，其将会转变成为一个 Immutable memtable，同时 levelDB 会新建新的 Log 文件和 memtable 结构用来接收后续的插入操作。内存的 Immutable memtable 将会被后台的线程持久化的存储到磁盘中，生成有序 sstable 文件。
3. 磁盘上的 sstable 文件按照 level 的形式组织，从 memtable 序列化得到的 sst 文件位于 level0 层。由于经过 compaction 线程的压缩，文件将不断地从 level n 层向 level n+1层移动。

delete操作

读取流程

leveldb读取数据总是先读取最新的数据,因为有可能插入键值一样的键值对,但是我们查询时是想获取最近插入的数据,所以读取数据时的顺序为：memtable->immemtable->sstable

compaction

minor compaction

就是将immemtable数据写回到磁盘的过程, 也就是L0层sst文件，L0 层的文件个数一般有一个限制

major compaction

即将某一层Ln某个文件和上一层Ln+1的几个sst文件合并的过程,合并时究竟应该选择哪个SSTable与上一层sst文件进行合并以及每层的SSTable空间上限是多大，不同的系统有不同的实现

源码分析

Put函数调用Write函数，触发后台合并操作，DoCompactionWork之前会先调用MakeRoomForWrite函数判断空间是否足够

LSM Tree存储引擎

LSM Tree 的写性能高于 B+ Tree，读性能低于 B+ Tree。原理就是磁盘的顺序访问速度远大于随机访问深度，甚至于磁盘的顺序访问速度大于内存的随机访问速度。

MemTable

核心是Get和Add函数实现对SkipList的操作

Skiplist跳跃表

• 构建

  

• 查找

  

• 插入/删除

  

• 复杂度

  

sstable

manifest

versionSet

Key/Value数据存储

Node数据结构

skiplist中的单个node不仅存储了key，也存储了value。dbformat.h文件中定义了跳跃表中的node数据结构，如下表。

skiplist中定义的几种key类型及其组成部分：

• LookupKey/memtable_key：klength + user_key + sequence+type
• InternalKey：user_key + sequence+type
• 不管是memtable还是sstable文件，其内部都是按InternalKey有序的。 比较时先使用InternalKey内部的user_key进行比较，再比较sequence_num

sstable存储结构

Cache

table cache

table cache的key值是SSTable的文件名称，Value部分包含两部分，一个是指向磁盘打开的SSTable文件的文件指针，这是为了方便读取内容；另外一个是指向内存中这个SSTable文件对应的Table结构指针。这样就将不同的sstable文件像cache一样进行管理。

block cache

block cache 的结构其中的key是文件的cache_id加上这个block在文件中的起始位置block_offset。而value则是这个Block的内容

Util基础工具包

coding.cc —- 编解码

leveldb所有数据都是字符形式，即使是整型，也将被转换为字符型存储。这样的好处就是可以减少内存空间的使用。例如，假如有一个int型数据，小于128，存储为整型时，需要占用四个字节，存储为字符型时，只需要一个字节即可。

LevelDB 使用了一种很简单的方案 varint 来节省小整数的存储。对于每一个字节，levelDB 使用其最高的 bit 位来表示当前的编码是否结束，而用低 7 bit 来存储实际的数据。如果最高位为1，表示当前的编码尚为结束，需要继续读下一字节的数据，否则当前的编码结束。示例：

1. 对于比较大的数，如果存储的数据如下
   1001 0001 1000 1001 0111 1100
   ^ ^ ^ A: 最高位是1，未结束，实际值是后七位 001 0001
   | | | B: 最高位是1，未结束，实际值是后七位 000 1001
   A B C C: 最高位是0，结束， 实际值是后七位 111 1100
   因此，三个字节拼接应该是 C + B + A :
   [1111100][000 1001][0010001] = 2032785
2. 对于 [0-127] 的整数，例如：
   0001 0001
   ^ A: 第一字节，最高位为0，表示结束，实际值是 0010001
   | 也就是 33
   A

arena.cc —- 内存池

Arena内存池实现原理是每次向系统申请4KB大小的一整块内存block, 程序需要内存时,直接从block中获取一部分即可, 这样可以减少系统分配内存次数(new char[]操作), 降低系统分配内存带来的消耗。但是当程序需要一大块内存时(>1024B)时就单独分配一块需要大小的内存，这样也是为了减少系统分配内存的次数。当需要的内存大于block剩余大小而且小于等于1024B时，重新分配一块block，这样会导致有1/4的block被浪费掉。

cache.cc —- LRU缓存

HashTable 和 环形双向链表的结合, hashtable实现O(1)存取时间复杂度; 双向链表实现每次读取或者插入元素都在链表head，每次淘汰链表tail。lru.prev is newest entry, lru.next is oldest entry.

schedule —- 后台任务调度队列

实例分析

RocksDb vs LevelDb

概述

RocksDb新增特性和优化列表

性能优化：

1. compaction和memtable inserts操作都多线程化，不止是后台单线程操作
2. 减少互斥锁，优化写锁
3. Fewer comparator calls during SkipList searches
4. Allocate memtable memory using huge page
5. Prefix bloom filter
6. Optimized level-based compaction style and universal compaction style
7. 对SSD存储做了优化，可以以in-memory方式运行

新增特性：

• 列簇（column families）
• 手动压缩与自动压缩并行运行
• Persistent Cache 持久化缓存
• Merge Operators，也就是原地更新，优化了modify的效率
• Transactions and WriteBatchWithIndex
• 单个删除，以及范围删除文件
• Vector-based and hash-based memtable format
• Group commit和AwaitState
• 内存中有多个Immutable memtable

memtable

rocksdb中,memtable在内存中的形式有三种：skiplist、hash-skiplist、hash-linklist。

内联跳跃表（Inline Skip List）

Group commit和AwaitState

RocksDB多个写线程组成一个group， leader 负责 group 的 WAL (write ahead log)及 memtable 的提交，提交完后唤醒所有的 follwer，向上层返回；leader批量提交group所有线程的WAL日志，然后唤醒follower，一起开始并发无锁写memtable（allow_concurrent_memtable_write开关），洗完之后更新线程链表，开始下一轮写入；还支持enable_pipelined_write流水线配置，允许在WAL写完之后开始并发写memtale时就开始下一轮的group。

参考链接

整体来看，从上到下，一个对象存储系统应该包括产品层的高级功能(包括鉴权、读写接口)、元数据管理模块(MySQL、NewSQL数据库)、数据管理模块(对象数据的管理)。可以参考S3、Ceph等系统。

元数据管理模块

NewSQL

NewSQL 的出现就是为了解决扩展性和一致性之间的矛盾，主要面向 OLTP 业务和轻量级的OLAP业务。几点特性：

1. 支持常见SQL语句查询，需要实现一个分布式SQL engine，利用多个节点的计算能力，生成更好的执行计划，将计算逻辑尽可能的均摊到多个存储节点上，与单机引擎不同的是考虑网络的开销和延迟。
2. 支持 ACID 的跨行事务，两阶段提交实现分布式事务，也就是保证多个节点操作的原子性，要么全部节点成功要么全部失败
3. 自动可扩展性。目前关系型数据库的扩展方案上，基本只有分库分表和 PROXY 中间件两种方案。
4. 自动FailOver。常规主从复制方式无法脱离人工运维，因此选用 Multi-Paxos 或者 Raft 这样基于分布式选举的复制协议，在某节点故障的时候，支持完全自动和强一致的故障转移和自我恢复，还能实现跨数据中心多活

NewSQL数据库探秘

数据管理模块

几个思考

为什么要用EC编码和三副本kv存储相结合的方式？

从3副本到1.5副本，主要是为了节省成本。3副本其实数据可靠性(也就是数据持久性)其实很低。对大对象直接进行EC编码，但是小对象不能直接EC，因为小对象太多，如果EC会带来IOPS放大；可以考虑对小对象打包之后做EC，避免增大IOPS。

如何实现快速空间回收？也就是快速删除object

如何将存储副本降低到1.33的？

EC编码如何提高数据的持久性？

如何实现多AZ和更高的集群可扩展性？

如何提高系统的读写性能？

C++常用std集合—map/set

1. unordered_map在C++11的时候被引入标准库了，而hash_map没有，所以建议还是使用unordered_map比较好。查询平均时间是O(1)，无序，类似于Java中HashMap。
2. map的内部结构是R-B-tree来实现的，所以保证了一个稳定的动态操作时间，查询、插入、删除都是O（logN），最坏和平均都是。而unordered_map如前所述，是哈希表。顺便提一下，哈希表的查询时间虽然是O（1），但是并不是unordered_map查询时间一定比map短，因为实际情况中还要考虑到数据量，而且unordered_map的hash函数的构造速度也没那么快，所以不能一概而论，应该具体情况具体分析。最坏会是O(n)，额外空间复杂度则要高出许多。map中的元素是按照二叉搜索树存储，进行中序遍历会得到有序遍历，默认遍历顺序为以key从小到大。
3. 无序集合（Unordered Set）容器是一个存储唯一（Unique，即无重复）元素的关联容器（Associative container），容器中的元素无特别的次序关系。该容器允许基于值地快速元素检索。类似于HashSet。
4. set/multiset/map/multimap的内部实现和常用函数
5. 红黑树原理

BloomFilter布隆过滤器

1. 核心实现是一个很长的二进制向量 （位数组）再加上一系列随机函数 (哈希)，空间效率和查询效率高，不会漏判，但是有一定的误判率（哈希表是精确匹配）。

2. 布隆过滤器解决缓存击穿、垃圾邮件识别、集合判重

SkipList跳跃表

参考链接

块存储/对象存储/文件系统

1. 块存储：访问时延是10ms级，常用于跟虚机搭配使用，与普通硬盘无异，读写速度由于并发所以非常快。既要能应付大文件读写，也能处理好小文件读写。但是硬盘的特点是容量大，热点明显。因此块存储主要可以应付热点问题。另外，块存储要求的延迟是最低的。通常以QEMU Driver或者Kernel Module的方式存在，这种接口需要实现Linux的Block Device的接口或者QEMU提供的Block Driver接口，如Sheepdog，AWS的EBS，ceph的RBD；分布式块存储系统通常提供快照功能，方便在故障或者是业务需要的时候，将块设备上的数据恢复到期望的一个时间点。每次快照并不是全量快照，而是增量快照，仅对修改过的区间进行备份。
2. 对象存储：访问时延是100ms-1s级，通常以大文件为主，要求足够的IO带宽。接口就是简单的GET、PUT、DEL和其他扩展，如七牛、又拍、Swift、S3
3. 文件存储：通常意义是支持POSIX接口，它跟传统的文件系统如Ext4是一个类型的，需要考虑目录、文件属性等支持；但区别在于分布式存储提供了并行化的能力，如Ceph的CephFS；分布式文件系统通常需要有一个或一组namenode节点维护目录树，一个或一组metaserver节点来维护文件元信息
4. 块存储和文件存储在形态上虽然不同，但实际使用基本一致，块存储扩展性好、兼容性更好，但使用略麻烦；文件存储使用方便，且故障隔离性好，但扩展性不好。
5. 表格存储
6. 归档存储

OLAP与OLTP

当今的数据处理大致可以分成两大类：联机事务处理OLTP（on-line transaction processing）、联机分析处理OLAP（On-Line Analytical Processing）。OLTP是传统的关系型数据库的主要应用，主要是基本的、日常的事务处理，例如银行交易，关注实时性，数据量较少。OLAP是数据仓库系统的主要应用，支持复杂的分析操作，侧重决策支持，并且提供直观易懂的查询结果。

• 数据库OLTP：传统的关系型数据库的主要应用，主要是基本的、日常的事务处理，例如银行交易。
• 数据仓库：数据仓库系统的主要应用主要是OLAP（On-Line Analytical Processing），支持复杂的分析操作，侧重决策支持，并且提供直观易懂的查询结果。
• 举个最常见的例子，拿电商行业来说好了。基本每家电商公司都会经历，从只需要业务数据库到要数据仓库的阶段。
  1. 电商早期启动非常容易，入行门槛低。找个外包团队，做了一个可以下单的网页前端 + 几台服务器 + 一个MySQL，就能开门迎客了。这好比手工作坊时期。
  2. 第二阶段，流量来了，客户和订单都多起来了，普通查询已经有压力了，这个时候就需要升级架构变成多台服务器和多个业务数据库（量大+分库分表），这个阶段的业务数字和指标还可以勉强从业务数据库里查询。初步进入工业化。
  3. 第三个阶段，一般需要 3-5 年左右的时间，随着业务指数级的增长，数据量的会陡增，公司角色也开始多了起来，开始有了 CEO、CMO、CIO，大家需要面临的问题越来越复杂，越来越深入。高管们关心的问题，从最初非常粗放的：“昨天的收入是多少”、“上个月的 PV、UV 是多少”，逐渐演化到非常精细化和具体的用户的集群分析，特定用户在某种使用场景中，例如“20~30岁女性用户在过去五年的第一季度化妆品类商品的购买行为与公司进行的促销活动方案之间的关系”。
  4. 这类非常具体，且能够对公司决策起到关键性作用的问题，基本很难从业务数据库从调取出来。原因在于：业务数据库中的数据结构是为了完成交易而设计的，不是为了而查询和分析的便利设计的。业务数据库大多是读写优化的，即又要读（查看商品信息），也要写（产生订单，完成支付）。因此对于大量数据的读（查询指标，一般是复杂的只读类型查询）是支持不足的。
  5. 而怎么解决这个问题，此时我们就需要建立一个数据仓库了，公司也算开始进入信息化阶段了。数据仓库的作用在于：数据结构为了分析和查询的便利；只读优化的数据库，即不需要它写入速度多么快，只要做大量数据的复杂查询的速度足够快就行了。那么在这里前一种业务数据库（读写都优化）的是业务性数据库，后一种是分析性数据库，即数据仓库。
• 最后总结一下：数据库比较流行的有：MySQL, Oracle, SqlServer等。数据仓库比较流行的有：AWS Redshift, Greenplum, Hive等。这样把数据从业务性的数据库中提取、加工、导入分析性的数据库就是传统的 ETL 工作。

CAP理论

2000年7月，加州大学伯克利分校的Eric Brewer教授在ACM PODC会议上提出CAP猜想。2年后，麻省理工学院的Seth Gilbert和Nancy Lynch从理论上证明了CAP；也就是：一个分布式系统最多只能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）这三项中的两项。

1. 一致性：all nodes see the same data at the same time；根据业务场景可以分为强一致性，弱一致性和最终一致性。对于关系型数据库，要求更新过的数据能被后续的访问都能看到，这是强一致性。如果能容忍后续的部分或者全部访问不到，则是弱一致性。如果经过一段时间后要求能访问到更新后的数据，则是最终一致性。
2. 可用性：Reads and writes always succeed，即服务一直可用，而且是正常响应时间。如果系统每运行100个时间单位，会有1个时间单位无法提供服务，则说系统的可用性是99%。
3. 分区容错性：the system continues to operate despite arbitrary message loss or failure of part of the system，即分布式系统在遇到某节点或网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务。
4. CAP权衡：

CA without P：如果不要求P（不允许分区），则C（强一致性）和A（可用性）是可以保证的。但其实分区不是你想不想的问题，而是始终会存在，因此CA的系统更多的是允许分区后各子系统依然保持CA。

CP without A：如果不要求A（可用），相当于每个请求都需要在Server之间强一致，而P（分区）会导致同步时间无限延长，如此CP也是可以保证的。很多传统的数据库分布式事务都属于这种模式。

AP wihtout C：要高可用并允许分区，则需放弃一致性。一旦分区发生，节点之间可能会失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。现在众多的NoSQL都属于此类。

对于多数大型互联网应用，集群规模庞大、主机众多、部署分散，节点故障、网络故障是常态，而且要保证服务可用性达到N个9，往往采用AP without C，只保证最终一致性即可。

对于银行业场景，C必须保证。网络发生故障宁可停止服务，这是保证CA，舍弃P；还有一种是保证CP，舍弃A，例如网络故障事只读不写。

保证P的前提下，选择一致性C，举例：传统单库水平切分，就是这类选型的典型

保证P的前提下，选择可用性A，举例：双主库同步高可用，就是这类选型的典型

分布式存储常见概念名词

1. RAID(Redundant Array of Independent Disk 独立冗余磁盘阵列)是加州大学伯克利分校1987年提出，最初是为了组合小的廉价磁盘来代替大的昂贵磁盘，同时希望磁盘失效时不会使对数据的访问受损失而开发出一定水平的数据保护技术。RAID就是一种由多块廉价磁盘构成的冗余阵列，在操作系统下是作为一个独立的大型存储设备出现。RAID可以充分发挥出多块硬盘的优势，可以提升硬盘速度，增大容量，提供容错功能够确保数据安全性，易于管理的优点，在任何一块硬盘出现问题的情况下都可以继续工作，不会受到损坏硬盘的影响。
2. RAID卡就是用来实现RAID功能的板卡，通常是由I/O处理器、SCSI控制器、SCSI连接器和缓存等一系列零组件构成的。不同的RAID卡支持的RAID功能不同。支持RADI0、RAID1、RAID3、RAID4、RAID5、RAID10不等。RAID卡可以让很多磁盘驱动器同时传输数据，而这些磁盘驱动器在逻辑上又是一个磁盘驱动器，所以使用RAID可以达到单个的磁盘驱动器几倍、几十倍甚至上百倍的速率。这也是RAID卡最初想要解决的问题。可以提供容错功能，这是RAID卡的第二个重要功能。
3. MVCC
4. EC编码与各级RAID

轮询调度算法

1. 轮询调度算法的原理是每一次把来自用户的请求轮流分配给内部中的服务器，从1开始，直到N(内部服务器个数)，然后重新开始循环；即每次调度执行i = N-1; i = (i+1) mod N，并选出第i台服务器
2. 适合于服务器组中的所有服务器都有相同的软硬件配置并且平均服务请求相对均衡的情况, 它无需记录当前所有连接的状态，是一种无状态调度。

Learned Indexes VS Traditional Indexes

目前存在多种索引的选择来解决各种访问模式的需求。例如 B-Trees 是范围请求最好的选择（例如在特定时间线上索引所有的数据记录），哈希表（Hash-Maps）在性能上很难打败基于键值的搜索方法，而布隆过滤器 (Bloom Filter) 通常用于检测是否存在某条记录。由于索引对于数据库系统和其它一些应用的重要性，过去几十年来，它们已经广泛地发展为更高的内存、缓存和 CPU 效率的方法

本论文的核心思想是一个模型可以学习排序顺序或查找键的结构，并使用这一信号有效地预测记录的位置或存在。我们从理论上分析了学习索引在什么条件下表现优于传统索引结构，并描述了设计学习索引结构的主要挑战。我们的初步结果表明，借助神经网络，我们能够超过缓存优化的 B-Trees 高达 70％的速度，同时为若干个真实数据集节省一个数量级的内存。

分布式事务

两阶段提交2PC

1. 二阶段提交2PC（Two phase Commit）是一种在分布式环境下所有节点进行事务提交保持一致性的算法。它通过引入一个协调者（Coordinator）来统一掌控所有参与者（Participant）的操作结果，并指示它们是否要把操作结果进行真正的提交（commit）或者回滚（rollback）。
2. 两个阶段：
   • 投票阶段（voting phase）：参与者通知协调者，协调者反馈结果；
   • 提交阶段（commit phase）：收到参与者的反馈后，协调者再向参与者发出通知，根据反馈情况决定各参与者是否要提交还是回滚
3. 2PC在执行过程中，所有节点都处于阻塞状态，所有节点所持有的资源（例如数据库数据，本地文件等）都处于封锁状态。例如，某一个参与者回复消息之前，所有参与者以及协调者都处于阻塞状态；在协调者发出消息之前，所有参与者都处于阻塞状态。要打破完全阻塞状态需要引入超时机制。

常见分布式一致性算法

Paxos

Raft

异同点

应用场景

1. 2PC和Paxos区别：2PC用于保证多个数据分片上分布式事务的原子性，Paxos协议用于保证同一个数据分片在多个副本的分布式一致性，所以两者可以是互补的关系，绝不是替代关系。对于2PC协调者单点问题，可以利用Paxos协议解决，当协调者出问题时，选一个新的协调者继续提供服务。

计算机系统是由硬件和系统软件组成的，它们共同工作来运行应用程序。

操作系统

操作系统处于中间位置，它的一边是应用程序、实用程序和用户，另一边是计算机系统的硬件。

计算机硬件