摘要：设计数据密集型应用程序，作者：Martin Kleppmann
可靠、可扩展、可维护的应用程序。可靠性意味着即使在事情出错的情况下，也能继续正常工作。常见故障和预防措施包括：硬件故障：硬盘崩溃、断电、网络配置不正确、…。只要我们能将备份快速恢复到新计算机上，停机时间就不会致命。
可伸缩性描述了系统处理增加的负载的能力。描述性能：当您增加负载参数时，如果希望保持性能不变，您会增加多少资源？
可维护性侧重于3个设计原则：简单性：使新工程师更容易理解系统。提供良好的抽象层，允许我们将大型系统的各个部分提取到定义良好的、可重用的组件中。
数据模型和查询语言。数据最初被表示为一棵大树，尽管它不适合表示多对多关系模型，因此关系模型应运而生。
然而，一些应用程序不能很好地适应关系模型，非关系NoSQL应运而生：
存储和检索。为数据库提供动力的数据结构：散列索引：基本上是键-值对，其中每个键都映射到数据文件中的一个字节偏移量。
尽管它很容易理解和实现，但它有内存限制，即哈希表必须放在内存中。此外，范围查询效率不高，因为散列键没有放在一起。
排序字符串表(SSTable)和日志结构化合并树(LSM-Trees)：表还可以拆分成更小的段，并且合并很简单，因为它是排序的。
在磁盘上维护排序结构是可能的，尽管将其保存在内存中很容易，因为我们可以使用树数据结构，如红黑树或AVL树(Memtable)。
如果数据库崩溃，Memtable可能会丢失，尽管我们可以根据LSM树索引结构为其保留单独的日志。
B树：与SSTables一样，B树保留按键排序的键-值对，从而允许高效的键值查找和范围查询。
B树不是将数据库拆分成可变大小的段并始终按顺序写入，而是将其拆分成固定大小的块/页，并且一次读/写一页。
每次修改都首先写入预写日志(WAL)，以便索引在崩溃后可以恢复到一致状态。
事务处理还是分析？基本数据库访问模式类似于处理业务事务(创建、读取、更新、删除记录)，称为联机事务处理(OLTP)。
由于OLTP对业务运营至关重要，因此预计OLTP将高度可用，因此他们不愿让业务分析师运行即席分析查询。
数据仓库是分析师可以在不影响OLTP操作的情况下查询的单独数据库。从OLTP数据库中提取数据，将其转换为便于分析的模式，进行清理，然后加载到数据仓库中。
使用单独数据仓库的一大优势是数据仓库可以针对分析访问模式进行优化。
面向列的存储：在大多数OLTP数据库中，存储是以面向行的方式布局的：表中一行中的所有值都是相邻存储的。在面向列的存储中，来自每列的所有值都存储在一起。
因为每列的值序列通常看起来是重复的(不同的值很小)，所以它们通常很适合压缩。
聚合：由于数据仓库查询通常涉及聚合函数，如COUNT、SUM、AVG、MIN或MAX，我们可以缓存这些常用的聚合值。
创建此类缓存的一种方式是实体化视图，而数据立方体是一个特例。
编码和进化。用于编码数据的格式。许多语言都内置了将内存中的对象编码为字节序列的支持，尽管它们并没有使用，因为它是特定于语言的，并且没有显示出良好的性能。
JSON、XML广为人知，由于它们简单、可被多种语言使用并具有对Web浏览器的内置支持而受到支持。但是，关于数字的编码有很多不明确之处，而且它们也不支持二进制编码(紧凑、高效的编码)。因此出现了MessagePack、BSON、BJSON等。
Thrift和Protocol Buffers是二进制编码库，需要任何已编码数据的模式，这是明确定义的向前和向后兼容语义。它们附带一个代码生成工具，可以生成以各种编程语言实现模式的类。
还有一个二进制编码库Avro，可以很好地处理大型文件，就像Hadoop的用例一样。
数据流的模式(从一个进程到另一个进程)。数据库：写入数据库的进程对数据进行编码，从数据库读取的进程对数据进行解码。
对服务、REST和RPC的调用(GRPC)：客户端对请求进行编码，服务器对请求进行解码并对响应进行编码，客户端最终对响应进行解码。
异步消息传递(RabbitMQ、Apache Kafka)：节点相互发送消息，消息由发送方编码，接收方解码。
ii.复制、分区/分片、事务，以及在分布式系统中实现一致性和一致性的意义。
复制。基于引导者的复制：工作流：客户端必须向引导者发送写请求，但可以向引导者和跟随者发送读请求。
在领导者将数据写入其本地存储之后，它会将更改发送给所有跟随者，以便他们可以相应地自我应用。
复制系统的一个重要细节是复制是同步进行还是异步进行。即使同步复制的优点是跟随者保证具有最新的数据，但是如果同步跟随者没有响应，则无法处理写入，因此引导者必须阻止所有写入并等待，直到再次有一个可用。
让所有跟随者保持同步是不切实际的，因此基于领导者的复制通常被配置为完全异步的。
有时，您需要设置新的跟随者以增加副本数量，或替换出现故障的节点。这通常可以通过维护领导者数据库的一致快照在不停机的情况下完成。
如果跟随者倒下，它可以很容易地从从领导者那里收到的日志中恢复过来。稍后，当它能够再次与领导者交谈时，它可以请求所有丢失的数据并赶上领导者。
如果领导者倒下，一种可能的方法是故障转移：需要使用一致算法将其中一个跟随者提升为新领导者，客户端和跟随者需要配置为与新领导者对话。然而，故障转移也可能出错(两个领导者，在领导者被宣布死亡之前选择正确的超时，…)。因为这些问题没有简单的解决方案。
复制日志的不同实现：基于语句的复制：领导者记录其执行的每个写请求，并将该语句日志发送给其跟随者。尽管看起来合理，但非确定性函数(如now())获取当前日期和时间可能会在每个副本上生成不同的值。
预写日志(WAL)传送：类似于B-tree的方法，即每个修改都首先写入WAL，除了将日志写入磁盘之外，领导者还将日志发送给其追随者，以便他们可以构建与领导者上发现的完全相同的数据结构的副本。
逻辑日志复制：允许使用不同的日志格式将复制日志与存储引擎解耦。
基于触发器的复制：注册触发器只复制数据的子集，或者从一种数据库复制到另一种数据库，依此类推。
复制延迟：如果用户在写入后不久查看数据，则新数据可能尚未到达复制副本。在这种情况下，我们需要写后读一致性，这意味着我们可以首先从领导者处读取，以便用户始终看到他们的最新更改。
如果用户从不同的副本进行多次读取，并且副本之间存在滞后，则他们可能看不到正确的数据。单调读取通过确保每个用户始终从同一副本进行读取来保证不会发生此类异常。
如果一些追随者的复制速度比其他人慢，观察者可能会在看到问题之前就看到答案。防止此类异常需要一致的前缀读取，以便如果写入序列按特定顺序发生，则读取这些写入的任何人都将看到它们以相同的顺序出现。
多领导者复制：使用案例：多数据中心运营：每个数据中心都有自己的领导者。尽管可能在两个不同的数据中心同时修改相同的数据，并且必须解决这些写入冲突，但这可以提高数据中心的性能和对数据中心中断的容忍度。
具有离线操作的客户端：每个客户端都有一个充当引导者的本地数据库，并且您所有客户端上的副本之间有一个异步多引导者复制过程(同步)。
实时协作编辑：当一个用户编辑文档时，更改将立即应用于其本地副本，并异步复制到服务器和正在编辑同一文档的任何其他用户。
处理写入冲突：写入冲突可能是由两个领导者同时更新同一记录引起的。在单引头方案中，这是不可能发生的，因为第二个引头将等待第一次写入或中止它。在多引头的情况下，两次写入都是成功的，并且只能在稍后的时间点异步检测冲突。
处理多引导器写入冲突的最简单方法是通过确保所有写入都通过同一指定引导器来避免冲突。
由于在多引头数据库中没有定义的写入顺序，因此不清楚所有副本中的最终值应该是什么。收敛到最终值的方法有很多种，包括为每个写入提供唯一的ID，并选择ID最高的一个作为获胜者，以某种方式将值合并在一起，…。
拓扑：将写入从一个节点传播到另一个节点的通信路径。最常见的拓扑是All-to-All，即每个领导者将其写入内容发送给其他每个领导者。其他流行的拓扑是环形拓扑和星形拓扑。
环形拓扑和星形拓扑的一个问题是，如果一个节点发生故障，路径就会中断，从而导致一些节点无法连接到其他节点。
尽管All-to-All拓扑避免了单点故障，但它们也可能存在一些问题，即某些复制速度更快，并且可能会覆盖其他复制。可以使用一种称为版本矢量的技术来正确地对这些事件进行排序。
无领导复制：客户端写入多个副本，或者协调器节点代表客户端执行此操作。无引线复制中不存在故障切换。如果节点出现故障，客户端将并行写入所有可用的副本，验证它们是否成功，并简单地忽略一个不可用的副本。读请求也会并行发送到多个节点，以避免过时的值。
为了确保将所有最新数据复制到每个副本，两种常用的机制是读取修复(并行向多个节点发出请求，并使用版本控制检测过时的值)、反熵处理(不断查找副本之间的数据差异并将任何丢失的数据从一个副本复制到另一个副本的后台进程)。
如果有n个副本，则必须由w个节点确认每个写入才能被视为成功，并且我们必须为每个读取查询至少r个节点，只要w+r>；n，我们希望在读取时获得最新的值，因为我们从中读取的r个节点中至少必须有一个是最新的。但是，当返回过时值时，仍然存在边缘情况：
对于多数据中心操作，一些无领导复制的实现将客户端和数据库节点之间的所有通信保持在一个数据中心本地，因此n描述了一个数据中心内的副本数量。跨数据中心复制的工作原理类似于多引线复制。
处理并发写入冲突：最后一次写入获胜：为每个写入附加一个时间戳，选择最大的时间戳作为最新的，并丢弃时间戳较低的所有写入。
版本向量：对于单个复制品，算法的工作原理如下：服务器为每个密钥维护一个版本号，每次写入该密钥时增加版本号，并将新版本号与写入的值一起存储。
客户端必须在写入之前读取密钥。当客户端写入密钥时，它必须包括前一次读取的版本号，并且必须将它在前一次读取中收到的所有值合并在一起。
当服务器接收到具有特定版本号的写入时，它可以覆盖具有该版本号或更低版本号的所有值，但它必须保留具有更高版本号的所有值。
对于多个复制副本：每个复制副本在处理写入时会递增其自己的版本号，并且还会跟踪它从所有其他复制副本看到的版本号。
分区/分片。分区的主要原因是可伸缩性：分区可以分布在许多节点、磁盘等上。
它通常与复制结合使用，以便将每个分区的副本存储在多个节点上。
分区的目标是跨节点均匀分布数据和查询负载。
键值数据的分区。分区的一种方式是将连续范围的键分配给每个分区。然而，缺点是某些模式可能会导致高负载。
另一种方式是使用散列函数来确定给定键的分区。缺点是无法高效地执行范围查询，因为相邻键现在分散在所有分区中。
分区和辅助索引。如果涉及二级索引，分区就会变得更加复杂，因为它们并不唯一地标识记录，而是一种搜索特定值的匹配项的方式。
使用基于文档的分区，每个分区维护其自己的辅助索引，仅覆盖该分区中的文档。因为它不关心其他分区，所以读取它的开销可能相当高，因为需要查询所有分区并聚合所有内容以获得更准确的结果。
使用基于术语的分区，而不是每个分区都有自己的二级索引，我们可以构建一个覆盖所有分区中数据的全局索引。这可以提高读取效率，而不是在所有分区上进行分散/聚集。缺点是写入现在变得更慢、更复杂，因为对单个文档的写入现在可能会影响索引的多个分区。
随着时间的推移，我们增加节点和计算机，从而重新平衡分区。当节点数N发生变化时，MoD-N方法是有问题的，大多数密钥也需要移动。
一个简单的解决方案是创建比节点数量多得多的分区，并为每个节点分配多个分区。如果添加新节点，它可以从每个现有节点窃取几个分区。
再平衡可以自动完成，不过让人参与进来以帮助防止操作意外并不会有什么坏处。
请求路由/服务发现。在分区和重新平衡之后，客户端如何知道要连接到哪个节点？如果需要，客户端可以与任何节点通信，并将请求转发到适当的节点。
客户端可以与确定应该处理该请求的节点的路由层进行通信，并相应地转发该请求。
交易记录。原子性、一致性、隔离性和耐久性(酸)。由于事务通常由多个语句组成，原子性保证每个事务都被视为单个“单元”，要么完全成功，要么完全失败。
一致性确保事务只能将数据库从一种有效状态转换到另一种状态，同时维护数据库不变量。
持久性保证了事务一旦提交，即使在系统出现故障的情况下也会保持提交状态。
弱隔离级别。数据库通过提供事务隔离(尤其是可序列化隔离)向应用程序开发人员隐藏并发问题，方法是确保事务具有与串行运行相同的效果，一次一个，不带任何并发。
在实践中，可序列化隔离有性能代价，许多数据库不想为此付出代价。取而代之的是，他们使用较弱的隔离级别。
快照隔离或多版本并发控制(MVCC)。每个事务从数据库的一致快照读取。每个事务都会查看从其启动时开始的最新数据。
防止丢失更新。如果两个事务同时修改该值，则可能发生更新丢失，即一个修改丢失。
防止写偏差和幻象。写偏差是丢失更新的泛化。当两个事务更新一些相同的对象，而不仅仅是相同的对象时，就会发生这种情况。
当一个事务中的写入更改了另一个事务中搜索查询的结果时，就会发生幻影。
由于涉及多个对象，原子单对象或快照隔离写入没有帮助，因为它不能阻止有效的冲突并发写入。
可序列化隔离的实现。实际的串行执行。避免并发问题的最佳方法是在单个线程上按串行顺序一次只执行一个事务。
整个事务作为存储过程提交，因为数据必须小而快。
两相锁定(2PL)。2PL有非常强烈的要求，写入者不仅阻止写入者，读者也阻止写入者，反之亦然。
最大的缺点是性能，因为它在实践中使用得不多。
可序列化快照隔离(SSI)。由于串行隔离不能很好地扩展，2PL也不能很好地执行，因此SSI很有前途，因为它提供了完全的可序列化，并且与快照隔离相比性能损失很小。
它允许事务在不阻塞的情况下继续进行。当事务想要提交时，会检查该事务，如果执行不可序列化，则中止该事务。
在分布式系统中可能出错的事情。部分故障是指系统的某些部分以某种不可预测的方式损坏，尽管其余部分工作正常。由于部分故障在某种意义上是不确定的，即您的解决方案有时可能会不可预测地失败，因此它很难处理分布式系统。
不可靠的网络。网络请求可能会出现很多问题，例如您的请求可能已丢失、在队列中等待、远程节点可能已失败、响应已丢失、延迟等等。
超时通常是检测故障的好方法。系统可以根据观察到的响应时间分布自动调整超时，而不是使用配置的恒定超时。
不可靠的钟。时间是棘手的，因为通信不是即时的，消息从一个点到另一个点需要时间，而且由于涉及多台机器的网络中的延迟变量，很难确定操作的顺序。
现代计算机至少有两种不同的时钟：一天中的时间时钟，通常与网络时间协议(NTP)同步，这意味着来自一台机器的时间戳(理想情况下)意味着与另一台机器上的时间戳相同。
单调时钟适用于测量持续时间，例如超时或服务的响应时间。
为了有用，需要根据NTP设置一天中的时间时钟，尽管这不像我们希望的计算机中的石英钟那样可靠。
..
