阅读全文

⭐⭐⭐ Spring Boot 项目实战	⭐⭐⭐ Spring Cloud 项目实战
《Dubbo 实现原理与源码解析 —— 精品合集》	《Netty 实现原理与源码解析 —— 精品合集》
《Spring 实现原理与源码解析 —— 精品合集》	《MyBatis 实现原理与源码解析 —— 精品合集》
《Spring MVC 实现原理与源码解析 —— 精品合集》	《数据库实体设计合集》
《Spring Boot 实现原理与源码解析 —— 精品合集》	《Java 面试题 + Java 学习指南》

摘要: 原创出处 zhuanlan.zhihu.com/p/369581725 「satanson」欢迎转载，保留摘要，谢谢！

• 动机
• 分布式存储
• 1. 复制
• 2. 存储引擎
• 3. 事务
• 4. 分析
• 5. 多核
• 6. 计算
• 7. 编译

---

🙂🙂🙂关注**微信公众号：【芋道源码】**有福利：

1. RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表
2. RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址
3. 您对于源码的疑问每条留言都将得到认真回复。甚至不知道如何读源码也可以请教噢。
4. 新的源码解析文章实时收到通知。每周更新一篇左右。
5. 认真的源码交流微信群。

---

动机

为什么是7方面的问题？虽说7面只比6面多了一面，又比8面少了1面；然而并非刻意为之。存储领域内的很多知识，可以归结于7个方面： 复制、存储引擎、事务、分析、多核、计算和编译。

分布式存储

什么是分布式存储呢？如果一个存储系统，不管是对象、块、文件、kv、log、olap、oltp，只要对所管理的数据做了Partitioning&Replication，不管姿势对不对，其实都可以归纳于分布式存储。分布式存储就是：Partitioning以多机scale，Replication以灾备容错。

1. 复制

复制是解决可用性，可扩展性和高性能的关键。为了灾备，数据需要冗余存储；为了高可用，服务需要hot standby。缺乏灾备的系统难以在生产环境使用。元数据和数据的维护均离不开复制，复制可转移而不可消除。复制引出了多副本一致性问题，而一致性保证需要考虑各种软件和硬件故障，以及误操作。共识算法和复制日志是解决复制问题的核心，具体涉及：

1. 故障检查，租约协议；
2. 选主算法，primary uniqueness invariant，网络隔离，脑裂，双主，拜占庭故障，failfast/failstop，failover；
3. 日志复制，RSM；
4. membership change，或者config change，主机上下线管理，扩缩容；
5. 数据复制，data rebalancing，data recovery；
6. 副本放置逻辑和副本路由逻辑；
7. primary和backup之间如何fence？
8. 外部一致性，线性一致性；
9. pipeline，fanout，primary-backup，quorum-based，gossip；
10. 分布式日志，active-standby架构，active-active架构；
11. ……

2. 存储引擎

此处的引擎是指本地的持久化存储引擎，持久化存储引擎要考虑CPU和memory系统和持久化设备之间的速度和带宽差异，可以总结为1-3-5。

1-3-5

• 1是指fsync的调用，以及和fsync地位等同的函数的调用。调用次数，调用频率，在多少数据上施加调用等。设备的带宽和利用率是否合理，fsync的调用怎么均摊到更多io次数和吞吐之上呢？
• 3是指读/写/空间的放大。怎么tradeoff，牺牲一个保住其他两个呢？
• 5是指WAL的5个LSN，分别为prepare point，commit point，apply point，checkpoint，prune point。

• • 处于prepare point和commit point之间的数据需要group commit；
• 处于apply point和commit point点之间的提交数据需要apply到内存的数据结构之上以后对读可见；
• 内存数据结构需要以一定的调度策略存档于持久化设备, checkpoint就是存档点；
• recover from crash需要从最近的checkpoint点恢复到commit point；
• 而一段checkpoint完成，则截止该checkpoint的日志可以截断，因此存在一个不大于checkpoint的点，是为prune point，截止改点的日志和老的on-disk镜像可以安全删除。
• 因此这5个点始终保持一条约束：它们之间存在全序关系。

数据结构和算法

内存和磁盘数据的管理，需要用到丰富的数据结构和算法。此外解压缩和编解码算法用于降低数据的size，也很有意思。

3. 事务

事务是指ACID，很多存储系统，其实可以用事务做baseline进行分析，看这个系统在原子性，一致性，隔离性和持久化四个方面的设计究竟走多远。其实事务反应了正确性和并发性的折中。作为事务的使用方，理论上（实践上未必），并发访问存储系统时，不需要担心结果不正确的问题。假如这种担忧存在，一定是事务处理上，牺牲了某些正确性，偏向了并发性，将错误处理和选择权交给了使用方处理，使用方需要额外花费心智在客户代码中插入fence代码和做容错处理。

存储引擎部分，其实已经或多或少地涉及到了事务处理的提交协议，提交协议主要解决事务的A和D。事务处理的核心是并发控制（concurrency control）协议。并发控制主要解决这样的问题：

• 两个并发事务冲突（读写，写读，写写），应该怎么处理呢？加锁等待还是检测到冲突主动夭折呢？
• 已经提交的事务对数据库的影响，怎么对当前outstanding事务的读操作可见呢？

这两个问题本质是隔离性和一致性，冲突事务加以同步，前置的提交事务对后置outstanding事务可见。

理想的正确性是这样子的：所有的事务，不管是否存在冲突，都一个一个串行执行，时间上没有任何重叠。理想的并发性是这样子的：所有事务都没有冲突，可以以最佳的并行度同时执行。但现实是冲突始终存在，解决冲突，意味着在并行执行的某个环节插入了同步点，需要判断和仲裁是否有冲突。

冲突等待，是lock-based CC协议；冲突夭折重试，是timestamp ordering CC协议。前者就是所谓的悲观事务，后者则为乐观事务。事务处理在Jim Gray的书中和知名教材里其实已经讲得很清楚了。这里只提一下乐观事务的冲突检查的直观性的简单的理解：两个事务存在两种定序方法，一种是由TSO分配的时间戳确定的顺序，一种是由数据依赖（WAW，RAW，WAR）确定顺序。如果这两种顺序破坏事务之间的偏序关系，那么这两个事务必然冲突，可以选择让一个事务夭折并且重试。

定序是一个比较关键的问题，比如乐观事务的begin和commit的时间戳分配，悲观事务的基于时间戳的死锁预防也会用到时间戳的分配。

存储系统自身做了partitioning之后，单个partition的事务处理可下沉于本地存储引擎，然而如果一个操作涉及对多个partition的修改，则需要考虑跨partition的事务处理能力。其实分布式事务并没有一个清晰的定义，但蕴含了“跨（across）”的意思，不管是提交协议还是CC协议，都依赖于分布式存储系统的实现或者单机事务的实现。虽然有很多文献中反复用到2PC和3PC，但有时候是指提交协议，有时候是指CC协议，有时候是指提交协议和CC协议的混合体。

事务给存储系统的行为做出了明确的定义和保证，从事务的角度可推测系统的实现，比如加锁的粒度，多版本的管理，全局同步点，怎么处理write-too-late问题。

4. 分析

分析处理涵盖的东西太多了。从一个角度看，是怎么实现SQL语言；从另一个角度看，是怎么实现一个分布式系统由SQL驱动起来工作。一条文本的SQL语句，历经分词，语法分析，访问catalog和语意分析，关系代数的等价变化，形成逻辑的查询计划，然后根据数据的分布，算子自身特点和计算资源状况，生成物理执行计划。

一条SQL可以对应多个逻辑执行计划，一个逻辑执行计划，对应多个物理执行计划。比如join的顺序，join的算子的实现。谓词过滤时谓词的顺序，谓词是否下沉。一个关系代数的算子，有多种的不同实现算法，而多个关系算子，不同的计算顺序也会有不同的执行效率。根据先验知识，使用启发式的策略；或者利用数据分布的统计信息，采用某种cost估算模型；又或者根据已有执行经验，自适应地调整到最优或者次优的执行计划。

在计算层，通过三大优化策略parallelism，pipelining和batch加速处理。比如数据经过parititioning形成多个partition，放置于多机上，采用MPP的方式，做多机的并行处理。计算的过程可以看成是把关系作为输入，流经执行树的叶子节点，汇聚于根节点，每个节点的对应算子的具体算法实现所输入数据进行处理后输出。从计算模型的角度看，有这么几种情况：

• tuple-at-a-time：采用了迭代器的模式，当前迭代器执行get_next时，调用child算子对应迭代器的get_next获取计算所需的输入tuple，然后执行一段计算代码，产生一个输出tuple，发射parent算子。
• full materialization：每个算子接收到全部的输入数据，计算出输出结果，交给下一个算子计算。这种方式类似于批处理。
• vectorized execution：数据在内存中按列存储，以数组表示。选择数组的大小，让其可以在L1 data cache中装得下，然后执行树的每个算子执行tight for-loop按数组处理数据。这样即避免了full materialization过多的资源索取，又能避免tuple-at-a-time的处理单个tuple的overhead，同时对cache更加友好，减少spurious invalidation，提升speculative cache missing的产生。同时简单tight for-loop，编译器能更好点编译成高效执行指令，同时也能更好地填充CPU的指令流水，充分利用CPU的multiple issue的功能加速简单指令的处理。

在存储层，数据采用列式存储，可获得很好的编码效率，降低读放大和空间放大，访问持久化存储的带宽被高效利用，CPU和Memory的带宽增速相对于持久化存储带宽增速表现出了显著的差异，使用CPU的计算交换磁盘带宽，提升了数据的处理能力。

列存，向量化执行引擎，MPP是现代分析性数据库的关键技术。

5. 多核

从编程实现的角度看，多核scale，CC协议，共识算法是计算机中比较有挑战，并且是纯自然的问题。即便技术上不深入接触数据库，也对这三个问题相当地痴迷，被数据库技术的吸引加入这个领域，或多或少和这三个问题相关。

为什么多核如此重要呢？

假设摩尔定律，没有功率墙的限制，世界会怎样呢？显然我们不需要修改老代码，只要增加单核晶体管数量，老代码自然而然会提升。我们撞到了功率墙后，发现需要增加核数以提升计算速度。现在问题来了，我们的代码已经写成了多线程执行，那么随着核数增长，修改worker线程池的大小，老代码的计算能力会随着核数增加而持续增加吗？显然不是这样，因为多核上的scale受到阿姆达尔定律的制约，当代码中串行执行的部分占比1%时，256核机器只能最多加速到72倍，如果是10%，只能最多加速到10倍。显然修改线程池的大小，并不是一个好方法，减少代码中contention才是关键。

这种情况下，speedup想要随着核数而scale，发现很多算法，数据结构，CC协议和分析处理的算子实现，需要case-by-case重构以减少contention，重构方式是采用lockfree算法。但是这还不是事实的全部，当面对多核scale时，其实我们面对的是一个新的分布式系统，这个新的分布式系统是以interconnect为网络，以核为计算资源，并且还需要考虑屏蔽内存体系的延迟。如果说原来的分布式系统中，我们倾向于每个机器各干各的，数据做到均衡，计算资源就可以充分利用。对于多核编程同样有这个问题，怎么将原来的任务均匀地拆成多个子任务，然后多个子任务可以齐头并进，几乎同时冲线结束。显然数据拆分不均衡，跨核通信等因素都会造成快核等慢核的问题。同时，多核处理时，倾向于协作完成一个共同的任务，而非各干各的，这种情况下，将任务均匀拆分成子任务的的调度代码，共享的数据结构的访问代码，多核彼此之间等待本身就是同步点，即contention，总之，contention怎么降低呢？

现实中，lockfree算法，怎么描述和验证正确性呢？我们对比其他两个问题的思路，或许有解法。比如共识算法中，采用invariant描述算法；而CC协议中，采用反例（anormaly）攻击算法。或许这两种方法相互结合，能够帮助我们研究lockfree算法。

多核scale的挑战性很大，但这可以让具有优势的传统数据库和数据库的新进入者，处于赛道的同一起跑线，比拼谁的代码case-by-case优化做得好。

也有不少团队，在思考异构计算加速数据处理，这同样充满机会。但是，依靠程序员的心智构造精巧而高质量的代码，费时费力。或许的确应该通过编译器的后端技术一劳永逸解决这类问题，现在做不到，不代表未来也做不到。到时候，有人看着前人写得如此复杂的代码，就好比我们现在看到泥板书和带孔的卡片。

6. 计算

计算主要讲执行引擎， 执行引擎是一个很大的scope，目前roadmap已经建立，但是缺乏baseline，待两者都ready之后，会补充。

7. 编译

编译对数据库的渗透是全方位的：比如计算引擎在向量化之外可采用编译技术优化性能。数据库中很多case-by-case的性能优化，需要深入研究体系结构，异构计算加速处理也需要使用编译技术。流批DSL脚本使用现有的SQL执行引擎做计算，UDF扩充等。目前动机已经明了，但roadmap和baseline尚未建立，两者ready之后，也会补充进来。