• 首页
• 新闻中心
  • 内部新闻
  • 公共新闻
  • 业界新闻
  • 产品新闻
• 产品应用
  • 程序开发工具
  • 企业级应用
  • 服务器软件
  • 应用工具
  • 数字娱乐
  • 硬件
• 解决方案
  • 系统架构经验谈
  • 系统部署应用
  • 办公自动化
  • 案例集锦
  • 参考手册
• 开源应用支持
  • 认识Unix
  • 系统管理
  • 网络管理
  • 桌面应用
  • 存储备份
  • 引导安装
  • 服务应用
  • 群集应用
  • 数据库
  • 系统安全
• 程序设计与开发
  • Perl编程
  • 设计与开发
  • 应用编程开发
  • Web设计与编程
• 关于我们
  • 关于本站

业界说开源数据库的现状

2016-07-03 17:45:06 阿炯

数据库作为业务的核心，是整个基础软件栈非常重要的一环。近几年的开源社区，新的思想和方案层出不穷，我将总结一下近几年一些主流的开源数据库方案，及其背后的设计思想以及适用场景。本人才疏学浅如有遗漏或者错误请见谅，本次分享聚焦于数据库即结构化数据存储 OLTP 及 NoSQL 领域，不会涉及 OLAP、对象存储以及分布式文件系统。

开源 RDBMS 与互联网的崛起

很长时间以来，关系型数据库一直是大公司的专利，市场被 Oracle / DB2 等企业数据库牢牢把持。但是随着互联网的崛起和开源社区的发展，上世纪九十年代 MySQL 1.0 的发布，标志着在关系型数据库的领域，社区终于有了可选择的方案。

MySQL

第一个介绍的单机 RDBMS 就是 MySQL。相信大多数朋友都已经对 MySQL 非常熟悉，基本上 MySQL 的成长史就是互联网的成长史。我接触的第一个 MySQL 版本是 MySQL 4.0，后来的 MySQL 5.5 更是经典——基本上所有的互联网公司都在使用。MySQL 也普及了「可插拔」引擎这一概念，即针对不同的业务场景选用不同的存储引擎，这也是 MySQL tuning 的一个重要方式。比如对于有事务需求的场景使用 InnoDB；对于并发读取的场景 MyISAM 可能比较合适；但是现在我推荐绝大多数情况还是使用 InnoDB，毕竟 MySQL 5.6 后它已经成为了官方的默认引擎。MySQL适用于几乎所有需要持久化结构化数据的场景， 大多数朋友应该都知道，我就不赘述了。

另外值得一提的是 MySQL 5.6 中引入了多线程复制和 GTID，使得故障恢复和主从的运维变得比较方便。另外，MySQL 5.7(目前处于 GA 版本) 发布了一个重大更新，主要是在读写性能和复制性能上有了长足的进步：在5.6版本中实现了 SCHEMA 级别的并行复制。不过意义不大，倒是 MariaDB 的多线程并行复制大放异彩，有不少人因为这个特性选择 MariaDB。另外，MySQL 5.7 MTS 支持两种模式，一种是和5.6一样，另一种则是基于 binlog group commit 实现的多线程复制，也就是MASTER上同时提交的 binlog 在 SLAVE 端也可以同时被 apply，实现并行复制。如果有单机数据库技术选型的朋友，基本上只需要考虑 MySQL 5.7 或者 MariaDB 就好了，而且 MySQL 5.6和5.7 由 Oracle 接手后，性能和稳定性都有了明显的提升。

PostgreSQL

PostgreSQL 的历史也非常悠久，其前身是 UCB 的 Ingres，主持这个项目的 Michael Stronebraker 于 2015 年获得图灵奖。后来该项目更名为 Post-Ingres，基于 BSD license 下开源。 1995 年几个 UCB 的学生为 Post-Ingres 开发了 SQL 的接口，正式发布了 PostgreSQL95，随后一步步在开源社区中成长起来。和 MySQL 一样，PostgreSQL 也是一个单机的关系型数据库，但是与 MySQL 方便用户过度扩展的 SQL 文法不一样的是，PostgreSQL 的 SQL 支持非常强大，不管是内置类型、JSON 支持、GIS 类型以及对于复杂查询的支持，PL/SQL 等都比 MySQL 强大得多，而且从代码质量上来看，PostgreSQL 的代码质量是优于 MySQL 的。另外，相对于MySQL 5.7以前的版本， PostgreSQL 的 SQL 优化器比 MySQL 强大很多，几乎所有稍微复杂的查询PostgreSQL 的表现都优于 MySQL。

从近几年的趋势上来看，PostgreSQL 的势头也很强劲，我认为 PostgreSQL 的不足之处在于没有 MySQL 那样强大的社区和群众基础。MySQL 经过那么多年的发展，积累了很多的运维工具和最佳实践，但是 PostgreSQL 作为后起之秀，拥有更优秀的设计和更丰富的功能。PostgreSQL 9 以后的版本也足够稳定，在做新项目技术选型的时候，是一个很好的选择。另外也有很多新的数据库项目是基于 PostgreSQL 源码的基础上进行二次开发，比如 Greenplum 等。

我认为，单机数据库的时代很快就会过去。摩尔定律带来的硬件红利总是有上限的，现代业务的数据规模、流量以及现代的数据科学对于数据库的要求，单机已经很难满足。比如，网卡磁盘 IO 和 CPU 总有瓶颈，线上敏感的业务系统可能还得承担 SPOF(单点故障) 的风险，主从复制模型在主挂掉时到底切还是不切？切了以后数据如何恢复？如果只是出现主从机器网络分区问题呢？甚至是监控环境出现网络分区问题呢？这些都是单机数据库面临的巨大挑战。所以我的观点是，无论单机性能多棒(很多令人乍舌的评测数据都是针对特定场景的优化，另外甚至有些都是本机不走网络，而大多数情况数据库出现的第一个瓶颈其实是网卡和并发连接……)，随着互联网的蓬勃发展和移动互联网的出现，数据库系统迎来了第一次分布式的洗礼。

分布式时代：NoSQL 的复兴和模型简化的力量

在介绍 NoSQL 之前，我想提两个公司，一个是 Google，另一个是 Amazon。

Google

Google 应该是第一个将分布式存储技术应用到大规模生产环境的公司，同时也是在分布式系统上积累最深的公司，可以说目前工业界的分布式系统的工程实践及思想大都来源于 Google。比如 2003 年的 GFS 开创了分布式文件系统，2006 年的 Bigtable 论文开创了分布式键值系统，直接催生的就是 Hadoop 的生态；至于 2012 年发表论文的 Spanner 和 F1更是一个指明未来关系型数据库发展方向的里程碑式的项目，这个我们后续会说。

Amazon

另一个公司是 Amazon。2007 年发表的 Dynamo的论文 尝试引入了最终一致性的概念， WRN 的模型及向量时钟的应用，同时将一致性 HASH、merkle tree 等当时一些很新潮的技术整合起来，正式标志着 NoSQL 的诞生。NoSQL——对后来业界的影响非常也是很大，包括后来的 Cassandra、RiakDB、Voldemort 等数据库都是基于 Dynamo 的设计发展起来的。

新思潮

另外这个时期(2006年前后持续至今)一个比较重要的思潮就是数据库(持久化)和缓存开始有明确的分离——我觉得这个趋势是从 memcached 开始的。随着业务的并发越来越高，对于低延迟的要求也越来越高；另外一个原因是随着内存越来越便宜，基于内存的存储方案渐渐开始普及。当然内存缓存方案也经历了一个从单机到分布式的过程，但是这个过程相比关系型数据库的进化要快得多。这是因为 NoSQL 的另外一个重要的标志——数据模型的变化——大多 NoSQL 都抛弃了关系模型，选择更简单的键值或者文档类型进行存储。数据结构和查询接口都相对简单，没有了 SQL 的包袱，实现的难度会降低很多。另外 NoSQL 的设计几乎都选择牺牲掉复杂 SQL 的支持及 ACID 事务换取弹性扩展能力，也是从当时互联网的实际情况出发：业务模型简单、爆发性增长带来的海量并发及数据总量爆炸、历史包袱小、工程师强悍，等等。其中最重要的还是业务模型相对简单。

嵌入式存储引擎

在开始介绍具体的开源的完整方案前，我想介绍一下嵌入式存储引擎们。

随着 NoSQL 的发展，不仅仅缓存和持久化存储开始细分，再往后的存储引擎也开始分化并走上前台。之前很难想象一个存储引擎独立于数据库直接对外提供服务，就像你不会直接拿着 InnoDB 或者 MyISAM甚至一个 B-tree 出来用一样(当然，bdb 这样鼎鼎大名的除外)。人们基于这些开源的存储引擎进行进一步的封装，比如加上网络协议层、加上复制机制等等，一步步构建出完整的风格各异的 NoSQL 产品。

这里我挑选几个比较著名的存储引擎介绍一下。

TC

我最早接触的是 Tokyo Cabinet(TC)。TC 相信很多人也都听说过，TC 是由日本最大的社交网站 Mixi 开发并开源的一个混合 Key-Value 存储引擎，其中包括 HASH Table 和 B+ Tree 的实现。但是这个引擎的一个缺陷是随着数据量的膨胀，性能的下降会非常明显，而且现在也基本不怎么维护了，所以入坑请慎重。与于 TC 配合使用的 Tokyo Tyrant(TT) 是一个网络库，为 TC 提供网络的接口使其变成一个数据库服务，TT + TC 应该是比较早的 NoSQL 的一个尝试。

LevelDB

在 2011 年，Google 开源了 Bigtable 的底层存储引擎： LevelDB。LevelDB 是一个使用 C++ 开发的嵌入式的 Key-Value 存储引擎，数据结构采用了 LSM-Tree，具体 LSM-Tree 的算法分析可以很容易在网上搜索到，我就不赘述了。其特点是，对于写入极其友好，LSM 的设计避免了大量的随机写入；对于特定的读也能达到不错的性能(热数据在内存中)；另外 LSM-Tree 和 B-tree 一样是支持有序 Scan 的；而且 LevelDB 是出自 Jeff Dean 之手，他的事迹做分布式系统的朋友一定都知道，不知道的可以去 Google 搜一下。

LevelDB 拥有极好的写性能，线程安全，BatcTCh Write 和 Snapshot 等特性，使其很容易的在上层构建 MVCC 系统或者事务模型，这对于数据库来说非常重要。另外值得一说的是，Facebook 维护了一个活跃的 LevelDB 的分支，名为 RocksDB。RocksDB 在 LevelDB 上做了很多的改进，比如多线程 Compactor、分层自定义压缩、多 MemTable 等。另外 RocksDB 对外暴露了很多 ConfigurationConfigration ，可以根据不同业务的形态进行调优；同时 Facebook 在内部正在用 RocksDB 来实现一个全新的 MySQL 存储引擎：MyRocks，值得关注。RocksDB 的社区响应速度很快也很友好，实际上 PingCAP 也是 RocksDB 的社区贡献者。我建议新的项目如果在 LevelDB 和 RocksDB 之间纠结的话，请果断选择 RocksDB。

B-tree 家族

当然，除了 LSM-Tree 外，B-tree 的家族也还是有很多不错的引擎。首先大多数传统的单机数据库的存储引擎都选择了B+Tree，B+Tree 对磁盘的读比较友好，第三方存储引擎比较著名的纯 B+Tree 实现是 LMDB。首先 LMDB 选择在内存映像文件 (mmap) 实现 B+Tree，而且同时使用了 Copy-On-Write 实现了 MVCC 实现并发事务无锁读的能力，对于高并发读的场景比较友好；同时因为使用的是 mmap 所以拥有跨进程读取的能力。不过因为我并没有在生产环境中使用过 LMDB ，所以并不能给出 LMDB 的一些缺陷，见谅。

混合引擎

还有一部分的存储引擎选择了多种引擎混合，比如最著名的应该是 WiredTiger，大概是2014年去年被 MongoDB 收购，现在成为了 MongoDB 的默认存储引擎。WiredTiger 内部有 LSM-Tree 和 B-tree 两种实现，对外提供相同的一套接口，根据业务的情况可自由选择。另外一些特殊数据结构的存储引擎在某些特殊场合下非常抢眼，比如极高压缩比 TokuDB，采用了名为分形树的数据结构，在维持一个可接受的读写压力的情况下，能拥有 10 倍以上的压缩率。

NoSQL

说完了几个比较著名的存储引擎，我们来讲讲比较著名的 NoSQL。在我的定义中，NoSQL 是 Not Only SQL 的缩写，所以可能包含的范围有内存数据库，持久化数据库等。总之就是和单机的关系型数据库不一样的结构化数据存储系统。我们先从缓存开始。

memcached

前面提到了 memcached 应该是第一个大规模在业界使用的缓存数据库，memcached 的实现极其简单，相当于将内存用作大的 HASH Table，只能在上面进行 get/set/ 计数器等操作，在此之上用 libevent 封装了一层网络层和文本协议(也有简单的二进制协议)，虽然支持一些 CAS 的操作，但是总体上来看，还是非常简单的。但是 memcached 的内存利用率并不太高，这是这个因为 memcached 为了避免频繁申请内存导致的内存碎片的问题，采用了自己实现的 slab allocator 的方式。即内存的分配都是一块一块的，最终存储在固定长度的 chunk 上，内存最小的分配单元是 chunk，另外 libevent 的性能也并没有优化到极致。但是这些缺点并不妨碍 memcached 成为当时的开源缓存事实标准。(另外，八卦一下，memcached 的作者 Brad Fitzpatrick 现在在 Google，大家如果用 Golang 的话，Go 的官方 HTTP 包就是这哥们写的，是个很高产的工程师)。

Redis

如果我没记错的话，在 2009 年前后，一位意大利的工程师 Antirez ，开源了 Redis。从此彻底颠覆了缓存的市场，到现在大多数缓存的业务都已用上 Redis，memcached 基本退出了历史舞台。Redis 最大的特点是拥有丰富的数据结构支持，不仅仅是简单的 Key-Value，还包括队列、集合、Sorted Set 等等，提供了非常丰富的表达力，而且 Redis 还提供 sub/pub 等超出数据库范畴的便捷功能，使得几乎一夜之间大家纷纷投入 Redis 的怀抱。

Twemproxy

但是随着 Redis 渐渐的普及，而且越用越狠，另外内存也越来越便宜，人们开始寻求扩展单机 Redis 的方案，最早的尝试是 twitter 开源的 twemproxy。twemproxy 是一个 Redis 中间件，基本只有最简单的数据路由功能，并没有动态的伸缩能力，但是还是受到了很多公司的追捧，因为确实没其他替代方案。随后的 Redis Cluster 也是难产了好久，时隔好几年，中间出了 7 个RC 版本，最后才发布；2014 年底，我们开源了 Codis，解决了 Redis 中间件的数据弹性伸缩问题，目前广泛应用于国内各大互联网公司中，这个在网上也有很多文章介绍，我也就不展开了。所以在缓存上面，开源社区现在倒是非常统一，就是 Redis 及其极其周边的扩展方案。

MongoDB

在 NoSQL 的大家庭中，MongoDB 其实是一个异类，大多 NoSQL 舍弃掉 SQL 是为了追求更极致的性能和可扩展能力，而 MongoDB 主动选择了文档作为对外的接口，非常像 JSON 的格式。Schema-less 的特性对于很多轻量级业务和快速变更的了互联网业务意义很大，而且 MongoDB 的易用性很好，基本做到了开箱即用，开发者不需要费心研究数据的表结构，只需要往里存就好了，这确实笼络了一大批开发者。

尽管 MongoDB 早期的版本各种不稳定，性能也不太好(早期的 Mongo 并没有存储引擎，直接使用了 mmap 文件)，集群模式还全是问题(比如至今还未解决的 Cluster 同步带宽占用过多的问题)，但是因为确实太方便了，在早期的项目快速迭代中，Mongo 是一个不错的选择。但是这也正是它的问题，我不止一次听到当项目变得庞大或者「严肃」的时候，团队最后还是回归了关系型数据库。Anyway，在 2014 年底 MongoDB 收购了 WiredTiger 后，在 2.8 版本中正式亮相，同时 3.0 版本后更是作为默认存储引擎提供，性能和稳定性有了非常大的提升。

但是从另一方面讲，Schema-less 到底对软件工程是好事还是坏事这个问题还是有待商榷。我个人是站在 Schema 这边的，不过在一些小项目或者需要快速开发的项目中使用 Mongo 确实能提升很多的开发效率，这是毋庸置疑的。

HBase

说到 NoSQL 不得不提的是 HBase，HBase 作为 Hadoop 旗下的重要产品，Google Bigtable 的正统开源实现，是不是有一种钦定的感觉 :)。提到 HBase 就不得不提一下 Bigtable， Bigtable 是 Google 内部广泛使用的分布式数据库，接口也不是简单的Key-Value，按照论文的说法叫：multi-dimensional sorted map，也就是 Value 是按照列划分的。Bigtable 构建在 GFS 之上，弥补了分布式文件系统对于海量、小的、结构化数据的插入、更新以及、随机读请求的缺陷。

HBase 就是这么一个系统的实现，底层依赖 HDFS。HBase 本身并不实际存储数据，持久化的日志和 SST file (HBase 也是 LSM-Tree 的结构) 直接存储在 HDFS 上，Region Server (RS) 维护了 MemTable 以提供快速的查询，写入都是写日志，后台进行 Compact，避免了直接随机读写 HDFS。数据通过 Region 在逻辑上进行分割，负载均衡通过调节各个 Region Server 负责的 Region 区间实现。当某 Region 太大时，这个 Region 会分裂，后续可能由不同的 RS 负责，但是前面提到了，HBase 本身并不存储数据，这里的 Region 仅是逻辑上的，数据还是以文件的形式存储在 HDFS 上，所以 HBase 并不关心 Replication 、水平扩展和数据的分布，统统交给 HDFS 解决。

和 Bigtable 一样，HBase 提供行级的一致性，严格来说在 CAP 理论中它是一个 CP 的系统，但遗憾的是并没有更进一步提供 ACID 的跨行事务。HBase 的好处就不用说了，显而易见，通过扩展 RS 可以几乎线性提升系统的吞吐，及 HDFS 本身就具有的水平扩展能力。

但是缺点仍然是有的。首先，Hadoop 的软件栈是 Java，JVM 的 GC Tuning 是一个非常烦人的事情，即使已经调得很好了，平均延迟也得几十毫秒；另外在架构设计上，HBase 本身并不存储数据，所以可能造成客户端请求的 RS 并不知道数据到底存在哪台 HDFS DataNode 上，凭空多了一次 RPC；第三，HBase 和 Bigtable 一样，并不支持跨行事务，在 Google 内部不停的有团队基于 Bigtable 来做分布式事务的支持，比如 MegaStore、Percolator。后来 Jeff Dean 有次接受采访也提到非常后悔没有在 Bigtable 中加入跨行事务，不过还好这个遗憾在 Spanner 中得到了弥补，这个一会儿说。总体来说，HBase 还是一个非常健壮且久经考验的系统，但是需要你有对于 Java 和 Hadoop 比较深入的了解后，才能玩转，这也是 Hadoop 生态的一个问题，易用性真是不是太好，而且社区演进速度相对缓慢，也是因为历史包袱过重的缘故吧。

Cassandra

提到 Cassandra (C*)，虽然也是 Dynamo 的开源实现，但就没有这种钦定的感觉了。C* 确实命途多舛，最早 2008 由 Facebook 开发并开源，早期的 C* 几乎全是 bug，Facebook 后来索性也不再维护转过头搞 HBase 去了，一个烂摊子直接丢给社区。还好 DataStax 把这个项目捡起来商业化，搞了两年，终于渐渐开始流行起来。

C* 不能简单的归纳为读快写慢，或者读慢写快，因为采用了 qourm 的模型，调整复制的副本数以及读的数量，可以达到不同的效果，对于一致性不是特别高的场景，可以选择只从一个节点读取数据，达到最高的读性能。另外 C* 并不依赖分布式文件系统，数据直接存储在磁盘上，各个存储节点之间自己维护复制关系，减少了一层 RPC 调用，延迟上对比 HBase 还是有一定优势的。

不过即使使用 qourm 的模型也并不代表 C* 是一个强一致的系统。C* 并不帮你解决冲突，即使你 W(写的副本数) + R(读请求的副本数) > N(节点总数)，C* 也没办法帮你决定哪些副本拥有更新的版本，因为每个数据的版本是一个 NTP 的时间戳或者客户端自行提供，每台机器可能都有误差，所以有可能并不准确，这也就是为什么 C* 是一个 AP 的系统。不过 C* 一个比较友好的地方是提供了 CQL，一个简单的 SQL 方言，比起 HBase 在易用性上有明显优势。

即使作为一个 AP 系统，C* 已经挺快了，但是人们追求更高性能的脚步还是不会停止。应该是今年年初，ScyllaDB 的发布就是典型的证明，ScyllaDB 是一个兼容 C* 的 NoSQL 数据库，不一样的是，ScyllaDB 完全用 C++ 开发，同时使用了类似 DPDK 这样的黑科技，具体我就不展开了，有兴趣可以到 Scylla 的官网去看看。BTW， 国内的蘑菇街第一时间使用了 ScyllaDB，同时在 Scylla 的官网上 share 了他们的方案，性能还是很不错的。

中间件与分库分表

NoSQL 就先介绍到这里，接下来我想说的是一些在基于单机关系型数据库之上的中间件和分库分表方案。

这些技术确实历史悠久，而且也是没有办法的选择。关系型数据库不比 Redis，并不是简单的写一个类似 Twemproxy 的中间件就搞定了。数据库的中间件需要考虑很多，比如解析 SQL，解析出 sharding key，然后根据 sharding key 分发请求，再合并；另外数据库有事务，在中间件这层还需要维护 Session 及事务状态，而且大多数方案并没有办法支持跨 shard 的事务。这就不可避免的导致了业务使用起来会比较麻烦，需要重写代码，而且会增加逻辑的复杂度，更别提动态的扩容缩容和自动的故障恢复了。在集群规模越来越大的情况下，运维和 DDL 的复杂度是指数级上升的。

中间件项目盘点

数据库中间件最早的项目大概是 MySQL Proxy，用于实现读写分离。后来国人在这个领域有过很多著名项目，比如阿里的 Cobar 和 TDDL(并未完全开源)；后来社区基于 Cobar 改进的 MyCAT、360 开源的 Atlas 等，都属于这一类中间件产品；在中间件这个方案上基本走到头的开源项目应该是 Youtube 的 Vitess。Vitess 基本上是一个集大成的中间件产品，内置了热数据缓存、水平动态分片、读写分离等等，但是代价也是整个项目非常复杂，另外文档也不太好。大概1年多以前，我们尝试搭建起完整的 Vitess 集群，但是并未成功，可见其复杂度。

另外一个值得一提的是 Postgres-XC 这个项目，Postgres-XC 的野心还是很大的，整体的架构有点像早期版本的 OceanBase，由一个中央节点来处理协调分布式事务 / 解决冲突，数据分散在各个存储节点上，应该是目前 PostgreSQL 社区最好的分布式扩展方案。其他的就不提了。未来在哪里？NewSQL！

一句话，NewSQL 就是未来。

2012 年 Google 在 OSDI 上发表了 Spanner 的论文，2013 年在 SIGMOD 发表了 F1 的论文。这两篇论文让业界第一次看到了关系模型和 NoSQL 的扩展性在超庞大集群规模上融合的可能性。在此之前，大家普遍认为这个是不可能的，即使是 Google 也经历了 Megastore 这样的失败。

Spanner综述

但是 Spanner 的创新之处在于通过硬件(GPS时钟+原子钟)来解决时钟同步的问题。在分布式系统里，时钟是最让人头痛的问题，刚才提到了 C* 为什么不是一个强 C 的系统，正是因为时钟的问题。而 Spanner 的厉害之处在于即使两个数据中心隔得非常远，不需要有通信(因为通信的代价太大，最快也就是光速)就能保证 TrueTime API的时钟误差在一个很小的范围内(10ms)。另外 Spanner 沿用了很多 Bigtable 的设计，比如 Tablet / Directory 等，同时在 Replica 这层使用 Paxos 复制，并未完全依赖底层的分布式文件系统。但是 Spanner 的设计底层仍然沿用了 Colossus，不过论文里也说是可以未来改进的点。

Google 的内部的数据库存储业务，大多是 3～5 副本，重要一点的 7 副本，遍布全球各大洲的数据中心，由于普遍使用了 Paxos，延迟是可以缩短到一个可以接受的范围(Google 的风格一向是追求吞吐的水平扩展而不是低延迟，从悲观锁的选择也能看得出来，因为跨数据中心复制是必选的，延迟不可能低，对于低延迟的场景，业务层自己解决或者依赖缓存)。另外由 Paxos 带来的 Auto-Failover 能力，更是能让整个集群即使数据中心瘫痪，业务层都是透明无感知的。另外 F1 构建在 Spanner 之上，对外提供了更丰富的 SQL 语法支持，F1 更像一个分布式 MPP SQL——F1 本身并不存储数据，而是将客户端的 SQL 翻译成类似 MapReduce 的任务，调用 Spanner 来完成请求。

其实 Spanner 和 F1 除了 TrueTime 整个系统并没有用什么全新的算法，其意义在于这是近些年来第一个 NewSQL 在生产环境中提供服务的分布式系统技术。

Spanner 和 F1 有以下几个重点：
1. 完整的 SQL 支持，ACID 事务；

2. 弹性伸缩能力；

3. 自动的故障转移和故障恢复，多机房异地灾备。

NewSQL 特性确实非常诱人，在 Google 内部，大量的业务已经从原来的 Bigtable 切换到 Spanner 之上。我相信未来几年，整个业界的趋势也是如此，就像当年的 Hadoop 一样，Google 的基础软件的技术趋势是走在社区前面的。

社区反应

Spanner 的论文发表之后，当然也有社区的追随者开始实现(比如我们 :D )，第一个团队是在纽约的 CockroachDB。CockroachDB 的团队的组成还是非常豪华的，早期团队由是 Google 的分布式文件系统 Colossus 团队的成员组成；技术上来说，Cockroach 的设计和 Spanner 很像，不一样的地方是没有选择 TrueTime而是 HLC (Hybrid logical clock)，也就是 NTP +逻辑时钟来代替 TrueTime 时间戳；另外 Cockroach 选用了 Raft 代替 Paxos 实现复制和自动容灾，底层存储依赖 RocksDB 实现，整个项目使用 Go 语言开发，对外接口选用 PostgreSQL 的 SQL 子集。

TiDB

目前从全球范围来看，另一个朝着 Spanner / F1 的开源实现这个目标上走的产品是 TiDB(终于谈到我们的产品了)。TiDB 本质上是一个更加正统的 Spanner 和 F1 实现，并不像 CockroachDB 那样选择将 SQL 和 Key-Value 融合，而是像 Spanner 和 F1 一样选择分离，这样分层的思想也是贯穿整个 TiDB 项目始终的。对于测试、滚动升级以及各层的复杂度控制会比较有优势；另外 TiDB 选择了 MySQL 协议和语法的兼容，MySQL 社区的 ORM 框架和运维工具，直接可以应用在 TiDB 上。

和 F1 一样，TiDB 是一个无状态的 MPP SQL Layer，整个系统的底层是依赖 TiKV 来提供分布式存储和分布式事务的支持。TiKV 的分布式事务模型采用的是 Google Percolator 的模型，但是在此之上做了很多优化。Percolator 的优点是去中心化程度非常高，整个集群不需要一个独立的事务管理模块，事务提交状态这些信息其实是均匀分散在系统的各个 Key 的 meta 中，整个模型唯一依赖的是一个授时服务器。在我们的系统上，极限情况这个授时服务器每秒能分配 400w 以上个单调递增的时间戳，大多数情况基本够用了(毕竟有 Google 量级的场景并不多见)；同时在 TiKV中，这个授时服务本身是高可用的，也不存在单点故障的问题。

TiKV 和 CockroachDB 一样也是选择了 Raft 作为整个数据库的基础；不一样的是，TiKV 整体采用 Rust 语言开发，作为一个没有 GC 和 Runtime 的语言，在性能上可以挖掘的潜力会更大。

关于未来

我觉得未来的数据库会有几个趋势，也是 TiDB 项目追求的目标：

●数据库会随着业务云化，未来一切的业务都会跑在云端，不管是私有云、公有云还是混合云，运维团队接触的可能再也不是真实的物理机，而是一个个隔离的容器或者「计算资源」。这对数据库也是一个挑战，因为数据库天生就是有状态的，数据总是要存储在物理的磁盘上，而移动数据的代价比移动容器的代价可能大很多。

●多租户技术会成为标配，一个大数据库承载一切的业务，数据在底层打通，上层通过权限，容器等技术进行隔离；但是数据的打通和扩展会变得异常简单，结合第一点提到的云化，业务层可以再也不用关心物理机的容量和拓扑，只需要认为底层是一个无穷大的数据库平台即可，不用再担心单机容量和负载均衡等问题。

●OLAP 和 OLTP 会进一步细分，底层存储也许会共享一套，但是SQL优化器这层的实现一定是千差万别的。对于用户而言，如果能使用同一套标准的语法和规则来进行数据的读写和分析，会有更好的体验。

●在未来分布式数据库系统上，主从日志同步这样落后的备份方式会被 Multi-Paxos / Raft 这样更强的分布式一致性算法替代，人工的数据库运维在管理大规模数据库集群时是不可能的，所有的故障恢复和高可用都会是高度自动化的。

Q&A

问：HANA等内存数据库怎么保证系统掉电而处理结果不丢？传统数据库也用缓存，可是HANA用的内存太大。

黄东旭：没用过 HANA，但是直观感觉这类内存数据库的可用性可能通过集中方式保证：●写入会先写 WAL；写入可能会通过主从或者paxos 之类的算法做同步和冗余复制还有 HANA 本身就是内存数据库，会尽可能把数据放到内存里，这样查询才能快呀。

问：对于传统创业公司如何弥补NoSQL的技术短板？快速的引入NoSQL提高效率？

黄东旭：选用 NoSQL 主要注意两点：1.做好业务的调研，估计并发量，数据量，数据的结构看看适不适合；2.对各种 NoSQL 擅长和不擅长的地方都尽可能了解。不要盲目相信关系型数据库，也不要盲目相信 NoSQL，没有银弹的。

问：有多个条件  比如年龄20到30或年龄35到40 并且加入购物车或下单  这种数据怎么存储？

黄东旭：购物车这种场景是典型的 OLTP 的场景，可以选用关系型数据库 MySQL PostgreSQL 什么的，如果对于扩展性的数据跨机房有要求的话，可以调研一下 NewSQL，比如我们的 TiDB。

问：多纬度查询应该选择哪种数据库？

黄东旭：多纬度查询可以说是一个 OLAP 的场景，可以选用 Greenplum 或者 Vertica 之类的分析性数据库。

问：想知道为什么需要这些开源的数据库，既然已经有了MySQL、DB2、Oracle这些成熟的数据库，成本考虑，还是传统数据库满足不了需求？

黄东旭：对，传统数据库的扩展性是有问题的，在海量并发和数据量的场景下很难支持业务。所以可以看到比较大的互联网公司基本都有自己的分布式数据库方案。

问：未来可能不再需要数据仓库吗？

黄东旭：大家可以想想数据仓库的定义，如果是还需要离线的从线上库倒腾数据到数据仓库上，这样很难做到实时查询，而且空间的利用率也低，我认为是目前并没有太好的方案的情况下的折衷……如果有一个更好的数据库能解决数据仓库的场景，为什么还需要一个独立的数据仓库？

关于作者

黄东旭，PingCAP 联合创始人兼 CTO。PingCAP 是一家专注于研发下一代的开源的分布式数据库的公司，主要作品是 TiDB/TiKV，是 Google Spanner 及 F1 的开源实现。


数据库发展历程与数据结构设计探析
--转于京东云开发者（Developer of JD Technology）的博客空间，感谢原作者。

1、数据库发展史

起初，数据的管理方式是文件系统，数据存储在文件中，数据管理和维护都由程序员完成。后来发展出树形结构和网状结构的数据库，但都存在着难以扩展和维护的问题。直到七十年代，关系数据库理论的提出，以表格形式组织数据，数据之间存在关联关系，具有了良好的结构化和规范化特性，成为主流数据库类型。先来看一张数据库发展史图鉴：


随之高并发大数据时代的来临，数据库按照各种应用场景进行了更细粒度的拆分和演进，数据库细分领域的典型代表：

类型	产品代表	适用场景
层次数据库（NDB）	IMS/IDMS	以树形结构组织数据，数据之间存在父子关系，查询速度快，但难以扩展和维护
关系型数据库（RDBMS）	Oracle/MySQL	事务的一致性需求场景
键值数据库（KVDB）	Redis/Memcached	针对高性能并发读写场景
文档数据库（DDB）	MongoDB/CouchDB	针对海量复杂数据访问场景
图数据库（GDB）	Neo4j	以点、边为基础存储单元，高效存储、查询图数据场景
时序数据库（TSDB）	InfluxDB/OpenTSDB	针对时序数据的持久化和多维度的聚合查询等场景
对象数据库（ODB）	Db4O	支持完整的面向对象(OO)概念和控制机制，目前使用场景较少
搜索引擎（SE）	ElasticSearch/Solr	适合于以搜索为主的业务场景
列数据库（WCDB）	HBase/ClickHouse	分布式存储的海量数据存储和查询场景
XML数据库（NXD）	MarkLogic	支持对XML格式文档进行存储和查询等操作场景
内容仓库（CDB）	Jackrabbit	大规模高性能的内容仓库

2、数据库名词概念

RDBS
1970 年的 6 月，IBM 公司的研究员埃德加・考特 （Edgar Frank Codd） 发表了那篇著名的《大型共享数据库数据的关系模型》（A Relational Model of Data for Large Shared Data Banks）的论文，拉开了关系型数据库（Relational DataBase Server）软件革命的序幕（之前是层次模型和网状模型数据库为主）。直到现在，关系型数据库在基础软件应用领域仍是最主要的数据存储方式之一。

关系型数据库建立在关系型数据模型的基础上，是借助于集合代数等数学概念和方法来处理数据的数据库。在关系型数据库中，实体以及实体间的联系均由单一的结构类型来表示，这种逻辑结构是一张二维表。关系型数据库以行和列的形式存储数据，这一系列的行和列被称为表，一组表组成了数据库。

NoSQL
NoSQL（Not Only SQL） 数据库也即非关系型数据库，它是在大数据的时代背景下产生的，它可以处理分布式、规模庞大、类型不确定、完整性没有保证的 “杂乱” 数据，这是传统的关系型数据库远远不能胜任的。NoSQL 数据库并没有一个统一的模型，是以牺牲事务机制和强一致性机制，来获取更好的分布式部署和横向扩展能力，使其在不同的应用场景下，对特定业务数据具有更强的处理性能。常用数据模型示例如下：

类型	产品代表	应用场景	数据模型	优缺点
键值数据库	Redis/Memcached	内容缓存，如会话，配置文件等； 频繁读写，拥有简单数据模型的应用；	键值对，通过散列表来实现	优点： 扩展性和灵活性好，性能高； 缺点： 数据无结构化，只能通过键来查询
列簇数据库	HBase/ClickHouse	分布式数据存储管理	以列簇存储，将同一列存在一起	优点： 简单，扩展性强，查询速度快 缺点： 功能局限，不支持事务的强一致性
文档数据库	MongoDB/CouchDB	Web应用，存储面向文档或半结构化数据	键值对，value是JSON结构文档	优点： 数据结构灵活 缺点： 缺乏统一查询语法
图形数据库	Neo4j/InfoGrid	社交网络，应用监控，推荐系统等专注构建关系图谱	图结构	优点： 支持复杂的图形算法 缺点： 复杂性高，支持数据规模有限

NewSQL
NewSQL 是一类新的关系型数据库， 是各种新的可扩展和高性能的数据库的简称。它不仅具有 NoSQL 数据库对海量数据的存储管理能力，同时还保留了传统数据库支持的 ACID 和 SQL 特性，典型代表有 TiDB 和 OceanBase。

OLTP
联机事务处理过程 (On-Line Transaction Processing)：也称为面向交易的处理过程，其基本特征是前台接收的用户数据可以立即传送到计算中心进行处理，并在很短的时间内给出处理结果，是对用户操作快速响应的方式之一。

OLAP
联机分析处理（On-Line Analytical Processing）是一种面向数据分析的处理过程，它使分析人员能够迅速、一致、交互地从各个方面观察信息，以达到深入理解数据的目的。它具有 FASMI (Fast Analysis of Shared Multidimensional Information)，即共享多维信息的快速分析的特征。

关于 OLTP 和 OLAP 的区别，借用一张表格对比如下：


HTAP

HTAP (Hybrid Transactional/Analytical Processing) 混合型数据库基于新的计算存储框架，能够同时支撑 OLTP 和 OLAP 场景，避免传统架构中大量数据交互造成的资源浪费和冲突。

3、领域数据库

列式数据库
传统的以行形式保存的数据主要满足 OLTP 应用，列形式保存的数据主要满足以查询为主的 OLAP 应用。在列式数据库中，数据按列存储，而每个列中的数据类型相同。这种存储方式使列式数据库能够更高效地处理大量的数据，特别是需要进行大规模的数据分析和处理时（如金融、医疗、电信、能源、物流等行业）。

两种存储结构的区别如下图：


列式数据库的主要优点：
• 更高的压缩比率：由于每个列中的数据类型相同，列式数据库可以使用更高效的压缩算法来压缩数据（压缩比可达到 5～20 倍），从而减少存储空间的使用。
• 更快的查询速度：列式数据库可以只读取需要的列，而不需要读取整行数据，从而加快查询速度。
• 更好的扩展性：列式数据库可以更容易地进行水平扩展，即增加更多的节点和服务器来处理更大规模的数据。
• 更好的数据分析支持：由于列式数据库可以处理大规模的数据，它可以支持更复杂的数据分析和处理操作，例如数据挖掘、机器学习等。

列式数据库的主要缺点：
• 更慢的写入速度：由于数据是按列存储，每次写入都需要写入整个列，而不是单个行，因此写入速度可能较慢。
• 更复杂的数据模型：由于数据是按列存储，数据模型可能比行式数据库更复杂，需要更多的设计和开发工作。

列式数据库的应用场景：
• 金融：金融行业的交易数据和市场数据，例如股票价格、外汇汇率、利率等。列式数据库可以更快速地处理这些数据，并且支持更复杂的数据分析和处理操作，例如风险管理、投资分析等。
• 医疗：医疗行业的病历数据、医疗图像和实验数据等。列式数据库可以更高效地存储和处理这些数据，并且支持更复杂的医学研究和分析操作。
• 电信：电信行业的用户数据和通信数据，例如电话记录、短信记录、网络流量等。列式数据库可以更快速地处理这些数据，并且支持更复杂的用户行为分析和网络优化操作。
• 能源：能源行业的传感器数据、监测数据和生产数据等。列式数据库可以更高效地存储和处理这些数据，并且支持更复杂的能源管理和控制操作。
• 物流：物流行业的运输数据、库存数据和订单数据等。列式数据库可以更快速地处理这些数据，并且支持更复杂的物流管理和优化操作。

总之，列式数据库是一种高效处理大规模数据的数据库管理系统，但需要权衡写入速度、数据模型复杂度和成本等因素。随着传统关系型数据库与新兴的分布式数据库不断的发展，列式存储与行式存储会不断融合，数据库系统呈现双模式数据存放方式。

时序数据库
时序数据库全称为时间序列数据库 (Time Series Database)，用于存储和管理时间序列数据的专业化数据库，是优化用于摄取、处理和存储时间戳数据的数据库。其跟常规的关系数据库 SQL 相比，最大的区别在于：时序数据库是以时间为索引的规律性时间间隔记录的数据库。其在物联网和互联网应用程序监控（APM）等场景应用比较多，以监控数据采集来举例，如果数据监控数据采集时间间隔是 1s，那一个监控项每天会产生 86400 个数据点，若有 10000 个监控项，则一天就会产生 864000000 个数据点。在物联网场景下，这个数字会更大，整个数据的规模，是 TB 甚至是 PB 级的。

时序数据库发展史：


当下最常见的 Kubernetes 容器管理系统中，通常会搭配普罗米修斯（Prometheus）进行监控，Prometheus 就是一套开源的监控 & 报警 & 时间序列数据库的组合。

图数据库
图数据库（Graph Database）是基于图论实现的一种新型 NoSQL 数据库。它的数据存储结构和数据的查询方式都是以图论为基础的。图论中图的基本元素为节点和边，在图数据库中对应的就是节点和关系。它在反欺诈多维关联分析场景，社交网络图谱，企业关系图谱等场景中可以做一些非常复杂的关系查询。这是由于图数据结构表现的是实体联系本身，它表现了现实世界中事物联系的本质，它的联系在节点创建时就已经建立，所以在查询中能以快捷的路径返回关联数据，从而表现出非常高效的查询性能。

目前市面上较为流行的图数据库产品有以下几种：


与传统的关系数据库相比，图数据库具有以下优点：
1. 更快的查询速度：图数据库可以快速遍历图数据，找到节点之间的关联和路径，因此查询速度更快。
2. 更好的扩展性：图数据库可以轻松地扩展到大规模的数据集，因为它们可以分布式存储和处理数据。
3. 更好的数据可视化：图数据库可以将数据可视化为图形，使用户更容易理解和分析数据。
4. 更好的数据一致性：图数据库可以确保数据的一致性，因为它们可以在节点和边之间建立强制性的关系。

4、数据结构设计

前面简单介绍了数据库相关的基础知识，下面再介绍几种我们常见的数据结构设计相关的应用实践：拉链表，位运算和环形队列。

4.1 拉链表
拉链表是一种数据仓库中常用的数据模型，用于记录维度数据的变化历史。我们以一个人员变动的场景举例，假设有一个员工信息表，其中包含了员工的姓名、工号、职位、部门、入职时间等信息。如果需要记录员工的变动情况，就可以使用拉链表来实现。

首先，在员工信息表的基础上新增两个字段：生效时间和失效时间。当员工信息发生变动时，不再新增一条记录，而是修改原有记录的失效时间，同时新增一条新的记录。如下表所示：

姓名	工号	职位	部门	入职时间	生效时间	失效时间
张三	001	经理	技术	2010-01-01	2010-01-01	2012-12-31
张三	001	总监	技术	2013-01-01	2013-01-01	2015-12-31
张三	001	总经理	技术	2016-01-01	2016-01-01	9999-12-31

这里的生效时间指的是该记录生效的时间，失效时间指的是该记录失效的时间。例如，张三最初是技术部经理，生效时间为入职时间，失效时间为 2012 年底，之后晋升为技术部总监，生效时间为 2013 年初，失效时间为 2015 年底，最后又晋升为技术部总经理，生效时间为 2016 年初，失效时间为 9999 年底。

通过这种方式，可以记录员工变动的历史信息，并能够方便地查询某个时间点的员工信息。例如，如果需要查询张三在 2014 年的职位和部门信息，只需查询生效时间小于 2014 年且失效时间大于 2014 年的记录即可。

拉链表通常包括以下几个字段：
1.主键：唯一标识每个记录的字段，通常是一个或多个列的组合。
2.生效时间：记录的生效时间，即该记录开始生效的时间。
3.失效时间：记录的失效时间，即该记录失效的时间。
4.版本号：记录的版本号，用于标识该记录的版本。
5.其他维度属性：记录的其他维度属性，如客户名、产品名、员工名等。
当一个记录的维度属性发生变化时，不再新增一条记录，而是修改原有记录的失效时间，同时新增一条新的记录。新记录的生效时间为变化的时间，失效时间为 9999 年底。这样就能够记录每个维度属性的历史变化信息，同时保证查询时能够正确获取某个时间点的维度属性信息。

拉链表与传统的流水表相比，它们的主要区别在于：
1. 数据结构不同：流水表是一张只有新增和更新操作的表，每次更新都会新增一条记录，记录中包含了所有的历史信息。而拉链表则是一张有新增、更新和删除操作的表，每个记录都有一个生效时间段和失效时间段，记录的历史信息通过时间段的变化来体现。
2. 查询方式不同：流水表的查询方式是基于时间点的查询，即查询某个时间点的记录信息。而拉链表的查询方式是基于时间段的查询，即查询某个时间段内的记录信息。
3. 存储空间不同：由于流水表需要记录所有历史信息，所以存储空间相对较大。而拉链表只记录生效时间段和失效时间段，所以存储空间相对较小。
4. 数据更新方式不同：流水表只有新增和更新操作，每次更新都会新增一条记录，不会对原有记录进行修改。而拉链表有新增、更新和删除操作，每次更新会修改原有记录的失效时间，同时新增一条新的记录。

4.2 巧用位运算
借助于计算机位运算的特性，可以巧妙的解决某些特定问题，使实现更加优雅，节省存储空间的同时，也可以提高运行效率，典型应用场景：压缩存储、位图索引、数据加密、图形处理和状态判断等，下面介绍几个典型案例。

4.2.1 位运算
• 使用位运算实现开关和多选项叠加（资源权限）等应用场景。一个 int 类型有 32 个位，理论上可以表示 32 个开关状态或业务选项；以用户每个月的签到场景举例：用一个 int 字段来表示用户一个月的签到情况，0 表示未签到，1 表示签到。想知道某一天是否签到，则只需要判断对应的比特位上是否为 1。计算一个月累计签到了多少次，只需要统计有多少个比特位为 1 就可以了。这种设计巧妙的数据存储结构在后面的位图（BitMap）中，还会进行更为详细的介绍。


• 使用位运算实现业务优先级计算：
public abstract class PriorityManager {
    // 定义业务优先级常量
    public static final int PRIORITY_LOW = 1;     // 二进制：001
    public static final int PRIORITY_NORMAL = 2;  // 二进制：010
    public static final int PRIORITY_HIGH = 4;    // 二进制：100
    
    // 定义用户权限常量
    public static final int PERMISSION_READ = 1;  // 二进制：001
    public static final int PERMISSION_WRITE = 2; // 二进制：010
    public static final int PERMISSION_DELETE = 4;// 二进制：100
    
    // 定义用户权限和业务优先级的组合值
    public static final int PERMISSION_LOW_PRIORITY = PRIORITY_LOW | PERMISSION_READ;     // 二进制：001 | 001 = 001
    public static final int PERMISSION_NORMAL_PRIORITY = PRIORITY_NORMAL | PERMISSION_READ | PERMISSION_WRITE;  // 二进制：010 | 001 | 010 = 011
    public static final int PERMISSION_HIGH_PRIORITY = PRIORITY_HIGH | PERMISSION_READ | PERMISSION_WRITE | PERMISSION_DELETE;  // 二进制：100 | 001 | 010 | 100 = 111
    
    // 判断用户权限是否满足业务优先级要求
    public static boolean checkPermission(int permission, int priority) {
        return (permission & priority) == priority;
    }
}
• 其它使用位运算的典型场景：HashMap 中的队列长度的设计和线程池 ThreadPoolExcutor 中使用 AtomicInteger 字段 ctl，存储当前线程池状态和线程数量（高 3 位表示当前线程的状态，低 29 位表示线程的数量）。

4.2.2 BitMap
位图（BitMap）是一种常用的数据结构，在索引，数据压缩等方面有广泛应用。基本思想就是用一个 bit 位来标记某个元素对应的 Value，而 Key 即是该元素。由于采用了 Bit 为单位来存储数据，因此可以大大节省存储空间，是少有的既能保证存储空间又能保证查找速度的数据结构（而不必空间换时间）。

举个例子，假设有这样一个需求：在 20 亿个随机整数中找出某个数 m 是否存在其中，并假设 32 位操作系统，4G 内存，在 Java 中，int 占 4 字节，1 字节 = 8 位（1 byte = 8 bit）。

• 如果每个数字用 int 存储，那就是 20 亿个 int，因而占用的空间约为 (2000000000*4/1024/1024/1024)≈7.45G
• 如果按位存储就不一样了，20 亿个数就是 20 亿位，占用空间约为 (2000000000/8/1024/1024/1024)≈0.233G
存储空间可以压缩节省 31 倍！那么它是如何通过二进制位实现数字标记的呢？ 其原理是用每个二进制位（下标）表示一个真实数字，0 表示不存在，1 表示存在，这样我们可以很容易表示 {1,2,4,6} 这几个数：


计算机内存分配的最小单位是字节，也就是 8 位，那如果要表示 {12,13,15} 怎么办呢？可以另申请一个字节 b [1]：


通过一个二维数组来实现位数叠加，1 个 int 占 32 位，那么我们只需要申请一个 int 数组长度为 int index [1+N/32] 即可存储，其中 N 表示要存储的这些数中的最大值：
index [0]：可以表示 0~31
index [1]：可以表示 32~63
index [2]：可以表示 64~95

以此类推... 如此一来，给定任意整数 M，那么 M/32 就得到下标，M%32 就知道它在此下标的哪个位置。

BitMap 数据结构通常用于以下场景：
1. 压缩存储大量布尔值：BitMap 可以有效地压缩大量的布尔值，从而减少内存的使用；
2. 快速判断一个元素是否存在：BitMap 可以快速地判断一个元素是否存在，只需要查找对应的位即可；
3. 去重：BitMap 可以用于去重操作，将元素作为索引，将对应的位设置为 1，重复元素只会对应同一个位，从而实现去重；
4. 排序：BitMap 可以用于排序，将元素作为索引，将对应的位设置为 1，然后按照索引顺序遍历位数组，即可得到有序的元素序列；
5. ElasticSearch 和 Solr 等搜索引擎中，在设计搜索剪枝时，需要保存已经搜索过的历史信息，可以使用位图减小历史信息数据所占空间；

4.2.3 布隆过滤器
位图（Bitmap）这种数据存储结构，如果数据量大到一定程度，比如 64bit 类型的数据，简单算一下存储空间就知道，海量硬件资源要求，已经不太现实了：


所以另一个著名的工业实现 - 布隆过滤器（Bloom Filter）出现了。如果说 BitMap 对于每一个可能的整型值，通过直接寻址的方式进行映射，相当于使用了一个哈希函数，那布隆过滤器就是引入了 k (k> 1 ) 个相互独立的哈希函数，保证在给定的空间和误判率情况下，完成元素判重的过程。下图中是 k = 3 时的布隆过滤器：


布隆过滤器的内部依赖于哈希算法，当检测某一条数据是否见过时，有一定概率出现假阳性（False Positive），但一定不会出现假阴性（False Negative）。也就是说，当布隆过滤器认为一条数据出现过，那么该条数据很可能出现过；但如果布隆过滤器认为一条数据没出现过，那么该条数据一定没出现过。布隆过滤器通过引入一定错误率，使得海量数据判重在可以接受的内存代价中得以实现。

上图中，x,y,z 经由哈希函数映射将各自在 Bitmap 中的 3 个位置置为 1，当 w 出现时，仅当 3 个标志位都为 1 时，才表示 w 在集合中。图中所示的情况，布隆过滤器将判定 w 不在集合中。

常见实现
• Java 中 Guava 工具包中实现；
• Redis 4.0 开始以插件形式提供布隆过滤器功能；

适用场景
• 网页爬虫对 URL 的去重，避免爬去相同的 URL 地址，比如 Chrome 浏览器就是使用了一个布隆过滤器识别恶意链接；
• 垃圾邮件过滤，从数十亿个垃圾邮件列表中判断某邮箱是否是杀垃圾邮箱；
• 解决数据库缓存击穿，黑客攻击服务器时，会构建大量不存在于缓存中的 key 向服务器发起请求，在数据量足够大的时候，频繁的数据库查询会导致挂机；
• 谷歌 Bigtable、Apache HBase、Apache Cassandra 和 PostgreSQL 使用布隆过滤器来减少对不存在的行或列的磁盘查找；
• 秒杀系统，查看用户是否重复购买.

4.2.4 小结
• 位运算有着执行速度快，占用空间小，代码实现简洁等优点，往往能起到四两拨千斤的效果。同样也有着代码可读性差，使用范围和可维护性受限等不足；
• 在 BitMap 中，占用空间大小还与实际应用场景有关，这种结构无法容忍误判，只能判断一个元素是否存在，如果数据离散度过高，空间利用率反而更低；
• 布隆过滤器则有着空间利用率高，可以容忍一定的误判率的优点。与 BitMap 相比，也存在着无法删除元素，误判率无法达到 0 等不足。

4.3 环形队列
环形队列是一种用于表示一个固定尺寸、头尾相连的数据结构，很适合缓存数据流。在通信开发（Socket，TCP/IP，RPC 开发），在内核的进程间通信（IPC），视频音频播放等各种场景中，都有其身影。日常开发过程中使用的 Dubbo、Netty、Akka、Quartz、ZooKeeper 、Kafka 等各种中间件，也都有环形队列的思想。下面介绍两种常用的环形数据结构：Hash 环和时间轮。

4.3.1 一致性 Hash 环
先来看一下，典型 Hash 算法结构如下：


以上图 Hash 策略为例，当节点数 N 发生变化的时候 之前所有的 hash 映射几乎全部失效，如果集群是无状态的服务，倒是没什么事情，但是如果是分布式缓存这种场景，就会导致比较严重的问题。比如 Key1 原本是路由到 Node1 上，命中缓存的 Value1 数据。但是当 N 节点变化后，Key1 可能就路由到了 Node2 节点，这就产生了缓存数据无法命中的问题。而无论是机器故障还是缓存扩容，都会导致节点数的变化。

如何解决上面场景的问题呢？就是接下来介绍的一致性 Hash 算法。

一致性哈希将整个哈希值空间组织成一个虚拟的圆环，假设某哈希函数 H 的值空间为 0-2^32-1（即哈希值是一个 32 位无符号整型），所有的输入值都被映射到 0-2^32-1 之间，组成一个圆环。整个哈希空间环如下：


路由数据的过程如下：将数据 key 使用相同的函数 Hash 计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针 “行走”，遇到的第一个节点就是其应该定位到的服务器。如果某个节点的服务器故障，其影响范围也不再是所有集群，而是限定在故障节点与其上游节点的部分区域。

当某个节点宕机后，原本属于它的请求都会被重新 hash 映射到下游节点，会突然造成下游节点压力过大有可能也会造成下游节点宕机，从而容易形成雪崩，为此引入了虚拟节点来解决这个问题。

根据 Node 节点生成很多的虚拟节点分布在圆环上，，一个真实节点映射对应多个虚拟节点。这样当某个节点挂了后原本属于它的请求，会被均衡的分布到其他节点上降低了产生雪崩的情况，也解决了物理节点数少，导致请求分布不均的问题。

带有虚拟节点的 Hash 环：


一致性 Hash 算法由于均衡性，持久性的映射特点被广泛应用于负载均衡领域，比如 nginx、dubbo 等内部都有一致性 hash 的实现。

4.3.2 时间轮分片
时间轮（TimeWheel）是一种实现延迟功能（定时器）的精妙的算法，可以实现高效的延时队列。以 Kafka 中的时间轮实现方案为例，它是一个存储定时任务的环形队列，底层采用数组实现，数组中的每个元素可以存放一个定时任务列表（TimerTaskList）。TimerTaskList 是一个环形的双向链表，链表中的每一项表示的都是定时任务项（TimerTaskEntry），其中封装了真正的定时任务 TimerTask。


通过上图可以发现，时间轮算法不再任务队列作为数据结构，轮询线程不再负责遍历所有任务，而是仅仅遍历时间刻度。时间轮算法好比指针不断在时钟上旋转、遍历，如果一个发现某一时刻上有任务（任务队列），那么就会将任务队列上的所有任务都执行一遍。

假设相邻 bucket 到期时间的间隔为 bucket=1s，从 0s 开始计时，1s 后到期的定时任务挂在 bucket=1 下，2s 后到期的定时任务挂在 bucket=2 下，当检查到时间过去了 1s 时，bucket=1 下所有节点执行超时动作，当时间到了 2s 时，bucket=2 下所有节点执行超时动作。时间轮使用一个表盘指针（pointer），用来表示时间轮当前指针跳动的次数，可以用 tickDuration * (pointer + 1) 来表示下一次到期的任务，需要处理此 bucket 所对应的 TimeWheel 中的所有任务。

时间轮的优点

1. 任务的添加与移除，都是 O (1) 级的复杂度；
2. 只需要有一个线程去推进时间轮，不会占用大量的资源；
3. 与其他任务调度模式相比，CPU 的负载和资源浪费减少

适用场景

时间轮是为解决高效调度任务而产生的调度模型。在周期性定时任务，延时任务，通知任务等场景都可以发挥效用。

5、总结

本文针对数据存储相关名词概念进行了解释，重点介绍了数据库技术的发展史。为了丰富文章的可读性以及实用性，又从数据结构设计层面进行了部分技术实战能力的外延扩展，阐述了拉链表，位运算，环形队列等相关数据结构在软件开发领域的应用，希望本文给你带来收获。