Database

注: 本文仅为笔记，不怎么通顺和严谨。 KV系列属于一个大规模场景的必备品，而且通常很多公司会选择自研，一方面是各种不同产品均有局限，而大家的需求都有差别。另一方面社区已经有一些比较好的 building blocks，可以方便地进行组装和修改。最常见的情境是，分布式KV的开发 = 选一个底层kv存储 + 一个分布式协议。比如TiDB,ETCD等等。最近看 cloudflare 的 blog, 也是类似的场景。他们选的是 LMDB + 自研的分布式策略(称不上算法，比较简单)，也很好的满足了自己的需求。 LMDB 全称是 Lightning Memory-Mapped Database, 使用内存映射文件，读写性能比较高。 LMDB的一些特性: 支持APPEND模式，提高写操作的性能 支持多进程/线程同时访问。这种场景下读性能可以随着实例数增加而线性提升。 单独写不block读, 读也不 block 写。 不需要 transcation log, 提高了写性能。 实现上来讲，利用内存映射是一大特色。通常的文件读取操作，通过read系统调用，要先把数据从硬盘 copy 到内核，然后再拷贝到用户空间。而 mmap， 不直接进行数据拷贝，而是在缺页中断时进行处理。而且是直接拷贝到用户态，所以会比 read 效率高些。另外，这种内存映射是只读的，也避免了程序错误破坏存储结构。写操作则是通过 write 系统调用完成，由系统来保证数据一致性。其他细节： 使用 B+ tree. LMDB只允许单个写，性能有所降低，但是不再需要WAL日志，以及其他种种并发控制的冲突及代价。 LMDB中，数据的基本操作单元是页，COW也是以页为单位。 如果写操作比较多，那么数据版本也会很多，旧数据会占用大量空间。LMDB会将旧的页插入到一棵B+tree当中，然后等没有事物再用到它之后就可以重复利用。这样省去了定期清理操作，但是无法保证数据可以恢复到任意时刻了。 数据访问可以直接返回内存指针，避免内存拷贝。 COW保证存储结构一直是合法的。系统崩溃不会导致数据库处于一个不一致的状态。最坏的情况只是丢失了一些未提交的数据。根据一些学界的研究，尚没有发现因为使用 LMDB 导致数据损坏的案例。 LMDB中事物的实现思路如下: Atom（A）: LMDB中通过txn数据结构和cursor数据结构的控制，通过将脏页列表放入 dirtylist中，当txn进行提交时再一次性统一刷新到磁盘中或者abort时都不提交保证事务要不全成功、要不全失败。对于长事务，若页面spill到磁盘，因为COW技术，这些页面未与整棵B-Tree的rootpage产生关联，因此后续的事务还是不能访问到这些页面，同样保证了事务的原子性。 Consistency(C): 有如上的操作,保证其数据就是一致的，不存在因为多线程同时写数据导致数据产生错误的情况。 Isolation（I）：事务隔离通过锁控制（MUTEX），LMDB支持的锁互斥是进程级别/线程级别，支持的隔离方式为锁表支持，读读之间不锁，写等待读完成之后开始，读等待写完成后开始. Duration（D）:LMDB中，没有使用WAL、undo/redo log等技术来保证系统崩溃时数据库的可用性，其保证数据持续可用的技术是COW技术和只有一线程写技术。假如LMDB或者系统崩溃时，只有读操作，那么数据本来就没有发生变化，因此数据将不可能遭到破坏。假如崩溃时，有一个线程在进行写操作，则只需要判断最后的页面号与成功提交到数据库中的页面号是否一致，若不一致则说明写操作没有完成，则最后一个事务写失败，数据在最后一个成功的页面前的是正确的，后续的属于崩溃事务的，不能用，这样就保证了数据只要序列化到磁盘则一定可用，要不其就是还没有遵循ACI原则序列化到磁盘 总结来看，LMDB是一个极为优秀的产品。即使作者声称它主要是为了读场景而不是写场景，但实测的结果都不错。BUG少，稳定性强。 Cloudflare 的实践 Cloudflare 需要一个分布式的 KV Storage 来存储用户配置信息，当用户做了改动之后，能很快地分发到所有的数据中心。最开始用的是Kyoto Tycoon datastore, 在使用过程中发现了不少问题，最终切换到了 LMDB. ...

虽然日常工作需要涉及到数据库的底层部分并不多，但Postgresql作为一个数据库实现的范本是很值得研究的。可以通过它的实现来探索很多通用的数据库设计以及系统设计的理念。本文主要关注于事物设计方面。 MVCC pg底层使用MVCC，修改数据时会直接创建新版本，而不是直接修改旧数据。这部分有一点需要注意的是在pg中，所有的语句都是在事物中执行的，不管是不是明确地用了BEGIN/COMMIT。 Transactions, tuples, and snapshots 先看一下 Transaction 的主要数据结构: typedef struct PGXACT { TransactionId xid; /* id of top-level transaction currently being * executed by this proc, if running and XID * is assigned; else InvalidTransactionId */ TransactionId xmin; /* minimal running XID as it was when we were * starting our xact, excluding LAZY VACUUM: * vacuum must not remove tuples deleted by * xid >= xmin ! */ ... } PGXACT; 事物以xid作为标识.pg针对它做了很多优化，仅在真正开始写数据的时候才分配xid,如果是只读的事物就完全不分配。 xmin表示当这个事物开始的时候仍然处在运行中的事物列表中最小的那个xid ...

数据库一般认为是一种系统软件。而操作系统处于更底层的位置。这是一种通常的认知。 Unix 的一切皆文件的设计思想，从一定程度上来讲，表明了操作系统内部不同组件之间有一定的结构上的一致性。比如网络接口和文件接口，都有如下的操作 Rread Write Close/Open permission 等等。进程和内存管理也是类似的逻辑。所以我们现在可以看到 Linux 系统中有很多类似的尝试，用文件的形式来来作为很多内部组件对外的接口。 这是 Linux 一直在被夸赞的地方。一个听起来优美的设计哲学，吸引了很多人从奇怪的，程序员不友好的 Windows 逃离过来，并花费大量的精力来学习和理解这个设计之下隐藏的诸多肮脏的细节。 工作越久，越来越多的人发现。相比较而言，平时还是 Mac 和 Linux 用起来更方便。即使是爱折腾的程序员，也大多不愿再去浪费时间去折腾 Linux，去折腾 VIM/Emacs。不是因为年纪大了，而是因为这些东西确实用户不友好，而且有设计缺陷。 几十年前， 已经很清楚地点评了 Linux/Unix 上的诸多问题。然而它并没有推动 Linux/Unix 去改变和解决这些问题。开源是一面美好的大旗，但它也蒙蔽了跟着的人。 Linux 桌面的失败简直惨不忍睹。自由的 fork, Client-Server 的架构，无尽的口水仗。最终活下来了两个无法合作的 KDE/Gnome。Windows 自然也有很多设计的问题，但注册表现在看来相对于 Linux 的配置文件来说简直是太优秀了。多年人，有些人会想到： 不同 cmd 的 input 和 ouput 的格式都不一样，增加了很多研发的负担 能否用一种统一的数据格式来表达配置以及输入输出？比如 json 也有人尝试过，但从来不会真正影响到社区。即使成功了，systemd 的经历也历历在目。 虽然能将操作系统的诸多概念简化成文件，但文件仍然是一个相对复杂的抽象概念。除了文件系统，没有哪个其他模块能够与文件如此对齐。就数据本身而言，打开文件之后，读写数据，本质上简化为两个结构: list 和 dict，组合起来就是一个 table。 读写文件，基本上就是不断地对这个 table 做修改，增加，删除，修改行。CSV 格式的文件更是可以直接直接对应于一张表。所有其他的内部模块,其操作也是类似的； 创建进程： 往进程列表里添加一个元素 销毁进程: 从进程列表里删除一个元素 添加设备: 往设备列表里增加一个元素 配置设备: 修改设备的属性 不只是 Linux，所有操作系统面临的都是同样的问题，使用的都是同样的的机制: 不听地对Table 做各种操作。现状是，所有的操作系统在不同模块的管理上都是有差别的，因为没有统一数据模型的支持，每个模块都在不断地用不同的形式做类似的操作，其提供给用户的功能也因此而受限。 ...

介绍 分片策略 The Lookup strategy The Range strategy The Hash strategy 相关技术 BRIN 介绍 Shard 指对数据的水平切分,每一个切分的部分都可以叫做一个shard,它们拥有相同的 schema,但却拥有不同的数据集。对数据库来说，是指对数据库的表按行进行切分(与按列的垂直切分对应)，不同的 shard 可能位于不同的数据库服务器或者物理机器上。它的优势体现在以下几点: 表的大小减少,索引体积减小,提升查询性能(某些方面) 如果数据本身有比较明显的分区(比如国家,地区等),那么做 shard 很容易并且查询很大程度上都能落在一个 shard 上。 水平扩展性好，可以通过添加新节点来扩充 劣势有以下几点: 查询需要跨多个 shard 时会增加 latency 因为 shard 经常只能做到某一位维度。所以在这一维度的查询的性能可能提高，但其他维度的查询的性能则可能会下降。 跨 shard 的数据一致性和可用性也更加复杂和难以保障 shard 本身的问题让他成为一个迫不得已的选择。尽量在没有其他优化方式的情况下选择 shard.理想情况下，应该有底层框架来处理 shard 而让应用层做到对 shard 无感知，不然还不如不用。 分片策略 如果将数据集进行 shard,有很多策略可以选择，常见的有 The Lookup strategy 用 shard key 做一个映射表，包含不同 shard key 的请求会转发到相应的 shard 上。这种情况下，不同 shard key 的数据可能会落在同一个 shard 上，但相同 shard key 的数据则一定在同一个 shard 上.shard 与物理地址的映射也不能是一对一的，可以用类似于 consistent hashing 里面的那种 virtual node 的方式，设置一些virtual shard，几个 virtual shard 可以对应于同样的物理位置(reblancing 的时候对上层代码的影响很小)。 ...