loomt

Interview

 29185  59 

Raft

介绍 6.824

6.824 是 MIT 的公开课，内容主要是用 Golang 实现 Raft 分布式共识算法，以及基于 Raft 实现分布式内存 KV 数据库。主要包括并发编程需要注意的各种细节，分布式系统的入门以及分布式场景下如何构建 kv 数据库。

Raft 用于在多个节点间就数据一致性达成共识。它通过领导人选举机制来确定一个唯一的 leader 节点，然后通过 leader 的日志复制机制让所有节点趋向于拥有相同的日志，那么这些节点就可以按照一定的顺序执行相同的命令，每个机器的状态机就会产生相同状态副本，并且在一些机器宕掉的情况下也可以继续运行。Raft 的一致性程度是比较高的，达到了线性一致性。

领导选举

首先每个节点都有三个状态：Leader、Candidate、Follower。当服务器程序启动时，他们都是 Follower 身份。如果一个 Follower 在选举超时之内没有接收到 Leader 发来的心跳，会自增任期号并转换为 Candidate，然后并行的向集群中的其他节点发送请求投票的 RPC 来给自己拉票。收到请求投票 RPC 的 peer 节点会根据 RPC 传来的 Candidate 任期以及日志新旧程度选择是否投票。具体而言，如果 Candidate 的任期比自己小就忽略掉这个 RPC，否则就看一下谁的日志更新，如果 Follower 的日志更新就会拒绝投票，否则就给 Candidate 投一票，投完这个票之后 Follower 就无法在这个任期之内再给其他 Candidate 进行投票。Candidate 如果得到了超过半数的 Follower 认可，那么这个节点就会转化为 Leader，并发送心跳包来维护自己的地位。

选票被瓜分咋办？

选举超时时间随机，这种情况不常见，因为每个节点设置的超时时间都不一样，会在一个范围内波动。假设出现了这种情况，如果所有 Candidate 收获的投票数都不超过半数，那么会等待选举随机超时进行重新选举。直到最后出现了新的 Leader。还有一个优化方法是设置一个 PreVote，在进行正式选举之前，帮助集群过滤掉不合适的候选人，从而减少正式选举的竞争。

日志复制

Candidate 成为 Leader 后，会为 peer 节点初始化一个 nextIndex，用以预判 peer 节点的下一个日志。Leader 会隔一段时间发送一次心跳，在发送心跳的同时 Leader 会根据 nextIndex 发送 peer 需要拼接的日志。peer 收到心跳包后，会重置选举超时并且检验 Leader 的任期，如果 Leader 的任期比自己小，则抛弃；否则只能强制更新自己的日志。更新日志前先检查 nextIndex，如果 Follower 的日志长度小于 nextIndex，则表明 Follower 的日志未同步到 nextIndex，也就是 Leader 预判失败，需要通知 Leader 回退 nextIndex；如果 Follower 的日志比 nextIndex 长，再检查 nextIndex 下的日志任期，如果与 nextTerm 相匹配，则以 nextIndex 为起点，进行日志覆盖。否则，通知 Leader 回退 nextIndex。回退日志的一个比较简单的方案是 Leader 收到 nextIndex 的回退请求后，直接令 nextIndex-1，还有一种优化的方案是 Follower 传递一个 ConflictIndex 和 ConflictTerm 给 Leader，然后每次回退一个任期的日志。这种情况下需要 Follower 用 ConflictTerm 记录 nextIndex 下冲突的任期，如果 Follower 没有 nextIndex 就将 ConflictTerm 置空；否则用 ConflictIndex 记录 ConflictTerm 的第一个日志。Leader 方面收到了 ConflictTerm 和 ConflictIndex 后需要先判断日志的任期是否有 ConflictTerm，如果有，则将 nextIndex 设为 ConflictTerm 最后一个日志的下一个下标，如果日志的任期没有 ConflictTerm，则将 nextIndex 设置为 ConflictIndex。

日志压缩

当日志占用空间过多的时候可以将 Server 层状态机的状态存到持久化存储。具体而言，Server 层将状态机压缩成快照，然后交给 Raft 层完成快照的持久化。Raft 层的节点会丢弃被快照压缩的所有日志。在 Leader 进行日志同步的时候，如果 Follower 的日志比快照压缩的日志要旧，需要发送快照给 Follower 以实现同步。

日志匹配的正确性

  • 不同节点的两个日志条目拥有相同的索引和任期号，那么这两个日志条目存储了相同的指令。
  • 不同节点的两个日志条目拥有相同的索引和任期号，那么这两个日志条目之前的所有日志都相同。 第一个特性的依据：leader 最多在一个任期里在指定的一个日志索引位置创建一条日志条目，同时日志条目在日志中的位置也从来不会改变。第二个特性的依据。在发送附加日志 RPC 的时候，leader 会把新的日志条目紧接着之前的条目的索引位置和任期号包含在里面。如果 follow 在它的日志中找不到包含相同索引位置和任期号的条目，那么他就会拒绝接收新的日志条目。

线性化语义

每一次操作立即执行，只执行一次，在他调用和收到回复之间。客户端对于每一条指令都赋予一个唯一的序列号。然后，状态机跟踪每台机器最新的序列号和相应的响应。如果接收到一条指令，它的序列号已经被执行了，那么就立即返回结果，而不重新执行指令。

Multi-Raft 分三层：Client、Server、Raft。

Client：发出 Get、Put、Append 命令到 Server 层。 Server：Server 层有一个集群注册中心，注册中心本身也是通过 Raft 层同步的，负责 shard 的分配变动以及负载均衡，不同的命令会通过 hash 分配到不同的 shard，也就是会发送命令到不同的群组，相应的 Group 会发送给 Raft 层的 Leader，待达成共识后，再将日志应用到状态机。 Raft：用来进行共识。

PreVote 优化

PreVote 是一个领导人选举的优化机制。在原始的 Raft 协议中，如果一个 follow 节点由于网络分区或其他原因错过了一些心跳，它的任期会无限递增，重新回到集群时，可能会发起一个选举。如果它的日志并不是最新的，这可能会导致多个不必要的 leader 选举和日志不一致性。

为了解决这个问题，需要引入 PreVote 机制。在正式进入选举前，follow 先进行一轮预投票（PreVote）来判断它是否有资格成为 leader 。在这个阶段，它向其他节点询问是否会支持它成为 leader ，但并不真正改变自己或其他节点的任期号。只有在得到大多数节点的预支持后，follow 才会递增其任期号，并开始正式的选举流程。这样可以防止不必要的 leader 更迭，并减少因为网络问题引起的脑裂（split brain）情况。

ReadIndex 优化

ReadIndex 是一种用于处理读取请求的一致性保证机制。在读取请求传入的时候，server 记录下读请求对应的 id，当执行到此 id 对应的最后一个写请求后，不需要经过 Raft 共识，即可直接执行读请求，返回状态机对应的内容。但是在分布式系统中，即使一个节点是 leader ，由于网络延迟和分区，它可能已经被替换了，但自己并不知情。如果在这个状态下处理读取请求，可能会返回旧的数据。为了确保读取操作返回的是最新的提交数据，ReadIndex 流程要求 leader 在处理读取请求之前，先向集群发送一个心跳信号，并等待大多数节点的响应。通过这个过程，leader 可以确认它仍然处于 leader 地位，并且有权处理读取请求。心跳信号的响应还包含了节点的日志提交位置，leader 使用这个信息来决定读取请求可以安全地进行。

LeaseRead 优化

LeaseRead 是一个基于租约的读取机制。它的基本思想是，leader 在没有收到更高任期号的消息情况下，可以在一段时间内（称为租约时间）安全地响应读取请求，而无需每次读取都与其他节点通信确认。 这种机制通过减少与其他节点的通信，来降低了读取操作的延迟。但是，它依赖于系统内的时钟同步。如果时钟不同步，或者 leader 在租约时间内失去了 leader 地位，那么就可能返回过时的数据。因此，实现 LeaseRead 时需要非常小心地处理这些边缘情况，确保系统的一致性不会被破坏。 这些优化机制都是为了提高 Raft 算法在不同场景下的性能和稳定性，同时确保系统状态的一致性。

成员变更

Raft 的成员变更主要有两种，一是单步成员变更，二是 joint consensus。

在 6.824，默认的成员变更是单步成员变更。先读取 shardctler 的 config，如果 config id 有更新，将这个更新通过 Raft 层共识。并且在 Leader 刚刚选举成功后，必须通过一次 no-op 日志的提交，才能正式提交成员变更的配置。这样做可以让目前的 follower 日志比之前的更新，防止前 leader 重新当选为 leader 抹去现有日志。

joint consensus 则是联合一致成员配置，主要流程是 Leader 收到成员变更请求后，向 $C_old$ 和 new 同步一条新旧成员配置的组合 $C_old,new$，此后的所有日志都需要 $C_old$ 和 $C_new$ 两个多数派的确认，$C_old,new$ 完成同步后，Leader 再向 $C_old$ 和 $C_new$ 同步一条 $C_new$ 的日志，此后只需要 $C_new$ 的 Quorum 就可以提交，不在 $C_new$ 的节点会自动下线。 精髓在于 $C_old,new$ 这个日志 需要被 $C_old$ 和 $C_new$ 两个 Quorum 确认，平滑地防止了脑裂。

Majority 和 Quorum

两者在日常分布式论文的语境里面可能区别不大，前者是多数派的意思，即大于二分之一；后者是法定人数，不一定是大多数，但是需要满足两个 Quorum 之间必定有交集。 比如可以设定 Quorum 的集合需要包含特定的节点，对于{a, b, c}三个节点组成的集群，定义每个 Quorum 必须包含 a，那么 Q ={{a},{a, b},{a, c},{a, b, c}}

Paxos 与 Raft 的区别

https://loomt.top/posts/paper/paxos-vs-raft/

什么是 CAP？

Consistency 一致性，Available 可用性，Partition tolerance 分区容忍性。

什么是 2PC？

Two-Phase Commit，分布式事务协议，用于确保多节点执行事务的原子性和一致性。

准备阶段（Prepare phase）：事务管理器给每个参与者发送 Prepare 消息，每个数据库参与者在本地执行事务，并写本地的 Undo/Redo 日志，此时事务没有提交。 （Undo 日志是记录修改前的数据，用于数据库回滚，Redo 日志是记录修改后的数据，用于提交事务后写入数据文件） 提交阶段（commit phase）：如果事务管理器收到了参与者的执行失败或者超时消息时，直接给每个参与者发送回滚 (Rollback) 消息；否则，发送提交 (Commit) 消息；参与者根据事务管理器的指令执行提交或者回滚操作，并释放事务处理过程中使用的锁资源。注意：必须在最后阶段释放锁资源。

MySQL 的 2PC

在 MySQL 中，数据落盘时需要写入 binlog 和 redo log，无论是 binlog 或 redo log 谁没写入盘就宕机了都会造成主从数据不一致。所以需要 2PC

prepare 阶段：将 XID（内部 XA 事务的 ID）写入到 redo log，同时将 redo log 对应的事务状态设置为 prepare，然后将 redo log 持久化到磁盘（innodb_flush_log_at_trx_commit = 1 的作用）；

commit 阶段：把 XID 写入到 binlog，然后将 binlog 持久化到磁盘（sync_binlog = 1 的作用），接着调用引擎的提交事务接口，将 redo log 状态设置为 commit，此时该状态并不需要持久化到磁盘，只需要 write 到文件系统的 page cache 中就够了，因为只要 binlog 写磁盘成功，就算 redo log 的状态还是 prepare 也没有关系，一样会被认为事务已经执行成功；

什么是 BASE？

Basically Available 基本可用，Soft state 软状态，Eventually consistent 最终一致性

什么是一致性？

一致性是对于一个分布式集群，一旦集群做出了某个决定，此决定最终的决定。

什么是线性一致性？

简单来说是表现得像一台机器那样。 具体来说：以一个整体顺序执行；顺序与真实时间匹配；读操作返回最后一个写操作的值。 在分布式上一个很重要的特点是在读在写的执行过程中可以读到不一样的值，但读写都是原子的，一旦写执行了，对以后的所有 Client 可见。

什么是顺序一致性？

比线性一致性稍弱，表现在顺序一致性不要求对于所有 Client 都要在时间上顺序执行，只需要保证对于每一个 Client 单独在时间上顺序执行。

Raft 如何保证线性一致性？

Raft 是一个共识算法，单凭 Raft 是无法保证绝对的线性一致性的，Raft 只能保证不同 Raft 节点对 Log 达成一致。Raft 层给状态机的线性一致性提供了基础，因为它保证了 commit 的顺序性。

什么是幂等？

一个操作执行一次和执行多次的结果是一样的，幂等主要通过去重表。

讲一下 Raft 的优化，主要是 PreVote，ReadIndex，LeaseRead 这三个。

PreVote：在进行正式选举之前，过滤掉不合适的候选人，从而减少正式选举的竞争，减少选票瓜分的情况。 Read Index：省去了 Raft log 的流程，大幅提升读的吞吐并显著降低延时。

  1. 记录当前的 commit index，称为 ReadIndex
  2. Leader 向 Follower 发起一次心跳，如果大多数节点回复了，那就能确定现在仍然是 Leader
  3. 等待状态机 至少 应用到 ReadIndex 记录的 Log，Leader apply 到 Server 层
  4. Server 层执行读请求，将结果返回给 Client

Lease Read:

Lease Read 与 ReadIndex 类似，但更进一步，不仅省去了 Log，还省去了网络交互，不再需要 heartbeat。它可以大幅提升读的吞吐也能显著降低延时。基本的思路是 Leader 取一个比 Election Timeout 小的租期，在租期不会发生选举，确保 Leader 不会变，所以可以跳过 ReadIndex 的第二步，也就降低了延时。LeaseRead 的正确性和时间挂钩，因此时间的实现至关重要，如果漂移严重，这套机制就会有问题。

分片分配的逻辑

分片分配的时候固定了分片的数量为 10，Multi-Raft 的每个组平均地处理分片的数量。如果发生了 Raft Group 的增加或者删除，则配置中心(同样是 Raft Group)会发送最新的设置到 Multi-Raft，然后 Multi-Raft 的每个节点根据自己的 Group ID 查看自己所在的 Raft Group 是否有变动，如果自己处理的分片移交到了其他节点，则进行迁移，用推的方式，将自己的状态机状态设定为 pushing，对方的状态机设定为 pulling，通过共识层执行 push 分片并被对方接收后再执行 del 操作。

Raft 如何进行 peer 的初始化

配置文件、服务发现工具、集群引导节点 Bootstrap Peers

Raft 哪些 state 需要持久化。

log、votefor、term、lastTerm、lastIndex

Raft applyIndex 和 commitIndex 的关系以及区别，是否需要持久化，持久化有什么好处。

applyIndex 为日志成功 apply 到 server 后的最新下标，commitIndex 为超过半数 Raft 节点保存的最新下标。

分布式 id

snowflake

  1. 1 个符号位（第一个 bit 位）：决定生成的数字是正数还是负数，其中 0 表示正数，1 表示负数。
  2. 41 个时间戳位：记录了生成该 ID 时的精确时间戳，精确到毫秒级别。
  3. 10 个工作机器位：记录了该 ID 是由哪台机器生成的。
  4. 12 个序列号位：记录了同一毫秒内生成的不同 ID（即同一台机器在同一时间戳内生成的多个 ID）。

数据库

Innodb 介绍

底层存储为 B+树，提供了 ACID 事务支持以及高度的并发性，相比于其他存储引擎，Innodb 具有更好的性能、可靠性和稳定性。 数据是按照数据页来进行读取的，InnoDB 的默认数据页是 16KB，当需要读取一条记录的时候，会以页为单位，将整体读进内存。 InnoDB 还支持崩溃恢复（redo log），多版本控制（MVCC），外键，用索引优化查询速度。

存储引擎

MyISAM：不支持事务、表级锁，读多写少 Memory：临时表，基于内存

ACID 介绍

  • 原子性（Atomicity）：一个事务中的所有操作，要么全部完成，要么全部不完成，不会结束在中间某个环节，而且事务在执行过程中发生错误，会被回滚到事务开始前的状态，就像这个事务从来没有执行过一样，就好比买一件商品，购买成功时，则给商家付了钱，商品到手；购买失败时，则商品在商家手中，消费者的钱也没花出去。
  • 一致性（Consistency）：是指事务操作前和操作后，数据满足完整性约束，数据库保持一致性状态。比如，用户 A 和用户 B 在银行分别有 800 元和 600 元，总共 1400 元，用户 A 给用户 B 转账 200 元，分为两个步骤，从 A 的账户扣除 200 元和对 B 的账户增加 200 元。一致性就是要求上述步骤操作后，最后的结果是用户 A 还有 600 元，用户 B 有 800 元，总共 1400 元，而不会出现用户 A 扣除了 200 元，但用户 B 未增加的情况（该情况，用户 A 和 B 均为 600 元，总共 1200 元）。
  • 隔离性（Isolation）：数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致，因为多个事务同时使用相同的数据时，不会相互干扰，每个事务都有一个完整的数据空间，对其他并发事务是隔离的。也就是说，消费者购买商品这个事务，是不影响其他消费者购买的。
  • 持久性（Durability）：事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失。

乐观锁、悲观锁

先进行操作，如果其他线程对数据也进行了修改，就放弃这次操作（或者做进一步的处理）；加锁避免 race

B 树，LSM 树，B+树，红黑树，跳表的优缺点，什么场景用什么

  1. B 树：多路搜索树，它可以在磁盘等外部存储设备上高效地进行数据访问，因此被广泛应用于文件系统和数据库等领域。B 树的优点是可以在磁盘上进行高效的查找、插入和删除操作，缺点是节点的大小比较大，与 B+树存储数据量相同时层数较多，需要进行频繁的 I/O 操作。
  2. B+树：多路搜索树，它是 B 树的一种变体，相比于 B 树，B+树的叶子节点只存储数据，而非指针，可以减少磁盘 I/O 操作，因此在数据库和文件系统等领域得到广泛应用。B+树的优点是可以在磁盘上进行高效的查找、插入和删除操作，缺点是节点的大小比较大，需要进行频繁的 I/O 操作。
  3. LSM 树：基于磁盘的数据结构，它将数据分为内存和磁盘两部分，内存中维护一个有序的数据结构，磁盘中维护一个较大的无序数据结构。LSM 树的优点是可以快速地进行插入操作，缺点是查询操作需要在内存和磁盘之间进行多次合并操作，效率较低。
  4. 红黑树：红黑树是一种自平衡二叉查找树，它在维护二叉查找树的基础上，通过颜色标记节点，保证树的平衡性，被广泛应用于 STL 等标准库中。红黑树的优点是可以快速地进行查找、插入和删除操作，缺点是节点的旋转操作比较复杂，实现难度较大。
  5. 跳表：跳表是一种基于链表的数据结构，它通过在链表中添加多级索引，可以快速地进行查找操作，被广泛应用于 Redis 等内存数据库中。跳表的优点是可以快速地进行查找、插入和删除操作，而且实现相对简单，缺点是需要占用更多的内存空间来维护索引，不适合存储大量数据。

如果需要在磁盘等外部存储设备上进行高效的数据访问，可以选择 B 树或 B+树；写入较多，可以选择 LSM 树；需要在内存中进行快速的查找、插入和删除操作，可以选择红黑树或跳表。

B+树于 B 树

  • B+树中间节点存的是索引，只有叶子节点存数据，叶子节点被链接成一个有序双向链表，有利于范围查找。B+树的单个节点数据量更小，在相同的磁盘 I/O 次数下，可以查询更多的节点（这个方面主要是因为每个节点的默认大小是 16KB，如果用的是 B+树，非叶子节点只会包含索引，假设索引的大小是 14byte，那么一个结点存储的索引数量为 1e3 个，对于一颗高度为 3 的 B+树可以存储 1e3 * 1e3 个叶子节点）。
  • 单点查询的时候 B 树的性能可能比 B+树要好，范围查询和遍历就是 B+树更优。
  • B+树冗余较多，插入删除改动比 B 树要少。
  • B+树的非叶子节点可以存放更多索引，因此 B+树可以比 B 树更矮胖，查询底层节点的磁盘 IO 次数会更少。

B+树如果存在多个索引，并且通过非主键索引找到了一个叶子节点，叶子节点存的并不是数据，而是主键，这时候就需要回表进一步查询（回表）。

跳表于平衡树

在做范围查找的时候，平衡树比 skiplist 操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在 skiplist 上进行范围查找就非常简单，只需要在找到小值之后，对第 1 层链表进行若干步的遍历就可以实现。

平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而 skiplist 的插入和删除只需要修改相邻节点的指针，操作简单又快速。

从内存占用上来说，skiplist 比平衡树更灵活一些。一般来说，平衡树每个节点包含 2 个指针（分别指向左右子树），而 skiplist 每个节点包含的指针数目平均为 1/(1-p)，具体取决于参数 p 的大小。如果像 Redis 里的实现一样，取 p = 1/4，那么平均每个节点包含 1.33 个指针，比平衡树更有优势。

查找单个 key，skiplist 和平衡树的时间复杂度都为 O(log n)，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近 O(1)，性能更高一些。所以我们平常使用的各种 Map 或 dictionary 结构，大都是基于哈希表实现的。 从算法实现难度上来比较，skiplist 比平衡树要简单得多。

sql 优先级

group by > where > order by > limit

索引，按物理存储分类

  • 主键索引（聚簇索引）的 B+Tree 的叶子节点存放的是实际数据，所有完整的用户记录都存放在主键索引的 B+Tree 的叶子节点里；
  • 二级索引（辅助索引）的 B+Tree 的叶子节点存放的是主键值，而不是实际数据。

索引，按字段特性分类

  • 主键索引
  • 唯一索引（可多个）
  • 普通索引
  • 前缀索引 对字符类型字段的前几个字符建立索引，减少索引占用的存储空间并提升查询效率。
  • 联合索引 将多个字段组合成一个索引。 联合索引遵循最左匹配原则，假设（a，b，c）为索引，应该先按照 a 排序，在 a 相同的情况下按 b 排序，再按 c 排序。所以 b 和 c 是全局无序，局部相对有序的。 如果 select * from t_table where a > 1 and b = 2，则只有 a 字段用到了联合索引进行查询；但 select * from t_table where a >= 1 and b = 2，就是 ab 两个字段都用到了。因为在 a = 1 的时候，b 是有序的。

同时处理多个事务时，可能出现什么问题

脏读：读到未提交事务修改过的数据（未提交事务可能发生回滚） 不可重复读：在一个事务中多次读取同一行数据，但是却读取到了不同的数据。这是因为在此过程中，另一个事务可能已经修改了这一行数据（快照读） 幻读：在一个事务中执行一次查询操作，发现有新的符合条件的行，但是在此之前的查询操作中不存在这些符合条件的行，这是因为在此期间另一个事务插入了一些新的数据行（MVCC+间隙锁）

  • 读未提交（read uncommitted），指一个事务还没提交时，它做的变更就能被其他事务看到；
  • 读提交（read committed），指一个事务提交之后，它做的变更才能被其他事务看到；
  • 可重复读（repeatable read），指一个事务执行过程中看到的数据，一直跟这个事务启动时看到的数据是一致的，MySQL InnoDB 引擎的默认隔离级别；
  • 串行化（serializable ）；会对记录加上读写锁，在多个事务对这条记录进行读写操作时，如果发生了读写冲突的时候，后访问的事务必须等前一个事务执行完成，才能继续执行；

InnoDB 的可重复读针对以下两点优化了幻读发生的概率：

  • 针对 快照读（普通 select 语句），是 通过 MVCC 方式解决了幻读，因为可重复读隔离级别下，事务执行过程中看到的数据，与这个事务启动时看到的数据是一致的，即使中途有其他事务插入了一条数据，是查询不出来这条数据的，所以就很好了避免幻读问题。
  • 针对 当前读（select … for update 等语句），是 通过 next-key lock（记录锁 + 间隙锁）方式解决了幻读，因为当执行 select … for update 语句的时候，会加上 next-key lock，如果有其他事务在 next-key lock 锁范围内插入了一条记录，那么这个插入语句就会被阻塞，无法成功插入，所以就很好了避免幻读问题。
  • InnoDB 幻读举例： 第一个例子：对于快照读，MVCC 并不能完全避免幻读现象。因为当事务 A 更新了一条事务 B 插入的记录，假如这个记录之前查到是没有的，更新完再查询发现有了，那么事务 A 前后两次查询的记录条目就不一样了，也就发生幻读了；第二个例子：对于当前读，如果事务开启后，并没有执行当前读，而是先快照读，然后这期间如果其他事务插入了一条记录，那么事务后续使用当前读进行查询的时候，就会发现两次查询的记录条目就不一样了，所以就发生幻读。 为了避免幻读，尽量在开启事务之后，马上执行 select … for update 这类当前读的语句，因为它会对记录加 next-key lock，从而避免其他事务插入一条新记录。

NoSQL

Elasticsearch 以倒排索引作为核心技术，提供了分布式全文搜索服务（将计入的某些列进行分词，形成分词与记录 ID 之间的映射关系） MongoDB

Log

  1. Undo log：

    • 实现事务回滚，保障事务的原子性。事务处理过程中，如果出现了错误或者用户执 行了 ROLLBACK 语句，MySQL 可以利用 undo log 中的历史数据将数据恢复到事务开始之前的状态。
    • 实现 MVCC（多版本并发控制）关键因素之一。MVCC 是通过 ReadView + undo log 实现的。undo log 为每条记录保存多份历史数据，MySQL 在执行快照读（普通 select 语句）的时候，会根据事务的 Read View 里的信息，顺着 undo log 的版本链找到满足其可见性的记录。

  2. Redo log： Redo 日志用于在 MySQL 崩溃时恢复未提交的更改。每个修改数据的事务都必须写入 Redo log，以确保在 MySQL 崩溃后可以恢复该修改。Redo 日志的作用是，当数据库系统崩溃时，使用 Redo 日志重放（或重新执行）未提交的事务，因此在崩溃后数据库可以恢复到之前的状态。 由两个文件组成，可以循环读写。

  3. Binlog： 二进制日志（Binlog）记录了每个对 MySQL 数据库进行的更改，包括对表结构、记录和数据库选项的更改。用于备份恢复、主从复制；

两阶段提交

  • prepare 阶段：将 XID（内部 XA 事务的 ID）写入到 redo log，同时将 redo log 对应的事务状态设置为 prepare，然后将 redo log 持久化到磁盘（innodb_flush_log_at_trx_commit = 1 的作用）；
  • commit 阶段：把 XID 写入到 binlog，然后将 binlog 持久化到磁盘（sync_binlog = 1 的作用），接着调用引擎的提交事务接口，将 redo log 状态设置为 commit，此时该状态并不需要持久化到磁盘，只需要 write 到文件系统的 page cache 中就够了，因为只要 binlog 写磁盘成功，就算 redo log 的状态还是 prepare 也没有关系，一样会被认为事务已经执行成功；

索引失效

  • 当我们使用左或者左右模糊匹配的时候，也就是  like %xx  或者  like %xx% 这两种方式都会造成索引失效；
  • 当我们在查询条件中对索引列使用函数，就会导致索引失效。
  • 当我们在查询条件中对索引列进行表达式计算，也是无法走索引的。
  • MySQL 在遇到字符串和数字比较的时候，会自动把字符串转为数字，然后再进行比较。如果字符串是索引列，而条件语句中的输入参数是数字的话，那么索引列会发生隐式类型转换，由于隐式类型转换是通过 CAST 函数实现的，等同于对索引列使用了函数，所以就会导致索引失效。
  • 联合索引要能正确使用需要遵循最左匹配原则，也就是按照最左优先的方式进行索引的匹配，否则就会导致索引失效。
  • 在 WHERE 子句中，如果在 OR 前的条件列是索引列，而在 OR 后的条件列不是索引列，那么索引会失效。

MVCC

通过 Read View 实现。针对不同的隔离级别：读未提交、读已提交、可重复读、串行化，会有不同的创建 Read View 的时机，创建的 Read View 包括几个字段：creator_trx_id, m_ids[], min_trx_id, max_trx_id。比如读已提交，事务的每条指令都要创建一个 Read View，读之前需要看一下需要读的数据的 trx_id，如果小于 min_trx_id 的话就直接读，如果在 min_trx_id 和 max_trx_id 之间，就看一下是否在 m_id[] 里面，如果在，就看上一条 Undo Log，否则直接读这个。

范式

1NF：单个属性 2NF：非主属性都依赖于所有主码 3NF：无传递依赖 BCNF：主属性互相不依赖 4NF：无多对多关系

Redis

Redis 采用单线程（网络 I/O 和执行命令）的原因

  • Redis 的大部分操作 都在内存中完成，并且采用了高效的数据结构，因此 Redis 瓶颈可能是机器的内存或者网络带宽，而并非 CPU，既然 CPU 不是瓶颈，那么自然就采用单线程的解决方案了；
  • Redis 采用单线程模型可以 避免了多线程之间的竞争，省去了多线程切换带来的时间和性能上的开销，而且也不会导致死锁问题。
  • Redis 采用了  I/O 多路复用机制 处理大量的客户端 Socket 请求，IO 多路复用机制是指一个线程处理多个 IO 流，就是我们经常听到的 select/epoll 机制。简单来说，在 Redis 只运行单线程的情况下，该机制允许内核中，同时存在多个监听 Socket 和已连接 Socket。内核会一直监听这些 Socket 上的连接请求或数据请求。一旦有请求到达，就会交给 Redis 线程处理，这就实现了一个 Redis 线程处理多个 IO 流的效果。

Golang

GO 环境

GOPATH：工作目录，告诉 Go 编译器和构建系统在哪里查找依赖包。 GOBIN：$GOPATH/bin 存可执行文件，一般是像 goctl 那样的。go get -u xxx GOROOT：标准库和其他系统级别的包。 go install 会自动将可执行文件放在当前目录

数组，slice，map 底层机制以及扩容

  • 数组是由固定长度，存储同一类型元素的数据结构，每个元素的存储地址是相邻的。
  • slide 是一个结构体，包含指向数组的指针，以及长度和容量，如果需要扩容，则指针改变，原内容复制。扩容的具体实现我看的是 go 1.19.4 源码，如果目标容量大于两倍，直接扩容到目标容量；否则，容量如果小于 256，是按照两倍来扩容，否则就 newcap += (newcap + 3*threshold) / 4, threshold = 256，并且会进行内存对齐（传入当前的 newcap，然后根据 go 定义好的内存分配数组进行 lower_bound），按照 1.25 倍以上来扩容，使得前期扩容快一点，容量如果比较大，扩容后的数量会无限接近 1.25 倍。

map 的 key 不能是什么，为啥？

不能是函数、字典、切片。因为不支持判等（用 == 和 !=）

make 和 new

make 和 new 的第一个参数都是 type，但是 make 返回的是类对象，而 new 返回的是类的指针。

goroutine 和 channel

Go 有一个理念是不要用共享内存来通信，用通信来实现共享内存。Go 的通信顺序进程就是通过 goroutine 和 channel 来实现的。

接口

在 Go 语言中，接口是一种类型，它定义了一个类的行为规范，具体实现则由实现该接口的类决定。任何类只要实现了接口定义的方法即可被称为该接口类型的实例。 在 Go 语言中，接口变量包含两部分内容：类型和值。其中类型表示该接口变量所代表的接口类型，值则表示该接口变量所代表的实际类型的值。对于接口类型的变量，其值可以是任何实现了该接口的类型的值。 interface 结构体包含 eface 和 iface，iface 是一个指向方法表和数据结构的指针。这个指针包含了类型信息和一组方法的指针。iface 主要用于类型断言和类型转换，并且在接口变量赋值时会进行类型转换操作。eface 是指向任意类型和数据结构的指针（空接口）。eface 包含了实际的值和类型信息。eface 可以用于存储任意类型的数据，并传递给需要使用通用类型参数的函数，通过反射实现动态类型检查和方法调用。

反射

允许程序在运行时动态获取一个值的类型信息并对其进行操作。Go 语言的反射机制包括两个主要的类型：reflect.Type 和 reflect.Value。

receiver 规范

在 golang 的方法中，值类型的接收者既可以接收指针，也可以接收值；但指针类型的接收者只能接收指针。

channel

一种基于通信的并发编程原语，用于在 goroutine 之间同步数据和控制流 buffer 指向底层的循环数组；sendq 和 recvq 存储的是协程发送的队列以及接收队列

Go 实现面向对象

封装、继承、多态 struct、struct 内嵌、interface

Go map

map 底层是基于哈希表实现的。读写的平均复杂度是 O(1)。 map 的主要结构是 hmap hashmap。map 会包含一个桶的数组，数组的长度是 2 的 B 次方，B 的大小与负载因子有关。每个 bucket 设计成最多只能放 8 个 key-value 对，如果有第 9 个 key-value 落入当前的 bucket，那就需要再构建一个 bucket，通过 overflow 指针连接起来。key 分配：hash(key)&0b1111 在向 map 插入新 key 的时候，会进行条件检测，符合下面这 2 个条件，就会触发扩容：

  1. 负载因子超过 6.5，非等量扩容。等量扩容是指在达到 map 容量上限时将容量按照一定比例增加。
  2. overflow bucket 太多（cnt >= min(2^15, 2^m)）等量扩容。而非等量扩容则是根据当前元素数量重新计算容量，并分配一个新的底层数组。 在写操作的时候，会观察 flag 的写标志位是不是 1，如果是 1，则表明这时候有其他 Goroutine 正在对 map 进行写操作，就会发生 panic。

for range 是语法糖，会被隐式转换成传统的 for

Go 中 slice 和 map 的底层实现原理

slice 的底层是一个可以扩容的数组，它包含三个字段：指针、长度、容量。 map 的底层是一个哈希表，其中包含若干个桶，每个桶又包含若干个键值对。为了解决哈希冲突，每个桶可能会包含一个链表。

Go GC

从标记清除（从全局 STW 到清除时不 STW）到三色标记（如果对象的引用被用户修改了，那么之前的标记就无效了。因此 Go 采用了 写屏障技术，当对象新增或者更新会将其着色为灰色）。 混合写屏障：1. GC 开始时，将栈上的全部对象标记为黑色（不需要二次扫描，无需 STW）；2. GC 期间，任何栈上创建的新对象均为黑；3. 被删除引用的对象标记为灰；4. 被添加引用的对象标记为灰色

GMP 在程序运行初始 G、M、P 分别会怎么创建和分配？

M 最大 10000，debug.SetMaxThreads；G 受内存影响，由用户自己创建；P 受 CPU 虚拟核心数影响，可通过 runtime.GOMAXPROCS 配置。初始化的时候会初始化 g0 和 m0，p 的数量为 GOMAXPROCS，最大不能超过 1024。

内存泄漏

内存泄漏是指在程序运行中无法释放已经分配的内存，导致程序运行的期间实际可用的内存逐渐减少。发生的场景有：有缓冲的 go channel 没有接收端，循环引用，全局变量，文件句柄未关闭，大量内存分配……

内存逃逸

Golang 在编译的时候会将变量放在堆或者栈上面，当一个变量在函数执行结束后仍然有可能被访问或者其生命周期未能在编译阶段确定时，就会发生“逃逸”，导致程序运行的期间实际可用的内存逐渐减少。发生的场景有：有缓冲的 go channel，因为需要发送内容到接收端，所以需要变量逃逸到堆；动态类型，比如说子类用到了接口的函数；局部变量指针的返回；文件句柄未关闭，大量内存分配……

Go Scheduler

https://golang.design/go-questions/sched/init/ Golang 调度器，通过 GMP 实现。 特点：

  1. reuse threads；
  2. 限制同时运行（不包含阻塞）的线程数为 N，N 等于 CPU 的核心数目；
  3. 线程私有的 runqueues，并且可以从其他线程 stealing goroutine 来运行，线程阻塞后，可以将 runqueues 传递给其他线程。

初始化：

  1. call osinit。初始化系统核心数。
  2. call schedinit。初始化调度器。
  3. make & queue new G。创建新的 goroutine。
  4. call runtime · mstart。调用 mstart，启动调度。
  5. The new G calls runtime · main。在新的 goroutine 上运行 runtime.main 函数。

主 Goroutine 的运行

变量初始化，调度器初始化，调用 newproc(fn, fn_size)，创建 G0 和 P [GOMAXPROCS]，将 G0 和 P0 绑定，用 G0 进行循环调度（执行 Goroutine 工作）

sysmon 后台监控线程

线程，不依赖 P

  1. 抢占处于系统调用的 P，让其他 m 接管它，以运行其他的 goroutine。
  2. 将运行时间过长的 goroutine 调度出去，给其他 goroutine 运行的机会。

讲讲 GPM

GPM 是 Golang 调度器的核心设计。 其中，G 是 Goroutine，Goroutine 是轻量级的线程，可以用来并发执行函数，每个 Goroutine 由一个 G 结构体和一个堆栈组成，用于存储函数调用的参数，局部变量和返回值。 P 是 Processor，Processor 是 Golang 调度器的处理器，用于执行 Goroutine。每个 Processor 都绑定了一个 Goroutine 运行队列，用于存储可执行的 Goroutine，当某个 Processor 上的 Goroutine 全部都被阻塞或者为空时，该 Processor 就会向全局调度器请求更多的 Goroutine 来执行。调度器会负责将可执行的 Goroutine 分配到空闲的 Processor 上，从而实现高效的并发和调度。 M 是 Machine，Machine 是 Golang 调度器的机器，就是操作系统的线程。每个 Machine 都用于执行一个 Processor，当一个 Processor 需要执行 Goroutine 时，它会将 Goroutine 绑定到一个 Machine 上运行。每个 Machine 都有一个固定大小的栈和元信息，例如当前执行的 Goroutine、内存分配器的状态等。 每个 Goroutine 都会绑定到一个 Processor 上运行，每个 Processor 都会绑定到一个 Machine 上运行。当一个 Goroutine 需要执行时，它会被分配到其中一个 Processor 上，并在该 Processor 上执行。当它需要阻塞时，它就会放弃 Processor，并等待其他 Goroutine 的执行。

go 内存分配

每一个进程会维护一个页表，用于转换虚拟地址到实际地址。这个虚拟地址是从 0 开始的，堆内存不够用的时候，进程可以通过系统调用 brk（sbrk/mmap）获得内存。 Golang 的内存分配算法是 TCMalloc 在 TCMalloc 内存管理分为两个部分：线程内存（thread memory) 和页堆（page heap）。

线程内存：每一个内存页都被分为多个固定分配大小规格 (<= 32KB) 的空闲列表（free list）用于减少碎片化。并使得在内存分配过程中只需要一次系统调用，后续分配都是用户态。并进行多级管理，以降低锁的粒度。 页堆：一组连续的页面被表示为 span，当分配的对象大于 32KB，会使用页堆进行内存分配。

golang 通过 mspan 对内存页进行管理，mspan  是一个包含页起始地址、页的 span 规格和页的数量的双端链表。

每个 Processor 会维护一个本地线程缓存（mcache，存的是不同 mspan 的指针），如果 Goroutine 需要内存可以直接从 mcache 获取。如果 mcache 没有可用空间，会从 mcentral 的 mspans 列表获取一个新的所需大小规格的 mspan。

mcentral 为所有 mcache 切分好后备的 mspan。每一个  mcentral  都包含两个 mspan 的列表：

  1. empty mspanList – 没有空闲对象或 span 已经被 mcache 缓存的 span 列表
  2. nonempty mspanList – 有空闲对象的 span 列表

每一个 mcentral 结构体都维护在  mheap  结构体内。

Go 使用 mheap 对象管理堆，只有一个全局变量。持有虚拟地址空间。

  • 大于 32K 的大对象直接从  mheap  分配 (mheap 唯一，需要加锁)
  • 小于 16B 的使用  mcache  的微型分配器分配
  • 对象大小在 16B ~ 32K 之间的的，首先通过计算使用的大小规格，然后使用  mcache  中对应大小规格的块分配
  • 如果对应的大小规格在  mcache  中没有可用的块，则向  mcentral  申请
  • 如果  mcentral  中没有可用的块，则向  mheap  申请，并 根据 BestFit 算法找到最合适的 mspan。如果申请到的  mspan  超出申请大小，将会根据需求进行切分，以返回用户所需的页数。剩余的页构成一个新的  mspan  放回  mheap  的空闲列表。
  • 如果  mheap  中没有可用 span，则向操作系统申请一系列新的页（最小 1MB）

    但是 Go 会在操作系统分配超大的页（称作 arena）。分配一大批页会减少和操作系统通信的成本。

操作系统

锁

死锁：互斥、占有且等待、不可强制占用、循环等待 互斥锁：当无法获取锁的时候，需要切换到内核态进行线程休眠，将 CPU 释放给其他线程；但锁释放的时候，之前休眠的线程就会变成就绪状态，内核在恰当的时间切换 CPU 给线程。有两次上下文切换的开销。 自旋锁：在用户态完成加锁和解锁，不会产生线程上下文切换，适合锁住的复杂度不高的情况。

程序启动

  1. 从磁盘上读取可执行文件，加载到内存
  2. 创建进程和主线程
  3. 为主线程分配栈空间
  4. 把由用户在命令行输入的参数拷贝到主线程的栈
  5. 把主线程放入操作系统的运行队列等待被调度

锁类型

互斥锁：通过休眠使线程阻塞 自旋锁：不断判断锁时候能被获取，占有 CPU 饥饿模式：当前在 CPU 上运行的 goroutine 更先获取到锁，新请求锁的 Goroutine 具有优势，因为其正在 CPU 上执行

中断

  • 上半部，对应硬中断，由硬件触发中断，快速处理中断；
  • 下半部，对应软中断，由内核触发中断，异步处理上半部未完成的工作；

进程、线程、协程

进程是操作系统进行资源分配的最小单位、线程是 CPU 执行的最小单位、协程是用户态的轻量级线程，由线程进行调度。 同一个进程内的线程共享本进程的资源和地址空间；进程之间则相互独立。 多进程的鲁棒性更强，进程崩溃后一般不会对其他进程产生影响；线程崩溃后进程内的其他线程可能会受到影响。 进程切换开销较大；线程切换则开销较小，因为进程下不同线程的切换时不用切换进程的上下文、文件句柄、进程堆栈等信息。

通信

管道、消息队列、共享内存、信号量（PV）、信号、Socket PV：

  • 进程 A 在访问共享内存前，先执行了 P 操作，由于信号量的初始值为 1，故在进程 A 执行 P 操作后信号量变为 0，表示共享资源可用，于是进程 A 就可以访问共享内存。
  • 若此时，进程 B 也想访问共享内存，执行了 P 操作，结果信号量变为了 -1，这就意味着临界资源已被占用，因此进程 B 被阻塞。
  • 直到进程 A 访问完共享内存，才会执行 V 操作，使得信号量恢复为 0，接着就会唤醒阻塞中的线程 B，使得进程 B 可以访问共享内存，最后完成共享内存的访问后，执行 V 操作，使信号量恢复到初始值 1。

Socket：

  • 服务端和客户端初始化  socket，得到文件描述符；
  • 服务端调用  bind，将绑定在 IP 地址和端口;
  • 服务端调用  listen，进行监听；
  • 服务端调用  accept，等待客户端连接；
  • 客户端调用  connect，向服务器端的地址和端口发起连接请求；
  • 服务端  accept  返回用于传输的  socket  的文件描述符；
  • 客户端调用  write  写入数据；服务端调用  read  读取数据；
  • 客户端断开连接时，会调用  close，那么服务端  read  读取数据的时候，就会读取到了  EOF，待处理完数据后，服务端调用  close，表示连接关闭。

这里需要注意的是，服务端调用  accept  时，连接成功了会返回一个已完成连接的 socket，后续用来传输数据。

所以，监听的 socket 和真正用来传送数据的 socket，是「两个」socket，一个叫作 监听 socket，一个叫作 已完成连接 socket。

本地字节流 socket 和 本地数据报 socket 在 bind 的时候，不像 TCP 和 UDP 要绑定 IP 地址和端口，而是 绑定一个本地文件，这也就是它们之间的最大区别。

虚拟内存的好处

虚拟内存： 分段：段选择因子 + 段内偏移量，问题：虽无内部内存碎片，但有外部内存碎片 分页：每一页的大小为 4KB，需要分多级页表来节约页表的空间（如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表） 64 位通常是四级分页 段页式管理：段号 + 段内页号 + 页内偏移量 Linux 的段主要用于访问控制和内存保护

  • 读写内存的安全性
  • 让每个进程有独立的地址空间
  • 虚拟内存到真实内存的映射会给分配和释放带来方便
  • 一个系统如果同时运行着很多进程，为各个内存分配的虚拟内存之和可能会大于可用的物理内存，但通过虚拟内存管理可以使得各个进程正常运行

进程与虚拟内存

虽然每个进程都各自有独立的虚拟内存，但是 每个虚拟内存中的内核地址，其实关联的都是相同的物理内存。这样，进程切换到内核态后，就可以很方便地访问内核空间内存。

  • 代码段，包括二进制可执行代码；
  • 数据段，包括已初始化的静态常量和全局变量；
  • BSS 段，包括未初始化的静态变量和全局变量；
  • 堆段，包括动态分配的内存，从低地址开始向上增长；
  • 文件映射段，包括动态库、共享内存等，从低地址开始向上增长（跟硬件和内核版本有关  (opens new window)）；
  • 栈段，包括局部变量和函数调用的上下文等。栈的大小是固定的，一般是  8 MB。当然系统也提供了参数，以便我们自定义大小；

内存满了

触发内存回收，先是后台内存回收，如果后台异步回收跟不上内存申请的速度，就进行直接（同步）内存回收，会阻塞进程的执行。 还是无法满足的话就会触发 OOM 机制。 OOM Killer 机制会根据算法选择一个占用物理内存较高的进程，然后将其杀死，以便释放内存资源，如果物理内存依然不足，OOM Killer 会继续杀死占用物理内存较高的进程，直到释放足够的内存位置。

零拷贝

传统数据拷贝是通过 read()、write() 完成的，需要四次用户态和内核态切换、四次数据拷贝。首先 read() 是切换内核态进行系统调用（DMA 拷贝），DMA 拷贝完成后，CPU 再将数据拷贝到用户缓冲区，同时切回用户态；write 同理，先 CPU 拷贝数据到缓冲区，再通过 DMA 拷贝从换成功领取拷贝到网卡。 mmap+write：操作系统将缓冲区的数据拷贝到 socket 缓冲区，mmap() 会直接把内核缓冲区的数据映射到用户空间，CPU 直接在内核态将内核缓冲区的数据拷贝到 socket 缓冲区中。实际需要 4 次上下文切换，因为系统调用还是两次。 sendfile：代替 read()+write()，减少一次系统调用，减少两次上下文切换。主要交给内核态处理（在网卡支持 SG-DMA 的时候，只会用到两次 DMA 拷贝——从硬盘读到内核缓冲区再读到目的地，但不支持的话，只能从一个缓冲区拷贝到另一个缓冲区再拷贝到目的地） 大文件 IO 操作通常采用异步实现，因为零拷贝大文件会占用热点小文件的空间。

进程切换会包含什么

进程的上下文切换不仅包含了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的资源。

什么是 IO 多路复用，说一下 select/poll/epoll

IO 多路复用是一种处理多个 IO 请求的技术，它可以让单个线程同时监控多个 IO 操作。在传统的 IO 操作中，每个 IO 请求需要创建一个进程或线程来进行读写操作。为了提高效率和性能，这种方法逐渐被 IO 多路复用技术代替。

在 Linux 下，一般使用 select、poll 和 epoll 这三种 IO 多路复用方式来监控多个网络连接。这些方式都允许单个线程监控多个文件描述符，让它们在有 I/O 事件到来时能够触发相应的回调函数进行处理。其中，select 和 poll 使用的是轮询的方式，而 epoll 则使用了事件通知的方式，具有更快的响应速度，更低的系统开销和更高的并发能力。

在使用 select/poll/epoll 时，内核都会将需要监视的文件描述符集合拷贝到内核空间进行监听，当发生事件时，通过回调函数通知应用程序进行处理。其中，select 会限制了监视的文件描述符数量；poll 则用动态数组维护监听的文件描述符集合，同时也不能处理文件描述符的状态变化；epoll 则将文件描述符添加到红黑树中进行管理，每次有事件发生时，只通知发生变化的文件描述符，避免了轮询时的浪费。因此，在 IO 多路复用中，epoll 是更加高效和灵活的方式。

一致性哈希

是一种实现均衡负载的机制，具体而言是在客户端和服务器之间通过分流的方式将请求均匀地分给不同的服务器。并且请求到达的服务器应该是相对确定的，因为这样可以更好地用到缓存机制。比较常用的哈希方法是虚拟一个圆环，然后将机器的虚拟节点均匀地分布到圆环的不同位置，通过对请求进行 hash，将哈希值对应到圆环上，用 lower_bound 找到下一个虚拟节点，那么这个请求就由这个服务器进行相应。

水平触发和边缘触发

水平触发的意思是只要满足事件的条件，比如内核中有数据需要读，就一直不断地把这个事件传递给用户；而边缘触发的意思是只有第一次满足条件的时候才触发，之后就不会再传递同样的事件了。 如果使用边缘触发模式，I/O 事件发生时只会通知一次，而且我们不知道到底能读写多少数据，所以在收到通知后应尽可能地读写数据，以免错失读写的机会。因此，我们会 循环 从文件描述符读写数据，那么如果文件描述符是阻塞的，没有数据可读写时，进程会阻塞在读写函数那里，程序就没办法继续往下执行。所以，边缘触发模式一般和非阻塞 I/O 搭配使用，程序会一直执行 I/O 操作，直到系统调用（如  read  和  write）返回错误，错误类型为  EAGAIN  或  EWOULDBLOCK。

select/poll 只有水平触发模式，epoll 默认的触发模式是水平触发，但是可以根据应用场景设置为边缘触发模式。

Linux

常用：cd ls rm mkdir mv vim grep tail chmod 777 ：第一个数字表示用户的权限，第二个数字表示用户所在组的权限，第三个数字表示其他用户的权限。数字 1 代表执行权限，数字 2 代表写权限，数字 4 代表读权限 history | awk '{print $2}'| sort | uniq -c | sort -rn | head -30 ：uniq -c 计数，sort -r 倒序，sort -n 以数字而非字典序排序

硬链接和软连接

linux 下的文件是通过（索引节点）Inode 来识别的，文件系统会给硬盘上的区块一个引用计数，只要有文件指向这个区块，它就不会从硬盘上消失。

硬链接：创建新的文件，指向同一个 Inode 软链接：文件名指向一个新建的 Inode，新的 Inode 指向老的 Inode

计网

TCP 三次握手

  • 一开始，客户端和服务器都处于  CLOSED  状态。先是服务器主动监听某个端口，处于  LISTEN  状态。
  • 然后客户端会主动发送  SYN 包并随机初始化一个序列号（seq = x），变为  SYN-SENT  状态。
  • 服务器收到 SYN 报文之后，返回  SYN （seq = y）和  ACK （seq = x+1）包，在请求响应的同时响应客户端的  SYN，之后处于  SYN-RCVD  状态。
  • 客户端收到服务器发送的  SYN  和  ACK  包之后，发送对  SYN  确认的  ACK （seq = y+1），之后处于  ESTABLISHED  状态，因为它已经一发一收了。
  • 服务器收到客户端的  ACK  之后，也处于 ESTABLISHED  状态，因为它也一发一收了。

三次握手目的是保证双方都有发送和接收的能力，具体而言：

  • 阻止重复历史连接的初始化（主要原因）
  • 同步双方的初始序列号
  • 避免资源浪费

TCP 四次挥手

TCP 是双工的，假设现在客户端需要关闭连接

  • 客户端发送 FIN 包给服务器，处于 FIN-WAIT-1 状态。
  • 服务器收到 FIN 包后，回复 ACK 包给客户端，然后处于 CLOSE-WAIT 状态，表示知道了。
  • 客户端收到 ACK 包后，进入 FIN-WAIT-2 状态，等待服务器发送自己的 FIN 包。
  • 服务器仍可单方向发送数据。
  • 服务器发送 FIN 包后，进入 LAST-ACK 状态。
  • 客户端发送 ACK 后，进入 TIME-WAIT 状态（2MSL），最终关闭连接，进入 CLOSED 状态。
  • 服务器收到 ACK 后，进入 CLOSED 状态。

TIME-WAIT 的用途

  1. 确保被动关闭的一方可以收到第四次挥手的 ACK 包
  2. 避免上一次 TCP 连接的数据包影响到下一次 TCP 连接（如果主动关闭方发送了第四次挥手的 ACK 包，但是在发送过程中丢失了，那么被动关闭方就无法收到 ACK 包，会触发第三次挥手的重传，如果重传的时候客户端和服务器建立了新的连接，那么这次 FIN 报文可能就会对新的 TCP 连接造成影响）

HTTP 状态码有哪些

100 中间态

200 OK

300 重定向

400 客户端错误

500 服务端错误

HTTP1.0 和 1.1 的区别

HTTP/1.0 每次发起请求都要进行 TCP 三次握手，HTTP/1.1 提出了长连接的通信方式，也叫持久连接。

这种方式的好处在于减少了 TCP 连接的重复建立和断开所造成的额外开销，减轻了服务器端的负载。

HTTP/1.1 管道解决了请求的队头阻塞，但是没有解决响应的队头阻塞。

1.1 的缺点：

  • 请求 / 响应头部（Header）未经压缩就发送，首部信息越多延迟越大。只能压缩  Body  的部分；
  • 发送冗长的首部。每次互相发送相同的首部造成的浪费较多；
  • 服务器是按请求的顺序响应的，如果服务器响应慢，会招致客户端一直请求不到数据，也就是队头阻塞；
  • 没有请求优先级控制；
  • 请求只能从客户端开始，服务器只能被动响应；

1.1 和 2.0 的区别

头部压缩：客户端和服务器会维护一张头信息表，生成一个索引号，以后就不发送同样字段了。

二进制格式：HTTP/2.0 头部基于二进制编码，通过「静态表、动态表、Huffman 编码」共同完成。

每个 TCP 连接都用多条 Stream 进行并发传输。

服务器主动推送资源（客户端需要的 HTML、CSS、JavaScript、图片等文件）。

2.0 的缺点：

HTTP/2.0 还是存在阻塞的问题，只不过问题不是在 HTTP 这一层面，而是在 TCP 这一层

2.0 和 3.0 的区别

无队头阻塞，QUIC 连接上的多个 Stream 之间并没有依赖，都是独立的，也不会有底层协议限制，某个流发生丢包了，只会影响该流，其他流不受影响；

建立连接速度快，因为 QUIC 内部包含 TLS 1.3，因此仅需 1 个 RTT 就可以「同时」完成建立连接与 TLS 密钥协商，甚至在第二次连接的时候，应用数据包可以和 QUIC 握手信息（连接信息 + TLS 信息）一起发送，达到 0-RTT 的效果；

连接迁移，QUIC 协议没有用四元组的方式来“绑定”连接，而是通过「连接 ID」来标记通信的两个端点，客户端和服务器可以各自选择一组 ID 来标记自己，因此即使移动设备的网络变化后，导致 IP 地址变化了，只要仍保有上下文信息（比如连接 ID、TLS 密钥等），就可以“无缝”地复用原连接，消除重连的成本；

TCP 如何保证可靠性传输

校验和、确认应答、超时重传、滑动窗口、拥塞控制

UDP 如何实现可靠传输

RTO（超时时间）是基于 RTT 来计算的，每次 QUIC 发送数据包 Packet Number 都是单增的，可以保证 RTO 没有歧义。

QUIC 通过单向递增的 Packet Number，配合 Stream ID 与 Offset 字段信息，可以支持乱序确认而不影响数据包的正确组装，摆脱了 TCP 必须按顺序确认应答 ACK 的限制，解决了 TCP 因某个数据包重传而阻塞后续所有待发送数据包的问题。

HTTPS 的特性，加密的具体实现

在 HTTP 和 TCP 之间加了一层 SSL/TLS，最初，客户端发送自己支持的加密算法给服务端，然后服务端传一个证书给客户端，包含自己的公钥以及使用的加密算法，而后客户端会通过内置的证书颁发机构对证书进行检验。而后客户端和服务端统一一个对称加密的密钥（ClientRandom+ServerRandom+Pre-Master），对以后的信息进行加密。

HTTPS 一定可靠吗

中间人攻击

TCP 重传

超时重传 超时重传时间：RTO 略大于 RTT 快速重传：不以时间为驱动，而是以数据驱动重传。比如三次收到相同序号的 ACK 立刻重传（可以通过 SACK 方法通知发送方接收方已经收到了什么包-》让发送方选择发送缺失的包）。

TCP 滑动窗口

发送方和接收方都有窗口。 发送方：发送并被收到 + 发送但未收到 + 未发送但在接收方的处理范围内 + 未发送但总大小超过接收方处理范围，会根据接受情况动态调整。 接收方：成功接收并确认的数据 + 未接收到但可以接受的数据 + 未接收且不能接受的数据。

TCP 拥塞控制

首先会有一个拥塞窗口（cwnd），与发送窗口类似，会对发送的数据包进行限流，在拥塞窗口小于阈值的时候，进行慢启动（这个时候拥塞窗口呈指数增长），大于阈值的时候就会进入拥塞避免算法（线性缓慢增长）。当超时重传的时候，就会使用拥塞发生算法（重设阈值为 cwnd/2，并将 cwnd 重置为初始值）；如果发生的是快速重传（收到三次 ACK）就重置阈值和窗口为 cwnd/2，并且同时使用快速恢复算法将窗口+= 3，并重传丢失的数据包，如果再收到重复的 ACK，cwnd+= 1，如果收到新数据的 ACK，将 cwnd 设为最初的阈值。

防范 SYN 半连接攻击

  1. 启用 SYN Cookies：SYN Cookies 是一种防范 SYN 攻击的方法，其将 TCP 握手过程中的 SYN 包和 ACK 包通过一定算法计算出一个 cookie 值，同时利用该 cookie 值的有效期来保护服务器，从而防止攻击者向服务器发送伪造的 SYN 包。SYN Cookie 技术可以让服务器在收到客户端的 SYN 报文时，不分配资源保存客户端信息，而是将这些信息保存在 SYN+ACK 的初始序号和时间戳中。对正常的连接，这些信息会随着 ACK 报文被带回来。

  2. 增加服务器连接数限制：可以通过调整服务器的连接数限制，限制每个 IP 地址可以同时建立的连接数量，这样可以防止攻击者使用大量伪造的 IP 地址占用服务器资源。

  3. 配置防火墙：可以配置防火墙来过滤掉一些源地址伪造的请求，或对一些频繁访问服务器的 IP 地址进行限制。

  4. 增加服务器硬件能力：当服务器硬件能力增加时，可以承载更多的连接请求，从而减轻 SYN 攻击对服务器的影响。

OSI

  • 应用层，负责给应用程序提供统一的接口；
  • 表示层，负责把数据转换成兼容另一个系统能识别的格式；
  • 会话层，负责建立、管理和终止表示层实体之间的通信会话；
  • 传输层，负责端到端的数据传输；
  • 网络层，负责数据的路由、转发、分片；
  • 数据链路层，负责数据的封帧和差错检测，以及 MAC 寻址；
  • 物理层，负责在物理网络中传输数据帧，通过二进制比特流传输实现；

TCP/IP 模型：四层

  1. 应用层：定义应用程序之间的通信，HTTP、FTP、Telnet、DNS、SMTP 等，当不同设备的应用通信时，应用层就将数据发给下一层（应用层处于操作系统的用户态，以下层为应用态）。
  2. 传输层：端到端的通信。最常用的传输层协议是传输控制协议（TCP）和用户数据报协议（UDP）。TCP 相比 UDP 多了很多特性，比如流量控制、超时重传、拥塞控制等，这些都是为了保证数据包能可靠地传输给对方。TCP segment（分块）可以减少分块损坏重传的大小，最多一个 MSS 1460bytes。
  3. 网络层：负责网络包的封装、分片、路由、转发，比如 IP、ICMP 等；
    • 寻址：子网掩码找到网络号和主机号（方向）
    • 路由：找到 IP 地址应该向哪里转发（导航）
  4. 网络接口层（Link Layer）：在 IP 头部前面加上 MAC 头，并将数据封装成帧、MAC 寻址、差错检测，以及通过网卡传输网络帧等；。其中，最常用的链路层协议是以太网协议。

键入网址到网页显示：

  1. URL 解析：浏览器解析 URL。
  2. DNS 解析：浏览器首先会检查浏览器自己和操作系统缓存是否存在目标主机名的 IP 地址，如果没有，则浏览器会向本地计算机上配置的 DNS 服务器发送一个 DNS 请求，以获取该网站的 IP 地址。
  3. TCP 连接：一旦浏览器具备了目标主机的 IP 地址，它将调用 Socket 库委托操作系统的协议栈工作。具体会使用 TCP 协议建立与该 IP 地址的服务器之间的连接。该协议通过建立一个可靠的连接，确保了数据传输的完整性。
  4. IP：封装成网络包（主要包含的是源地址 IP 和目标地址 IP 以及协议号（TCP：0x06））
    • ICMP  用于告知网络包传送过程中产生的错误以及各种控制信息。
    • ARP  用于根据 IP 地址查询相应的以太网 MAC 地址。
  5. MAC：网络设备间的传输（MAC 地址、接收方地址，协议类型（IP：0x0800，ARP：0x0806））
  6. 网卡：数字信号转为电信号，加上报头、起始帧分界符和末尾的 FCS 帧校验序列。
  7. 交换机（无 mac）：根据 mac 表查找 mac 地址，将信号发送到相应的端口。包接收：将电信号转化成数字信号（广播地址会将包发送到除源端口外的所有端口）。
  8. 路由器（有 mac）：根据 ip 进行转发。
  9. 发送 HTTP 请求：浏览器向服务器发送 HTTP 请求，该请求包含要访问的网站和要执行的操作类型（例如 GET 请求）等信息。
  10. 服务器响应：一旦服务器接收到 HTTP 请求，它将根据请求的内容和其他信息生成一个 HTTP 响应。HTTP 响应通常包含一个状态代码，例如 200 OK，用于指示服务器是否成功处理请求。
  11. 浏览器渲染：一旦浏览器接收到服务器的响应，它将根据响应的内容和 HTML 文档中的其他信息生成网页。浏览器将使用 CSS 和 JavaScript 等附加文件来增强网页并提供附加功能。
  12. 连接关闭：一旦浏览器完成渲染过程，它将使用 TCP 协议中的四次握手来关闭与服务器的连接。

路由器与交换机的区别

  • 路由器 是基于 IP 设计的，俗称 三层 网络设备，路由器的各个端口都具有 MAC 地址和 IP 地址。
  • 交换机 是基于以太网设计的，俗称 二层 网络设备，交换机的端口不具有 MAC 地址。

路由器的端口都具有 MAC 地址，只接收与自身地址匹配的包，遇到不匹配的包则直接丢弃。

MAC 头部的作用就是将包送达路由器，其中的接收方 MAC 地址就是路由器端口的 MAC 地址。因此，当包到达路由器之后，MAC 头部的任务就完成了，于是 MAC 头部就会 被丢弃。

路由器会根据 MAC 头部后方的  IP  头部中的内容进行包的转发操作。 转发操作分为几个阶段，首先是查询 路由表 判断转发目标。 实在找不到匹配路由时，就会选择 默认路由，路由表中子网掩码为  0.0.0.0  的记录表示「默认路由」。

包发送

  • 如果网关是一个 IP 地址，则这个 IP 地址就是我们要转发到的目标地址，还未抵达终点，还需继续需要路由器转发。
  • 如果网关为空，则 IP 头部中的接收方 IP 地址就是要转发到的目标地址，也是就终于找到 IP 包头里的目标地址了，说明 已抵达终点。

发送的时候也需要通过 ARP 协议查询对应 IP 的 MAC 地址，网络包完成后，接下来会将其转换成电信号并通过端口发送出去。这一步的工作过程和计算机也是相同的。在网络包传输的过程中，源 IP 和目标 IP 始终是不会变的，一直变化的是 MAC 地址，因为需要 MAC 地址在以太网内进行 两个设备 之间的包传输。

Linux 收发网络包

网卡是计算机里的一个硬件，专门负责接收和发送网络包，当网卡接收到一个网络包后，会通过 DMA 技术，将网络包写入到指定的内存地址，也就是写入到 Ring Buffer，这个是一个环形缓冲区，接着就会告诉操作系统这个网络包已经到达。

为了解决频繁中断带来的性能开销，Linux 内核在 2.6 版本中引入了  NAPI 机制，它是混合「中断和轮询」的方式来接收网络包，它的核心概念就是 不采用中断的方式读取数据，而是首先采用中断唤醒数据接收的服务程序，然后  poll  的方法来轮询数据。

当有网络包到达时，会通过 DMA 技术，将网络包写入到指定的内存地址，接着网卡向 CPU 发起硬件中断，当 CPU 收到硬件中断请求后，根据中断表，调用已经注册的中断处理函数：

  • 需要先「暂时屏蔽中断」，表示已经知道内存中有数据了，告诉网卡下次再收到数据包直接写内存就可以了，不要再通知 CPU 了，这样可以提高效率，避免 CPU 不停的被中断。
  • 接着，发起「软中断」，然后恢复刚才屏蔽的中断。（软中断会让 ksoftirqd 线程从 Ring Buffer 中获取一个数据帧，用 sk_buff 表示，从而可以作为一个网络包交给网络协议栈进行逐层处理。）

当应用程序通过 Socket 接口发送数据包，数据包会被网络协议栈从上到下进行逐层处理后，才会被送到网卡队列（Ring Buffer）中，随后由网卡将网络包发送出去。

而在接收网络包时，同样也要先经过网络协议栈从下到上的逐层处理，最后才会被送到应用程序。

发送网络数据的时候，涉及几次内存拷贝操作？

第一次，调用发送数据的系统调用的时候，内核会申请一个内核态的 sk_buff 内存，将用户待发送的数据拷贝到 sk_buff 内存，并将其加入到发送缓冲区。

第二次，在使用 TCP 传输协议的情况下，从传输层进入网络层的时候，每一个 sk_buff 都会被克隆一个新的副本出来。副本 sk_buff 会被送往网络层，等它发送完的时候就会释放掉，然后原始的 sk_buff 还保留在传输层，目的是为了实现 TCP 的可靠传输，等收到这个数据包的 ACK 时，才会释放原始的 sk_buff。

第三次，当 IP 层发现 sk_buff 大于 MTU 时才需要进行。会再申请额外的 sk_buff，并将原来的 sk_buff 拷贝为多个小的 sk_buff。

HTTP

HTTP 是一个在计算机世界里专门在「两点」之间「传输」文字、图片、音频、视频等「超文本」数据的「约定和规范」。

HTTPS

  • 信息加密： HTTP 交互信息是被加密的，第三方就无法被窃取；

  • 校验机制：校验信息传输过程中是否有被第三方篡改过，如果被篡改过，则会有警告提示；

  • 身份证书：证明网站的正确性；

    建立连接时增加了 SSL/TLS 验证

  1. 三次握手后，浏览器将支持的加密算法发给服务器
  2. 服务器选择加密算法发证书给浏览器
  3. 客户端（SSL/TLS）解析证书，取出服务器公钥（服务器有私钥，非对称加密），生成对话秘钥（对称加密）客户端随机数+服务器随机数+pre-master
  4. 服务器拿到对话秘钥的密文后，用私钥进行非对称解密，得到对话密钥，在通信时用对话密钥对数据进行加密，数据就变成了密文，服务器再将密文发给客户端。

RPC

RPC 不是协议，gRPC 才是，RPC 的出现时间比 HTTP 流行时间要早。

RPC 大部分情况下比主流 HTTP1.1 性能好，冗余少。

Websocket

  • TCP 协议本身是 全双工 的，但我们最常用的 HTTP/1.1，虽然是基于 TCP 的协议，但它是 半双工 的，对于大部分需要服务器主动推送数据到客户端的场景，都不太友好，因此我们需要使用支持全双工的 WebSocket 协议。
  • 在 HTTP/1.1 里，只要客户端不问，服务端就不答。基于这样的特点，对于登录页面这样的简单场景，可以使用 定时轮询或者长轮询 的方式实现 服务器推送(comet) 的效果。
  • 对于客户端和服务端之间需要频繁交互的复杂场景，比如网页游戏，都可以考虑使用 WebSocket 协议。
  • WebSocket 和 socket 几乎没有任何关系，只是叫法相似。
  • 正因为各个浏览器都支持 HTTP 协 议，所以 WebSocket 会先利用 HTTP 协议加上一些特殊的 header 头进行握手升级操作，升级成功后就跟 HTTP 没有任何关系了，之后就用 WebSocket 的数据格式进行收发数据。

WebSocket 完美继承了 TCP 协议的 全双工 能力，并且还贴心的提供了解决粘包的方案。

它适用于 需要服务器和客户端（浏览器）频繁交互 的大部分场景，比如网页/小程序游戏，网页聊天室，以及一些类似飞书这样的网页协同办公软件。

TCP

面向连接，可靠，基于字节流

  • 面向连接：一定是「一对一」才能连接，不能像 UDP 协议可以一个主机同时向多个主机发送消息，也就是一对多是无法做到的；
  • 可靠的：无论的网络链路中出现了怎样的链路变化，TCP 都可以保证一个报文一定能够到达接收端；
  • 字节流：用户消息通过 TCP 协议传输时，消息可能会被操作系统「分组」成多个的 TCP 报文，如果接收方的程序如果不知道「消息的边界」，是无法读出一个有效的用户消息的。并且 TCP 报文是「有序的」，当「前一个」TCP 报文没有收到的时候，即使它先收到了后面的 TCP 报文，那么也不能扔给应用层去处理，同时对「重复」的 TCP 报文会自动丢弃。 TCP 滑动窗口是一种流量控制的机制，发送方在向接收方发送数据时，会根据接收方的窗口大小逐步增加发送数据的量，从而防止网络拥塞。窗口大小是接收方告诉发送方自己还有多少接收缓存可用的指标，发送方发送数据时，只能发送窗口大小内的数据。

当接收方发送的信息过多时，即缓存数据已满，接收方的窗口大小会降低，限制发送方每次发送的数据量，从而保证接收方不会超出自己的容量。这样做可以防止接收方因为过多的数据导致缓存区溢出，影响网络性能。

所以，接收方发送的信息过多确实可能导致窗口大小减小，但这并不是一定的，可能会出现数据包滞留的情况。通常情况下，TCP 的拥塞控制机制会尽可能地将网络拥塞控制在一个相对稳定的范围内，从而保证网络的性能和稳定性。

IP

跟 IP 协议相关的技术也不少，接下来说说与 IP 协议相关的重要且常见的技术。

  • DNS 域名解析
  • ARP 与 RARP 协议，根据 IP 确定 MAC 地址，反之
  • DHCP 动态获取 IP 地址
  • NAT 网络地址转换
  • ICMP 互联网控制报文协议
  • IGMP 因特网组管理协议

NAT 动态地址转换

解决了 IPv4 地址数量不足的问题

IPv6

IPv4 地址长度共 32 位，是以每 8 位作为一组，并用点分十进制的表示方式。

IPv6 地址长度是 128 位，是以每 16 位作为一组，每组用冒号「:」隔开。 对于一对一通信的 IPv6 地址，主要划分了三类单播地址，每类地址的有效范围都不同。

  • 在同一链路单播通信，不经过路由器，可以使用 链路本地单播地址，IPv4 没有此类型
  • 在内网里单播通信，可以使用 唯一本地地址，相当于 IPv4 的私有 IP
  • 在互联网通信，可以使用 全局单播地址，相当于 IPv4 的公有 IP

Ping

ICMP 全称是  Internet Control Message Protocol，也就是 互联网控制报文协议。 封装在 IP 包里面

Docker

Docker 是一种轻量级的虚拟化技术，可以将应用程序及其依赖项打包成可移植的容器，从而实现跨平台的部署。容器可以在不同的环境中运行，而不需要重新配置或重新编译应用程序。Docker 的优点包括快速部署、可移植性强、资源利用率高等，因此广泛应用于云计算、持续集成等领域。

Kubernetes

Kubernetes（简称 K8s）是一个开源的容器编排工具，用于管理 Docker 容器集群。K8s 可以自动化地部署、扩展和管理容器化的应用程序，从而实现高可用性和弹性。K8s 提供了一种基于声明式的、自动化的资源管理模式，可以根据应用程序的需要自动调整容器的数量和位置，从而实现负载均衡和故障恢复等功能。K8s 的优点包括高可用性、可扩展性、灵活性、自动化管理等，因此被广泛应用于云原生应用程序的开发和部署。

场景题

MapReduce 堆、双堆（中位数，大根堆放小根堆的最小值） 位图法 Trie 黑白名单

设计模式

七大原则

开闭原则：对扩展开放，对修改关闭。在程序需要进行拓展的时候，不能去修改原有的代码。

依赖倒置原则：针对接口编程，依赖于抽象类或接口而不依赖于具体实现类。

里氏替换原则：任何基类可以出现的地方，子类一定可以出现。

接口隔离原则：将不同功能定义在不同接口中实现接口隔离。

单一职责原则：一个类、接口或方法只负责一个职责，降低代码复杂度以及变更引起的风险。

迪米特原则：每个模块对其他模块都要尽可能少地了解和依赖，降低代码耦合度。

合成复用原则：合成复用原则是指：尽量使用合成/聚合的方式，而不是使用继承。

设计模式的分类

创建型模式：在创建对象的同时隐藏创建逻辑，不使用 new 直接实例化对象。有工厂方法模式、抽象工厂模式、单例模式、建造者模式、原型模式。

结构型模式：通过类和接口间的继承和引用实现创建复杂结构的对象。有适配器模式、装饰器模式、代理模式、外观模式、桥接模式、组合模式、享元模式。

行为型模式：通过类之间不同通信方式实现不同行为。有策略模式、模板方法模式、观察者模式、迭代子模式、责任链模式、命令模式、备忘录模式、状态模式、访问者模式、中介者模式、解释器模式。

常见模式

工厂模式

简单工厂：通过接口让工厂类创建对象，一个工厂类，一个产品抽象类 工厂方法：多个工厂类，一个产品抽象类 抽象工厂：多个工厂类，多个产品抽象类

定义一个创建对象的接口，让其子类自己决定实例化哪一个工厂类，工厂模式使其创建过程延迟到子类进行。 具体而言，工厂模式主要包含三个角色：抽象产品、具体产品和工厂。其中，抽象产品是对产品功能的抽象描述，具体产品则是实现抽象产品接口的具体类，而工厂则是负责生产具体产品的类。

在工厂模式中，客户端并不需要知道具体产品的类名，只需要知道产品的类型即可，由工厂类负责创建相应的产品对象。这种方式可以使系统更加灵活，易于扩展和维护。

抽象工厂模式

抽象工厂：多个工厂类，多个产品抽象类

原理：将一组相关或独立的产品组成一个产品族，提供一套构建复杂对象的接口，具体产品的生成由实现类完成。 实现：定义一个抽象工厂接口，由具体工厂来实现该接口，生成一系列相关的产品。 作用：用于创建一系列相互依赖或者独立的产品，保证这些产品能够协同工作。

单例模式

static，保证在类创建的时候只生成一个实例，并且构造函数需要进行私有化。分为饥饿模式（启动时创建）和懒汉模式（延迟创建，在多线程环境需要双重检验———null && synchronize(target_class)）

主要是用于工具类，这个类只需要负责创建自己的对象，然后确保自己只会被创建一次，这个类提供了一种访问其唯一的对象的方式，可以直接访问，不需要实例化该类的对象。

建造者模式

复杂对象的构造（与工厂的区别是更加关注零件装配的顺序

原理：将一个复杂对象的构造过程拆分成多个部分，在客户端进行组装，可以灵活的构建不同的对象。 实现：将复杂对象的组成部分抽象为一个个对象，然后利用 Builder 类来将这些组成部分组装为复杂的对象。 作用：在创建对象时，可以避免使用长参数列表的方式，减少对客户端的依赖，在构建不同的对象时有较高的灵活性。

原型模式

重写 clone()，解决创建对象成本过高，以及避免重复配置对象

原理：该模式通过克隆方式实现多个相似对象的生成，从而避免了对象的重复创建和初始化。 实现：在原型类中实现 Clone() 方法，可以使用浅复制或深复制，根据需求创建新的对象。 作用：用于创建对象的成本过高时，或者需要频繁生成相似对象的场景。

适配器模式

将两个不兼容的接口兼容起来

原理：将一个已存在但是接口不兼容的类，通过适配器转换成客户端期望的接口进行使用。 实现：定义一个适配器类，将不兼容的接口进行转换，并提供与客户端一致的接口。 作用：用于兼容已存在的接口，并将其转换成符合客户端需求的接口。

桥接模式

将 m*n 个实现类转换为 m+n 个实现类

原理：将抽象和实现分离，使它们可以独立变化，从而扩展性更强，更加容易维护。 实现：建立一个抽象类，其中包含要使用的一套对象，然后让需要使用这些对象的类继承这个抽象类。 作用：将对象的实现和抽象分离开，避免某个类承受过大的责任，可以灵活的扩展实现。

过滤器模式

以某些标准对容器对象的元素进行过滤

允许开发人员使用不同的标准来过滤一组对象，通过逻辑运算以解耦的方式把它们连接起来。这种类型的设计模式属于结构型模式，它结合多个标准来获得单一标准。

组合模式

将类对象组合成树形结构（类里面的容器对象）以实现组合

原理：将对象组合成树状层次结构，使用户对单个对象和组合对象具有一致的访问性，在组合中可以含有其他组合，形成复合结构。 实现：对于树形结构中的每个节点，都进行分离封装，使单个节点对象和组合对象的操作具有一致性。 作用：统一处理单个对象和组合对象。

装饰器模式

InputStreamReader BufferedReader InputStreamReader <- InputStream 装饰者模式可以动态地给对象添加一些额外的属性或行为，即需要修改原有的功能，但又不愿直接去修改原有的代码时，设计一个 Decorator 套在原有代码外面。

外观模式

解耦，将独立的多个方法通过一个统一的接口暴露。

原理：为多个复杂的子系统提供一个统一的接口，提高系统的易用性和易扩展性。 实现：定义一个外观类，将一系列复杂操作封装在该类中，对外提供统一的接口。 作用：用于简化多个复杂子系统之间的交互，为用户提供一个简单易用的统一接口。

享元模式

在画图的时候，引用同样的对象，修改坐标值

减少创建对象的数量，以减少内存占用和提高性能。

代理模式

通过代理类，对原始对象进行访问

原理：为某个对象提供一个代理，控制对原始对象的访问。可以通过代理实现对原始对象的增强或者隐藏。 实现：代理类与原始类实现同样的接口，代理类实例化时传入一个原始对象，并在调用时对原始对象进行封装或者增强。 作用：用于对原始对象进行控制，增强或者限制其访问方式。

职责链模式

log 多级别打印

避免请求发送者与接收者耦合在一起，让多个对象都有可能接收请求，将这些对象连接成一条链，并且沿着这条链传递请求，直到有对象处理它为止。

职责链上的处理者负责处理请求，客户只需要将请求发送到职责链上即可，无须关心请求的处理细节和请求的传递，所以职责链将请求的发送者和请求的处理者解耦了。

命令模式

模拟 CMD，可以进行 Redo，Undo 原理：将一个请求封装成一个对象，由这个对象来完成请求和响应的分离，并且支持撤销操作。

实现：请求者类包含命令对象，命令对象包含执行者，通过将请求者与执行者分离，在调用执行者操作过程中进行额外的处理，支持撤销操作。

作用：用于将请求者与执行者解耦合，并且支持撤销操作。

解释器模式

解析 SQL

提供了评估语言的语法或表达式的方式，它属于行为型模式。这种模式实现了一个表达式接口，该接口解释一个特定的上下文。

迭代器模式

iterator

原理：提供一种方法来顺序访问聚合对象中的一系列数据，而无需暴露其内部的数据表示细节。

实现：使用一个 Iterator 对象来对聚合对象进行遍历和访问，对外提供 next() 方法和 hasNext() 方法，以此来访问聚合对象。

作用：用于管理聚合对象或者集合对象的遍历，不暴露其内部结构

中介者模式

降低多个对象之间通信的复杂性，ChatRoom

原理：通过抽象出一个中介者来控制多个对象的交互，将一些对象之间的复杂关系转换为中介者与对象之间的简单关系。

实现：定义中介者接口，将对象之间的交互统一成中介者与对象之间的消息传递。

作用：用于降低系统中对象之间的耦合性，对于多个对象之间的调度、通信等等问题，可以通过中介者来解决。

备忘录模式

保存一个对象的某个状态，以便在适当的时候恢复对象。

属于行为型模式。在不破坏封装性的前提下，捕获一个对象的内部状态，并在该对象之外保存这个状态。

为了符合迪米特原则，还要增加一个管理备忘录的类。

观察者模式

当一个对象被修改时，则会自动通知依赖它的对象 键盘输入

原理：定义对象间的一种一对多的依赖关系，当一个对象发生改变时，所有依赖于它的对象都会得到通知并更新。

实现：定义两个类，一个是 Subject 类，另一个是观察者类，当 Subject 发生改变时，观察者类会得到通知，从而实现了通知机制。

作用：用于建立对象和对象之间的联系，当一个对象的状态发生改变时，可以通知所有相关的对象，使得对象之间能够更加灵活的通信和执行。

状态模式

类的行为基于它的状态改变

原理：在不同的状态下，对象具备不同的行为方式，可以根据状态的改变来改变对象的行为。 实现：在状态设计方面，每个状态都有一个对应的具体实现类，并且维护一个对上下文的引用，在状态的转换时改变对上下文的引用。 作用：将对象的状态和行为分离，提高系统的灵活性和可扩展性。

策略模式

类的行为或其算法可以在运行时更改。状态模式主要是用来解决状态转移的问题，当状态发生转移了，那么 Context 对象就会改变它的行为；而策略模式主要是用来封装一组可以互相替代的算法族，并且可以根据需要动态地去替换 Context 使用的算法。

原理：将一系列的算法进行抽象化，定义每个算法的接口，并通过组合的方式让其动态的使用某一个算法。 实现：通过定义一个 Context 类，这个类持有一个算法的接口，在运行时通过 setter 方法动态的修改算法接口，来改变算法使用的方式。 作用：用于针对某个问题使用不同的算法，在运行时可以动态的切换使用的算法，提高算法的灵活性和可维护性。

模板方法模式

抽象类公开定义了执行它的方法的方式/模板。它的子类可以按需要重写方法实现，但调用将以抽象类中定义的方式进行。

数据驱动的设计模式，它属于行为型模式。请求以命令的形式包裹在对象中，并传给调用对象。调用对象寻找可以处理该命令的合适的对象，并把该命令传给相应的对象，该对象执行命令。

实现：定义一个抽象基类，包含算法骨架中的一些方法和具体实现的剩余部分，子类继承并实现这些部分来完成算法。

updatedupdated2024-06-122024-06-12