关于架构:架构师日记从数据库发展历程到数据结构设计探析-京东云技术团队

作者：京东批发 刘慧卿

一 数据库发展史

起初，数据的治理形式是文件系统，数据存储在文件中，数据管理和保护都由程序员实现。起初倒退出树形构造和网状结构的数据库，但都存在着难以扩大和保护的问题。直到七十年代，关系数据库实践的提出，以表格模式组织数据，数据之间存在关联关系，具备了良好的结构化和规范化个性，成为支流数据库类型。

先来看一张数据库发展史图鉴：

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

二 数据库名词概念

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 数据库并没有一个对立的模型，是以就义事务机制和强一致性机制，来获取更好的分布式部署和横向扩大能力，使其在不同的利用场景下，对特定业务数据具备更强的解决性能。罕用数据模型示例如下：

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 场景，防止传统架构中大量数据交互造成的资源节约和抵触。

三 畛域数据库

列式数据库

传统的以行模式保留的数据次要满足 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.1 拉链表

拉链表是一种数据仓库中罕用的数据模型，用于记录维度数据的变动历史。咱们以一个人员变动的场景举例，假如有一个员工信息表，其中蕴含了员工的姓名、工号、职位、部门、入职工夫等信息。如果须要记录员工的变动状况，就能够应用拉链表来实现。

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

这里的失效工夫指的是该记录失效的工夫，生效工夫指的是该记录生效的工夫。例如，张三最后是技术部经理，失效工夫为入职工夫，生效工夫为 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.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 的负载和资源节约缩小；

实用场景

工夫轮是为解决高效调度工作而产生的调度模型。在周期性定时工作，延时工作，告诉工作等场景都能够施展效用。

五 总结

本文针对数据存储相干名词概念进行了解释，重点介绍了数据库技术的发展史。为了丰盛文章的可读性以及实用性，又从数据结构设计层面进行了局部技术实战能力的内涵扩大，论述了拉链表，位运算，环形队列等相干数据结构在软件开发畛域的利用，心愿本文给你带来播种。

注：本文个别图片来自互联网