《数据密集型应用系统设计》笔记二

发表于 2021-08-26 更新于 2025-09-13 分类于笔记，分布式，分布式综合本文字数： 16k 阅读时长 ≈ 14 分钟

《数据密集型应用系统设计》笔记二

第五章：数据复制

复制主要指通过网络在多台机器上保存相同数据的副本。通过复制，可以达到以下目的：

使数据在地理位置上更接近用户，从而降低访问延迟。如：CDN
当部分组件出现故障，系统依然可以继续工作，从而提高可用性。
扩展至多台机器以同事提供数据访问服务，从而提高读吞吐量。

主流的复制模式：主从复制、多主复制、无主复制。

复制需要考虑的细节：同步复制还是异步复制？如何处理失败的副本（故障转移）？处理策略通常采用可配置项来调整。

主节点与从节点

每个保存数据库完整数据集的节点称之为副本。有了多副本，必然会面临一个问题：如何确保所有副本之间的数据是一致的？

主从复制的工作原理如下：

指定某一个副本为主副本（或称为主节点）。当客户写数据库时，必须将写请求首先发送给主副本，主副本首先将新数据写入本地存储。
其他副本则全部称为从副本（或称为从节点）。主副本把新数据写入本地存储后，然后将数据更改作为复制的日志或更改流发送给所有从副本。每个从副本获得更改日志之后将其应用到本地，且严格保持与主副本相同的写入顺序。
客户端从数据库中读数据时，可以在主副本或者从副本上执行查询。再次强调，只有主副本才可以接受写请求：从客户端的角度来看，从副本都是只读的。

支持主从复制的案例：

关系型数据库：MySql、SQL Server、PostgreSQL 等
Nosql：MongoDB、Redis 等
消息队列：Kafka、RabbitMQ 等

同步复制与异步复制

复制的基本流程是，客户将更新请求发送给主节点，主节点接收到请求，接下来将数据更新转发给从节点。最后，由
主节点来通知客户更新完成。

通常情况下，复制速度会非常快，例如多数数据库系统可以在一秒之内完成所有从节点的更新。但是，系统其
实并没有保证一定会在多长时间内完成复制。有些情况下，从节点可能落后主节点几分钟甚至更长时间，例如，由于从节点刚从故障中恢复，或者系统已经接近最大设计上限，或者节点之间的网络出现问题。

同步复制的优点：一旦向用户确认，从节点可以明确保证完成了与主节点的更新同步，数据已经处于最新版本。万一主节点发生故障，总是可以在从节点继续访问最新数据。
同步复制的缺点：如果同步的从节点无法完成确认（例如由于从节点发生崩愤，或者网络故障，或任何其他原因），写入就不能视为成功。主节点会阻塞其后所有的写操作，直到同步副本确认完成。

因此，把所有从节点都配置为同步复制有些不切实际。因为这样的话，任何一个同步节点的中断都会导致整个系统更新停滞不前。

实际应用中，很多数据库推荐的模式是：只要有一个从节点或半数以上的从节点同步成功，就视为同步，直接返回结果；剩下的节点都通过异步方式同步。

异步复制的优点：不管从节点上数据多么滞后，主节点总是可以继续响应写请求，系统的吞吐性能更好。
异步复制的缺点：如果主节点发生失败且不可恢复，则所有尚未复制到从节点的写请求都会丢失。

主从复制还经常会被配置为全异步模式。此时如果主节点发生失败且不可恢复，则所有尚未复制到从节点的写请求都会丢失。这意味着即使向客户端确认了写操作，却无法保证数据的持久化。

配置新的从节点

要做到在不停机、服务不中断的前提下，完成配置新的从节点，主要操作步骤是：

在某个时间点对主节点的数据副本产生一个一致性快照，这样避免长时间锁定整个数据库。目前大多数数据库都支持此功能，快照也是系统备份所必需的。而在某些情况下，可能需要第三方工具，如 MySQL 的 innobackupex。
将此快照拷贝到新的从节点。
从节点连接到主节点并请求快照点之后所发生的数据更改日志。因为在第一步创建快照时，快照与系统复制日志的某个确定位置相关联，这个位置信息在不同的系统有不同的称呼，如 PostgreSQL 将其称为“ log sequence number” （日志序列号），而 MySQL 将其称为“ binlog coordinates ” 。
获得日志之后，从节点来应用这些快照点之后所有数据变更，这个过程称之为追赶。接下来，它可以继续处理主节点上新的数据变化。井重复步骤 1 ～步骤 4 。

建立新的从副本具体操作步骤可能因数据库系统而异。

处理节点失效

如何通过主从复制技术来实现系统高可用呢？

从节点失效：追赶式恢复

从节点的本地磁盘上都保存了副本收到的数据变更日志。如果从节点发生崩溃，然后顺利重启，或者主从节点之间的网络发生暂时中断（闪断），则恢复比较容易，根据副本的复制日志，从节点可以知道在发生故障之前所处理的最后一笔事务，然后连接到主节点，并请求自那笔事务之后中断期间内所有的数据变更。在收到这些数据变更日志之后，将其应用到本地来追赶主节点。之后就和正常情况一样持续接收来自主节点数据流的变化。

主节点失效：节点切换

选择某个从节点将其提升为主节点；客户端也需要更新，这样之后的写请求会发送给新的主节点，然后其他从节点要接受来自新的主节点上的变更数据，这一过程称之为切换。

自动切换的步骤通常如下：

确认主节点失效。有很多种出错可能性，所以大多数系统都采用了基于超时的机制：节点间频繁地互相发生发送心跳悄息，如果发现某一个节点在一段比较长时间内（例如 30s ）没有响应，即认为该节点发生失效。
选举新的主节点。可以通过选举的方式（超过多数的节点达成共识）来选举新的主节点，或者由之前选定的某控制节点来指定新的主节点。候选节点最好与原主节点的数据差异最小，这样可以最小化数据丢失的风险。让所有节点同意新的主节点是个典型的共识问题。
重新配置系统使新主节点生效。客户端现在需要将写请求发送给新的主节点。如果原主节点之后重新上线，可能仍然自认为是主节点，而没有意识到其他节点已经达成共识迫使其下台。这时系统要确保原主节点降级为从节点，并认可新的主节点。

上述切换过程依然充满了很多变数：

如果使用了异步复制，且失效之前，新的主节点并未收到原主节点的所有数据；在选举之后，原主节点很快又重新上线并加入到集群，接下来的写操作会发生什么？新的主节点很可能会收到冲突的写请求，这是因为原主节点未意识的角色变化，还会尝试同步其他从节点，但其中的一个现在已经接管成为现任主节点。常见的解决方案是，原主节点上未完成复制的写请求就此丢弃，但这可能会违背数据更新持久化的承诺。
如果在数据库之外有其他系统依赖于数据库的内容并在一起协同使用，丢弃数据的方案就特别危险。例如，在 GitHub 的一个事故中，某个数据并非完全同步的 MySQL 从节点被提升为主副本，数据库使用了自增计数器将主键分配给新创建的行，但是因为新的主节点计数器落后于原主节点（即二者并非完全同步），它重新使用了已被原主节点分配出去的某些主键，而恰好这些主键已被外部 Redis 所引用，结果出现 MySQL 和 Redis 之间的不一致，最后导致了某些私有数据被错误地泄露给了其他用户。
在某些故障情况下，可能会发生两个节点同时都自认为是主节点。这种情况被称为脑裂，它非常危险：两个主节点都可能接受写请求，并且没有很好解决冲突的办法，最后数据可能会丢失或者破坏。作为一种安全应急方案，有些系统会采取措施来强制关闭其中一个节点。然而，如果设计或者实现考虑不周，可能会出现两个节点都被关闭的情况。
如何设置合适的超时来检测主节点失效呢？主节点失效后，超时时间设置得越长也意味着总体恢复时间就越长。但如果超时设置太短，可能会导致很多不必要的切换。例如，突发的负载峰值会导致节点的响应时间变长甚至超肘，或者由于网络故障导致延迟增加。如果系统此时已经处于高负载压力或网络已经出现严重拥塞，不必要的切换操作只会使总体情况变得更糟。

复制日志的实现

基于语句的复制

最简单的情况，主节点记录所执行的每个写请求（操作语句）井将该操作语句作为日志发送给从节点。对于关系数据库，这意味着每个 INSERT 、UPDATE 或 DELETE 语句都会转发给从节点，并且每个从节点都会分析井执行这些 SQL 语句，如同它们是来自客户端那样。

听起来很合理也不复杂，但这种复制方式有一些不适用的场景：

任何调用非确定性函数的语句，如 NOW() 获取当前时间，或 RAND() 获取一个随机数等，可能会在不同的副本上产生不同的值。
如果语句中使用了自增列，或者依赖于数据库的现有数据（例如， UPDATE ... WHERE <某些条件>），则所有副本必须按照完全相同的顺序执行，否则可能会带来不同的结果。进而，如果有多个同时并发执行的事务时，会有很大的限制。
有副作用的语句（例如，触发器、存储过程、用户定义的函数等），可能会在每个副本上产生不同的副作用。

有可能采取一些特殊措施来解决这些问题，例如，主节点可以在记录操作语句时将非确定性函数替换为执行之后的确定的结果，这样所有节点直接使用相同的结果值。但是，这里面存在太多边界条件需要考虑，因此目前通常首选的是其他复制实现方案。

MySQL 5.1 版本之前采用基于操作语句的复制。现在由于逻辑紧凑，依然在用，但是默认情况下，如果语句中存在一些不确定性操作，则 MySQL 会切换到基于行的复制（稍后讨论）。VoltDB 使用基于语句的复制，它通过事务级别的确定性来保证复制的安全。

基于预写日志（WAL）传输

通常每个写操作都是以追加写的方式写入到日志中：

对于日志结构存储引擎，日志是主要的存储方式。日志段在后台压缩井支持垃圾回收。
对于采用覆写磁盘的 BTree 结构，每次修改会预先写入日志，如系统发生崩溃，通过索引更新的方式迅速恢复到此前一致状态。

不管哪种情况，所有对数据库写入的字节序列都被记入日志。因此可以使用完全相同的日志在另一个节点上构建副本：除了将日志写入磁盘之外，主节点还可以通过网络将其发送给从节点。

PostgreSQL 、Oracle 以及其他系统等支持这种复制方式。其主要缺点是日志描述的数据结果非常底层：一个 WAL 包含了哪些磁盘块的哪些字节发生改变，诸如此类的细节。这使得复制方案和存储引擎紧密耦合。如果数据库的存储格式从一个版本改为另一个版本，那么系统通常无法支持主从节点上运行不同版本的软件。

基于行的逻辑日志复制

关系数据库的逻辑日志通常是指一系列记录来描述数据表行级别的写请求：

对于行插入，日志包含所有相关列的新值。
对于行删除，日志里有足够的信息来唯一标识已删除的行，通常是靠主键，但如果表上没有定义主键，就需要记录所有列的旧值。
对于行更新，日志包含足够的信息来唯一标识更新的行，以及所有列的新值（或至少包含所有已更新列的新值）。

如果一条事务涉及多行的修改，则会产生多个这样的日志记录，并在后面跟着一条记录，指出该事务已经提交。MySQL 的二进制日志 binlog （当配置为基于行的复制时）使用该方式。

由于逻辑日志与存储引擎逻辑解耦，因此可以更容易地保持向后兼容，从而使主从节点能够运行不同版本的软件甚至是不同的存储引擎。

对于外部应用程序来说，逻辑日志格式也更容易解析。

基于触发器的复制

在某些情况下，我们可能需要更高的灵活性。例如，只想复制数据的一部分，或者想从一种数据库复制到另一种数据库，或者需要订制、管理冲突解决逻辑（参阅本章后面的“处理写冲突”），则需要将复制控制交给应用程序层。

有一些工具，可以通过读取数据库日志让应用程序获取数据变更。另一种方法则是借助许多关系数据库都支持的功能：触发器和存储过程。

触发器支持注册自己的应用层代码，使得当数据库系统发生数据更改（写事务）时自动执行上述自定义代码。通过触发器技术，可以将数据更改记录到一个单独的表中，然后外部处理逻辑访问该表，实施必要的自定义应用层逻辑，例如将数据更改复制到另一个系统。Oracle 的 Databus 和 Postgres 的 Bucardo 就是这种技术的典型代表。基于触发器的复制通常比其他复制方式开销更高，也比数据库内置复制更容易出错，或者暴露一些限制。然而，其高度灵活性仍有用武之地。

复制滞后问题

主从复制要求所有写请求都经由主节点，而任何副本只能接受只读查询。对于读操作密集的负载（如 Web ），这是一个不错的选择：创建多个从副本，将读请求分发给这些从副本，从而减轻主节点负载井允许读取请求就近满足——读写分离。

在这种扩展体系下，只需添加更多的从副本，就可以提高读请求的服务吞吐量。但是，这种方法实际上只能用于异步复制，如果试图同步复制所有的从副本，则单个节点故障或网络中断将使整个系统无法写入。而且节点越多，发生故障的概率越高，所以完全同步的配置现实中反而非常不可靠。

不幸的是，如果一个应用正好从一个异步的从节点读取数据，而该副本落后于主节点，则应用可能会读到过期的信息。这会导致数据库中出现明显的不一致：由于并非所有的写入都反映在从副本上，如果同时对主节点和从节点发起相同的查询，可能会得到不同的结果。经过一段时间之后，从节点最终会赶上并与主节点数据保持一致。这种效应也被称为最终一致性。

读自己的写

许多应用让用户提交一些数据，接下来查看他们自己所提交的内容。例如客户数据库中的记录，亦或者是讨论主题的评论等。提交新数据须发送到主节点，但是当用户读取数据时，数据可能来自从节点。这对于读密集和偶尔写入的负载是个非常合适的方案。

然而对于异步复制存在这样一个问题，用户在写入不久即查看数据，则新数据可能尚未到达从节点。对用户来讲，看起来似乎是刚刚提交的数据丢失了。

对于这种情况，我们需要强一致性。如何实现呢？有以下方案：

如果用户访问可能会被修改的内容，从主节点读取；否则，在从节点读取。这背后就要求有一些方法在实际执行查询之前，就已经知道内容是否可能会被修改。例如，社交网络上的用户首页信息通常只能由所有者编辑，而其他人无法编辑。因此，这就形成一个简单的规则：总是从主节点读取用户自己的首页配置文件，而在从节点读取其他用户的配置文件。
如果应用的大部分内容都可能被所有用户修改，那么上述方法将不太有效，它会导致大部分内容都必须经由主节点，这就丧失了读操作的扩展性。此时需要其他方案来判断是否从主节点读取。例如，跟踪最近更新的时间，如果更新后一分钟之内，则总是在主节点读取；井监控从节点的复制滞后程度，避免从那些滞后时间超过一分钟的从节点读取。
客户端还可以记住最近更新时的时间戳，井附带在读请求中，据此信息，系统可以确保对该用户提供读服务时都应该至少包含了该时间戳的更新。如果不够新，要么交由另一个副本来处理，要么等待直到副本接收到了最近的更新。时间戳可以是逻辑时间戳（例如用来指示写入顺序的日志序列号）或实际系统时钟。
如果副本分布在多数据中心（例如考虑与用户的地理接近，以及高可用性），情况会更复杂些。必须先把请求路由到主节点所在的数据中心（该数据中心可能离用户很远）。

如果同一用户可能会从多个设备访问数据，情况会更加复杂。

记住用户上次更新时间戳的方法实现起来会比较困难，因为在一台设备上运行的代码完全无法知道在其他设备上发生了什么。此时，元数据必须做到全局共享。
如果副本分布在多数据中心，无法保证来自不同设备的连接经过路由之后都到达同一个数据中心。例如，用户的台式计算机使用了家庭宽带连接，而移动设备则使用蜂窝数据网络，不同设备的网络连接线路可能完全不同。如果方案要求必须从主节点读取，则首先需要想办毡确保将来自不同设备的请求路由到同一个数据中心。

单调读

假设用户从不同副本进行了多次读取，可能会出现：用户看到了最新内容之后又读到了过期的内容，好像时间被回拨，此时需要单调读一致性。

单调读一致性可以确保不会发生这种异常。单调读一致性是一个比强一致性弱，但比最终一致性强的保证。当读取数据时，单调读保证，如果某个用户依次进行多次读取，则他绝不会看到回滚现象，即在读取较新值之后又发生读旧值的情况。

实现单调读的一种方式是，确保每个用户总是从固定的同一副本执行读取（而不同的用户可以从不同的副本读取）。

前缀一致读

前缀一致读：对于一系列按照某个顺序发生的写请求，那么读取这些内容时也会按照当时写入的顺序。

如果数据库总是以相同的顺序写入，则读取总是看到一致的序列，不会发生这种反常。然而，在许多分布式数据库中，不同的分区独立运行，因此不存在全局写入顺序。这就导致当用户从数据库中读数据时，可能会看到数据库的某部分旧值和另一部分新值。

一个解决方案是确保任何具有因果顺序关系的写入都交给一个分区来完成，但该方案效率很低。此外，还有一些算法来显示地跟踪事件因果关系（Happend Before）。

复制滞后的解决方案

解决方案是分布式事务。

多主节点复制

主从复制存在一个明显的缺点：系统只有一个主节点，而所有写入都必须经由主节点。主从复制方案就会影响所有的写入操作。典型代表：ZooKeeper。

适用场景

在一个数据中心内部使用多主节点基本没有太大意义，其复杂性已经超过所能带来的好处。

但是，以下场景这种配置则是合理的：

多数据中心
离线客户端操作
协作编辑

多数据中心

为了容忍整个数据中心级别故障或更接近用户，可以把数据库的副本横跨多个数据中心。

在每个数据中心内，采用常规的主从复制；而在数据中心之间，由各数据中心的主节点来负责同其他数据中心的主节点进行数据的交换、更新。

主从复制和多主复制的差异：

性能：对于主从复制，每个写请求都必须经由广域网传送至主节点所在的数据中心。这会大大增加写入延迟，井基本偏离了采用多数据中心的初衷（即就近访问）。而在多主节点模型中，每个写操作都可以在本地数据中心快速响应，然后采用异步复制方式将变化同步到其他数据中心。因此，对上层应用有效屏蔽了数据中心之间的网络延迟，使得终端用户所体验到的性能更好。
容忍数据中心失效：对于主从复制，如果主节点所在的数据中心发生故障，必须切换至另一个数据中心，将其中的一个从节点被提升为主节点。在多主节点模型中，每个数据中心则可以独立于其他数据中心继续运行，发生故障的数据中心在恢复之后更新到最新状态。
容忍网络问题：数据中心之间的通信通常经由广域网，它往往不如数据中心内的本地网络可靠。对于主从复制模型，由于写请求是同步操作，对数据中心之间的网络性能和稳定性等更加依赖。多主节点模型则通常采用异步复制，可以更好地容忍此类问题，例如临时网络闪断不会妨碍写请求最终成功。

离线客户端操作

多主复制的另一适用场景：应用在断网后仍然需要继续工作。典型代表：各种电子笔记软件。
在这种情况下，每个设备都有一个充当领导者的本地数据库（用来接受写请求），然后在所有设备上采用异步方式同步这些多主节点的副本，同步滞后可能是几小时或数天。
从架构层面来看，每个设备相当于一个“数据中心”。

协同编辑

实时协作编辑应用允许多个用户同时编辑文档。

协同编辑和数据库复制有很多相似之处：用户对文档的编辑立即应用到其本地副本，并异步复制到服务器和编辑同一文档的其他用户。

如果想避免编辑发生冲突，则应该对编辑的内容加锁，此时其他用户不能编辑该内容。为了减少锁冲突，锁的粒度应尽可能小：可能是 word 文档的一行内容，也可能是 Excel 的某一单元格。

处理写冲突

多主复制的最大问题是可能发生写冲突。

同步与异步冲突检测

理论上，也可以做到同步冲突检测，即等待写请求完成对所有副本的同步，然后再通知用户写入成功。但是，这样做将会失去多主节点的主要优势：允许每个主节点独立接受写请求。如果确实想要同步方式冲突检测，或许应该考虑采用单主节点的主从复制模型。

避免冲突

处理冲突最理想的策略是避免发生冲突，即如果应用层可以保证对特定记录的写请求总是通过同一个主节点，这样就不会发生写冲突。现实中，由于不少多主节点复制模型所实现的冲突解决方案存在瑕疵，因此，避免冲突反而成为大家普遍推荐的首选方案。

但是，有时可能需要改变事先指定的主节点，例如由于该数据中心发生故障，不得不将流量重新路由到其他数据中心，或者是因为用户已经漫游到另一个位置，因而更靠近新数据中心。此时，冲突避免方式不再有效，必须有措施来处理同时写入冲突的可能性。

收敛于一致状态

对干主从复制模型，数据更新符合顺序性原则，即如果同一个字段有多个更新，则最后一个写操作将决定该字段的最终值。

对于多主节点复制模型，由于不存在这样的写入顺序，所以最终值也会变得不确定。

实现收敛的冲突解决有以下可能的方式：

给每个写入分配唯一的 ID ，例如，一个时间戳，二个足够长的随机数，一个 UUID 或者一个基于键－值的 Jl 合希，优先挑选最高 ID 的写入，并将其他写入丢弃。如果基于时间戳，这种技术被称为最后写入者获胜。虽然这种方陆很流行，但是很容易造成数据丢失。
为每个副本分配一个唯一的 ID ，井制定规则，例如序号高的副本写入始终优先于序号低的副本。这种方法也可能会导致数据丢失。
以某种方式将这些值合并在一起。例如，按字母顺序排序，然后拼接在一起
利用预定义好的格式来记录和保留冲突相关的所有信息，然后依靠应用层的逻辑，事后解决冲突（可能会提示用户）。

自定义冲突解决逻辑

解决冲突最合适的方式可能还是依靠应用层，所以大多数多主节点复制模型都有工具来让用户编写应用代码来解决冲突。可以在写入时或在读取时执行这些代码逻辑：

在写入时执行：只要数据库系统在复制变更日志时检测到冲突，就会调用应用层的冲突处理程序。
在读取时执行：当检测到冲突时，所有冲突写入值都会暂时保存下来。下一次读取数据时，会将数据的多个版本读返回给应用层。应用层可能会提示用户或自动解决冲突，井将最后的结果返回到数据库。

什么是冲突？

显而易见的冲突：两个写操作并发地修改了同一条记录中的同一个字段。
微秒的冲突：一个房间接受了两个预定。

拓扑结构

复制拓扑（replication topology）描述写入从一个节点传播到另一个节点的通信路径。
只有两个领导者时，只有一个合理的拓扑：互相写入。
当有两个以上的领导，拓扑很多样：

最普遍的是全部到全部；
MySQL 仅支持环形拓扑。

防止无限复制循环：

圆形和星型拓扑，节点需要转发从其他节点收到的数据更改。
防止无限复制循环：每个节点都有唯一的标识符，在复制日志中，每个写入都标记了所有已经过的节点的标识符。

环形和星形拓扑的问题

一个节点故障，可能中断其他节点之间的复制消息流。
拓扑结构可以重新配置，但是需要手动操作。
全部到全部的容错性更好，避免单点故障。

全部到全部拓扑的问题

网络问题导致消息顺序错乱

写入时添加时间戳是不够的。
解决办法是版本向量技术。
有些数据库没有该功能。

无主复制

客户端将写请求发送到多个节点上，读取时从多个节点上并行读取，以此检测和纠正某些过期数据。

第六章：分区

在不同系统中，分区有着不同的称呼，例如它对应于 MongoDB, Elasticsearch 和 SolrCloud 中的 shard, HBase 的 region, Bigtable 中的 tablet, Cassandra 和 Riak 中的 vnode ，以及 Couch base 中的 vBucket。总体而言，分区是最普遍的术语。

分区定义：每条数据只属于特定分区。

采用数据分区的主要目的是提高可扩展性。不同的分区可以放在一个无共享集群的不同节点上，这样一个大数据集可以分散在更多的节点上，查询负载也随之分散。

对单个分区进行查询时，每个节点对自己所在分区可以独立执行查询操作，因此添加更多的节点可以提高查询吞吐量。超大而复杂的查询尽管比较困难，但也可能做到跨节点的并行处理。

数据分区与数据复制

分区通常与复制结合使用，即每个分区在多个节点都存有副本。这意味着某条记录属于特定的分区，而同样的内容会保存在不同的节点上以提高系统的容错性。

一个节点上可能存储了多个分区。每个分区都有自己的主副本，而从副本则分配在其他一些节点。一个节点可能既是某些分区的主副本，同时又是其他分区的从副本。

键－值数据的分区

分区的主要目标是将数据和查询负载均匀分布在所有节点上。如果节点平均分担负载，那么理论上 10 个节点应该能够处理 10 倍的数据量和 10 倍于单个节点的读写吞吐量（忽略复制）。

而如果分区不均匀，则会出现某些分区节点比其他分区承担更多的数据量或查询负载，称之为倾斜。倾斜会导致分区效率严重下降，在极端情况下，所有的负载可能会集中在一个分区节点上，这就意味着 10 个节点 9 个空闲，系统的瓶颈在最繁忙的那个节点上。这种负载严重不成比例的分区即成为系统热点。

避免热点最简单的方法是将记录随机分配给所有节点。这种方法的缺点是：当视图读取特定数据时，无法知道数据保存在哪个节点，所以不得不并行查询所有节点。

基于关键字区间分区

一种分区方式是为每个分区分配一段连续的关键字或者关键宇区间范围（以最小值和最大值来指示）。

关键字的区间段不一定非要均匀分布，这主要是因为数据本身可能就不均匀。

分区边界可以由手动选择或自动选择。采用这种分区策略的数据存储有：Bigtable、HBase、RethinkDB、2.4 版本前的 MongoDB。

每个分区内可以按照关键字排序保存。这样可以轻松支持区间查询，即将关键字作为一个拼接起来的索引项从而一次查询得到多个相关记录。

然而，基于关键字的区间分区的缺点是某些访问模式会导致热点。如果关键字是时间戳，则分区对应于一个时间范围。所有的写入操作都集中在同一个分区（即当天的分区），这会导致该分区在写入时负载过高，而其他分区始终处于空闲状态。为了避免上述问题，需要使用时间戳以外的其他内容作为关键字的第一项。

基于关键字晗希值分区

一个好的哈希函数可以处理数据倾斜并使其均匀分布。

用于数据分区目的的哈希函数不需要在加密方面很强。

一且找到合适的关键宇哈希函数，就可以为每个分区分配一个哈希范围（而不是直接作用于关键宇范围），关键字根据其哈希值的范围划分到不同的分区中。

这种方总可以很好地将关键字均匀地分配到多个分区中。分区边界可以是均匀间隔，也可以是伪随机选择（在这种情况下，该技术有时被称为一致性哈希）。

然而，通过关键宇哈希进行分区，我们丧失了良好的区间查询特性。即使关键字相邻，但经过哈希之后会分散在不同的分区中，区间查询就失去了原有的有序相邻的特性。在 MongoDB 中，如果启用了基于哈希的分片模式，则区间查询会发送到所有的分片上，而 Riak、Couchbase 和 Voldemort 直接就不支持关键字上的区间查询。

Cassandra 中的表可以声明为由多个列组成的复合主键。复合主键只有第一部分可用于哈希分区，而其他列则用作组合索引来对 Cassandra SSTable 中的数据进行排序。

负载倾斜与热点

基于哈希的分区方能可以减轻热点，但无住做到完全避免。一个极端情况是，所有的读／写操作都是针对同一个关键字，则最终所有请求都将被路由到同一个分区。典型：名人的热点事件（关键字是名人的 ID）。

一个简单的规避热点的技术就是：在关键字的开头或结尾处添加一个随机数。只需一个两位数的十进制随机数就可以将关键字的写操作分布到 100 个不同的关键字上，从而分配到不同的分区上。

但是，随之而来的问题是，之后的任何读取都需要些额外的工作，必须从所有 100 个关键字中读取数据然后进行合井。因此通常只对少量的热点关键字附加随机数才有意义；而对于写入吞吐量低的绝大多数关键宇，这些都意味着不必要的开销。此外，还需要额外的元数据来标记哪些关键字进行了特殊处理。

分区与二级索引

二级索引通常不能唯一标识一条记录，而是用来加速特定值的查询。

二级索引带来的主要挑战是它们不能规整的地映射到分区中。有两种主要的方法来支持对二级索引进行分区：基于文档的分区和基于词条的分区。

基于文档分区的二级索引

在这种索引方法中，每个分区完全独立，各自维护自己的二级索引，且只负责自己分区内的文档而不关心其他分区中数据。每当需要写数据库时，包括添加，删除或更新文档等，只需要处理包含目标文档 ID 的那一个分区。因此文档分区索引也被称为本地索引，而不是全局索引。

这种查询分区数据库的方法有时也称为分散／聚集，显然这种二级索引的查询代价高昂。即使采用了并行查询，也容易导致读延迟显著放大。尽管如此，它还是被广泛应用： MongoDB 、Riak、Cassandra、Elasticsearch 、SolrCloud 和 VoltDB 都支持基于文档分区二级索引。

基于词条的二级索引分区

可以对所有的数据构建全局索引，而不是每个分区维护自己的本地索引。

为避免成为瓶颈，不能将全局索引存储在一个节点上，否则就破坏了设计分区均衡的目标。所以，全局索引也必须进行分区，且可以与数据关键字采用不同的分区策略。

可以直接通过关键词来全局划分索引，或者对其取哈希值。直接分区的好处是可以支持高效的区间查询；而采用哈希的方式则可以更均匀的划分分区。

词条索引分区 vs. 文档索引分区

优点：它的读取更为高效，客户端不需要对所有的分区都执行一遍查询，只需要向包含词条的那一个分区发出读请求。
缺点：写入速度较慢且非常复杂，主要因为单个文档的更新时，里面可能会涉及多个二级索引，而二级索引的分区又可能完全不同甚至在不同的节点上，由此势必引入显著的写放大。

理想情况下，索引应该时刻保持最新，即写入的数据要立即反映在最新的索引上。但是，对于词条分区来讲，这需要一个跨多个相关分区的分布式事务支持，写入速度会受到极大的影响，所以现有的数据库都不支持同步更新二级索引。对全局二级索引的更新往往都是异步的 。

分区再均衡

随着时间的推移，数据库可能总会出现某些变化：

查询压力增加，因此需要更多的 C PU 来处理负载。
数据规模增加，因此需要更多的磁盘和内存来存储数据。
节点可能出现故障，因此需要其他机器来接管失效的节点。

所有这些变化都要求数据和请求可以从一个节点转移到另一个节点。这样一个迁移负载的过程称为再均衡（或者动态均衡）。无论对于哪种分区方案，分区再均衡通常至少要满足：

均衡之后，负载、数据存储、读写请求等应该在集群范围更均匀地分布。
再均衡执行过程中，数据库应该可以继续正常提供读写服务。
避免不必要的负载迁移，以加快动态再均衡，井尽量减少网络和磁盘 I/O 影响。

动态再均衡的策略

为什么不用取模？

最好将哈希值划分为不同的区间范围，然后将每个区间分配给一个分区。

对节点数取模方法的问题是：如果节点数 N 发生了变化，会导致很多关键字需要从现有的节点迁移到另一个节点。

固定数量的分区

创建远超实际节点数的分区数，然后为每个节点分配多个分区。

如果集群中添加了一个新节点，该新节点可以从每个现有的节点上匀走几个分区，直到分区再次达到全局平衡。

选中的整个分区会在节点之间迁移，但分区的总数量仍维持不变，也不会改变关键字到分区的映射关系。这里唯一要调整的是分区与节点的对应关系。考虑到节点间通过网络传输数据总是需要些时间，这样调整可以逐步完成，在此期间，旧的分区仍然可以接收读写请求。

动态分区

对于采用关键字区间分区的数据库，如果边界设置有问题，最终可能会出现所有数据都挤在一个分区而其他分区基本为空，那么设定固定边界、固定数量的分区将非常不便：而手动去重新配置分区边界又非常繁琐。

一些数据库如 HBase 和 RethinkDB 等采用了动态创建分区。当分区的数据增长超过一个可配的参数阔值（ HBase 默认值是 10 GB ），它就拆分为两个分区，每个承担一半的数据量；相反，如果大量数据被删除，并且分区缩小到某个阈值以下，则将其与相邻分区进行合井。

每个分区总是分配给一个节点，而每个节点可以承载多个分区，这点与固定数量的分区一样。当一个大的分区发生分裂之后，可以将其中的一半转移到其他某节点以平衡负载。对于 HBase ，分区文件的传输需要借助 HDFS。

需要注意的是，对于一个空的数据库，因为没有任何先验知识可以帮助确定分区的边界，所以会从一个分区开始。可能数据集很小，但直到达到第一个分裂点之前，所有的写入操作都必须由单个节点来处理，而其他节点则处于空闲状态。为了缓解这个问题，HBase 和 MongoDB 允许在一个空的数据库上配置一组初始分区（这被称为预分裂）。

按节点比例分区

采用动态分区策略，拆分和合并操作使每个分区的大小维持在设定的最小值和最大值之间，因此分区的数量与数据集的大小成正比关系。另一方面，对于固定数量的分区方式，其每个分区的大小也与数据集的大小成正比。两种情况，分区的数量都与节点数无关。

Cassandra 和 Ketama 则采用了第三种方式，使分区数与集群节点数成正比关系。换句话说，每个节点具有固定数量的分区。此时，当节点数不变时，每个分区的大小与数据集大小保持正比的增长关系；当节点数增加时，分区则会调整变得更小。较大的数据量通常需要大量的节点来存储，因此这种方陆也使每个分区大小保持稳定。当一个

新节点加入集群时，它随机选择固定数量的现有分区进行分裂，然后拿走这些分区的一半数据量，将另一半数据留在原节点。随机选择分区边界的前提要求采用基于哈希分区（可以从哈希函数产生的数字范围里设置边界）。

自动与手动再平衡操作

全自动式再平衡会更加方便，它在正常维护之外所增加的操作很少。但是，也有可能出现结果难以预测的情况。再平衡总体讲是个比较昂贵的操作，它需要重新路由请求井将大量数据从一个节点迁移到另一个节点。万一执行过程中间出现异常，会使网络或节点的负载过重，井影响其他请求的性能。

将自动平衡与自动故障检测相结合也可能存在一些风险。例如，假设某个节点负载过重，对请求的响应暂时受到影响，而其他节点可能会得到结论：该节点已经失效；接下来激活自动平衡来转移其负载。客观上这会加重该节点、其他节点以及网络的负荷，可能会使总体情况变得更槽，甚至导致级联式的失效扩散。

请求路由

路由处理策略

允许客户端链接任意的节点（例如，采用循环式的负载均衡器）。如果某节点恰好拥有所请求的分区，则直接处理该请求：否则，将请求转发到下一个合适的节点，接收答复，并将答复返回给客户端。
将所有客户端的请求都发送到一个路由层，由后者负责将请求转发到对应的分区节点上。路由层本身不处理任何请求，它仅充一个分区感知的负载均衡器。
客户端感知分区和节点分配关系。此时，客户端可以直接连接到目标节点，而不需要任何中介。

许多分布式数据系统依靠独立的协调服务（如 ZooKeeper ）跟踪集群范围内的元数据。每个节点都向 ZooKeeper 中注册自己， ZooKeeper 维护了分区到节点的最终映射关系。其他参与者（如路由层或分区感知的客户端）可以向 ZooKeeper 订阅此信息。一旦分区发生了改变，或者添加、删除节点， ZooKeeper 就会主动通知路由层，这样使路由信息保持最新状态。

Linkedln的Espresso使用 Helix进行集群管理（底层是ZooKeeper ），实现了请求路由层。 HBase, SolrCloud和Kafka也使用 ZooKeeper来跟踪分区分配情况。 MongoDB有类似的设计，但它依赖于自己的配置服务器和mongos守护进程来充当路由层。

Cassandra和 Riak 在节点之间使用 gossip协议来同步群集状态的变化。请求可以发送到任何节点，由该节点负责将其转发到目标分区节点。这种方式增加了数据库节点的复杂性，但是避免了对ZooKeeper之类的外部协调服务的依赖。

小结

分区的目地是通过多台机器均匀分布数据和查询负载，避免出现热点。这需要选择合适的数据分区方案，在节点添加或删除时重新动态平衡分区。

基于关键字区间的分区 - 先对关键字进行排序，每个分区只负责一段包含最小到最大关键字范围的一段关键字。对关键字排序的优点是可以支持高效的区间查询，但是如果应用程序经常访问与排序一致的某段关键字，就会存在热点的风险。采用这种方怯，当分区太大时，通常将其分裂为两个子区间，从而动态地再平衡分区。
哈希分区 - 将哈希函数作用于每个关键字，每个分区负责一定范围的哈希值。这种方法打破了原关键字的顺序关系，它的区间查询效率比较低，但可以更均匀地分配负载。采用哈希分区时，通常事先创建好足够多（但固定数量）的分区，让每个节点承担多个分区，当添加或删除节点时将某些分区从一个节点迁移到另一个节点，也可以支持动态分区。

混合上述两种基本方法也是可行的，例如使用复合键：键的一部分来标识分区，而另一部分来记录排序后的顺序。

二级索引也需要进行分区，有两种方法：

基于文档来分区二级索引。二级索引存储在与关键字相同的分区中，这意味着写入时我们只需要更新一个分区，但缺点是读取二级索引时需要在所有分区上执行scatter/gather。
基于词条来分区二级索引。它是基于索引的值而进行的独立分区。二级索引中的条目可能包含来自关键字的多个分区里的记录。在写入时，不得不更新二级索引的多个分区；但读取时，则可以从单个分区直接快速提取数据。

第七章：事务

事务中的所有读写是一个执行的整体，整事务要么成功（提交）、要么失败（中止或回滚）。如果失败，应用程序可以安全地重试。

深入理解事务

ACID，分别代表原子性（ Atomicity ），一致性（ Consistency ），隔离性（ Isolation ）与持久性（ Durability ）的首字母。

原子性

原子是指不可分解为更小粒度的东西。

弱隔离级别

串行化

第八章：分布式系统的挑战

所有可能出错的事情一定会出错。

分布式系统中可能发生各种问题：

不可靠的网络：当通过网络发送数据包时，数据包可能会丢失或者延迟；同样，回复也可能会丢失或延迟。所以如果没有收到回复，并不能确定消息是否发送成功。
不可靠的时钟：节点的时钟可能会与其他节点存在明显的不同步（尽管尽最大努力设置了 NTP 服务器），时钟还可能会突然向前跳跃或者倒退，依靠精确的时钟存在一些风险，没有特别简单的办法来精确测量时钟的偏差范围。
进程可能在执行过程中的任意时候遭遇长度未知的暂停（一个重要的原因是垃圾回收），结果它被其他节点宣告为失效，尽管后来又恢复执行，却对中间的暂停毫无所知。

部分失效可能是分布式系统的关键特征。对于分布式环境，应该具备必要的容错能力。这样即使某些部件发生失效，系统整体还可以继续运行。

为了容忍错误，第一步是检测错误。多数系统没有检测节点是否发生故障的准确机制，因此分布式算法更多依靠超时来确定远程节点是否仍然可用。但是，超时无法区分网络和节点故障，且可变的网络延迟有时会导致节点被误判
为宕机。此外，节点可能处于一种降级状态：例如，由于驱动程序错误，千兆网络接口可能突然降到 l kb/s 的吞吐量。这样一个处于“残废”的节点比彻底挂掉的故障节点更难处理。

检测到错误之后，让系统容忍失效也不容易。在典型的分布式环境下，没有全局变量，没有共享内存，没有约定的尝试或其他跨节点的共享状态。节点甚至不太清楚现在的准确时间，更不用说其他更高级的了。信息从一个节点流动到另一个节点只能是通过不可靠的网络来发送。单个节点无住安全的做出任何决策，而是需要多个节点之
间的共识协议，井争取达到法定票数（通常为半数以上）。

第九章：一致性与共识

分布式系统最重要的抽象之一就是共识：所有的节点就某一项提议达成一致。

参考资料

数据密集型应用系统设计 - 这可能是目前最好的分布式存储书籍，强力推荐【进阶】

海量数据处理

发表于 2021-08-19 更新于 2025-09-13 分类于设计，架构，解决方案本文字数： 8.3k 阅读时长 ≈ 8 分钟

海量数据处理

如何从海量的 URL 中找出相同的 URL？

问题描述

给定 a、b 两个文件，各存放 50 亿个 URL，每个 URL 各占 64B，内存限制是 4G。请找出 a、b 两个文件共同的 URL。

解决思路

每个 URL 占 64B，那么 50 亿个 URL 占用的空间大小约为 320GB。

$$5,000,000,000 * 64 B ≈ 5 GB * 64 = 320 GB$$

由于内存大小只有 4G，因此，我们不可能一次性把所有 URL 加载到内存中处理。对于这种类型的题目，一般采用分治策略，即：把一个文件中的 URL 按照某个特征划分为多个小文件，使得每个小文件大小不超过 4G，这样就可以把这个小文件读到内存中进行处理了。

思路如下：

首先遍历文件 a，对遍历到的 URL 求 hash(URL) % 1000，根据计算结果把遍历到的 URL 存储到 a0, a1, a2, …, a999，这样每个大小约为 300MB。使用同样的方法遍历文件 b，把文件 b 中的 URL 分别存储到文件 b0, b1, b2, …, b999 中。这样处理过后，所有可能相同的 URL 都在对应的小文件中，即 a0 对应 b0, …, a999 对应 b999，不对应的小文件不可能有相同的 URL。那么接下来，我们只需要求出这 1000 对小文件中相同的 URL 就好了。

接着遍历 ai( i∈[0,999])，把 URL 存储到一个 HashSet 集合中。然后遍历 bi 中每个 URL，看在 HashSet 集合中是否存在，若存在，说明这就是共同的 URL，可以把这个 URL 保存到一个单独的文件中。

方案总结

分而治之，进行哈希取余；
对每个子文件进行 HashSet 统计。

如何从海量数据中找出高频词？

问题描述

有一个 1GB 大小的文件，文件里每一行是一个词，每个词的大小不超过 16B，内存大小限制是 1MB，要求返回频数最高的 100 个词(Top 100)。

解决思路

由于内存限制，无法直接将大文件的所有词一次读到内存中。因此，可以采用分治策略，把一个大文件分解成多个小文件，保证每个文件的大小小于 1MB，进而直接将单个小文件读取到内存中进行处理。

思路如下：

首先遍历大文件，对遍历到的每个词 x，执行 hash(x) % 5000，将结果为 i 的词存放到文件 Ai 中。遍历结束后，我们可以得到 5000 个小文件。每个小文件的大小为 200KB 左右。如果有的小文件大小仍然超过 1MB，则采用同样的方式继续进行分解。

接着统计每个小文件中出现频数最高的 100 个词。最简单的方式是使用 HashMap 来实现。其中 key 为词，value 为该词出现的频率。具体方法是：对于遍历到的词 x，如果在 map 中不存在，则执行 map.put(x, 1) 若存在，则执行 map.put(x, map.get(x)+1)，将该词频数加 1。

上面我们统计了每个小文件单词出现的频数。接下来，我们可以通过维护一个小顶堆来找出所有词中出现频数最高的 100 个。具体方法是：依次遍历每个小文件，构建一个小顶堆，堆大小为 100。如果遍历到的词的出现次数大于堆顶词的出现次数，则用新词替换堆顶的词，然后重新调整为小顶堆，遍历结束后，小顶堆上的词就是出现频数最高的 100 个词。

方案总结

分而治之，进行哈希取余；
使用 HashMap 统计频数；
求解最大的 TopN 个，用小顶堆；求解最小的 TopN 个，用大顶堆。

如何找出某一天访问百度网站最多的 IP？

问题描述

现有海量日志数据保存在一个超大文件中，该文件无法直接读入内存，要求从中提取某天访问百度次数最多的那个 IP。

解决思路

这道题只关心某一天访问百度最多的 IP，因此，可以首先对文件进行一次遍历，把这一天访问百度 IP 的相关信息记录到一个单独的大文件中。接下来采用的方法与上一题一样，大致就是先对 IP 进行哈希映射，接着使用 HashMap 统计重复 IP 的次数，最后计算出重复次数最多的 IP。

注：这里只需要找出出现次数最多的 IP，可以不必使用堆，直接用一个变量 max 即可。

方法总结

分而治之，进行哈希取余；
使用 HashMap 统计频数；
求解最大的 TopN 个，用小顶堆；求解最小的 TopN 个，用大顶堆。

如何在大量的数据中找出不重复的整数？

问题描述

在 2.5 亿个整数中找出不重复的整数。注意：内存不足以容纳这 2.5 亿个整数。

解决思路

方法一：分治法

与前面的题目方法类似，先将 2.5 亿个数划分到多个小文件，用 HashSet/HashMap 找出每个小文件中不重复的整数，再合并每个子结果，即为最终结果。

方法二：位图法

位图，就是用一个或多个 bit 来标记某个元素对应的值，而键就是该元素。采用位作为单位来存储数据，可以大大节省存储空间。

位图通过使用位数组来表示某些元素是否存在。它可以用于快速查找，判重，排序等。不是很清楚？我先举个小例子。

假设我们要对 [0,7] 中的 5 个元素 (6, 4, 2, 1, 5) 进行排序，可以采用位图法。0~7 范围总共有 8 个数，只需要 8bit，即 1 个字节。首先将每个位都置 0：

1	0 0 0 0 0 0 0 0

然后遍历 5 个元素，首先遇到 6，那么将下标为 6 的位的 0 置为 1；接着遇到 4，把下标为 4 的位的 0 置为 1：

1	0 0 0 0 1 0 1 0

依次遍历，结束后，位数组是这样的：

1	0 1 1 0 1 1 1 0

每个为 1 的位，它的下标都表示了一个数：

1
2
3

for i in range(8):
    if bits[i] == 1:
        print(i)

这样我们其实就已经实现了排序。

对于整数相关的算法的求解，位图法是一种非常实用的算法。假设 int 整数占用 4B，即 32bit，那么我们可以表示的整数的个数为 232。

那么对于这道题，我们用 2 个 bit 来表示各个数字的状态：

00 表示这个数字没出现过；
01 表示这个数字出现过一次（即为题目所找的不重复整数）；
10 表示这个数字出现了多次。

那么这 232 个整数，总共所需内存为 232*2b=1GB。因此，当可用内存超过 1GB 时，可以采用位图法。假设内存满足位图法需求，进行下面的操作：

遍历 2.5 亿个整数，查看位图中对应的位，如果是 00，则变为 01，如果是 01 则变为 10，如果是 10 则保持不变。遍历结束后，查看位图，把对应位是 01 的整数输出即可。

方法总结

判断数字是否重复的问题，位图法是一种非常高效的方法。

如何在大量的数据中判断一个数是否存在？

题目描述

给定 40 亿个不重复的没排过序的 unsigned int 型整数，然后再给定一个数，如何快速判断这个数是否在这 40 亿个整数当中？

解答思路

方法一：分治法

依然可以用分治法解决，方法与前面类似，就不再次赘述了。

方法二：位图法

40 亿个不重复整数，我们用 40 亿个 bit 来表示，初始位均为 0，那么总共需要内存：4,000,000,000b≈512M。

我们读取这 40 亿个整数，将对应的 bit 设置为 1。接着读取要查询的数，查看相应位是否为 1，如果为 1 表示存在，如果为 0 表示不存在。

方法总结

判断数字是否存在、判断数字是否重复的问题，位图法是一种非常高效的方法。

如何查询最热门的查询串？

题目描述

搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询串的长度不超过 255 字节。

假设目前有 1000w 个记录（这些查询串的重复度比较高，虽然总数是 1000w，但如果除去重复后，则不超过 300w 个）。请统计最热门的 10 个查询串，要求使用的内存不能超过 1G。（一个查询串的重复度越高，说明查询它的用户越多，也就越热门。）

解答思路

每个查询串最长为 255B，1000w 个串需要占用约 2.55G 内存，因此，我们无法将所有字符串全部读入到内存中处理。

方法一：分治法

分治法依然是一个非常实用的方法。

划分为多个小文件，保证单个小文件中的字符串能被直接加载到内存中处理，然后求出每个文件中出现次数最多的 10 个字符串；最后通过一个小顶堆统计出所有文件中出现最多的 10 个字符串。

方法可行，但不是最好，下面介绍其他方法。

方法二：HashMap 法

虽然字符串总数比较多，但去重后不超过 300w，因此，可以考虑把所有字符串及出现次数保存在一个 HashMap 中，所占用的空间为 300w*(255+4)≈777M（其中，4 表示整数占用的 4 个字节）。由此可见，1G 的内存空间完全够用。

思路如下：

首先，遍历字符串，若不在 map 中，直接存入 map，value 记为 1；若在 map 中，则把对应的 value 加 1，这一步时间复杂度 O(N)。

接着遍历 map，构建一个 10 个元素的小顶堆，若遍历到的字符串的出现次数大于堆顶字符串的出现次数，则进行替换，并将堆调整为小顶堆。

遍历结束后，堆中 10 个字符串就是出现次数最多的字符串。这一步时间复杂度 O(Nlog10)。

方法三：前缀树法（字典树）

方法二使用了 HashMap 来统计次数，当这些字符串有大量相同前缀时，可以考虑使用前缀树来统计字符串出现的次数，树的结点保存字符串出现次数，0 表示没有出现。

思路如下：

在遍历字符串时，在前缀树中查找，如果找到，则把结点中保存的字符串次数加 1，否则为这个字符串构建新结点，构建完成后把叶子结点中字符串的出现次数置为 1。

最后依然使用小顶堆来对字符串的出现次数进行排序。

方法总结

前缀树经常被用来统计字符串的出现次数。它的另外一个大的用途是字符串查找，判断是否有重复的字符串等。

如何统计不同电话号码的个数？

题目描述

已知某个文件内包含一些电话号码，每个号码为 8 位数字，统计不同号码的个数。

解答思路

这道题本质还是求解数据重复的问题，对于这类问题，一般首先考虑位图法。

对于本题，8 位电话号码可以表示的号码个数为 $$10^8$$ 个，即 1 亿个。我们每个号码用一个 bit 来表示，则总共需要 1 亿个 bit，内存占用约 100M。

思路如下：

申请一个位图数组，长度为 1 亿，初始化为 0。然后遍历所有电话号码，把号码对应的位图中的位置置为 1。遍历完成后，如果 bit 为 1，则表示这个电话号码在文件中存在，否则不存在。bit 值为 1 的数量即为不同电话号码的个数。

方法总结

求解数据重复问题，记得考虑位图法。

如何从 5 亿个数中找出中位数？

题目描述

从 5 亿个数中找出中位数。数据排序后，位置在最中间的数就是中位数。当样本数为奇数时，中位数为第 (N+1)/2 个数；当样本数为偶数时，中位数为第 N/2 个数与第 1+N/2 个数的均值。

解答思路

如果这道题没有内存大小限制，则可以把所有数读到内存中排序后找出中位数。但是最好的排序算法的时间复杂度都为 O(NlogN)。这里使用其他方法。

方法一：双堆法

维护两个堆，一个大顶堆，一个小顶堆。大顶堆中最大的数小于等于小顶堆中最小的数；保证这两个堆中的元素个数的差不超过 1。

若数据总数为偶数，当这两个堆建好之后，中位数就是这两个堆顶元素的平均值。当数据总数为奇数时，根据两个堆的大小，中位数一定在数据多的堆的堆顶。

class MedianFinder {

    private PriorityQueue<Integer> maxHeap;
    private PriorityQueue<Integer> minHeap;

    /** initialize your data structure here. */
    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        minHeap = new PriorityQueue<>(Integer::compareTo);
    }

    public void addNum(int num) {
        if (maxHeap.isEmpty() || maxHeap.peek() > num) {
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }

        int size1 = maxHeap.size();
        int size2 = minHeap.size();
        if (size1 - size2 > 1) {
            minHeap.offer(maxHeap.poll());
        } else if (size2 - size1 > 1) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        int size1 = maxHeap.size();
        int size2 = minHeap.size();

        return size1 == size2
            ? (maxHeap.peek() + minHeap.peek()) * 1.0 / 2
            : (size1 > size2 ? maxHeap.peek() : minHeap.peek());
    }
}

见 LeetCode No.295：https://leetcode.com/problems/find-median-from-data-stream/

以上这种方法，需要把所有数据都加载到内存中。当数据量很大时，就不能这样了，因此，这种方法适用于数据量较小的情况。5 亿个数，每个数字占用 4B，总共需要 2G 内存。如果可用内存不足 2G，就不能使用这种方法了，下面介绍另一种方法。

方法二：分治法

分治法的思想是把一个大的问题逐渐转换为规模较小的问题来求解。

对于这道题，顺序读取这 5 亿个数字，对于读取到的数字 num，如果它对应的二进制中最高位为 1，则把这个数字写到 f1 中，否则写入 f0 中。通过这一步，可以把这 5 亿个数划分为两部分，而且 f0 中的数都大于 f1 中的数（最高位是符号位）。

划分之后，可以非常容易地知道中位数是在 f0 还是 f1 中。假设 f1 中有 1 亿个数，那么中位数一定在 f0 中，且是在 f0 中，从小到大排列的第 1.5 亿个数与它后面的一个数的平均值。

提示，5 亿数的中位数是第 2.5 亿与右边相邻一个数求平均值。若 f1 有一亿个数，那么中位数就是 f0 中从第 1.5 亿个数开始的两个数求得的平均值。

对于 f0 可以用次高位的二进制继续将文件一分为二，如此划分下去，直到划分后的文件可以被加载到内存中，把数据加载到内存中以后直接排序，找出中位数。

注意，当数据总数为偶数，如果划分后两个文件中的数据有相同个数，那么中位数就是数据较小的文件中的最大值与数据较大的文件中的最小值的平均值。

方法总结

分治法，真香！

如何找出排名前 500 的数？

题目描述

有 20 个数组，每个数组有 500 个元素，并且有序排列。如何在这 20*500 个数中找出前 500 的数？

解答思路

对于 TopK 问题，最常用的方法是使用堆排序。对本题而言，假设数组降序排列，可以采用以下方法：

首先建立大顶堆，堆的大小为数组的个数，即为 20，把每个数组最大的值存到堆中。

接着删除堆顶元素，保存到另一个大小为 500 的数组中，然后向大顶堆插入删除的元素所在数组的下一个元素。

重复上面的步骤，直到删除完第 500 个元素，也即找出了最大的前 500 个数。

为了在堆中取出一个数据后，能知道它是从哪个数组中取出的，从而可以从这个数组中取下一个值，可以把数组的指针存放到堆中，对这个指针提供比较大小的方法。

import lombok.Data;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author https://github.com/yanglbme
 */
@Data
public class DataWithSource implements Comparable<DataWithSource> {
    /**
     * 数值
     */
    private int value;

    /**
     * 记录数值来源的数组
     */
    private int source;

    /**
     * 记录数值在数组中的索引
     */
    private int index;

    public DataWithSource(int value, int source, int index) {
        this.value = value;
        this.source = source;
        this.index = index;
    }

    /**
     *
     * 由于 PriorityQueue 使用小顶堆来实现，这里通过修改
     * 两个整数的比较逻辑来让 PriorityQueue 变成大顶堆
     */
    @Override
    public int compareTo(DataWithSource o) {
        return Integer.compare(o.getValue(), this.value);
    }
}


class Test {
    public static int[] getTop(int[][] data) {
        int rowSize = data.length;
        int columnSize = data[0].length;

        // 创建一个columnSize大小的数组，存放结果
        int[] result = new int[columnSize];

        PriorityQueue<DataWithSource> maxHeap = new PriorityQueue<>();
        for (int i = 0; i < rowSize; ++i) {
            // 将每个数组的最大一个元素放入堆中
            DataWithSource d = new DataWithSource(data[i][0], i, 0);
            maxHeap.add(d);
        }

        int num = 0;
        while (num < columnSize) {
            // 删除堆顶元素
            DataWithSource d = maxHeap.poll();
            result[num++] = d.getValue();
            if (num >= columnSize) {
                break;
            }

            d.setValue(data[d.getSource()][d.getIndex() + 1]);
            d.setIndex(d.getIndex() + 1);
            maxHeap.add(d);
        }
        return result;

    }

    public static void main(String[] args) {
        int[][] data = {
                {29, 17, 14, 2, 1},
                {19, 17, 16, 15, 6},
                {30, 25, 20, 14, 5},
        };

        int[] top = getTop(data);
        System.out.println(Arrays.toString(top)); // [30, 29, 25, 20, 19]
    }
}

方法总结

求 TopK，不妨考虑一下堆排序？

如何按照 query 的频度排序？

题目描述

有 10 个文件，每个文件大小为 1G，每个文件的每一行存放的都是用户的 query，每个文件的 query 都可能重复。要求按照 query 的频度排序。

解答思路

如果 query 的重复度比较大，可以考虑一次性把所有 query 读入内存中处理；如果 query 的重复率不高，那么可用内存不足以容纳所有的 query，这时候就需要采用分治法或其他的方法来解决。

方法一：HashMap 法

如果 query 重复率高，说明不同 query 总数比较小，可以考虑把所有的 query 都加载到内存中的 HashMap 中。接着就可以按照 query 出现的次数进行排序。

方法二：分治法

分治法需要根据数据量大小以及可用内存的大小来确定问题划分的规模。对于这道题，可以顺序遍历 10 个文件中的 query，通过 Hash 函数 hash(query) % 10 把这些 query 划分到 10 个小文件中。之后对每个小文件使用 HashMap 统计 query 出现次数，根据次数排序并写入到零外一个单独文件中。

接着对所有文件按照 query 的次数进行排序，这里可以使用归并排序（由于无法把所有 query 都读入内存，因此需要使用外排序）。

方法总结

内存若够，直接读入进行排序；
内存不够，先划分为小文件，小文件排好序后，整理使用外排序进行归并。

《极客时间教程 - 从 0 开始学微服务》笔记

发表于 2021-08-15 更新于 2025-09-13 分类于笔记，设计本文字数： 7.7k 阅读时长 ≈ 7 分钟

《极客时间教程 - 从 0 开始学微服务》笔记

到底什么是微服务？

微服务定义

微服务是由单一应用程序构成的小服务，拥有自己的进程与轻量化处理，服务依业务功能设计，以全自动的方式部署，与其他服务使用 HTTP API 通讯。同时，服务会使用最小规模的集中管理（例如 Docker）技术，服务可以用不同的编程语言与数据库等。

——Martin Fowler 和 James Lewis

单体应用的问题

部署效率低
团队协作开发成本高
单点故障问题
线上发布变慢

服务化：本地方法调用转为远程方法调用（RPC）

微服务和服务化的差异：

服务拆分粒度更细
服务独立部署、维护
服务治理要求高

从单体应用走向服务化

什么时候进行服务化拆分？

经验：开发人员超过 10 人（沟通成本变高），就可以考虑服务化拆分

服务化拆分的两种姿势

纵向拆分，从业务维度进行拆分。标准是按照业务的关联程度来决定，关联比较密切的业务适合拆分为一个微服务，而功能相对比较独立的业务适合单独拆分为一个微服务。

横向拆分，从公共且独立功能维度拆分。标准是按照是否有公共的被多个其他服务调用，且依赖的资源独立不与其他业务耦合。

服务化拆分的前置条件

服务如何定义。通过接口来约定。
服务如何发布和订阅。通过服务注册和发现。
服务如何监控。故障如何定位。服务化需要链路监控。
服务如何治理。超时和重试、流量控制。

初探微服务架构

微服务通过注册中心，实现发布订阅模式。

服务调用主要依赖几个基本组件：

服务描述：常用的服务描述方式包括 RESTful API、XML 配置以及 IDL 文件三种。
- RESTful API 代表：Swagger
- XML 代表：Dubbo
- IDL 代表：Thrift、gRPC
注册中心
- 服务提供者在启动时，根据服务发布文件中配置的发布信息向注册中心注册自己的服务。
- 服务消费者在启动时，根据消费者配置文件中配置的服务信息向注册中心订阅自己所需要的服务。
- 注册中心返回服务提供者地址列表给服务消费者。
- 当服务提供者发生变化，比如有节点新增或者销毁，注册中心将变更通知给服务消费者。
服务框架
- 通信协议：选择 TCP、UDP、HTTP，还是其他？
- 数据传输方式：同步、异步、多路复用？
- 序列化方式：JDK 序列化、Json、二进制（Protobuf、Thrift）？
服务监控
- 数据采集
- 数据处理
- 数据展示
服务追踪
工作原理：通过 requestId、spanId 分别表示一次请求、请求中的某一环节
服务治理：
- 超时、重试
- 负载均衡
- 故障转移
- 流量控制

如何发布和引用服务？

RESTful API：主要被用作 HTTP 或者 HTTPS 协议的接口定义。代表：Eureka

XML 配置：代表：Dubbo。工作步骤：

服务提供者定义接口，并实现接口。
服务提供者进程启动时，通过加载 server.xml 配置文件将接口暴露出去。
服务消费者进程启动时，通过加载 client.xml 配置文件来引入要调用的接口。

IDL 文件：IDL 就是接口描述语言（interface description language）的缩写。主要用作跨语言平台的服务之间的调用。有两种最常用的 IDL：Thrift、gRPC。

如何注册和发现服务？

微服务架构下，主要有三种角色：

服务提供者（RPC Server）
服务消费者（RPC Client）
服务注册中心（Registry）

注册中心实现方式

注册中心必须提供以下最基本的 API，例如：

服务注册接口
服务注销接口
心跳汇报接口
服务订阅接口：服务消费者通过调用服务订阅接口完成服务订阅，获取可用的服务提供者节点列表。
服务变更查询接口
服务查询接口
服务修改接口

集群部署

注册中心一般都是采用集群部署来保证高可用性，并通过分布式一致性协议来确保集群中不同节点之间的数据保持一致。

以 ZooKeeper 的工作原理为例：

每个 Server 在内存中存储了一份数据，Client 的读请求可以请求任意一个 Server。
ZooKeeper 启动时，将从实例中选举一个 leader（Paxos 协议）。
Leader 负责处理数据更新等操作（ZAB 协议）。
一个更新操作成功，当且仅当大多数 Server 在内存中成功修改。

目录存储

注册中心存储服务信息一般采用层次化的目录结构：

每个目录在 ZooKeeper 中叫作 znode，并且其有一个唯一的路径标识。
znode 可以包含数据和子 znode。
znode 中的数据可以有多个版本，比如某一个 znode 下存有多个数据版本，那么查询这个路径下的数据需带上版本信息。

服务健康状态检测

ZooKeeper 客户端和服务端维持的是一个长连接。连接成功后，会生成一个全局唯一的 Session ID，客户端定期发送心跳消息，服务端收到后重置会话超时时间。如果超时，则认为连接结束。

如果一个服务将 ZooKeeper 作为服务注册中心，一旦连接超时，ZooKeeper 会认为这个服务节点已经不可用，就会将其信息删除。

服务状态变更通知

ZooKeeper 支持 Watch 机制。服务消费者可以监听服务提供者的节点信息。一旦服务提供者的节点信息哟变化，就可以获取到变更状态。

白名单机制

通常注册中心会有多套环境，区分开发、测试、线上等环境。如果弄错了，会出现意想不到的后果，为此需要引入白名单保护机制。只有添加到注册中心白名单内的 RPC Server，才能够调用注册中心的注册接口，这样的话可以避免测试环境中的节点意外跑到线上环境中去。

如何实现 RPC 远程服务调用？

客户端和服务端如何建立网络连接？

HTTP 通信：三次握手建立连接；四次挥手断开连接
Socket 通信
- 服务器监听
- 客户端请求
- 连接确认
- 数据传输

服务端如何处理请求？

数据传输采用什么协议？

Http
Dubbo

数据该如何序列化和反序列化？

JDK
JSON
二进制（PB、Thrift 等）

如何监控微服务调用？

监控对象

客户端监控
接口监控
资源监控
基础监控

监控指标

请求量
响应时间
错误率

监控维度

全局维度
机房维度
单机维度
时间维度
重要性维度

监控关键点

数据采集
- 主动上报
- 代理收集
数据传输
- UDP
- Kafka
数据处理
- 全文检索：如 Elasticsearch
- 时序数据库：如 InfluxDB、OpenTSDB
- 流计算：如 Spark、Storm、Flink
数据展示

如何追踪微服务调用？

服务追踪的作用

定位整个系统的瓶颈点
优化链路调用
生成网络拓扑
透明传输数据

服务追踪系统原理

经典论文：Dapper, a Large-Scale Distributed Systems Tracing Infrastructure

traceId，用于标识某一次具体的请求 ID。当用户的请求进入系统后，会在 RPC 调用网络的第一层生成一个全局唯一的 traceId，并且会随着每一层的 RPC 调用，不断往后传递，这样的话通过 traceId 就可以把一次用户请求在系统中调用的路径串联起来。
spanId，用于标识一次 RPC 调用在分布式请求中的位置。当用户的请求进入系统后，处在 RPC 调用网络的第一层 A 时 spanId 初始值是 0，进入下一层 RPC 调用 B 的时候 spanId 是 0.1，继续进入下一层 RPC 调用 C 时 spanId 是 0.1.1，而与 B 处在同一层的 RPC 调用 E 的 spanId 是 0.2，这样的话通过 spanId 就可以定位某一次 RPC 请求在系统调用中所处的位置，以及它的上下游依赖分别是谁。
annotation，用于业务自定义埋点数据，可以是业务感兴趣的想上传到后端的数据，比如一次请求的用户 UID。

服务追踪系统实现

服务追踪系统可以分为三层。

数据采集层，负责数据埋点并上报。
数据处理层，负责数据的存储与计算。
数据展示层，负责数据的图形化展示。

微服务治理的手段有哪些？

服务调用失败原因：

服务提供者自身问题，如宕机、进程退出等；
网络问题

节点管理

注册中心主动摘除机制：服务提供者定时发送心跳，如果超时，注册中心把节点从服务列表中删除
服务消费者摘除机制：如果服务消费者调用服务提供者节点失败，就将这个节点从内存中保存的可用服务提供者节点列表中移除。

负载均衡

随机算法
轮询算法
最少活跃调用算法
一致性 Hash 算法

服务路由

为什么要制定路由规则呢？

业务存在灰度发布的需求
多机房就近访问的需求

如何配置路由规则

静态配置：修改服务消费者本地配置，上线后生效
动态配置：修改注册中心的配置，服务消费者在下一个同步周期之后，就会动态更新

服务容错

FailOver：失败自动切换。
FailBack：失败通知。
FailCache：失败缓存。
FailFast：快速失败。

一般情况下对于幂等的调用，可以选择 FailOver 或者 FailCache，非幂等的调用可以选择 FailBack 或者 FailFast。

Dubbo 框架里的微服务组件

服务发布和引用的实践

XML 配置方式的服务发布和引用流程

服务提供者定义接口
服务提供者发布接口
服务消费者引用接口

服务发布和引用的那些坑

如何将注册中心落地？

注册中心如何存储服务信息

服务一般会分成多个不同的分组

核心与非核心，从业务的核心程度来分。
机房，从机房的维度来分。
线上环境与测试环境，从业务场景维度来区分。

所以注册中心存储的服务信息一般包含三部分内容：分组、服务名以及节点信息，节点信息又包括节点地址和节点其他信息。

注册中心工作流程

服务提供者注册流程。
服务提供者反注册流程。
服务消费者查询流程。
服务消费者订阅变更流程。

如何注册节点

首先查看要注册的节点是否在白名单内？如果不在就抛出异常，在的话继续下一步。
其次要查看注册的 Cluster（服务的接口名）是否存在？如果不存在就抛出异常，存在的话继续下一步。
然后要检查 Service（服务的分组）是否存在？如果不存在则抛出异常，存在的话继续下一步。
最后将节点信息添加到对应的 Service 和 Cluster 下面的存储中。

如何反注册

查看 Service（服务的分组）是否存在，不存在就抛出异常，存在就继续下一步。
查看 Cluster（服务的接口名）是否存在，不存在就抛出异常，存在就继续下一步。
删除存储中 Service 和 Cluster 下对应的节点信息。
更新 Cluster 的 sign 值。

如何查询节点信息

首先从 localcache（本机内存）中查找，如果没有就继续下一步。

接着从 snapshot（本地快照）中查找，如果没有就继续下一步。

如何订阅服务变更

服务消费者从注册中心获取了服务的信息后，就订阅了服务的变化，会在本地保留 Cluster 的 sign 值。
服务消费者每隔一段时间，调用 getSign() 函数，从注册中心获取服务端该 Cluster 的 sign 值，并与本地保留的 sign 值做对比，如果不一致，就从服务端拉取新的节点信息，并更新 localcache 和 snapshot。

注册与发现的几个问题

多注册中心
并行订阅服务
批量反注册服务
服务变更信息增量更新

开源服务注册中心如何选型？

应用内注册与发现：注册中心提供服务端和客户端的 SDK，业务应用通过引入注册中心提供的 SDK，通过 SDK 与注册中心交互，来实现服务的注册和发现。典型代表：Eureka
应用外注册与发现：业务应用本身不需要通过 SDK 与注册中心打交道，而是通过其他方式与注册中心交互，间接完成服务注册与发现。典型代表：Consul

二者对比：

用内的解决方案一般适用于服务提供者和服务消费者同属于一个技术体系；
应用外的解决方案一般适合服务提供者和服务消费者采用了不同技术体系的业务场景

注册中心选型要考虑的两个问题

高可用性
数据一致性
- CP 型：牺牲可用性来保证数据强一致性。代表：ZooKeeper、Etcd、Consul
- AP 型：代表：Eureka、Nacos

而对于注册中心来说，最主要的功能是服务的注册和发现，在网络出现问题的时候，可用性的需求要远远高于数据一致性。即使因为数据不一致，注册中心内引入了不可用的服务节点，也可以通过其他措施来避免，比如客户端的快速失败机制等，只要实现最终一致性，对于注册中心来说就足够了。因此，选择 AP 型注册中心，一般更加合适。

开源 RPC 框架如何选型？

限定语言 RPC

Dubbo：仅支持 Java
Motan：仅支持 Java
Tars：仅支持 C++
Spring Cloud：仅支持 Java

跨语言 RPC

gRPC：支持 C++、Java、Python、Go、Ruby、PHP、Android Java、Objective-C 等多种语言
Thrift：支持 C++、Java、PHP、Python、Ruby、Erlang 等多种语言

如何搭建一个可靠的监控系统？

日志解决方案：ELK

时序数据库解决方案：Graphite、TICK和Prometheus

如何搭建一套适合你的服务追踪系统？

代表：Zipkin、PinPoint

如何识别服务节点是否存活？

心跳开关保护机制

问题：服务消费者同时并发访问注册中心获取最新服务信息导致注册中心带宽被打满

方案：需要一种保护机制，即使在网络频繁抖动的时候，服务消费者也不至于同时去请求注册中心获取最新的服务节点信息。

服务节点摘除保护机制

问题：服务提供者节点被大量摘除导致服务消费者没有足够的节点可以调用

方案：需要根据实际业务的情况，设定一个阈值比例，即使遇到刚才说的这种情况，注册中心也不能摘除超过这个阈值比例的节点。

静态注册中心

如何使用负载均衡算法？

负载均衡算法

随机算法
轮询算法
加权轮询算法
最少活跃连接算法
一致性 hash 算法

如何使用服务路由？

服务路由就是服务消费者在发起服务调用时，必须根据特定的规则来选择服务节点，从而满足某些特定的需求。

服务路由的应用场景

分组调用
灰度发布
流量切换
读写分离

服务路由的规则

条件路由
- 排除某个服务节点
- 白名单和黑名单功能
- 机房隔离
- 读写分离
脚本路由

服务路由的获取方式

本地配置
配置中心管理
动态下发

服务端出现故障时该如何应对？

微服务故障种类

集群故障。解决：流量控制
- 限流
- 降级
单 IDC 故障。解决：多 IDC 部署、流量切换
- 多 IDC 部署
  - 同城多活
  - 异地多活
- 流量切换
  - DNS 解析流量切换
  - RPC 流量切换
单机故障

服务调用失败时有哪些处理手段？

超时

重试

流量控制

如何管理服务配置？

配置类型：

本地配置
配置中心

配置中心代表：

如何搭建微服务治理平台？

服务管理

服务上下线
节点添加 / 删除
服务查询
服务节点查询。这个操作会调用注册中心的节点查询接口，来查询某个服务下一共有多少个节点。

服务治理

限流
降级
切流量

服务监控

问题定位

日志查询

服务运维

发布部署
弹性伸缩

微服务架构该如何落地？

（略）

微服务为什么要容器化？

微服务引入的问题

设计复杂

测试复杂

运维困难

微服务容器化运维：镜像仓库和资源调度

容器运维平台的组成部分

镜像仓库
资源调度
容器调度
服务编排

微服务容器化运维：容器调度和服务编排

容器调度系统代表：Swarm、Mesos，Kubernetes

容器调度要解决的问题

主机过滤
- 存活过滤
- 硬件过滤
调度策略
服务编排
服务依赖：代表方案：Docker Compose
服务发现
- 基于 Nginx 的服务发现
- 基于注册中心的服务发现
- 弹性伸缩

微服务容器化运维：微博容器运维平台 DCP

微服务如何实现 DevOps？

CI（Continuous Integration），持续集成。开发完成代码开发后，能自动地进行代码检查、单元测试、打包部署到测试环境，进行集成测试，跑自动化测试用例。
- 代码检查
- 单元测试
- 集成测试
CD（Continuous Deploy），持续部署。代码测试通过后，能自动部署到类生产环境中进行集成测试，测试通过后再进行小流量的灰度验证，验证通过后代码就达到线上发布的要求了，就可以把代码自动部署到线上。

如何做好微服务容量规划？

微服务容量规划的问题

服务数量众多
服务的接口表现差异巨大
服务部署的集群规模大小不同
服务之间还存在依赖关系

容量规划系统的作用是根据各个微服务部署集群的最大容量和线上实际运行的负荷，来决定各个微服务是否需要弹性扩缩容，以及需要扩缩容多少台机器。

容量规划系统实施的关键在于两点：

容量评估
- 选择合适的压测指标
  - 系统类指标：CPU、内存、I/O、带宽等
  - 服务类指标：响应时间、P999 耗时、错误率等
- 压测获取单机的最大容量
  - 单机压测
    - 通过日志回放等手段，模拟线上流量来对单机进行压测；
    - 通过 TCP-Copy 的方式，把线上机器的流量拷贝过来对单机进行压测。
  - 集群压测
- 实时和获取集群的运行负荷
调度决策
- 可以使用水位线来进行调度决策：当集群的水位线位于致命线以下时，就需要立即扩容，在扩容一定数量的机器后，水位线回到安全线以上并保持一段时间后，就可以进行缩容了。
- 扩容
  - 按数量
  - 按比例
- 缩容
- 逐步缩容
- 为了避免因扩容、缩容导致的水位线抖动，可以多次采集水位线数据，超过 60% 数据满足库哦哦让条件，才真正触发扩容。

微服务多机房部署实践

多机房负载均衡：利用七层负载均衡和四层负载均衡，将流量根据用户就近访问的原则切分流量。

多机房数据同步

主从机房架构

由主机房的处理机来更新本机房的缓存和数据库
其他机房的缓存也通过主机房的处理机来更新
从机房的数据库则通过 MySQL 的 binlog 同步主机房的数据。

独立机房架构

每个机房的处理机接收到写请求后更新各自机房的缓存
只有主机房会更新数据库
从机房的数据库则通过 MySQL 的 binlog 同步主机房的数据。

WMB 消息同步组件的功能就是把一个机房的写请求发给另外一个机房

reship，负责把本机房的写请求分发一份给别的机房。
collector，负责从别的机房读取写请求，然后再把请求转发给本机房的处理机。

实现 WMB 的消息同步功能有两种方案：

MQ：两个机房的 MQ 通过维护状态机来读写请求
RPC

多机房数据一致性

微服务混合云部署实践

跨云服务的负载均衡

当服务上云后还需要考虑把一定比例的用户请求路由到云上部署的服务

跨云服务的数据同步

私有云与公有云之间的网络隔离

一般来讲，出于安全的需要，企业内部机房同公有云机房之间的网络是隔离的，为了实现互通，需要架设专门的 VPN 网络或者专线。

数据库能否上云

数据库能否上云的关键取决于数据的隐私性。

跨云服务的容器运维

跨云的主机管理：跨云主机管理的关键点在于，如何对内部私有云的机器和公有云的 ECS 进行管理，

跨云服务发现

跨云弹性扩容

跨云服务编排

下一代微服务架构 Service Mesh

为什么需要 Service Mesh

跨语言服务调用的需要
云原生应用服务治理的需要

Service Mesh 的实现原理

Service Mesh 实现的关键点：

轻量级网络代理 SideCar，它的作用就是转发服务之间的调用；
基于 SideCar 的服务治理也被叫作 Control Plane，它的作用是向 SideCar 发送各种指令，以完成各种服务治理功能。
服务发现
负载均衡
请求路由
故障处理
安全认证
监控上报
日志记录
配额控制

Istio：Service Mesh 的代表产品

Istio 整体架构

Istio 的架构可以说由两部分组成，分别是 Proxy 和 Control Plane。

Proxy，就是前面提到的 SideCar，与应用程序部署在同一个主机上，应用程序之间的调用都通过 Proxy 来转发，目前支持 HTTP/1.1、HTTP/2、gRPC 以及 TCP 请求。
Control Plane，与 Proxy 通信，来实现各种服务治理功能，包括三个基本组件：Pilot、Mixer 以及 Citadel。

《极客时间教程 - 左耳听风》笔记

发表于 2021-08-15 更新于 2025-09-13 分类于笔记，设计本文字数： 382 阅读时长 ≈ 1 分钟

《极客时间教程 - 左耳听风》笔记

洞悉技术的本质

分布式系统架构的本质

分布式系统架构的优点：

高性能
高可用

分布式系统架构的缺点：

设计复杂
运维复杂

分布式系统的技术栈

提高性能的技术

缓存
负载均衡
异步
分片

提供可用性的技术

服务拆分
服务冗余
流量控制
高可用架构：多租户、多活架构、灾备
高可用运维：监控、DevOps

分布式系统的关键技术

服务治理
服务、资源调度
DevOps
监控

编程范式游记

分布式系统设计模式

区块链

程序员练级攻略

面试攻略

高效学习

浅度学习和深度学习

高质量的信息源和第一手的知识。
把知识连成地图，将自己的理解反述出来。
不断地反思和思辨，与不同年龄段的人讨论。
举一反三，并践行之，把知识转换成技能。

深度，归纳和坚持实践

这个技术出现的背景、初衷和目标。
这个技术的优势和劣势分别是什么
这个技术适用的场景
技术的组成部分和关键点。
技术的底层原理和关键实现。
已有的实现和它之间的对比。

高效沟通

电商

发表于 2021-08-05 更新于 2025-09-13 分类于设计，架构，解决方案本文字数： 94 阅读时长 ≈ 1 分钟

电商

基本业务架构

订单

订单服务一般不主动调用其他服务

订单服务不负责和第三方集成

订单服务不提供优惠计算或成本分摊逻辑

订单信息管理

用户
商品
收货人
收货地址
收货时间
订单状态

优惠券

典型问题

秒杀活动

超卖

《极客时间教程 - 高并发系统设计 40 问》笔记

发表于 2021-08-05 更新于 2025-09-13 分类于笔记，设计本文字数： 2.7k 阅读时长 ≈ 2 分钟

《极客时间教程 - 高并发系统设计 40 问》笔记

基础篇

高并发系统：它的通用设计方法是什么？

并发、异步、缓存

架构分层：我们为什么一定要这么做？

分层架构典型代表：

MVC（Model-View-Controller）
表现层、逻辑层和数据访问层
OSI 七层网络模型

分层的好处

分层的设计可以简化系统设计，让不同的人专注做某一层次的事情。
再有，分层之后可以做到很高的复用。
分层架构可以让我们更容易做横向扩展。

分层架构的不足

增加了代码的复杂度

系统设计目标（一）：如何提升系统性能？

讲述了性能指标和性能量化方式。

系统设计目标（二）：系统怎样做到高可用？

故障转移

健康检查：心跳检测
选举：Paxos、Raft
负载均衡

流量控制：

超时与重试
限流
降级

系统运维

灰度发布
故障演练
CI/CD

多活架构

系统设计目标（三）：如何让系统易于扩展？

拆分首先考虑的维度是业务维度

其次，当吞吐量达到单机瓶颈，针对存储做水平差费

数据库篇

池化技术：如何减少频繁创建数据库连接的性能损耗？

池化技术解决频繁创建连接、创建对象的成本

数据库优化方案（一）：查询请求增加时，如何做主从分离？

读写分离：写入时只写主库，在读数据时只读从库。通常采用一主多从架构。

读写分离的问题：主从同步的延迟

读写分离的关键：

主从复制
读写流量分发
代理：Cobar、Mycat
客户端：sharding-jdbc、TDDL

数据库优化方案（二）：写入数据量增加时，如何实现分库分表？

垂直拆分：从业务维度，将表分为不同的库

水平拆分：分区 key 是关键。应使用合理策略，分库分表。如：hash 取 mod 法、范围划分

发号器：如何保证分库分表后 ID 的全局唯一性？

分布式 ID：UUID、Snowflake 算法

NoSQL：在高并发场景下，数据库和 NoSQL 如何做到互补？

LSM 树：牺牲了一定的读性能来换取写入数据的高性能，Hbase、Cassandra、LevelDB 都是用这种算法作为存储的引擎。

数据首先会写入到一个叫做 MemTable 的内存结构中，在 MemTable 中数据是按照写入的 Key 来排序的。为了防止 MemTable 里面的数据因为机器掉电或者重启而丢失，一般会通过写 Write Ahead Log 的方式将数据备份在磁盘上。

MemTable 在累积到一定规模时，它会被刷新生成一个新的文件，我们把这个文件叫做 SSTable（Sorted String Table）。当 SSTable 达到一定数量时，我们会将这些 SSTable 合并，减少文件的数量，因为 SSTable 都是有序的，所以合并的速度也很快。

当从 LSM 树里面读数据时，我们首先从 MemTable 中查找数据，如果数据没有找到，再从 SSTable 中查找数据。因为存储的数据都是有序的，所以查找的效率是很高的，只是因为数据被拆分成多个 SSTable，所以读取的效率会低于 B+ 树索引。

缓存篇

缓存：数据库成为瓶颈后，动态数据的查询要如何加速？

缓存分类：静态缓存、进程内缓存、分布式缓存

缓存的使用姿势（一）：如何选择缓存的读写策略？

Cache Aside（旁路缓存）策略

先写表，再写缓存，可能会导致缓存和数据库数据不一致

更新表，删除缓存 key；读数据时，从表中读取。

读策略的步骤

从缓存中读取数据；
如果缓存命中，则直接返回数据；
如果缓存不命中，则从数据库中查询数据；
查询到数据后，将数据写入到缓存中，并且返回给用户。

写策略的步骤

更新数据库中的记录；
删除缓存记录。

Cache Aside 理论上还是有较小概率导致数据不一致。

Cache Aside 存在的最大的问题是当写入比较频繁时，缓存中的数据会被频繁地清理，这样会对缓存的命中率有一些影响。

如果你的业务对缓存命中率有严格的要求，那么可以考虑两种解决方案：

一种做法是在更新数据时也更新缓存，只是在更新缓存前先加一个分布式锁，因为这样在同一时间只允许一个线程更新缓存，就不会产生并发问题了。当然这么做对于写入的性能会有一些影响；
另一种做法同样也是在更新数据时更新缓存，只是给缓存加一个较短的过期时间，这样即使出现缓存不一致的情况，缓存的数据也会很快地过期，对业务的影响也是可以接受。

Read/Write Through（读穿 / 写穿）策略

Write Back（写回）策略

核心思想是在写入数据时只写入缓存，并且把缓存块儿标记为“脏”的。而脏块儿只有被再次使用时才会将其中的数据写入到后端存储中。

这种策略不能被应用到我们常用的数据库和缓存的场景中，它是计算机体系结构中的设计，比如我们在向磁盘中写数据时采用的就是这种策略。

但因为缓存一般使用内存，而内存是非持久化的，所以一旦缓存机器掉电，就会造成原本缓存中的脏块儿数据丢失。所以你会发现系统在掉电之后，之前写入的文件会有部分丢失，就是因为 Page Cache 还没有来得及刷盘造成的。

缓存的使用姿势（二）：缓存如何做到高可用？

分布式缓存的高可用方案

客户端方案：在客户端配置多个缓存的节点，通过缓存写入和读取算法策略来实现分布式，从而提高缓存的可用性。
代理层方案：客户端所有的写入和读取的请求都通过代理层，而代理层中会内置高可用策略，帮助提升缓存系统的高可用。
服务度方案：Redis Sentinel 方案

缓存的使用姿势（三）：缓存穿透了怎么办？

缓存穿透解決方案：

保存 null 值
布隆过滤器

消息队列篇

消息队列：秒杀时如何处理每秒上万次的下单请求？

削峰、异步处理、系统解耦

消息投递：如何保证消息仅仅被消费一次？

系统架构：每秒 1 万次请求的系统要做服务化拆分吗？

系统中，使用的资源出现扩展性问题，尤其是数据库的连接数出现瓶颈；

大团队共同维护一套代码，带来研发效率的降低，和研发成本的提升；

系统部署成本越来越高。

微服务架构：微服务化后，系统架构要如何改造？

服务拆分时要遵循哪些原则？

服务的边界如何确定？服务的粒度是怎样呢？

在服务化之后，会遇到哪些问题呢？我们又将如何来解决？

分布式服务篇

维护篇

给系统加上眼睛：服务端监控要怎么做？

CPU、内存、磁盘、网络

道路千万条，监控第一条，监控不到位，领导两行泪

监控指标

采集方式

Agent
埋点
日志

处理和展示

应用性能管理：用户的使用体验应该如何监控？

压力测试：怎样设计全链路压力测试平台？

配置管理：成千上万的配置项要如何管理？

配置存储是分级的，有公共配置，有个性的配置，一般个性配置会覆盖公共配置，这样可以减少存储配置项的数量；
配置中心可以提供配置变更通知的功能，可以实现配置的热更新；
配置中心关注的性能指标中，可用性的优先级是高于性能的，一般我们会要求配置中心的可用性达到 99.999%，甚至会是 99.9999%。

实战篇

分布式算法 Gossip

发表于 2021-07-13 更新于 2025-09-13 分类于分布式，分布式综合本文字数： 3.1k 阅读时长 ≈ 3 分钟

分布式算法 Gossip

Gossip 也叫 Epidemic Protocol （流行病协议），这个协议基于最终一致性以及去中心化设计思想。主要用于分布式节点之间进行信息交换和数据同步，这种场景的一个最大特点就是组成的网络的节点都是对等节点，是非结构化网络（去中心化）。

Gossip 协议最早是在 1987 年发表在 ACM 上的论文《Epidemic Algorithms for Replicated Database Maintenance》中被提出，其理论基础来源于流行病学的数学模型，这种场景的一个最大特点就是组成的网络的节点都是去中心化的对等节点，在信息同步过程中不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，实现最终一致性协议。

Gossip 协议是集群中节点相互通信的内部通信技术。 Gossip 是一种高效、轻量级、可靠的节点间广播协议，用于传播数据。它是去中心化的、“流行病”的、容错的和点对点通信协议。

Gossip 的应用

在 Cassandra 中，节点间使用 Gossip 协议交换信息，因此所有节点都可以快速了解集群中的所有其他节点。

Consul 使用名为 SERF 的 Gossip 协议有两个作用：

发现新节点和宕机的节点
可靠且快速的事件广播，用于选举 Leader 等

Gossip 的执行过程

Gossip 协议在概念上非常简单，代码也非常简单。它们背后的基本思想是：一个节点想要与网络中的其他节点共享一些信息。然后周期性地从节点集中随机选择一个节点并交换信息。接收信息的节点做同样的事情。信息定期发送到 N 个目标，N 称为扇出（Fanout）。

循环：传播信息的回合数
扇出：一个节点在每个循环中闲聊的节点数。当一个节点想要广播一条消息时，它从系统中随机选择 t 个节点并将消息发送给它们。

Gossip 协议的执行过程：

Gossip 过程是由种子节点发起，当一个种子节点有状态需要更新到网络中的其他节点时，它会随机的选择周围几个节点散播消息，收到消息的节点也会重复该过程，直至最终网络中所有的节点都收到了消息。这个过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。

为了表述清楚，我们先做一些前提设定

种子节点周期性的散播消息，把周期限定为 1 秒
被感染节点随机选择 N 个邻接节点（fan-out）散播消息，这里把 fan-out 设置为 3，每次最多往 3 个节点散播。
节点只接收消息不反馈结果。
每次散播消息都选择尚未发送过的节点进行散播
收到消息的节点不再往发送节点散播，比如 A -> B，那么 B 进行散播的时候，不再发给 A。

注意：Gossip 过程是异步的，也就是说发消息的节点不会关注对方是否收到，即不等待响应；不管对方有没有收到，它都会每隔 1 秒向周围节点发消息。异步是它的优点，而消息冗余则是它的缺点。

Goosip 协议的信息传播和扩散通常需要由种子节点发起。整个传播过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。

Gossip 类型

Gossip 有两种类型：

**Anti-Entropy(反熵)**：以固定的概率传播所有的数据。Anti-Entropy 是 SI model，节点只有两种状态，Suspective 和 Infective，叫做 simple epidemics。
**Rumor-Mongering(谣言传播)**：仅传播新到达的数据。Rumor-Mongering 是 SIR model，节点有三种状态，Suspective，Infective 和 Removed，叫做 complex epidemics。

熵是物理学上的一个概念，代表杂乱无章，而反熵就是在杂乱无章中寻求一致。本质上，反熵是一种通过异步修复实现最终一致性的方法。反熵指的是集群中的节点，每隔段时间就随机选择某个其他节点，然后通过互相交换自己的所有数据来消除两者之间的差异，实现数据的最终一致性。由于消息会不断反复的交换，因此消息数量是非常庞大的，无限制的（unbounded），这对一个系统来说是一个巨大的开销。所以，反熵不适合动态变化或节点数比较多的分布式环境。

谣言传播模型指的是当一个节点有了新数据后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新数据，直到所有的节点都存储了该新数据。在谣言传播模型下，消息可以发送得更频繁，因为消息只包含最新 update，体积更小。而且，一个谣言消息在某个时间点之后会被标记为 removed，并且不再被传播，因此，谣言传播模型下，系统有一定的概率会不一致。而由于，谣言传播模型下某个时间点之后消息不再传播，因此消息是有限的，系统开销小。

一般来说，为了在通信代价和可靠性之间取得折中，需要将这两种方法结合使用。

Gossip 中的通信模式

在 Gossip 协议下，网络中两个节点之间有三种通信方式:

Push - 节点 A 将数据 (key,value,version) 及对应的版本号推送给 B 节点，B 节点更新 A 中比自己新的数据
Pull - A 仅将数据 key, version 推送给 B，B 将本地比 A 新的数据（Key, value, version）推送给 A，A 更新本地
Push/Pull - 与 Pull 类似，只是多了一步，A 再将本地比 B 新的数据推送给 B，B 则更新本地

如果把两个节点数据同步一次定义为一个周期，则在一个周期内，Push 需通信 1 次，Pull 需 2 次，Push/Pull 则需 3 次。虽然消息数增加了，但从效果上来讲，Push/Pull 最好，理论上一个周期内可以使两个节点完全一致。直观上，Push/Pull 的收敛速度也是最快的。

Gossip 的特点

Gossip 的优点

扩展性：网络可以允许节点的任意增加和减少，新增加的节点的状态最终会与其他节点一致。
容错：网络中任何节点的宕机和重启都不会影响 Gossip 消息的传播，Gossip 协议具有天然的分布式系统容错特性。
去中心化：Gossip 协议不要求任何中心节点，所有节点都可以是对等的，任何一个节点无需知道整个网络状况，只要网络是连通的，任意一个节点就可以把消息散播到全网。
一致性收敛：Gossip 协议中的消息会以一传十、十传百一样的指数级速度在网络中快速传播，因此系统状态的不一致可以在很快的时间内收敛到一致。消息传播速度达到了 logN。
简单：Gossip 协议的过程极其简单，实现起来几乎没有太多复杂性。

Gossip 的缺陷

分布式网络中，没有一种完美的解决方案，Gossip 协议跟其他协议一样，也有一些不可避免的缺陷，主要是两个：

消息的延迟：由于 Gossip 协议中，节点只会随机向少数几个节点发送消息，消息最终是通过多个轮次的散播而到达全网的，因此使用 Gossip 协议会造成不可避免的消息延迟。不适合用在对实时性要求较高的场景下。
消息冗余：Gossip 协议规定，节点会定期随机选择周围节点发送消息，而收到消息的节点也会重复该步骤，因此就不可避免的存在消息重复发送给同一节点的情况，造成了消息的冗余，同时也增加了收到消息的节点的处理压力。而且，由于是定期发送，因此，即使收到了消息的节点还会反复收到重复消息，加重了消息的冗余。

参考资料

Java 编码和加密

发表于 2021-05-24 更新于 2025-09-13 分类于 Java ， JavaCore ，高级特性本文字数： 27k 阅读时长 ≈ 25 分钟

Java 编码和加密

关键词：Base64、消息摘要、数字签名、对称加密、非对称加密、MD5、SHA、HMAC、AES、DES、DESede、RSA

Base64 编码

Base64 原理

Base64 内容传送编码是一种以任意 8 位字节序列组合的描述形式，这种形式不易被人直接识别。

Base64 是一种很常见的编码规范，其作用是将二进制序列转换为人类可读的 ASCII 字符序列，常用在需用通过文本协议（比如 HTTP 和 SMTP）来传输二进制数据的情况下。Base64 并不是加密解密算法，尽管我们有时也听到使用 Base64 来加密解密的说法，但这里所说的加密与解密实际是指编码（encode）和解码（decode）的过程，其变换是非常简单的，仅仅能够避免信息被直接识别。

Base64 算法主要是将给定的字符以字符编码(如 ASCII 码，UTF-8 码)对应的十进制数为基准，做编码操作：

将给定的字符串以字符为单位，转换为对应的字符编码。
将获得字符编码转换为二进制
对二进制码做分组转换，每 3 个字节为一组，转换为每 4 个 6 位二进制位一组（不足 6 位时低位补 0）。这是一个分组变化的过程，3 个 8 位二进制码和 4 个 6 位二进制码的长度都是 24 位（38 = 46 = 24）。
对获得的 4-6 二进制码补位，向 6 位二进制码添加 2 位高位 0，组成 4 个 8 位二进制码。
对获得的 4-8 二进制码转换为十进制码。
将获得的十进制码转换为 Base64 字符表中对应的字符。

Base64 编码表

索引	对应字符	索引	对应字符	索引	对应字符	索引	对应字符
0	A	17	R	34	i	51	z
1	B	18	S	35	j	52	0
2	C	19	T	36	k	53	1
3	D	20	U	37	l	54	2
4	E	21	V	38	m	55	3
5	F	22	W	39	n	56	4
6	G	23	X	40	o	57	5
7	H	24	Y	41	p	58	6
8	I	25	Z	42	q	59	7
9	J	26	a	43	r	60	8
10	K	27	b	44	s	61	9
11	L	28	c	45	t	62	+
12	M	29	d	46	u	63	/
13	N	30	e	47	v
14	O	31	f	48	w
15	P	32	g	49	x
16	Q	33	h	50	y

Base64 应用

Base64 编码可用于在 HTTP 环境下传递较长的标识信息。在其他应用程序中，也常常需要把二进制数据编码为适合放在 URL(包括隐藏表单域)中的形式。此时，采用 Base64 编码具有不可读性，即所编码的数据不会被人用肉眼所直接看到，算是起到一个加密的作用。

然而，标准的 Base64 并不适合直接放在 URL 里传输，因为 URL 编码器会把标准 Base64 中的 / 和 + 字符变为形如 %XX 的形式，而这些 % 号在存入数据库时还需要再进行转换，因为 ANSI SQL 中已将 % 号用作通配符。

为解决此问题，可采用一种用于 URL 的改进 Base64 编码，它不仅在末尾填充 = 号，并将标准 Base64 中的“+”和“/”分别改成了 - 和 _，这样就免去了在 URL 编解码和数据库存储时所要作的转换，避免了编码信息长度在此过程中的增加，并统一了数据库、表单等处对象标识符的格式。

另有一种用于正则表达式的改进 Base64 变种，它将 + 和 / 改成了 ! 和 -，因为 +, * 以及前面在 IRCu 中用到的 [ 和 ] 在正则表达式中都可能具有特殊含义。

【示例】java.util.Base64 编码、解码示例

Base64.getEncoder() 和 Base64.getDecoder() 提供了的是标准的 Base64 编码、解码方式；

Base64.getUrlEncoder() 和 Base64.getUrlDecoder() 提供了 URL 安全的 Base64 编码、解码方式（将 + 和 / 替换为 - 和 _）。

import java.nio.charset.StandardCharsets;
import java.util.Base64;

public class Base64Demo {

    public static void main(String[] args) {
        String url = "https://www.baidu.com";
        System.out.println("url:" + url);
        // 标准的 Base64 编码、解码
        byte[] encoded = Base64.getEncoder().encode(url.getBytes(StandardCharsets.UTF_8));
        byte[] decoded = Base64.getDecoder().decode(encoded);
        System.out.println("Url Safe Base64 encoded:" + new String(encoded));
        System.out.println("Url Safe Base64 decoded:" + new String(decoded));
        // URL 安全的 Base64 编码、解码
        byte[] encoded2 = Base64.getUrlEncoder().encode(url.getBytes(StandardCharsets.UTF_8));
        byte[] decoded2 = Base64.getUrlDecoder().decode(encoded2);
        System.out.println("Base64 encoded:" + new String(encoded2));
        System.out.println("Base64 decoded:" + new String(decoded2));
    }

}

输出：

url:https://www.baidu.com
Url Safe Base64 encoded:aHR0cHM6Ly93d3cuYmFpZHUuY29t
Url Safe Base64 decoded:https://www.baidu.com
Base64 encoded:aHR0cHM6Ly93d3cuYmFpZHUuY29t
Base64 decoded:https://www.baidu.com

消息摘要

消息摘要概述

消息摘要，其实就是将需要摘要的数据作为参数，经过哈希函数(Hash)的计算，得到的散列值。

消息摘要是一个唯一对应一个消息或文本的固定长度的值，它由一个单向 Hash 加密函数对消息进行作用而产生。如果消息在途中改变了，则接收者通过对收到消息的新产生的摘要与原摘要比较，就可知道消息是否被改变了。因此消息摘要保证了消息的完整性。消息摘要采用单向 Hash 函数将需加密的明文”摘要”成一串密文，这一串密文亦称为数字指纹(Finger Print)。它有固定的长度，且不同的明文摘要成密文，其结果总是不同的，而同样的明文其摘要必定一致。这样这串摘要便可成为验证明文是否是”真身”的”指纹”了。

消息摘要特点

唯一性：数据只要有一点改变，那么再通过消息摘要算法得到的摘要也会发生变化。虽然理论上有可能会发生碰撞，但是概率极其低。
不可逆：消息摘要算法的密文无法被解密。
不需要密钥，可使用于分布式网络。
无论输入的明文有多长，计算出来的消息摘要的长度总是固定的。

消息摘要常用算法

消息摘要算法包括**MD(Message Digest，消息摘要算法)、SHA(Secure Hash Algorithm，安全散列算法)、MAC(Message AuthenticationCode，消息认证码算法)**共 3 大系列，常用于验证数据的完整性，是数字签名算法的核心算法。

MD5和SHA1分别是MD、SHA算法系列中最有代表性的算法。

如今，MD5 已被发现有许多漏洞，从而不再安全。SHA 算法比 MD 算法的摘要长度更长，也更加安全。

消息摘要应用

MD5、SHA 的范例

JDK 中使用 MD5 和 SHA 这两种消息摘要的方式基本一致，步骤如下：

初始化 MessageDigest 对象
更新要计算的内容
生成摘要

import java.security.MessageDigest;
import java.util.Base64;

public class MessageDigestDemo {

    public static byte[] encode(byte[] input, Type type) throws Exception {
        // 根据类型，初始化消息摘要对象
        MessageDigest md5Digest = MessageDigest.getInstance(type.getName());

        // 更新要计算的内容
        md5Digest.update(input);

        // 完成哈希计算，返回摘要
        return md5Digest.digest();
    }

    public static byte[] encodeWithBase64(byte[] input, Type type) throws Exception {
        return Base64.getUrlEncoder().encode(encode(input, type));
    }

    public static String encodeWithBase64String(byte[] input, Type type) throws Exception {
        return Base64.getUrlEncoder().encodeToString(encode(input, type));
    }

    public enum Type {
        MD2("MD2"),
        MD5("MD5"),
        SHA1("SHA1"),
        SHA256("SHA-256"),
        SHA384("SHA-384"),
        SHA512("SHA-512");

        private String name;

        Type(String name) {
            this.name = name;
        }

        public String getName() {
            return this.name;
        }
    }

    public static void main(String[] args) throws Exception {
        String msg = "Hello World!";
        System.out.println("MD2: " + encodeWithBase64String(msg.getBytes(), Type.MD2));
        System.out.println("MD5: " + encodeWithBase64String(msg.getBytes(), Type.MD5));
        System.out.println("SHA1: " + encodeWithBase64String(msg.getBytes(), Type.SHA1));
        System.out.println("SHA256: " + encodeWithBase64String(msg.getBytes(), Type.SHA256));
        System.out.println("SHA384: " + encodeWithBase64String(msg.getBytes(), Type.SHA384));
        System.out.println("SHA512: " + encodeWithBase64String(msg.getBytes(), Type.SHA512));
    }

}

【输出】

MD2: MV98ZyI_Aft8q0uVEA6HLg==
MD5: 7Qdih1MuhjZehB6Sv8UNjA==
SHA1: Lve95gjOVATpfV8EL5X4nxwjKHE=
SHA256: f4OxZX_x_FO5LcGBSKHWXfwtSx-j1ncoSt3SABJtkGk=
SHA384: v9dsDrvQBv7lg0EFR8GIewKSvnbVgtlsJC0qeScj4_1v0GH51c_RO4-WE1jmrbpK
SHA512: hhhE1nBOhXP-w02WfiC8_vPUJM9IvgTm3AjyvVjHKXQzcQFerYkcw88cnTS0kmS1EHUbH_nlN5N7xGtdb_TsyA==

HMAC 的范例


import java.nio.charset.StandardCharsets;
import java.util.Base64;
import javax.crypto.Mac;
import javax.crypto.spec.SecretKeySpec;

public class HmacMessageDigest {

    public static void main(String[] args) throws Exception {
        String msg = "Hello World!";
        byte[] salt = "My Salt".getBytes(StandardCharsets.UTF_8);
        System.out.println("原文: " + msg);
        System.out.println("HmacMD5: " + encodeWithBase64String(msg.getBytes(), salt, HmacTypeEn.HmacMD5));
        System.out.println("HmacSHA1: " + encodeWithBase64String(msg.getBytes(), salt, HmacTypeEn.HmacSHA1));
        System.out.println("HmacSHA256: " + encodeWithBase64String(msg.getBytes(), salt, HmacTypeEn.HmacSHA256));
        System.out.println("HmacSHA384: " + encodeWithBase64String(msg.getBytes(), salt, HmacTypeEn.HmacSHA384));
        System.out.println("HmacSHA512: " + encodeWithBase64String(msg.getBytes(), salt, HmacTypeEn.HmacSHA512));
    }

    public static byte[] encode(byte[] plaintext, byte[] salt, HmacTypeEn type) throws Exception {
        SecretKeySpec keySpec = new SecretKeySpec(salt, type.name());
        Mac mac = Mac.getInstance(keySpec.getAlgorithm());
        mac.init(keySpec);
        return mac.doFinal(plaintext);
    }

    public static byte[] encodeWithBase64(byte[] plaintext, byte[] salt, HmacTypeEn type) throws Exception {
        return Base64.getUrlEncoder().encode(encode(plaintext, salt, type));
    }

    public static String encodeWithBase64String(byte[] plaintext, byte[] salt, HmacTypeEn type) throws Exception {
        return Base64.getUrlEncoder().encodeToString(encode(plaintext, salt, type));
    }

    /**
     * JDK支持 HmacMD5, HmacSHA1, HmacSHA256, HmacSHA384, HmacSHA512
     */
    public enum HmacTypeEn {

        HmacMD5, HmacSHA1, HmacSHA256, HmacSHA384, HmacSHA512;
    }

}

输出

原文: Hello World!
HmacMD5: re6BLRsB1Q26SfJTwXZUSQ==
HmacSHA1: CFu8a9H6CbY9C5fo0OmJ2bnuILM=
HmacSHA256: Z1czUqDWWfYYl7qEDJ2sUH6iieHVI7o83dXMl0JYER0=
HmacSHA384: 34mKtRQBOYnwwznmQubjrDk_MsLDGqM2PmgcplZUpLsKNrG_cwfz4bLPJCbBW88b
HmacSHA512: 6n77htTZ_atc04-SsmxhSK3wzh1sAmdudCl0Cb_RZp4DpienG4LZkhXMbq8lcK7XSnz6my_wIpnStDp6PC_-5w==

数字签名

数字签名概述

数字签名算法可以看做是一种带有密钥的消息摘要算法，并且这种密钥包含了公钥和私钥。也就是说，数字签名算法是非对称加密算法和消息摘要算法的结合体。

数字签名算法要求能够验证数据完整性、认证数据来源，并起到抗否认的作用。

数字签名算法包含签名和验证两项操作，遵循私钥签名，公钥验证的方式。

签名时要使用私钥和待签名数据，验证时则需要公钥、签名值和待签名数据，其核心算法主要是消息摘要算法。

数字签名常用算法：RSA、DSA、ECDSA

数字签名算法应用

DSA 的范例

数字签名有两个流程：签名和验证。

它们的前提都是要有一个公钥、密钥对。

数字签名用私钥为消息计算签名。

【示例】用公钥验证摘要

public class DsaCoder {

    public static final String KEY_ALGORITHM = "DSA";

    public static final String SIGN_ALGORITHM = "SHA1withDSA";

    /**
     * DSA密钥长度默认1024位。 密钥长度必须是64的整数倍，范围在512~1024之间
     */
    private static final int KEY_SIZE = 1024;

    private KeyPair keyPair;

    public DsaCoder() throws Exception {
        this.keyPair = initKey();
    }

    private KeyPair initKey() throws Exception {
        // 初始化密钥对生成器
        KeyPairGenerator keyPairGen = KeyPairGenerator.getInstance(DsaCoder.KEY_ALGORITHM);
        // 实例化密钥对生成器
        keyPairGen.initialize(KEY_SIZE);
        // 实例化密钥对
        return keyPairGen.genKeyPair();
    }

    public byte[] signature(byte[] data, byte[] privateKey) throws Exception {
        PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(privateKey);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        PrivateKey key = keyFactory.generatePrivate(keySpec);

        Signature signature = Signature.getInstance(SIGN_ALGORITHM);
        signature.initSign(key);
        signature.update(data);
        return signature.sign();
    }

    public byte[] getPrivateKey() {
        return keyPair.getPrivate().getEncoded();
    }

    public boolean verify(byte[] data, byte[] publicKey, byte[] sign) throws Exception {
        X509EncodedKeySpec keySpec = new X509EncodedKeySpec(publicKey);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        PublicKey key = keyFactory.generatePublic(keySpec);

        Signature signature = Signature.getInstance(SIGN_ALGORITHM);
        signature.initVerify(key);
        signature.update(data);
        return signature.verify(sign);
    }

    public byte[] getPublicKey() {
        return keyPair.getPublic().getEncoded();
    }

    public static void main(String[] args) throws Exception {
        String msg = "Hello World";
        DsaCoder dsa = new DsaCoder();
        byte[] sign = dsa.signature(msg.getBytes(), dsa.getPrivateKey());
        boolean flag = dsa.verify(msg.getBytes(), dsa.getPublicKey(), sign);
        String result = flag ? "数字签名匹配" : "数字签名不匹配";
        System.out.println("数字签名：" + Base64.getUrlEncoder().encodeToString(sign));
        System.out.println("验证结果：" + result);
    }

}

【输出】

1 2	数字签名：MCwCFDPUO_VrONl5ST0AWary-MLXJuSCAhRMeMnUVhpizfa2H2M37tne0pUtoA== 验证结果：数字签名匹配

对称加密

对称加密概述

对称加密算法主要有 DES、3DES（TripleDES）、AES、IDEA、RC2、RC4、RC5 和 Blowfish 等。

对称加密算法是应用较早的加密算法，技术成熟。在对称加密算法中，数据发信方将明文（原始数据）和加密密钥（mi yao）一起经过特殊加密算法处理后，使其变成复杂的加密密文发送出去。收信方收到密文后，若想解读原文，则需要使用加密用过的密钥及相同算法的逆算法对密文进行解密，才能使其恢复成可读明文。在对称加密算法中，使用的密钥只有一个，发收信双方都使用这个密钥对数据进行加密和解密，这就要求解密方事先必须知道加密密钥。

对称加密特点：

优点：计算量小、加密速度快、加密效率高。
缺点：算法是公开的，安全性得不到保证。

通信双方每次使用对称加密算法时，都需要使用其他人不知道的惟一密钥，这会使得通信双方所拥有的密钥数量呈几何级数增长，密钥管理成为用户的负担。对称加密算法在分布式网络系统上使用较为困难，主要是因为密钥管理困难，使用成本较高。

而与公钥、密钥加密算法比起来，对称加密算法能够提供加密和认证却缺乏了签名功能，使得使用范围有所缩小。

对称加密原理

对称加密要求加密与解密使用同一个密钥，解密是加密的逆运算。由于加密、解密使用同一个密钥，这要求通信双方必须在通信前商定该密钥，并妥善保存该密钥。

对称加密体制分为两种：

一种是对明文的单个位（或字节）进行运算，称为流密码，也称为序列密码；

一种是把明文信息划分为不同的组（或块）结构，分别对每个组（或块）进行加密、解密，称为分组密码。

假设甲乙方作为通信双方。假定甲乙双方在消息传递前已商定加密算法，欲完成一次消息传递需要经过如下步骤。

对称加密工作模式

以 DES 算法的工作模式为例，DES 算法根据其加密算法所定义的明文分组的大小（56 位），将数据分割成若干 56 位的加密区块，再以加密区块为单位，分别进行加密处理。如果最后剩下不足一个区块的大小，称之为短块。短块的处理方法有填充法、流密码加密法、密文挪用技术。

根据数据加密时每个加密区块见得关联方式来区分，可以分为以下种工作模式：

(1) 电子密码本模式(Electronic Code Book, ECB)

用途：适合加密密钥，随机数等短数据。例如，安全地传递 DES 密钥，ECB 是最合适的模式。

(2) 密文链接模式(Cipher Booki Chaining, CBC)

用途：可加密任意长度的数据，适用于计算产生检测数据完整性的消息认证 MAC。

(3) 密文反馈模式(Cipher Feed Back, CFB)

用途：因错误传播无界，可以用于检查发现明文密文的篡改。

(4) 输出反馈模式(Output Feed Back, OFB)

用途：使用于加密冗余性较大的数据，比如语音和图像数据。

AES 算法除了以上 4 中模式外，还有一种新的工作模式：

(5) 计数器模式(Counter, CTR)

用途：适用于各种加密应用。

本文对于各种工作模式的原理展开描述。个人认为，作为工程应用，了解其用途即可。

对称加密填充方法

Java 中对称加密对于短块的处理，一般是采用填充方式。

常采用的是：NoPadding（不填充）、Zeros 填充（0 填充）、PKCS5Padding 填充。

ZerosPadding

方式：全部填充为 0 的字节

结果如下：

F1 F2 F3 F4 F5 F6 F7 F8 //第一块

F9 00 00 00 00 00 00 00 //第二块

PKCS5Padding

方式：每个填充的字节都记录了填充的总字节数

结果如下：

F1 F2 F3 F4 F5 F6 F7 F8 //第一块

F9 07 07 07 07 07 07 07 //第二块

对称加密应用

基于密钥加密的流程（DES、DESede、AES 和 IDEA）

DES、DESede、AES 和 IDEA 等算法都是基于密钥加密的对称加密算法，它们的实现流程也基本一致。步骤如下：

（1）生成密钥

KeyGenerator kg = KeyGenerator.getInstance("DES");
SecureRandom random = new SecureRandom();
kg.init(random);
SecretKey secretKey = kg.generateKey();

建议使用随机数来初始化密钥的生成。

（2）初始化密码对象

1 2	Cipher cipher = Cipher.getInstance("DES/ECB/PKCS5Padding"); cipher.init(Cipher.ENCRYPT_MODE, secretKey);

ENCRYPT_MODE：加密模式

DECRYPT_MODE：解密模式

（3）执行

1 2	String plaintext = "Hello World"; byte[] ciphertext = cipher.doFinal(plaintext.getBytes());

一个完整的 DES 加密解密范例

import java.nio.charset.StandardCharsets;
import java.security.*;
import java.util.Base64;
import javax.crypto.*;
import javax.crypto.spec.IvParameterSpec;

/**
 * DES安全编码：是经典的对称加密算法。密钥仅56位，且迭代次数偏少。已被视为并不安全的加密算法。
 *
 * @author Zhang Peng
 * @since 2016年7月14日
 */
public class DESCoder {

    public static final String KEY_ALGORITHM_DES = "DES";

    public static final String CIPHER_DES_DEFAULT = "DES";

    public static final String CIPHER_DES_ECB_PKCS5PADDING = "DES/ECB/PKCS5Padding"; // 算法/模式/补码方式

    public static final String CIPHER_DES_CBC_PKCS5PADDING = "DES/CBC/PKCS5Padding";

    public static final String CIPHER_DES_CBC_NOPADDING = "DES/CBC/NoPadding";

    private static final String SEED = "%%%today is nice***"; // 用于生成随机数的种子

    private Key key;

    private Cipher cipher;

    private String transformation;

    public DESCoder() throws NoSuchAlgorithmException, NoSuchPaddingException, NoSuchProviderException {
        this.key = initKey();
        this.cipher = Cipher.getInstance(CIPHER_DES_DEFAULT);
        this.transformation = CIPHER_DES_DEFAULT;
    }

    /**
     * 根据随机数种子生成一个密钥
     *
     * @return Key
     * @throws NoSuchAlgorithmException
     * @throws NoSuchProviderException
     * @author Zhang Peng
     * @since 2016年7月14日
     */
    private Key initKey() throws NoSuchAlgorithmException, NoSuchProviderException {
        // 根据种子生成一个安全的随机数
        SecureRandom secureRandom = null;
        secureRandom = new SecureRandom(SEED.getBytes());

        KeyGenerator keyGen = KeyGenerator.getInstance(KEY_ALGORITHM_DES);
        keyGen.init(secureRandom);
        return keyGen.generateKey();
    }

    public DESCoder(String transformation)
        throws NoSuchAlgorithmException, NoSuchPaddingException, NoSuchProviderException {
        this.key = initKey();
        this.cipher = Cipher.getInstance(transformation);
        this.transformation = transformation;
    }

    /**
     * 加密
     *
     * @param input 明文
     * @return byte[] 密文
     * @throws InvalidKeyException
     * @throws IllegalBlockSizeException
     * @throws BadPaddingException
     * @throws InvalidAlgorithmParameterException
     * @author Zhang Peng
     * @since 2016年7月20日
     */
    public byte[] encrypt(byte[] input) throws InvalidKeyException, IllegalBlockSizeException, BadPaddingException,
        InvalidAlgorithmParameterException {
        if (transformation.equals(CIPHER_DES_CBC_PKCS5PADDING) || transformation.equals(CIPHER_DES_CBC_NOPADDING)) {
            cipher.init(Cipher.ENCRYPT_MODE, key, new IvParameterSpec(getIV()));
        } else {
            cipher.init(Cipher.ENCRYPT_MODE, key);
        }
        return cipher.doFinal(input);
    }

    /**
     * 解密
     *
     * @param input 密文
     * @return byte[] 明文
     * @throws InvalidKeyException
     * @throws IllegalBlockSizeException
     * @throws BadPaddingException
     * @throws InvalidAlgorithmParameterException
     * @author Zhang Peng
     * @since 2016年7月20日
     */
    public byte[] decrypt(byte[] input) throws InvalidKeyException, IllegalBlockSizeException, BadPaddingException,
        InvalidAlgorithmParameterException {
        if (transformation.equals(CIPHER_DES_CBC_PKCS5PADDING) || transformation.equals(CIPHER_DES_CBC_NOPADDING)) {
            cipher.init(Cipher.DECRYPT_MODE, key, new IvParameterSpec(getIV()));
        } else {
            cipher.init(Cipher.DECRYPT_MODE, key);
        }
        return cipher.doFinal(input);
    }

    private byte[] getIV() {
        String iv = "01234567"; // IV length: must be 8 bytes long
        return iv.getBytes();
    }

    public static void main(String[] args) throws Exception {
        DESCoder aes = new DESCoder(CIPHER_DES_CBC_PKCS5PADDING);

        String msg = "Hello World!";
        System.out.println("原文: " + msg);
        byte[] encoded = aes.encrypt(msg.getBytes(StandardCharsets.UTF_8));
        String encodedBase64 = Base64.getUrlEncoder().encodeToString(encoded);
        System.out.println("密文: " + encodedBase64);

        byte[] decodedBase64 = Base64.getUrlDecoder().decode(encodedBase64);
        byte[] decoded = aes.decrypt(decodedBase64);
        System.out.println("明文: " + new String(decoded));
    }

}

输出

1
2
3

原文: Hello World!
密文: TtnEu9ezNQtxFKpmq_37Qw==
明文: Hello World!

基于口令加密的流程（PBE）

DES、DESede、AES、IDEA 这几种算法的应用模型几乎如出一辙。

但是，并非所有对称加密算法都是如此。

基于口令加密(Password Based Encryption, PBE)是一种基于口令加密的算法。其特点是：口令由用户自己掌管，采用随机数（这里叫做盐）杂凑多重加密等方法保证数据的安全性。

PBE 没有密钥概念，密钥在其他对称加密算法中是经过计算得出的，PBE 则使用口令替代了密钥。

流程：

步骤如下：

（1）产生盐

1 2	SecureRandom secureRandom = new SecureRandom(); byte[] salt = secureRandom.generateSeed(8); // 盐长度必须为8字节

（2）根据密码产生 Key

String password = "123456";
PBEKeySpec keySpec = new PBEKeySpec(password.toCharArray());
SecretKeyFactory keyFactory = SecretKeyFactory.getInstance(KEY_ALGORITHM);
SecretKey secretKey = keyFactory.generateSecret(keySpec);

（3）初始化加密或解密对象

1
2
3

PBEParameterSpec paramSpec = new PBEParameterSpec(salt, ITERATION_COUNT);
Cipher cipher = Cipher.getInstance(KEY_ALGORITHM);
cipher.init(Cipher.ENCRYPT_MODE, secretKey, paramSpec);

（4）执行

1 2	byte[] plaintext = "Hello World".getBytes(); byte[] ciphertext = cipher.doFinal(plaintext);

（5）完整 PBE 示例

import java.security.Key;
import java.security.SecureRandom;
import java.util.Base64;
import javax.crypto.Cipher;
import javax.crypto.SecretKey;
import javax.crypto.SecretKeyFactory;
import javax.crypto.spec.PBEKeySpec;
import javax.crypto.spec.PBEParameterSpec;

/**
 * 基于口令加密(Password Based Encryption, PBE)，是一种对称加密算法。 其特点是：口令由用户自己掌管，采用随机数（这里叫做盐）杂凑多重加密等方法保证数据的安全性。
 * PBE没有密钥概念，密钥在其他对称加密算法中是经过计算得出的，PBE则使用口令替代了密钥。
 *
 * @author Zhang Peng
 * @since 2016年7月20日
 */
public class PBECoder {

    public static final String KEY_ALGORITHM = "PBEWITHMD5andDES";

    public static final int ITERATION_COUNT = 100;

    private Key key;

    private byte[] salt;

    public PBECoder(String password) throws Exception {
        this.salt = initSalt();
        this.key = initKey(password);
    }

    private byte[] initSalt() {
        SecureRandom secureRandom = new SecureRandom();
        return secureRandom.generateSeed(8); // 盐长度必须为8字节
    }

    private Key initKey(String password) throws Exception {
        PBEKeySpec keySpec = new PBEKeySpec(password.toCharArray());
        SecretKeyFactory keyFactory = SecretKeyFactory.getInstance(KEY_ALGORITHM);
        return keyFactory.generateSecret(keySpec);
    }

    public byte[] encrypt(byte[] plaintext) throws Exception {
        PBEParameterSpec paramSpec = new PBEParameterSpec(salt, ITERATION_COUNT);
        Cipher cipher = Cipher.getInstance(KEY_ALGORITHM);
        cipher.init(Cipher.ENCRYPT_MODE, key, paramSpec);
        return cipher.doFinal(plaintext);
    }

    public byte[] decrypt(byte[] ciphertext) throws Exception {
        PBEParameterSpec paramSpec = new PBEParameterSpec(salt, ITERATION_COUNT);
        Cipher cipher = Cipher.getInstance(KEY_ALGORITHM);
        cipher.init(Cipher.DECRYPT_MODE, key, paramSpec);
        return cipher.doFinal(ciphertext);
    }

    public static void test1() throws Exception {

        // 产生盐
        SecureRandom secureRandom = new SecureRandom();
        byte[] salt = secureRandom.generateSeed(8); // 盐长度必须为8字节

        // 产生Key
        String password = "123456";
        PBEKeySpec keySpec = new PBEKeySpec(password.toCharArray());
        SecretKeyFactory keyFactory = SecretKeyFactory.getInstance(KEY_ALGORITHM);
        SecretKey secretKey = keyFactory.generateSecret(keySpec);

        PBEParameterSpec paramSpec = new PBEParameterSpec(salt, ITERATION_COUNT);
        Cipher cipher = Cipher.getInstance(KEY_ALGORITHM);
        cipher.init(Cipher.ENCRYPT_MODE, secretKey, paramSpec);

        byte[] plaintext = "Hello World".getBytes();
        byte[] ciphertext = cipher.doFinal(plaintext);
        new String(ciphertext);
    }

    public static void main(String[] args) throws Exception {
        PBECoder encode = new PBECoder("123456");
        String message = "Hello World!";
        byte[] ciphertext = encode.encrypt(message.getBytes());
        byte[] plaintext = encode.decrypt(ciphertext);

        System.out.println("原文：" + message);
        System.out.println("密文：" + Base64.getUrlEncoder().encodeToString(ciphertext));
        System.out.println("明文：" + new String(plaintext));
    }

}

非对称加密

非对称加密概述

非对称加密常用算法：DH(Diffie-Hellman，密钥交换算法)、RSA

非对称加密算法和对称加密算法的主要差别在于非对称加密算法用于加密和解密的密钥是不同的。一个公开，称为公钥（public key）；一个保密，称为私钥（private key）。因此，非对称加密算法也称为双钥加密算法或公钥加密算法。

非对称加密特点：

优点：非对称加密算法解决了对称加密算法的密钥分配问题，并极大地提高了算法安全性。
缺点：算法比对称算法更复杂，因此加密、解密速度都比对称算法慢很多。

非对称加密算法实现机密信息交换的基本过程是：甲方生成一对密钥并将其中的一把作为公用密钥向其它方公开；得到该公用密钥的乙方使用该密钥对机密信息进行加密后再发送给甲方；甲方再用自己保存的另一把专用密钥对加密后的信息进行解密。

另一方面，甲方可以使用乙方的公钥对机密信息进行签名后再发送给乙方；乙方再用自己的私匙对数据进行验证。

甲方只能用其私钥解密，由其公钥加密后的任何信息。非对称加密算法的保密性比较好，它消除了最终用户交换密钥的需要。

非对称加密算法应用

import java.nio.charset.StandardCharsets;
import java.security.*;
import java.security.spec.PKCS8EncodedKeySpec;
import java.security.spec.X509EncodedKeySpec;
import java.util.Base64;
import javax.crypto.Cipher;

/**
 * RSA安全编码：非对称加密算法。它既可以用来加密、解密，也可以用来做数字签名
 *
 * @author Zhang Peng
 * @since 2016年7月20日
 */
public class RSACoder {

    public final static String KEY_ALGORITHM = "RSA";

    public final static String SIGN_ALGORITHM = "MD5WithRSA";

    private KeyPair keyPair;

    public RSACoder() throws Exception {
        this.keyPair = initKeyPair();
    }

    private KeyPair initKeyPair() throws Exception {
        // KeyPairGenerator类用于生成公钥和私钥对，基于RSA算法生成对象
        KeyPairGenerator keyPairGen = KeyPairGenerator.getInstance(KEY_ALGORITHM);
        // 初始化密钥对生成器，密钥大小为1024位
        keyPairGen.initialize(1024);
        // 生成一个密钥对
        return keyPairGen.genKeyPair();
    }

    public byte[] encryptByPrivateKey(byte[] plaintext, byte[] key) throws Exception {
        PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(key);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        PrivateKey privateKey = keyFactory.generatePrivate(keySpec);
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());
        cipher.init(Cipher.ENCRYPT_MODE, privateKey);
        return cipher.doFinal(plaintext);
    }

    public byte[] decryptByPublicKey(byte[] ciphertext, byte[] key) throws Exception {
        X509EncodedKeySpec keySpec = new X509EncodedKeySpec(key);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        PublicKey publicKey = keyFactory.generatePublic(keySpec);
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());
        cipher.init(Cipher.DECRYPT_MODE, publicKey);
        return cipher.doFinal(ciphertext);
    }

    public byte[] encryptByPublicKey(byte[] plaintext, byte[] key) throws Exception {
        X509EncodedKeySpec keySpec = new X509EncodedKeySpec(key);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        PublicKey publicKey = keyFactory.generatePublic(keySpec);
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());
        cipher.init(Cipher.ENCRYPT_MODE, publicKey);
        return cipher.doFinal(plaintext);
    }

    public byte[] decryptByPrivateKey(byte[] ciphertext, byte[] key) throws Exception {
        PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(key);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        PrivateKey privateKey = keyFactory.generatePrivate(keySpec);
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());
        cipher.init(Cipher.DECRYPT_MODE, privateKey);
        return cipher.doFinal(ciphertext);
    }

    public byte[] signature(byte[] data, byte[] privateKey, RsaSignTypeEn type) throws Exception {
        PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(privateKey);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        PrivateKey key = keyFactory.generatePrivate(keySpec);

        Signature signature = Signature.getInstance(type.name());
        signature.initSign(key);
        signature.update(data);
        return signature.sign();
    }

    public byte[] getPrivateKey() {
        return keyPair.getPrivate().getEncoded();
    }

    public boolean verify(byte[] data, byte[] publicKey, byte[] sign, RsaSignTypeEn type) throws Exception {
        X509EncodedKeySpec keySpec = new X509EncodedKeySpec(publicKey);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        PublicKey key = keyFactory.generatePublic(keySpec);

        Signature signature = Signature.getInstance(type.name());
        signature.initVerify(key);
        signature.update(data);
        return signature.verify(sign);
    }

    public byte[] getPublicKey() {
        return keyPair.getPublic().getEncoded();
    }

    public enum RsaSignTypeEn {

        MD2WithRSA,
        MD5WithRSA,
        SHA1WithRSA
    }

    public static void main(String[] args) throws Exception {
        String msg = "Hello World!";
        RSACoder coder = new RSACoder();
        // 私钥加密，公钥解密
        byte[] ciphertext = coder.encryptByPrivateKey(msg.getBytes(StandardCharsets.UTF_8), coder.keyPair.getPrivate().getEncoded());
        byte[] plaintext = coder.decryptByPublicKey(ciphertext, coder.keyPair.getPublic().getEncoded());

        // 公钥加密，私钥解密
        byte[] ciphertext2 = coder.encryptByPublicKey(msg.getBytes(), coder.keyPair.getPublic().getEncoded());
        byte[] plaintext2 = coder.decryptByPrivateKey(ciphertext2, coder.keyPair.getPrivate().getEncoded());

        byte[] sign = coder.signature(msg.getBytes(), coder.getPrivateKey(), RsaSignTypeEn.SHA1WithRSA);
        boolean flag = coder.verify(msg.getBytes(), coder.getPublicKey(), sign, RsaSignTypeEn.SHA1WithRSA);
        String result = flag ? "数字签名匹配" : "数字签名不匹配";

        System.out.println("原文：" + msg);
        System.out.println("公钥：" + Base64.getUrlEncoder().encodeToString(coder.keyPair.getPublic().getEncoded()));
        System.out.println("私钥：" + Base64.getUrlEncoder().encodeToString(coder.keyPair.getPrivate().getEncoded()));

        System.out.println("============== 私钥加密，公钥解密 ==============");
        System.out.println("密文：" + Base64.getUrlEncoder().encodeToString(ciphertext));
        System.out.println("明文：" + new String(plaintext));

        System.out.println("============== 公钥加密，私钥解密 ==============");
        System.out.println("密文：" + Base64.getUrlEncoder().encodeToString(ciphertext2));
        System.out.println("明文：" + new String(plaintext2));

        System.out.println("============== 数字签名 ==============");
        System.out.println("数字签名：" + Base64.getUrlEncoder().encodeToString(sign));
        System.out.println("验证结果：" + result);
    }

}

输出

原文：Hello World!
公钥：MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCzPtRLErTUcYtr8GmIpvbso7FN18thuEq02U21mh7TA4FH4TjvNgOZrZEORYu94dxrPdnrPjh0p62P5pDIjx_dtGlZr0aGWgtTvBbPwAKE4keXyPqv4VV6iXRzyQ2HdOvFOovim5eu0Tu_TxGeNpFfp0pYj2LXCzpsgSrdUPuPmwIDAQAB
私钥：MIICdwIBADANBgkqhkiG9w0BAQEFAASCAmEwggJdAgEAAoGBALM-1EsStNRxi2vwaYim9uyjsU3Xy2G4SrTZTbWaHtMDgUfhOO82A5mtkQ5Fi73h3Gs92es-OHSnrY_mkMiPH920aVmvRoZaC1O8Fs_AAoTiR5fI-q_hVXqJdHPJDYd068U6i-Kbl67RO79PEZ42kV-nSliPYtcLOmyBKt1Q-4-bAgMBAAECgYBJxOXiL8S0WjajKcKFNxIQuh3Sh6lwgkRcwcI1p0RgW-TtDEg-SuCYctJsKTsl3rq0eDQjmOvrNsc7ngygPidCiTdbD1H6m3tLrebBB-wZdXMSWPsHtQJsq4dE0e93mmfysciOP6QExOs0JqVjTyyBSK37LpUcLdalj2IJDtC0gQJBAPfMngZAuIPmXued7PUuWNBuwxnkmdMcs308eC_9vnLLXWhDB9xKMuXCMwqk16MJ6j1FQWtJu62T21yniWWQHIsCQQC5LWqKfRxVukgnBg0Pa95NVWWY01Yttnb125JsLxeKbR97KU4VgBaBcB9TyUdPr9lxAzGFg6Y3A1wfsfukaGsxAkEA1l719oLXHYSWZdmBvTozK14m-qeBS9lwjc9aSmpB8B1u2Vvj2Pd3wLyYW4Tv5-QT-J2JUr-e1TMseqOVgX-CsQJAETRoBq_zFv_0vjNwuTMTd2nsw5M3GY4vZU5eP1Dsxf63gxDmYVcCQEpzjqxPxNaYxEhArJ_7rHbSc1ts_ux4sQJBAIlbGQC4-92foXGzWT80rsqZlMQ8J8Nbjpoo7RUN9tgx60Vkr3xv26Vos77oqdufWlt5IiBZBS9acTA2suav6Qg=
============== 私钥加密，公钥解密 ==============
密文：qn6iGjSJV45EnH21RYRx2UZfMueqplbm1g3VIpBBQBuF63RdHdSgMJsVPAuB__V0rxpPlU3gR6qLyWu1mpaJ-ix_6KogAH64wqTWqPRh7E6aj767rybNpt9JyVlCmmpy9DiqHAUFWtBJDo34q-a7Fhq9c8bWrJ6jnn47IdmzHfU=
明文：Hello World!
============== 公钥加密，私钥解密 ==============
密文：fsz2IFs69d7JDrH-yoe5pi5WKQU1Zml7SDSpPqTZUn6muSCjNp6x312deQCXKMGSeAdMpVeb01yZBfa0MT_6eYJYVseU7Rd6bDf6YIg3AZFC41yh5ITiTvQ-XzxugnppS12sLpXSWg0faa5qjcVZnoTX9p7nHr8n20y4CNMI6Rw=
明文：Hello World!
============== 数字签名 ==============
数字签名：dTtUUlWX1wRQbW1PcA8O6WJcWcrHinEZRXwgLKEwBOm2DpvHnynvV_HYKS-qFE5_4vJQcPGJ2hZqWbfv1VKLHMUWuiXM7VJk70g3g7BF8i8RWbrCDOxgTR77jrEwidpr1PYJzWJVGq_HP36MxInGFLcVh2sN0fu8MppzsXUENZQ=
验证结果：数字签名匹配

术语

**明文(Plaintext)**：指待加密信息。明文可以是文本文件、图片文件、二进制数据等。
**密文(Ciphertext)**：指经过加密后的明文。密文通常以文本、二进制等形式存在。
**加密(Encryption)**：指将明文转换为密文的过程。
**解密(Decryption)**：指将密文转换为明文的过程。
**加密密钥(Encryption Key)**：指通过加密算法进行加密操作用的密钥。
**解密密钥(Decryption Key)**：指通过解密算法进行解密操作用的密钥。
**信道(Channel)**：通信的通道，是信号传输的媒介。

参考资料

Java 虚拟机简介

发表于 2021-05-24 更新于 2025-09-13 分类于 Java ， JavaCore ， JVM 本文字数： 1.1k 阅读时长 ≈ 1 分钟

Java 虚拟机简介

JVM 能跨平台工作，主要是由于 JVM 屏蔽了与各个计算机平台相关的软件、硬件之间的差异。

JVM 简介

计算机体系结构

真实的计算机体系结构的核心部分包含：

指令集
计算单元（CPU）
寻址方式
寄存器
存储单元

JVM 体系结构简介

JVM 体系结构与计算机体系结构相似，它的核心部分包含：

JVM 指令集
类加载器
执行引擎 - 相当于 JVM 的 CPU
内存区 - JVM 的存储
本地方法调用 - 调用 C/C++ 实现的本地方法

Hotspot 架构

Hotspot 是最流行的 JVM。

Java 虚拟机的主要组件，包括类加载器、运行时数据区和执行引擎。

Hotspot 虚拟机拥有一个架构，它支持强大特性和能力的基础平台，支持实现高性能和强大的可伸缩性的能力。举个例子，Hotspot 虚拟机 JIT 编译器生成动态的优化，换句话说，它们在 Java 应用执行期做出优化，为底层系统架构生成高性能的本地机器指令。另外，经过它的运行时环境和多线程垃圾回收成熟的进化和连续的设计， Hotspot 虚拟机在高可用计算系统上产出了高伸缩性。

Hotspot 关键组件

Java 虚拟机有三个组件关注着什么时候进行性能优化，堆空间是对象所存储的地方，这个区域被启动时选择的垃圾回收器管理，大部分调优选项与调整堆大小和根据你的情况选择最适当的垃圾收集器相关。即时编译器对性能也有很大的影响，但是使用新版本的 Java 虚拟机时很少需要调整。

性能指标

Java 虚拟机的性能指标主要有两点：

停顿时间 - 响应延迟是指一个应用回应一个请求的速度有多快。对关注响应能力的应用来说，长暂停时间是不可接受的，重点是在短的时间周期内能做出响应。
- 桌面 UI 响应事件的速度
- 网站返回网页的速度
- 数据查询返回的速度
吞吐量 - 吞吐量关注在特定的时间周期内一个应用的工作量的最大值。对关注吞吐量的应用来说长暂停时间是可以接受的。由于高吞吐量的应用关注的基准在更长周期时间上，所以快速响应时间不在考虑之内。
- 给定时间内完成事务的数量
- 一小时内批处理程序完成的工作数量
- 一小时内数据查询完成的数量

JVM 内存简介

物理内存和虚拟内存

所谓物理内存就是通常所说的 RAM（随机存储器）。

虚拟内存使得多个进程在同时运行时可以共享物理内存，这里的共享只是空间上共享，在逻辑上彼此仍然是隔离的。

内核空间和用户空间

一个计算通常有固定大小的内存空间，但是程序并不能使用全部的空间。因为这些空间被划分为内核空间和用户空间，而程序只能使用用户空间的内存。

使用内存的 Java 组件

Java 启动后，作为一个进程运行在操作系统中。

有哪些 Java 组件需要占用内存呢？

堆内存：Java 堆、类和类加载器
栈内存：线程
本地内存：NIO、JNI

参考资料

《深入理解 Java 虚拟机》

编码和加密

发表于 2021-05-24 更新于 2025-09-13 分类于设计，架构，安全本文字数： 4.6k 阅读时长 ≈ 4 分钟

编码和加密

关键词：Base64、消息摘要、数字签名、对称加密、非对称加密、MD5、SHA、HMAC、AES、DES、DESede、RSA

Base64 编码

Base64 原理

Base64 内容传送编码是一种以任意 8 位字节序列组合的描述形式，这种形式不易被人直接识别。

Base64 算法主要是将给定的字符以字符编码(如 ASCII 码，UTF-8 码)对应的十进制数为基准，做编码操作：

将给定的字符串以字符为单位，转换为对应的字符编码。
将获得字符编码转换为二进制
对二进制码做分组转换，每 3 个字节为一组，转换为每 4 个 6 位二进制位一组（不足 6 位时低位补 0）。这是一个分组变化的过程，3 个 8 位二进制码和 4 个 6 位二进制码的长度都是 24 位（38 = 46 = 24）。
对获得的 4-6 二进制码补位，向 6 位二进制码添加 2 位高位 0，组成 4 个 8 位二进制码。
对获得的 4-8 二进制码转换为十进制码。
将获得的十进制码转换为 Base64 字符表中对应的字符。

Base64 编码表

索引	对应字符	索引	对应字符	索引	对应字符	索引	对应字符
0	A	17	R	34	i	51	z
1	B	18	S	35	j	52	0
2	C	19	T	36	k	53	1
3	D	20	U	37	l	54	2
4	E	21	V	38	m	55	3
5	F	22	W	39	n	56	4
6	G	23	X	40	o	57	5
7	H	24	Y	41	p	58	6
8	I	25	Z	42	q	59	7
9	J	26	a	43	r	60	8
10	K	27	b	44	s	61	9
11	L	28	c	45	t	62	+
12	M	29	d	46	u	63	/
13	N	30	e	47	v
14	O	31	f	48	w
15	P	32	g	49	x
16	Q	33	h	50	y

Base64 应用

消息摘要

消息摘要概述

消息摘要，其实就是将需要摘要的数据作为参数，经过哈希函数(Hash)的计算，得到的散列值。

消息摘要特点

唯一性：数据只要有一点改变，那么再通过消息摘要算法得到的摘要也会发生变化。虽然理论上有可能会发生碰撞，但是概率极其低。
不可逆：消息摘要算法的密文无法被解密。
不需要密钥，可使用于分布式网络。
无论输入的明文有多长，计算出来的消息摘要的长度总是固定的。

消息摘要常用算法

MD5和SHA1分别是MD、SHA算法系列中最有代表性的算法。

如今，MD5 已被发现有许多漏洞，从而不再安全。SHA 算法比 MD 算法的摘要长度更长，也更加安全。

数字签名

数字签名算法要求能够验证数据完整性、认证数据来源，并起到抗否认的作用。

数字签名算法包含签名和验证两项操作，遵循私钥签名，公钥验证的方式。

签名时要使用私钥和待签名数据，验证时则需要公钥、签名值和待签名数据，其核心算法主要是消息摘要算法。

数字签名常用算法：RSA、DSA、ECDSA

对称加密

对称加密算法主要有 DES、3DES（TripleDES）、AES、IDEA、RC2、RC4、RC5 和 Blowfish 等。

对称加密特点：

优点：计算量小、加密速度快、加密效率高。
缺点：算法是公开的，安全性得不到保证。

而与公钥、密钥加密算法比起来，对称加密算法能够提供加密和认证却缺乏了签名功能，使得使用范围有所缩小。

对称加密原理

对称加密体制分为两种：

一种是对明文的单个位（或字节）进行运算，称为流密码，也称为序列密码；

一种是把明文信息划分为不同的组（或块）结构，分别对每个组（或块）进行加密、解密，称为分组密码。

假设甲乙方作为通信双方。假定甲乙双方在消息传递前已商定加密算法，欲完成一次消息传递需要经过如下步骤。

对称加密工作模式

根据数据加密时每个加密区块见得关联方式来区分，可以分为以下种工作模式：

(1) 电子密码本模式(Electronic Code Book, ECB)

用途：适合加密密钥，随机数等短数据。例如，安全地传递 DES 密钥，ECB 是最合适的模式。

(2) 密文链接模式(Cipher Booki Chaining, CBC)

用途：可加密任意长度的数据，适用于计算产生检测数据完整性的消息认证 MAC。

(3) 密文反馈模式(Cipher Feed Back, CFB)

用途：因错误传播无界，可以用于检查发现明文密文的篡改。

(4) 输出反馈模式(Output Feed Back, OFB)

用途：使用于加密冗余性较大的数据，比如语音和图像数据。

AES 算法除了以上 4 中模式外，还有一种新的工作模式：

(5) 计数器模式(Counter, CTR)

用途：适用于各种加密应用。

本文对于各种工作模式的原理展开描述。个人认为，作为工程应用，了解其用途即可。

对称加密填充方法

Java 中对称加密对于短块的处理，一般是采用填充方式。

常采用的是：NoPadding（不填充）、Zeros 填充（0 填充）、PKCS5Padding 填充。

ZerosPadding

方式：全部填充为 0 的字节

结果如下：

F1 F2 F3 F4 F5 F6 F7 F8 //第一块

F9 00 00 00 00 00 00 00 //第二块

PKCS5Padding

方式：每个填充的字节都记录了填充的总字节数

结果如下：

F1 F2 F3 F4 F5 F6 F7 F8 //第一块

F9 07 07 07 07 07 07 07 //第二块

基于口令加密的流程（PBE）

DES、DESede、AES、IDEA 这几种算法的应用模型几乎如出一辙。

但是，并非所有对称加密算法都是如此。

PBE 没有密钥概念，密钥在其他对称加密算法中是经过计算得出的，PBE 则使用口令替代了密钥。

流程：

非对称加密

非对称加密常用算法：DH(Diffie-Hellman，密钥交换算法)、RSA

非对称加密特点：

优点：非对称加密算法解决了对称加密算法的密钥分配问题，并极大地提高了算法安全性。
缺点：算法比对称算法更复杂，因此加密、解密速度都比对称算法慢很多。

另一方面，甲方可以使用乙方的公钥对机密信息进行签名后再发送给乙方；乙方再用自己的私匙对数据进行验证。

甲方只能用其私钥解密，由其公钥加密后的任何信息。非对称加密算法的保密性比较好，它消除了最终用户交换密钥的需要。

术语

**明文(Plaintext)**：指待加密信息。明文可以是文本文件、图片文件、二进制数据等。
**密文(Ciphertext)**：指经过加密后的明文。密文通常以文本、二进制等形式存在。
**加密(Encryption)**：指将明文转换为密文的过程。
**解密(Decryption)**：指将密文转换为明文的过程。
**加密密钥(Encryption Key)**：指通过加密算法进行加密操作用的密钥。
**解密密钥(Decryption Key)**：指通过解密算法进行解密操作用的密钥。
**信道(Channel)**：通信的通道，是信号传输的媒介。

索引	对应字符	索引	对应字符	索引	对应字符	索引	对应字符
0	A	17	R	34	i	51	z
1	B	18	S	35	j	52	0
2	C	19	T	36	k	53	1
3	D	20	U	37	l	54	2
4	E	21	V	38	m	55	3
5	F	22	W	39	n	56	4
6	G	23	X	40	o	57	5
7	H	24	Y	41	p	58	6
8	I	25	Z	42	q	59	7
9	J	26	a	43	r	60	8
10	K	27	b	44	s	61	9
11	L	28	c	45	t	62	+
12	M	29	d	46	u	63	/
13	N	30	e	47	v
14	O	31	f	48	w
15	P	32	g	49	x
16	Q	33	h	50	y

索引	对应字符	索引	对应字符	索引	对应字符	索引	对应字符
0	A	17	R	34	i	51	z
1	B	18	S	35	j	52	0
2	C	19	T	36	k	53	1
3	D	20	U	37	l	54	2
4	E	21	V	38	m	55	3
5	F	22	W	39	n	56	4
6	G	23	X	40	o	57	5
7	H	24	Y	41	p	58	6
8	I	25	Z	42	q	59	7
9	J	26	a	43	r	60	8
10	K	27	b	44	s	61	9
11	L	28	c	45	t	62	+
12	M	29	d	46	u	63	/
13	N	30	e	47	v
14	O	31	f	48	w
15	P	32	g	49	x
16	Q	33	h	50	y

索引	对应字符	索引	对应字符	索引	对应字符	索引	对应字符
0	A	17	R	34	i	51	z
1	B	18	S	35	j	52	0
2	C	19	T	36	k	53	1
3	D	20	U	37	l	54	2
4	E	21	V	38	m	55	3
5	F	22	W	39	n	56	4
6	G	23	X	40	o	57	5
7	H	24	Y	41	p	58	6
8	I	25	Z	42	q	59	7
9	J	26	a	43	r	60	8
10	K	27	b	44	s	61	9
11	L	28	c	45	t	62	+
12	M	29	d	46	u	63	/
13	N	30	e	47	v
14	O	31	f	48	w
15	P	32	g	49	x
16	Q	33	h	50	y

索引	对应字符	索引	对应字符	索引	对应字符	索引	对应字符
0	A	17	R	34	i	51	z
1	B	18	S	35	j	52	0
2	C	19	T	36	k	53	1
3	D	20	U	37	l	54	2
4	E	21	V	38	m	55	3
5	F	22	W	39	n	56	4
6	G	23	X	40	o	57	5
7	H	24	Y	41	p	58	6
8	I	25	Z	42	q	59	7
9	J	26	a	43	r	60	8
10	K	27	b	44	s	61	9
11	L	28	c	45	t	62	+
12	M	29	d	46	u	63	/
13	N	30	e	47	v
14	O	31	f	48	w
15	P	32	g	49	x
16	Q	33	h	50	y

《数据密集型应用系统设计》笔记二

第五章：数据复制

主节点与从节点

同步复制与异步复制

配置新的从节点

处理节点失效

从节点失效： 追赶式恢复

主节点失效：节点切换

复制日志的实现

基于语句的复制

基于预写日志（WAL）传输

基于行的逻辑日志复制

基于触发器的复制

复制滞后问题

读自己的写

单调读

前缀一致读

复制滞后的解决方案

多主节点复制

适用场景

多数据中心

离线客户端操作

协同编辑

处理写冲突

同步与异步冲突检测

避免冲突

收敛于一致状态

自定义冲突解决逻辑

什么是冲突？

拓扑结构

无主复制

第六章：分区

数据分区与数据复制

键－值数据的分区

基于关键字区间分区

基于关键字晗希值分区

负载倾斜与热点

分区与二级索引

基于文档分区的二级索引

基于词条的二级索引分区

分区再均衡

动态再均衡的策略

为什么不用取模？

固定数量的分区

动态分区

按节点比例分区

自动与手动再平衡操作

请求路由

小结

第七章：事务

深入理解事务

原子性

弱隔离级别

串行化

第八章：分布式系统的挑战

第九章：一致性与共识

参考资料

海量数据处理

如何从海量的 URL 中找出相同的 URL？

问题描述

解决思路

方案总结

如何从海量数据中找出高频词？

问题描述

解决思路

方案总结

如何找出某一天访问百度网站最多的 IP？

问题描述

解决思路

方法总结

如何在大量的数据中找出不重复的整数？

问题描述

解决思路

方法一：分治法

方法二：位图法

方法总结

如何在大量的数据中判断一个数是否存在？

题目描述

解答思路

方法一：分治法

从节点失效：追赶式恢复

索引	对应字符	索引	对应字符	索引	对应字符	索引	对应字符
0	A	17	R	34	i	51	z
1	B	18	S	35	j	52	0
2	C	19	T	36	k	53	1
3	D	20	U	37	l	54	2
4	E	21	V	38	m	55	3
5	F	22	W	39	n	56	4
6	G	23	X	40	o	57	5
7	H	24	Y	41	p	58	6
8	I	25	Z	42	q	59	7
9	J	26	a	43	r	60	8
10	K	27	b	44	s	61	9
11	L	28	c	45	t	62	+
12	M	29	d	46	u	63	/
13	N	30	e	47	v
14	O	31	f	48	w
15	P	32	g	49	x
16	Q	33	h	50	y

索引	对应字符	索引	对应字符	索引	对应字符	索引	对应字符
0	A	17	R	34	i	51	z
1	B	18	S	35	j	52	0
2	C	19	T	36	k	53	1
3	D	20	U	37	l	54	2
4	E	21	V	38	m	55	3
5	F	22	W	39	n	56	4
6	G	23	X	40	o	57	5
7	H	24	Y	41	p	58	6
8	I	25	Z	42	q	59	7
9	J	26	a	43	r	60	8
10	K	27	b	44	s	61	9
11	L	28	c	45	t	62	+
12	M	29	d	46	u	63	/
13	N	30	e	47	v
14	O	31	f	48	w
15	P	32	g	49	x
16	Q	33	h	50	y