聊聊后端程序员的知识体系-第一篇

0xFF 写在前面

之前总有一些年轻人问我，我应该了解哪些知识才能像某某某那么牛B。
这句话的意思其实就是：他们特别困惑，想知道一个后端程序员的知识体系，想知道从哪开始学起。

关于这个问题，琢磨了好久，我不想简单的一句话就敷衍过去了，这个问题我要深思熟虑去回答。
因为如果 10 年前有人告诉我这个问题的答案，现在的我将少走很多的弯路，技术水平也会更上一层楼。

简单说一下全文的结构，全文一共分为四大部分。第一部分，主要从硬件、操作系统、网络、数据结构&算法等几个方面跟大家聊一下计算机科学相关的基础知识。第二部分，讲一下设计一款高性能的服务框架，应该从哪些方面着手；第三部分，讲一下平常工作中使用最频繁的知识-数据库、缓存以及一些相关的经典问题；最后第四部分，讲述的侧重点从第二部分的微观转到相对宏观的内容，跟大家聊一下分布式系统、大型架构设计等相关知识。

引用古人的一句话，来开始我们的征程！

“路漫漫其修远兮，吾将上下而求索！”

0x00 计算机科学基础知识

0x01 硬件相关

首先思考这个问题：我又不是搞硬件的，为什么我需要了解计算机硬件？在我看来，有这么几个原因：

第一，“爱美之心，人皆有之！” 计算机硬件中很多设计非常优美，这些优美的设计自然会吸引人们去追逐它。例如，计算机如何表示一个负数、浮点数等。
第二，只有充分了解了硬件，才能设计出足够高性能的程序。试想，如果你不知晓CPU缓存一致性协议，甚至不知晓L1、L2缓存，怎么可能写出高性能并发程序？
第三，计算机硬件的许多设计思想，对我们平常设计系统大有裨益。举个例子：稀疏索引跟CPU缓存与主寸的组相联映射的设计思想便十分相似。

我这边尽量罗列一些跟我们平常工作相关的硬件知识，供各位参考。

计算机如何表示一个数，包括正整数、负数、浮点数等；

负数：通过补码来表示，反码 + 1（~N + 1）

浮点数：对于双精度浮点：符号位（1位） + 阶码（11位） + 尾数（52位）
CPU的组成以及了解各个寄存器如何协作完成一次完整的函数调用；

下面这篇文章很详细的介绍了CPU的寄存器
https://blog.csdn.net/zhangdaisylove/article/details/47804165

下面这篇文章很好的介绍了函数调用
https://blog.csdn.net/it_10/article/details/52986350

如何实现协程切换？
CPU L1/L2缓存作用以及缓存一致性协议MESI；
计算机访问时间金字塔；
中断：包括常见的硬件中断、软中断；
CPU是如何访问主存（By总线），外存（DMA）的；

设备	访问延迟	每秒钟吞吐量
execute typical instruction	1ns	10^9 = 1G
寄存器	？？ns	10^9 = 1G
fetch from L1 cache memory	0.5ns	2G
branch misprediction	5ns	200M
fetch from L2 cache memory	7ns
mutex lock/unlock	25ns
fetch from main memory	100ns
Compress 1KB wth Zippy	2微秒
SSD random read	16微秒	500MB/s
send 2K bytes over 1Gbps network	20微秒
read 1MB sequentially from memory	0.25ms	ddr4 17G/s
fetch from new disk location (seek)	8ms（7200转盘片旋转(半圈时间) + 磁盘寻道（固定为8ms) + 数据传输（传输数据大小/传输速率）	机械磁盘 130M/s
read 1MB sequentially from disk	20ms
send packet US to Europe and back	150ms（距离/光速）地球半径6600km

参考：

https://blog.csdn.net/aijia7039/article/details/101261797?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.control

https://colin-scott.github.io/personal_website/research/interactive_latency.html

http://norvig.com/21-days.html#answers

0x02 操作系统相关

操作系统是计算机学科必学科目，其重要性不言自明，不再赘述。同样罗列下比较实用的操作系统相关知识点：

进程与线程的本质，进程调度的原理；

进程：一个静态程序的执行过程；线程：操作系统调度的基本单位；

进程调度：多级反馈队列调度算法，既能使高优先级的作业得到响应又能使短作业（进程）迅速完成。具体原理我们可以了解一下：

1、进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。
2、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，当且仅当在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。
3、对于同一个队列中的各个进程，按照FCFS分配时间片调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列末尾，直至完成。
4、在最后一个队列QN中的各个进程，按照时间片轮转分配时间片调度。
5、在低优先级的队列中的进程在运行时，又有新到达的作业，此时须立即把正在运行的进程放回当前队列的队尾，然后把处理机分给高优先级进程。换而言之，任何时刻，只有当第1~i-1队列全部为空时，才会去执行第i队列的进程（抢占式）。特别说明，当再度运行到当前队列的该进程时，仅分配上次还未完成的时间片，不再分配该队列对应的完整时间片。
OS如何管理物理内存、虚拟内存，OS是如何跟硬件配合完成虚拟内存到物理内存的转换的；
TLB: 虚拟地址到物理地址的查询结果的高速缓存；
https://www.cnblogs.com/east1203/p/11572500.html
https://zhuanlan.zhihu.com/p/108425561?utm_source=wechat_timeline
OS是如何运行一个可执行程序的？虚拟内存空间构成如何？

操作系统的用户态、内核态
进程同步原理与思想；
从底层看待锁的实现：锁总线（锁定总线，禁止他人访问内存）、禁止中断（对于单核有效）
应用层面有哪些同步手段：锁（mutex、rw_lock、semphore、condition variable）、无锁（原子变量、不超过字长的内存访问的不可分割性）
OS如何管理磁盘（Bitmap)、文件系统；

page cache: 加速加速磁盘的写入；在现代计算机系统中，CPU，RAM，DISK的速度不相同。CPU与RAM之间，RAM与DISK之间的速度差异常常是指数级。为了在速度和容量上折中，在CPU与RAM之间使用CPU cache以提高访存速度，在RAM与磁盘之间，操作系统使用page cache提高系统对文件的访问速度。
OS是如何支持系统调用的，系统调用与库函数有何区别？

0x03 网络相关

网络相关知识中，最重要的有两块：

第一、TCP协议

TCP协议在平常工作中非常重要，如果熟悉tcp协议，那么一个合格的后端程序员借助于tcpdump输出的结果，搭上眼一看便应该可以知道
出现的问题是Client端还是Server端的问题。

最基本的三次握手、四次挥手以及其中涉及的种种状态（不要仅限于知道这个知识点，要去考虑为什么这么设计，而不那么设计。）

主动关闭端：ESTB, FIN_WAIT1, FIN_WAIT2, TIME_WAIT, CLOSED; 被动关闭端：ESTB, CLOSE_WAIT, LAST_ACK, CLOSED
需要可以解释time_wait的存在性：
（1）确认对方收到自己发送的最后一个ACK（如果提前关闭了，对方重传的FIN会无法响应）
（2）确认前连接在网络上的分组消失（客户端随机分配的端口与前一次重复，并且seqno发生回环）
https://www.cnblogs.com/rexcheny/p/11143128.html
TCP协议设计原理，包括窗口控制（滑动窗口思想）、拥塞控制等
慢开始阶段（发送窗口指数放大）、拥塞避免阶段（发送窗口线性放大）、快重传

https://blog.csdn.net/qq_41431406/article/details/97926927
TCP协议流量控制

第二、Http协议

平常工作中，会遇到个别同学搞不定Tcp协议与Http协议，这样子是非常不应该的。关于Http协议你不需要了解太多，但是你最起码应该要知道这些：

Http协议大概长什么样（Header、Body）
5XX， 3XX等各种Code的含义
500，服务器内部错误
504，服务器执行超过
502，Bad Gateway
301，永久重定向
302, 临时重定向
304，内容未改变
Post跟GET的区别，以及有多少种POST数据的方式？
application/x-www-form-urlencoded 类似于GET，对query params进行url编码
multipart/form-data 可上传FILE
了解http2.0的设计原理，并在平常工作中借鉴使用。https://www.cnblogs.com/barrywxx/p/8570006.html

双向流、消息头压缩、单TCP的多路复用、服务端推送等特性，这些特性使得 gRPC 在移动端设备上更加省电和节省网络流量；

0x04 数据结构与算法

这一块水很深，做一个简单的罗列，希望同学们多刷刷leetcode练练手！

0x041 掌握最基本的算法思想

首先，我们需要掌握最基本的算法思想，包括但不限于：位运算、前缀与差分、二分、双指针（对撞、快满、滑动窗口）、排序（离散化、中位数）、倍增、贪心等

第一，位运算。

第一个需要掌握的技巧是n & (n - 1)，通过该操作我们可以让n的最后一个1变为0。
第二个需要掌握的技巧是lowbit(n) = n & (-n) ,lowbit操作可以让我们获取到n的低位。
第三个需要知道的是二进制表示下不进位，例如：XOR又称作不进位加法。
第四个技巧在于 n XOR 1成对变换。
最后，掌握二进制位状态压缩的常见操作

操作	运算	说明
取出n的第k位	n & (1 << k)	n & (00010000)
取出n的后k位	n & (1 << k) - 1	n & (00011111)
n的第k位取反	n xor (1 << k)	n xor 00010000
n的第k位置1	n \| (1 << k)	n \| 000010000
n的第k位置0	n & ~(1 << k)	n & 1111101111

第二，前缀与差分

这里我们了解前缀和序列和差分序列可以帮我们做什么？

借助前缀和，我们可以把在原序列上的O(N)的累加操作转换为在前缀和序列上O(1)的相减操作。
而借助差分，我们可以把在原序列O(N)的区间操作转换为在差分序列上O(1)的双端操作。

第三，二分

二分的关键点在于我们是否可以找到一个特性，这个特性在一半满足，而在另一半不满足。
整数二分边界判定容易出错，附上模版：
(1) l + r >> 1, [l, mid], [mid + 1, r]
(2) l + r + 1 >> 1 [l, mid - 1], [mid, r]

二分思想简单，而难点在于我们能否找到那种特性。用于二分的对象也不尽相同，具体包括：
（1）二分下标：在一个有序数组（该条件可以适当放宽）中查找目标元素的下标。
（2）二分答案：我们找的是一个整数，并且这个整数我们知道它可能的最小值和最大值。此时，我们可以考虑使用二分查找算法找到这个目标值
（3）借助二分将最优化问题转判定问题

第四，双指针（对撞、快慢、滑动窗口）

首先我们把双指针问题分为两大类：双序列、单序列。
先说双序列，一般情况下，我们会分别维护每一个序列的头指针，头指针按照某条件分别移动，直到完成序列的遍历。这种模式的经典案例便是合并排序。
再说单序列，单序列我们又可以细分为对撞指针、快慢指针，其中滑动窗口是一类特别重要的快慢指针。

这里讨论一个特别重要的问题，双指针是做什么用的？一般来讲，他主要用来做时间复杂度优化的（将$O(n^2)$优化到$O(n)$

那么双指针为什么可以把时间复杂度优化掉呢？我们考虑两个指针:$i, j$，如果$j$的取值伴随$i$的取值是单调变化的，那么通过双指针算法我们可以让$j$的搜索空间大幅减少，从而起到了优化时间复杂度的功效。

第五，排序与离散化

首先，我们应该牢记各种排序算法的时间复杂度以及应用场合。
其次，我们需要了解每一次排序算法背后的思想。

|算法|思想|衍生问题|
|——|——|——|
|quick sort|分治思想，借助双指针在$O(n)$时间内完成partition|线性第k大，线性求中位数|
|merge sort|分治思想，双指针（稳定的）|逆序数|
|heap sort|借助容器来实现排序，还有类似的BST中序遍历|topK问题|
|counting sort|空间换时间，非比较；通过扫描min/max来支持负数，通过累加和+倒序遍历来保持稳定||
|bucket sort|抽屉原理，稳定排序，适合元素值集合较小的情况，特别适合外部排序|排序后最大间隔问题、大整数文件取中位数问题|
|radix sort|稳定子排序算法（计数排序、桶排序来实现）对数字进行k遍排序||
|shell sort|分块思想，缩小增量排序，一种特殊的插入排序；递减序列的选择很重要|适用于基本有序序列|
|insertion sort|减治思想，扑克牌|适用于基本有序序列
|Bubble sort|稳定|

最后，了解排序的用途，借助于排序，我们可以：

离散化：对序列进行保序处理
中位数

第六，概率相关题目

概率相关问题

最后，倍增（成倍增长）

我们在进行递推时，如果状态空间很大，那么常规的线性递推无法满足时空复杂度的要求，那么我们可以通过成倍增长的方式，只递推状态空间中在2的整数次幂位置上的值作为代表。当需要其他位置上的值时，我们通过“任意整数可以表示成若干个2的次幂项的和”这一性质，使用之前求出的代表值拼成所需的值。所以使用倍增算法也要求我们递推的问题的状态空间关于2的次幂具有可划分性

0x042 最基本的数据结构

掌握最基本的数据结构，包括但不限于：栈（单调栈思想解决NextSmaller问题）、队列（单调队列解决窗口最值问题）、链表、Hash、字符串（P进制哈希、KMP）、Trie、堆、并查集等

第一、最基本的链表（单链表、双向链表、XOR链表）

与链表相关的常见技巧：递归往往可以让你的链表程序变得更加简单、快慢指针

第二、Hash

Hash如何解决冲突：拉链法、开放定址法

第三、字符串

字符串的P进制Hash、KMP算法、字符串后缀数组

第四、Trie

借助Trie我们可以在$O(k)$的时间复杂度内找到集合中的字串，其中$k$是字串长度，与集合大小无关；但是Trie的空间复杂度较高，是一种典型的空间换时间的数据结构。特别提一下，前面提到的字串不应该局限于字母，还有可能是组成整数的0/1比特位。比如寻找最大XOR值题目中，我们用Trie数来维护所有的整数，字串便是0/1。借助Trie，我们便能够在线性时间复杂度($O(32)$)内找到target elment。

第五、栈与单调栈

栈的基本特性：后进先出。
重点说一下技巧性更强的单调栈。例如经典的Next Bigger Element问题，我们从后往前遍历序列并实时维护一个低大顶小的单调栈，每次访问到一个元素时，与栈顶元素挨个比较，如果栈顶元素比当前元素小，就直接出栈（为什么呢？用大白话是说，要找后面更大的元素，如果某个元素A后面的元素比A都小的话，那么A后面的元素是永远不可能成为备选集的。）如果栈顶元素更大，那么栈顶元素就是NextBiggerElement，同时把当前元素入栈。

第六、队列与单调队列

队列的基本特性：新进新出。
这里同样也讲一下技巧性很强的单调队列。通常我们利用单调队列来解决滑动窗口求最值问题。其核心思想在于每来一个新的窗口元素，我们需要从队列中依次取元素出来，并与之比较，如果队列中的元素更小，就直接出队。（为什么呢？新进来的元素比老元素更大，并且生命周期更长，显然老元素应该被淘汰掉）最后，再把新的元素放入队列。

除此，队列最主要的用途就是辅助完成图或者树的BFS，比较经典的问题包括：拓扑排序、分层打印等。

第七、堆与优先队列

我们需要知道堆的最重要特性：能够在$O(1)$时间复杂度内取得最小值。
鉴于此，堆有几大用途：利用堆来排序、利用堆来求解TopK问题、利用堆来求解贪心问题（例如，利用堆去优化dijkstra算法）

还有一点，我们可以$O(n)$的时间复杂度内完成堆的初始化（我们只需要从$i/2$开始往0遍历，并up堆化即可）

第八、并查集

并查集是一个代码很简单、但技巧性极强的数据结构，我们需要知道并查集的最重要特性：能够在近乎$O(1)$的时间复杂度内完成元素归属集合以及元素合并的操作。
通常我们利用数组来实现并查集，并经常会通过路径压缩技巧来进行性能优化。
我们在图的连通性判定、最小生成树-kraskal等问题中可以看到常规并查集的应用。另外，我们有时候需要额外维护size、distance等额外属性去解决更多的问题。这种技巧也需要掌握。

0x043 常见搜索思想

我们需要掌握计算机解决问题的唯一办法—搜索。我们需要了解计算机除了搜索，无他。我们平时听到的递归、递推、分治、BFS、DFS等，其无一不是在搜索。
我们前面提到的各种数据结构也只是让我们能够更加有效的组织信息，从而让搜索变得更加有效率而已。

为什么解决同一个问题，某些算法却比别的算法跑的更快？究其根本，我觉得有两点：第一，更好的算法避免了很多重复计算；第二，更好的算法避免了很多不可能成为解的无效计算。

让我们对计算机解决的问题做一下分类：
判定类问题：判定这个答案是不是问题的解
最值问题：求解满足XXX条件的最大值、最小值，一般解法
排序问题：对序列元素进行调整使之满足一定次序
查找问题：找到某一个符合条件的答案

程序遍历“状态空间”的两种基本方式：递归、递推。一般情况下，我们需要采用递归对方式来暴力枚举某一问题的状态空间。按照规模从大到小，有以下几种常见的方式：
多项式（$n^k$，循环、递推）、指数($k^n$，递归、位运算)、排列($n!$、递归)、组合(${n \choose m}$、递归+剪枝)

接下来我们聊一下分治、回溯、DFS三者的区别。

递归是一种算法结构。递归会出现在子程序中，形式上表现为直接或间接的自己调用自己。

回溯的思路基本如下：当前局面下，我们有若干种选择，所以我们对每一种选择进行尝试。如果发现某种选择违反了某些限定条件，此时 return；如果尝试某种选择到了最后，发现该选择是正确解，那么就将其加入到解集中。
回溯是一种算法思想，它是用递归实现的。回溯的过程类似于穷举法，但回溯有“剪枝”功能，即自我判断过程。
选择 (Options)，限制 (Restraints)，结束条件 (Termination)

回溯法的基本思想：
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

回溯法，一般可以解决如下几种问题：

组合问题：N个数里面按一定规则找出k个数的集合
排列问题：N个数按一定规则全排列，有几种排列方式
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
棋盘问题：N皇后，解数独等等

「回溯法解决的问题都可以抽象为树形结构」，是的，我指的是所有回溯法的问题都可以抽象为树形结构！

因为回溯法解决的都是在集合中递归查找子集，「集合的大小就构成了树的宽度，递归的深度，都构成的树的深度」。

递归就要有终止条件，所以必然是一颗高度有限的树（N叉树）。

算法模版：

回溯函数模板返回值以及参数, 返回值一般为void,参数要看具体的问题, 签名如下：

1	void backtracking(参数)

回溯函数终止条件：什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。代码入下：

if (终止条件) {
  存放结果;
  return;
}

回溯搜索的遍历过程

  void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

0x044 动态规划

第四、掌握动态规划思想，具体包括：线性DP、背包问题、区间DP、树形DP、数位统计DP、状态压缩DP、倍增优化DP等

动态规划的本质：计算机解决问题其实没有任何奇技淫巧，它唯一的解决办法就是穷举，穷举所有可能性。算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。
列出动态转移方程，就是在解决“如何穷举”的问题。之所以说它难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不那么容易穷举完整。
备忘录、DP table 就是在追求“如何聪明地穷举”。用空间换时间的思路，是降低时间复杂度的不二法门

动态规划：求最值问题
动态规划三要素：最优子结构、重复子问题、状态转移方程
明确状态、明确选择、确定状态转移方程

借助备忘录或者dp table，来解决子问题重复计算问题。
因为每次状态转移仅依赖dp table的一部分，所以通过状态压缩来缩小dp table

这里有更详细的介绍动态规划

0x045 图论算法

第五、图论，能够将具体的问题转化为图的几类问题（最短路、最小生成树、二分图匹配、网络最大流等）

最短路问题的解法：

算法	解决的问题	算法原理	时间复杂度
dijkstra	单源最短路，稠密图，正权	找到最小距离，用找到的最小距离更新剩余距离	O(N^2) N为图点的数量
堆优化版dijkstra	单源最短路，稀疏图，正权	借助堆来优化dijkstra算法中的查找最小值操作	O(N^2) N为图点的数量
bellman-ford	单源最短路，负边权，限制步数的情形	迭代k次，每次找最小距离	O(N^2) N为图点的数量
SPFA	单源最短路，负边权，判定有没有负环	队列优化	O(N^2) N为图点的数量
floyd	多源汇最短路	动态规划思想，三角不等式	O(N^3) N为图点的数量

最小生成树问题的解法：

算法	解决的问题	算法原理	时间复杂度
prim算法	单源最短路，稠密图，正权	找到最小距离，用找到的最小距离更新剩余距离	O(N^2) N为图点的数量
kraskal算法	单源最短路，稀疏图，正权	并查集	O(N^2) N为图点的数量

如何判定图是不是二分图：DFS遍历，奇数环

二分图匹配：匈牙利算法

第六，了解一些经典算法题目，尤其是一题多解的那种。

序列分割问题（两部分、三部分）

考察点：快排思想
第K大问题

$O(nLgn)$ => 考察点：分治、快排 / 小顶堆

$O(n)$ => 考察点：分组中位数
中位数相关

动态维护序列中位数 => 考察点：双堆

货仓选址问题（中位数）
均分纸牌问题

考察点：贪心、前缀和
环形均分纸牌

考察点：前缀和、中位数、减去平均值的技巧
逆序对问题

考察点：归并排序、平衡树、树状数组、线段树
高精度计算

考察点：大数的存储：数组，从0到N，分别对应低位到高位；方便进位
最大子数组和（积）
环形最大子数组和

考察点：滑动窗口最值（单调队列）、两次Kadane算法（一次最大值，一次最小值）

最后，掌握一些常见有用思想与技巧、性质

要从暴力、爆搜开始思考，然后再进一步思考怎么去优化复杂度。常见的思考方向如下：

常见的枚举可以看一看枚举的范围是否有序，可以考虑用二分；

双重循环看一看是否可以用双指针；

一些要查找的O(n)复杂度的部分是否可以用map、set;

括号、回文之类可以思考一下能否用栈;

一些暴力搜索的部分看一看是否存在根本不可能到达的状态可以考虑剪枝;

暴力搜索时看看是否有可重复利用的状态用map或数组把状态存起来（记忆化搜索），然后再看看是否可以用动态规划;

一些枚举的范围很大一看就知道不可能ac可能思考一下是否可以直接推出结论或数学公式（贪心的思考方向）;

一些感觉是动态规划的题目貌似，貌似每一个状态都是有规律的可以尝试用打表这种比较赖皮的方法;

一些需要反复计算的部分如果是固定的，可以考虑先计算好然后把它存起来，下次直接拿来用（前缀和思想）;

一些题目的条件和经典题型很像的可以考虑直接套用经典题型（例如01背包模型，完全背包模型）;

一些常见的操作可以看看有没有现成的类或方法可以直接拿来用（例如java大数、排序、字符串反转、拼接等常见操作）;

一些数字的操作可以看看是否涉及到二进制，可以尝试下异或、&这些操作;

动态规划的题目看一看这一次的状态和上一步的状态是否离得很近，如果离得很近可以考虑状态压缩，降低空间复杂度（例如斐波那契，每一次的状态只和前面两步状态有关）;

正难则反：广泛应用于各种问题。答案不容易求、不容易划分，利用全集减去补集从而求出答案。
字典序最小的方案：结合性质5，倒序处理
单调性（一阶导数）：不一定是常规意义上的“函数”，也可能是自己实现的复杂函数
凹凸性（二阶导数）：凸壳优化
对称性：优化枚举顺序、减少计算量
“一定的小于”：意为在有所有状态中，在当前步骤选择了某个决策，会导致一些决策一定小于
例如平衡树找kth，如果在某个节点上向右走，那么左子树的节点一定小于
试填法、字典序

参考：

https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews?aff=K7qB

https://www.educative.io/courses/grokking-the-coding-interview?aff=K7qB

0x10 高性能服务器设计

说完第一部分，可能会有人问了，“这些基础知识有啥用呢，平常工作中又用不着！” 下来让我们借助第二部分要讲的内容，来尝试着回答下这个问题。

服务器是做什么的？服务器是用来处理客户端请求的；我们的目标当然是希望服务器程序可以尽可能高吞吐的完成客户端的请求，那么一般而言高手会从哪些方面去考虑呢？这里说一下我的一些想法。

影响 RPC 框架性能的三个核心要素如下：

I/O 模型：用什么样的通道将数据发送给对方，BIO、NIO 或者 AIO，IO 模型在很大程度上决定了框架的性能；
协议：采用什么样的通信协议，Rest+ JSON 或者基于 TCP 的私有二进制协议，协议的选择不同，性能模型也不同，相比于公有协议，内部私有二进制协议的性能通常可以被设计的更优；
线程：数据报如何读取？读取之后的编解码在哪个线程进行，编解码后的消息如何派发，通信线程模型的不同，对性能的影响也非常大。

首先、事件处理模型是怎样的？可以从以下几个维度来考虑：多进程 OR 多线程、阻塞 OR 非阻塞、同步 OR 异步、Reactor模式 OR Proactor模式；提几个难点：如何避免惊群效应、如何避免worker饿死、如何做到Lock free等。

IO模型有哪几种：阻塞IO 非阻塞IO 多路复用IO 异步IO 信号驱动IO

BIO 线程模型主要存在如下三个问题：

性能问题：一连接一线程模型导致服务端的并发接入数和系统吞吐量受到极大限制；

可靠性问题：由于 I/O 操作采用同步阻塞模式，当网络拥塞或者通信对端处理缓慢会导致 I/O 线程被挂住，阻塞时间无法预测；

可维护性问题：I/O 线程数无法有效控制、资源无法有效共享（多线程并发问题），系统可维护性差。

为了解决同步阻塞 I/O 面临的一个链路需要一个线程处理的问题，通常会对它的线程模型进行优化，后端通过一个线程池来处理多个客户端的请求接入，形成客户端个数 “M” 与线程池最大线程数 “N” 的比例关系，其中 M 可以远远大于 N，通过线程池可以灵活的调配线程资源，设置线程的最大值，防止由于海量并发接入导致线程耗尽，它的工作原理如下所示：

通常一个 I/O 线程会聚合一个 Selector，一个 Selector 可以同时注册 N 个 Channel, 这样单个 I/O 线程就可以同时并发处理多个客户端连接。另外，由于 I/O 操作是非阻塞的，因此也不会受限于网络速度和对方端点的处理时延，可靠性和效率都得到了很大提升。

典型的 NIO 线程模型（Reactor 模式）如下所示：

对于IO模型，我们还需要进行网络参数的调优：

（1）tcp_nodelay(发送端 Nagle算法 + 接收端启用DelayedAck)

（2）backlog

（3）snd buffer / recv buffer

第二、如何对资源进行管理？

服务运行过程中，会利用到很多的资源，包括但不限于：内存、连接、线程、协程；其实，答案蛮简单，就是“池子”的思想，具体到特定的资源，也就变成了我们经常听到的“内存池”、“连接池”、“对象池”等。

取决于不同资源的访问特点，我们需要用不同的数据结构去管理我们的资源。例如，有一种经典的“内存池”管理算法叫做Buddy分配算法，它的主要思想就是倍增，数据结构的话主要是利用了双向链表；

再举一个例子，Nginx借助红黑树来高效管理超时时间。

第三、如何管理超时事件？

服务器程序有很多工作要借助于定时器来完成，例如连接多少时间内不活跃就断开连接、最多花多少时间去处理请求超时则终止处理等等。

既然如此，如何去设计一款高性能的定时器算法就至关重要了。这里提几个主要思路：有序双向链表、优先队列、红黑树、时间轮。

第四、如何进行并发控制？

当然最好的情况是没有并发，借助于TLS，每一个线程仅访问自己的资源；如果真的无法避免，我们需要尽量减少锁的粒度；更进一步，在更高的并发下，是不是需要追求Lock free等等。

前面四点讲的是对极致性能的追求，讲的是我的程序如何“活的更好”。

最后还有一点特别重要，这一点要考虑的问题在于如何让我的程序在极端恶劣的情况下“能够活下去”。

这里极端恶劣的情况一般分为两种：一种是上游流量徒增、另外一种是下游耗时陡增。如果程序无法很好的应对这种情况，很容易发生雪崩，导致程序死掉。这也就是大家经常听到的过载保护概念，

具体做法的话，最起码有限流和熔断吧。这些概念后面谈分布式系统时还会提及，所以在此不再赘述。

除了限流和熔断，我们有时候需要在宏观的业务层面，做主动的降级处理，牺牲一定程度的用户体验去让系统更好的活着。

0x20 数据库与缓存

一开始的时候已提到，数据库与缓存这块的知识，在平常工作中使用非常频繁，所以希望每一个有理想的程序员都应该尝试的了解更深一点，而不要仅浮于表面。

0x21 MySQL基础知识

关于MySQL数据库的基础知识，我认为有以下几点特别重要：

第一、了解数据库索引相关知识，包括但不限于：

Mysql 数据库有哪些索引以及他们各自的特点？InnoDB为什么选择用B+树作为索引，而不用B树？

索引	特点	使用场景
hash索引	散列表实现，等值查询效率高，不能排序,不能进行范围查询	不需要范围查询，仅需等值查询时，可以考虑使用
BTree索引	B+树实现，支持范围查询	默认
RTree索引	仅支持地理位置类型，RTree空间树实现，相比Btree有更好的范围查询性能	有按照地理位置检索需要的场景
FullText索引	分词加倒排索引实现	有类似like的全文检索类型的查询

索引匹配原则：左前缀匹配原则
聚簇索引、非聚簇索引是怎么回事？

索引	特点	使用场景
聚簇索引	数据按照索引顺序存储，叶子节点存储真实的数据	InnoDB索引
非聚簇索引	叶子节点存储指向真正数据行的指针	MyISAM

数据库回表是怎么回事？如何避免？
在查询辅助索引时，如果要查询的字段已经全部在索引中了，那么就不需要额外再查询主索引了；反之，如果要查询的字段当前索引无法覆盖，那么Mysql需要额外查询主索引去获取要查询的字段，访问索引的次数多了一次，我们称刚才的过程为回表。我们通过增加全覆盖索引可以避免回表。
出现慢查询时会用explain来定位解决
索引为什么要用B+树来实现？
首先，相比红黑树、AVL等二叉平衡树，B+树更加矮胖，这样子索引查找便能够更好的访问磁盘IO，从而有更好的查询性能；另外相比B树，B+树在叶子节点之间维护了一根链表，借助该链表，范围查找性能更加稳定。
InnoDB索引与MyISAM索引的区别

索引	特点	使用场景
InnoDB索引	InnoDB的主索引的叶子节点就是数据本身，而辅助索引的叶子节点是主键ID	InnoDB索引
MyISAM索引	InnoDB的主索引与辅助索引没有区别，叶子节点存储都是指向真实数据行的指针	MyISAM

两种存储引擎区别与各自使用场景

存储引擎	特点	使用场景
MyISAM	不支持外键，表锁，插入数据时锁定整个表，查表的总行数不需要扫表，索引与数据分开	不需要支持事务，绝大多数请求为读操作，系统崩溃后数据丢失可接受
InnoDB	支持外键，行级锁，事务，查表的总行数时需要扫表，必须有唯一索引，索引与数据在一个文件中	需要支持事务，读写相当，不可接受数据丢失

第二、了解数据库的那几把锁是怎么回事

悲观锁 VS 乐观锁（其实是两种思想）
首先悲观锁、乐观锁并不是两种锁，而是两种思想，两种用于实现并发控制的思想。其中，悲观锁指的是对数据被外界修改持悲观态度，认为数据大概率会被他人修改，所以在我准备修改数据时，我会对该数据加锁以避免其他人对该数据进行并发访问。而乐观锁指的是对外部修改数据持乐观态度，认为数据不会修改，所以我会直接对数据进行修改，在修改的以后再进行冲突的检查。如果修改失败了，我再决定如何去做。悲观锁适合写多读少的场景，而乐观锁适合读多写少的场景。悲观锁一般通过数据库锁来实现，而乐观锁一般是通过CAS来实现。
意向锁是什么？为什么需要意向锁？
意向锁是实现多粒度锁的一种方式，是表锁，分为意向排他锁、意向共享锁，意向锁之间是兼容的；意向锁与表级别的共享锁、拍他锁是可能互斥的；意向锁与行级的互斥锁、共享锁是兼容的；实现意向锁的目的有两个：第一，让多粒度锁共存；第二，加快是否可以加锁的判定效率。

	意向共享锁	意向互斥锁
意向共享锁	兼容	兼容
意向互斥锁	兼容	兼容

	意向共享锁	意向互斥锁
表级共享锁	兼容	互斥
表级互斥锁	互斥	互斥

	意向共享锁	意向互斥锁
行级共享锁	兼容	兼容
行级互斥锁	兼容	兼容

Record lock、gap lock、next-key lock
record lock, 行锁，锁直接加在索引记录上面，锁住的是key。
gap lock, 间隙锁，用来解决幻读问题
next-key lock， gap lock + reocrd lock
关于next-key lock的两个原则、两个优化、一个bug:
原则1: 加锁的基本单位是next-key lock, 前开后闭区间
原则2: 查找过程中遇到的对象才会加锁
优化1: 索引上的等值查询，给唯一索引加锁的时候，next-key lock退化为行锁
优化2: 索引上的等值查询，向右遍历时且最后一个值不满足等值条件时，next-key lock退化为gap lock
bug: 唯一索引的范围查找会访问到不满足条件的第一个值为止。

https://blog.csdn.net/zwx900102/article/details/106544634

第三、了解事务特性、各种隔离级别以及相应的问题

事务的特性：

A 原子性，要么执行要么不执行
C 一致性，事务前后，数据总额一致
I 隔离型，所有操作全部执行完以前其它会话不能看到过程
D 持久性，一旦事务提交，对数据的改变就是永久的

可能出现的问题：

脏读，事务B读到事务A还没有提交的数据
不可重复读，一行被SELECT两次，返回的结果不一样
幻读，两次读取返回的集合不一样

四种隔离级别：

读未提交，在该隔离级别，会出现脏读、不可重复读、幻读等问题。
读已提交，该隔离级别解决了脏读的问题，依旧会出现不可重复读、幻读问题。
可重复读，该隔离解决进一步解决了不可重复读的问题，会出现幻读问题。（但是对于InnoDB存储引擎，通过间隙锁解决了该问题，不会出现幻度现象）
串行，该隔离级别把所有操作都串行化了，没有并发访问，解决了以上所有问题。

虽说希望你了解，但是友情提示一波：线上高并发应用，尽量不要用事务！

第四、了解InnoDB存储引擎的几个概念

Redo log: 是什么？通过它解决了什么问题？redo log是InnoDB存储引擎为了解决事务持久性而引入的WAL技术。借助redo log，InnoDB存储引擎将事务的commit提交简化为一次内存操作与一次磁盘写入操作。
如果磁盘页中的数据发生了丢失，也就是在崩溃恢复过程中，存储引擎会通过重做redo log中的操作来进行数据恢复。

binlog: 又是什么？他是干什么用的？了解主从同步原理。binlog是Mysql server层为了解决主从数据同步而引入的一套日志系统。binlog中记录的是一个数据行发生了什么操作。

LBCC，基于锁的并发控制，英文全称Lock Based Concurrency Control。这种方案比较简单粗暴，就是一个事务去读取一条数据的时候，就上锁，不允许其他事务来操作(当然这个锁的实现也比较重要，如果我们只锁定当前一条数据依然无法解决幻读问题)。

MVCC: 什么是MVCC、它的作用、他的大致实现；MVCC是InnoDB存储引擎为了实现事务的隔离级别而引入的一种乐观锁机制。

快照读、锁定读：了解这两种读取方式的发生时机以及如何实现的？
一致性读视图包括：视图数组（活跃的事务） + 高水位（已经创建过的事务ID + 1）
如果是可重复读，那么事务开启时创建一次访问视图，
如果是读已提交，那么事务每一个语句执行前都会重新计算出新的视图。

https://www.cnblogs.com/leeeeemz/p/12586815.html

Undo log: 是什么？通过它解决了什么问题？数据的多个版本，临时写在undo log中，并通过链表管理起来。

InnoDB的几个关键特性：insert buffer、double write、自适应hash索引、异步写等

Redo Log与binlog的两阶段提交
（1）prepare阶段，先写入rede log（状态为准备中）
（3）写入binlog（状态为已提交）—- TX_ID
（2)commit阶段，写入redo log（状态为已提交）

0x22 Redis基础知识

首先，对Redis本身足够了解：

如何评价redis的高性能？为何要把Redis设计成单线程？

redis全内存，单线程，无锁。
redis Rehash 渐进式hash,双缓冲 + 分而治之思想
Redis提供了哪些数据结构；每一种数据结构的使用场景、大致实现（编码方式、内存占用、时间复杂度）

十种编码方式：
RAW, INT, EMBSTR,
ZIPLIST(压缩列表，连续内存，内存利用率高，增删改查效率低下；当hash、zset、list元素少且内容不大时使用该编码),
QUICK_LIST（list元素较多时使用）
INTSET(整数集合，当set元素较少时，使用该编码,从小到大的顺序存储),
HASH（hash元素较多时使用）渐进式扩容缩容策略
SKIPLIST（跳表，zset元素多时使用）

数据结构	紧凑实现	大致实现
string	INT(仅限long类型的string), EMBSTR(字符串比较短)	RAW（普通字符串）
hash	ZIPLIST（元素较少，成员较小）	HASH
zset	ZIPLIST（元素较少，成员较小）	SKIPLIST
set	INTSET（集合元素不多）	HASH
list	ZIPLIST（元素较少，成员较小）	QUICK_LIST

数据结构持久化问题，两种策略：
（1）保留原有的存储格式，例如散列表
（2）仅保留数据，而清理存储格式，例如redis

redis是如何实现可靠存储的：真的可靠吗？ AOF、RDB有啥区别？分别适用于什么场景？

借助AOF、RDB可以一定程度上减少数据的损失，但是都无法做到数据的100%。

RDB，定期fork一个子进程，通过copy on write技术，来进行内存的dump，成本相对AOF较高，所以不可能很短时间内就dump一次，所以如果内存中的数据还没有来得及dump到RDB，那么会丢失比较多的数据，好处是借助RDB恢复数据比较快。

AOF，定期（通常是s级别）append 写操作命令到文件中，只是简单的写一次磁盘，所以性能较好，如果新的命令append到aof之间发生宕机，丢失的数据也比较少。缺点是每次基于AOF恢复数据会比较慢。
redis tw代理模式与cluster集群模式分别是如何工作的？哪一种模式使用了一致性Hash?

客户端通过tw代理模式访问redis集群，数据分片使用了一致性hash，以尽可能减少某台redis机器不可用造成的影响；
官方的cluster集群方案是由客户端sdk来维护slot分布，数据分片分片是通过CRC32(key)%16834来实现。无中心化，node之间通过gossip协议来进行通信，选主等。
使用TW来解决
Redis哨兵模式：只能解决高可用的问题，但是无法解决数据太大的问题；
如何通过Redis实现一个“可靠”的分布式锁？

分布式锁的特性：排他性、无死锁、高可用。
先说加锁，setnx命令，支持cas操作，并且支持设置超时时间。通过设置超时时间这个功能点，可以避免加锁后进程挂掉造成的锁没法释放的问题。但是这种加锁方案还有一个缺点，那就是超时时间很难设置的很合理，设置过短可能会引起加锁时间内不足以完成业务逻辑；设置过长又导致宕机恢复时间过长。这种情况下，我们可以额外启动一个WATCH-dog线程来监视这些锁，如果锁快要到期了，就调用expire命令对锁进行续期；业务完成时禁用watch-dog即可。
再说解锁，理想情况下，解锁时只要通过del命令来把锁定的key删除即可。但是实际情况可能会更复杂一些。第一个问题，如果删除的key不是加的锁怎么办？容易想到，加锁时，设置key的value为一个unique id。解锁删除时，先get一下key，看看key对应的value是不是跟预期的id相符，如果相符，del；否则，noop，说明我正准备删除别人加的锁。但是刚才的方案，还有一个缺陷那就是get跟del两个操作不是一个原子的，中途可能会被打断。如果真的被打断，还是会出现误解锁的过程。此时我们可以借助lua脚本将刚才的两个步骤原子化。至此，解锁操作才算基本完成。

最后再提一下，除了redis可以实现分布式锁，还可以通过mysql数据库（version乐观锁，for update悲观锁），zookeeper等来实现分布式锁。

再次，Redis与其他缓存的区别？做设计时如何选择？

0x23 数据库的可扩展、高可用、高性能

首先，考虑高性能。

突破单数据库表的性能上限，破解之道在于：拆分；而拆分带来的问题在于：扩展、迁移、负载均衡寻址不够方便；如何拆分大致有如下两种方式：

分库分表

垂直拆分、水平拆分

{UID%100}

策略1: range: 主键id / 单库单表限制（例如2000w)

优点：简单，容易扩展

缺点：各库压力不均（新号段更活跃）

策略2: Hash: 主键id % N （分库分表数）

优点：简单，数据均衡，负载均匀
缺点：迁移麻烦（2库扩3库数据要迁移）

策略3: Router-config-server ：将路由规则通过配置server统一管理，每次访问db前额外请求一次

优点：灵活性强，业务与路由算法解耦
缺点：每次访问数据库前多一次查询

分库分表后，业务ID不唯一了，如何解决？ID生成器

replication

主从同步，在使用主从同步策略来提升性能时，需要提前考虑主从同步延迟对系统一致性可能带来的影响。

（1）主从延迟/数据丢失

如何缓解数据延迟：通过消息队列冗余、使用缓存（适合比较简单的写操作：新增，而不适合复杂的写入，时序）、访问主库

（2）业务如何访问主库或者从库（感知了细节）

第二，考虑高可用。

高可用的唯一思路：冗余，并且尽可能无状态 （数据、服务、站点、机房）；冗余带来的问题： 一致性问题

数据库读高可用带来的副作用：主从延迟带来的不一致

数据库高可用保证：多写

多写带来的副作用：自增ID数据冲突，如何解决：

不同初始值，自增步长设置为2
ID生成器生成主键id

双主，但只有一个主提供服务（读+写），另一个主是“shadow-master”，只用来保证高可用，平时不提供服务。

master挂了，shadow-master顶上（vip漂移，对业务层透明，不需要人工介入）

最后，可扩展性。

如果数据量变大，扩展性比较好的方案有：

基于偶数倍扩容
基于时间来扩容
基于数据量来扩容

如果需要扩展新的列，可以考虑：

通过扩展行的方式来扩展属性
新增一个垂直表，使用时JOIN多张垂直表
在线表结构表更 “新表+触发器+迁移数据+rename”方案（pt-online-schema-change）

数据库的迁移

0x24 数据库、缓存的其他常见问题

先说最重要的数据库、缓存一致性问题，关于该问题，有以下几点需要考虑：

当DB数据发生变更时，是删除缓存还是修改缓存？

答案是删除缓存。相比修改缓存，删除缓存是幂等性操作。删除缓存可以避免出现双写并发问题。
先写DB还是先写缓存？

答案是先操作DB。结合case1, 在读多写少的高并发场景下，如果先删缓存再操作DB，有一个很明显的逻辑错误，使得有极高的概率出现读写并发问题。虽然先db后缓存的方式也无法完全避免这类问题，但是出现的概率极低。
高并发下，关于缓存的一致性会出现什么问题？

case1, case2中提到了在高并发的情况下，会出现某种并发逻辑错误，导致数据不一致。
是否听说过订阅数据库binlog变更去清理缓存的方法？这个方法的使用场景是啥？

通过binlog变更的方式去清理缓存，有两个好处：第一，无业务侵入型；第二，支持无限重试。

CacheAside模式，一定是最佳的吗？不一定，具体场景具体分析：

（1）新用户注册场景，同时数据库主从延迟1s

解决方案：新建数据库 + 新建缓存（避免读取到延迟的数据结果）

（2）写入特别频繁的场景，而我们对命中率有一定的要求

解决方案：

updateDB + updateCache(With Lock)
updateDB + updateCache(with TTL)

Write/Read Through模式

两种应对write miss的办法：

（1）write-allocate 写cache，再由cache更新db
（2）no write allocate 直接更新db

write back模式

变种：在允许数据丢失的情况下，写入时只写缓存，而异步写入存储

再说缓存穿透问题。

首先明确什么是缓存穿透问题？考虑在很高的读并发下，如果某一个redis key突然过期，会发生什么？如果真的发生这种情况，并且我们没有任何预防措施，按照cache aside模式，程序会read from db，然后set cache。但是由于并发很高，所有的线程同时去请求db，造成db过载不可用。我们称这种现象就缓存穿透。通过分布式锁来控制仅一个线程去read db，而其他线程等待，可以一定程度上避免缓存穿透问题。

还有一种情况，如果请求的某一个key在db中也不存在，我们需要设置一个拥有较短TTL的空缓存来避免每次请求都穿透到db。

回种空值—-缺点在于：会占用很大的内存来存储好多无用请求，需要评估内存是否OK

布隆过滤器—-在写入DB时，额外写一份数据到布隆过滤器，查询时优先访问过滤器

缓存并发穿透（狗桩效应）：极热点缓存失效，大量请求穿透到DB，造成DB瞬时压力过大

最后谈一下缓存雪崩。

同样先搞清楚什么是缓存雪崩。由于某些系统设计不合理，缓存会设置为相同的过期时间或者很接近。这样子在某个时间点，缓存便会近乎同时失效，造成业务请求全部回源db,造成db过载，我们称这种情况为缓存雪崩。一般情况下，我们需要有意的设置key的过期时间，让他们随机过期，从而解决缓存同时过期导致的缓存雪崩问题。

0x30 分布式系统

什么是分布式系统？

Distributed programming is the art of solving the same problem that you can solve on a single computer using multiple computers - usually, because the problem no longer fits on a single computer.

分布式系统牵扯甚广，主要分两部分来跟大家聊：
首先，你应该了解最基本的分布式理论，了解为什么不可能设计出一个完美的分布式系统？
第二，你应该去了解尽可能多的分布式系统

0x31 分布式理论

首先澄清一点，对于这些理论知识不求全部掌握，只是了解个大概即可。

CAP理论 / BASE理论
CAP：一致性，可用性，分区容错性三者不可兼得，只得取其二。
BASE: 基本可用、软状态、最终一致性
一致性模型：强一致性、弱一致性、最终一致性
强一致性：对于分布式系统，一般通过paxos、raft等一致性协议来保证
Quorum的NWR模型、时钟向量（clock-vector）
NWR模型中，N代表数据的副本数量，W表示更新操作至少W份写入成功，R表示读操作至少R份读取成功。当W+R>N时，整个系统对于客户端而言是强一致的。NWR模型的写入策略会让某些节点上的数据不是最新的，但是却进行了最新的写入操作。这个问题要如何解决呢？我们可以引入数据版本的概念，有点类似乐观锁的思想。有了数据版本，自然也就会出现版本冲突的问题。那么又如何解决版本冲突的问题呢？我们可以借助时钟向量把冲突的解决问题交给客户端。系统只是负责把读到的每一个node上的数据以及数据版本返回给客户端，剩下的工作由client自行搞定。
lease机制
lease是什么？从更深层次上讲，lease是一种带超时时间的分布式锁。如果没有lease,那么分布式环境中的锁可能会因为锁拥有者的失败而导致死锁。而有了lease, 死锁会被控制在一定超时间内。
一致性Hash、虚拟一致性hash
一致性hash为了解决什么问题：为了解决常规hash算法中节点数变更会导致数据访问全部失效的问题，解决一致性hash使得节点变更后仅会影响小范围的数据反问。
算法原理：计算key的hash值，计算每一个节点的hash值，放置在一个ring上，每次进行顺时针查找
虚拟一致性hash: 节点负载不均衡的问题
2PC/3PC：分布式事务
2PC，事务分为两个阶段。第一阶段，prepare；第二阶段，commit阶段。
这里可以结合mysql redo log/binlog的二阶段写入来举例。
prepare阶段：redo写入prepare
commit阶段：binlog写入，redo写入commit
一致性协议（Paxos、Raft)
RAFT是一个分布式协议，用于完成三件事：leader选举、成员变更通知、日志复制。
paxos协议：协议中规定了三种角色：提议者，接受者，学习者；
Paxos/Raft等一致性协议与2PC的关系？
2PC用于保证多个数据分片上事务的原子性，Paxos协议用于保证同一个数据分片在多个副本的一致性；二者是互补关系，而不是替代关系。
去中心化- Gossip协议
redis cluster集群通过gossip协议来完成去中心化的消息传递。

0x25 其他常见系统架构组件

CDN

静态资源的加速，就近访问

CDN DNS + 本地缓存

就近访问

消息队列

消息队列：削峰填谷、异步化、解除耦合

放入队列中，尽快让用户看到结果（用在秒杀中）

异步处理，来简化请求中的业务逻辑

如何确保消息仅仅被消费一次

生产时：失败重试
消息队列本身：集群部署，多副本（以防止机器断电造成的消息丢失）

Leader, Follwer, ISR (in-sync replicas)

一条都不能丢（建议：ack=all)
允许一定丢失（ack=leader, 异步复制给follower)

消费时（接收消息、处理消息、更新进度）

一定要确保正确的处理消息后，才可以更新进度；如此可以保证不丢，但是会造成重复消息。

生产幂等性：kafka维护一个生产者ID+消息ID的映射

消费幂等性：

消费之前，根据消息ID是否处理过，如果处理过了，则直接忽略。
如果没消费过，则进行消费处理，消费完之后，（注意此处有一个GAP）将消费这个事实，存储到DB中，然后提交进度。

但是如果GAP发生了呢？还是会重复。此处需要进行分布式事务处理。

显然比较复杂，更为简单的是，在业务层进行处理，例如借助乐观锁。
例如，数据处理是修改数据库，那么我可以在消息内容中加一个版本号；在更新时，进行版本号的添加。

监控队列长度

业务应用层：增加消费能力
（1）增加消费者的数量-受限于Kafka分区
（2）提升消费者的消费能力—多线程并行消费—乱序问题

组件本身：
（1）选择高性能的数据存储方式（磁盘+pageCache)
（2）配合zero拷贝技术

0x32 常见分布式系统

大家思考一下，如果你的公司打算用分布式的方式来构建一个大规模系统，那么这个时候会涉及哪些技术问题？

分布式（单机、数据并行、任务并行）
分布式系统指标（性能、资源、可用性与可扩展性）
分布式服务框架
这里先简单罗列下一款完整的分布式框架应该有哪些功能，具体实现思路放到第三部分。一般而言，常见分布式框架要支持以下功能：统一接入、服务注册与发现、配置中心、消息队列、负载均衡、限流、负载均衡等。
分布式锁
基于redis实现的分布式锁前面已经提过，除此以外我们还可以借助mysql的唯一主键冲突、zk的临时节点来实现，总之实现一款完美的分布式锁并不容易。
分布式缓存
通过tw访问的redis集群、redis cluster等，最主要的技术点还是如何做shard
分布式数据库
现在比较流行的是tidb,我们需要了解的是这些系统的核心技术点。
先说存储TiKV。tidb使用rocksdb来存储kv数据，使用raft协议来做数据复制，借助region来进行数据的分散管理。
关于数据分散，一般有两种方案。第一种是按照key进行hash, redis cluster就是这么做的。第二种就是按照key range, 将连续的key分在一组中。
使用MVCC来进行数据的并发访问控制，也就是说把key-value变为key-version-value。
最后是事务，总体是通过乐观锁来保证事务，具体不表。
再说计算。关于计算有两块，第一主要涉及关系型模型到KV模型的转换，第二主要主要设计SQL语句的分布式执行，以及计算下推到存储层。
分布式消息队列
消息队列的实现思路大同小异，这里以kafka为例，从高性能、高可用两个角度来看：
先说高性能：借助sendfile直接实现从磁盘到网卡的zero-copy快速传输、磁盘的顺序写入、每一个partition分为多个segment，并为segment建立稀疏索引、批量发送
再说高可用：ISR(in-sync replications) leader维护的一个follower列表，在这个列表中的集合同步进度拉后不会太多。
分布式文件系统
以HDFS为例，通常分为namenode与datanode, 将一个大文件切分为block来存储，而一个文件由哪些block来组成以及这些block存放在哪台dtanode中是由namenode来维护的。

多副本：写入多份；
一致性：客户端比对checksum

https://blog.csdn.net/scl323/article/details/106507192
分布式KV存储
一般而言，RocksDB + Raft一致性协议 + 分区（Range, Hash) + PlaceDriver Node(全局管理节点)

https://blog.csdn.net/weixin_34080951/article/details/87948196

https://github.com/youzan/ZanRedisDB

https://blog.csdn.net/u010454030/article/details/90414063

redis、mc kv缓存

hbase, cassandra 列式存储，适用于离线统计

mongodb 文档数据库 schema free

noSQL的写入性能：
Log-Structured Merge Tree 基于LSM树的存储：hbase、cassandra、levelDB

加速：memtable 有序的容器—底层是skiplist

持久化：write ahead log

但是内存有限，所以需要定期将memtable dump到磁盘上 sstable(sorted string table)
当sstable太多的时候，将sstable合并（因为有序，所以合并很快）

noSQL:
性能更好：顺序写=》随机写
功能可能更强大：ES倒排索引
扩展性好：天然支持副本与shard

一致性hash
（1）缓存节点在圆环上分布不均匀（虚拟节点）
（2）脏数据（节点不可用之后，又再次恢复，会造成数据是历史数据）
可以考虑设置TTL，确保缓存被动过期
分布式计算框架（MapReduce思想）
MapReduce框架，主要是利用分而治之的思想，将要处理的数据抽象为键值对，将数据的处理过程抽象为Map映射、Reduce简化两个操作。不可分拆的计算任务或相互间有依赖关系的数据无法进行并行计算！
分布式消息系统

https://zhuanlan.zhihu.com/p/65892918

TimeLine模型：消息存储库（用于新设备的数据漫游）、消息同步库（读扩散、写扩散）、准实时构建的消息索引库（文本检索、消息类型、消息接受者等）
推送Push系统
分布式搜索系统

倒排索引
分布式配置中心、分布式日志中心、分布式监控告警中心

0x33 分布式服务框架

0x331 服务注册与发现

集成：在服务提供端或者调用端，如何集成注册中心？应用内 OR 应用外
测活：服务注册之后，如何对服务进行测活以保证服务的可用性
负载均衡：当存在多个服务提供者时，如何均衡各个提供者的负载？
运行时依赖：引入注册中心之后，对应用的运行时环境有何影响？
可用性：如何保证注册中心本身的可用性，特别是消除单点故障？

状态获取：（1）主动探测（2）心跳上报

一些可能问题：
（1）保护机制：如果短时间内摘除的节点数量超过集群的40%，则停止摘除节点
（2）通知风暴问题（准备更多的注册中心节点；精简通知内容）

目前比较流行的解决方案包括：

对比维度	euraka	consul	ZK
实现思路	去中心化，通过复制来同步数据，但不保证一致性。只要有一个节点可用，系统整体就可用。	内置了服务注册与发现框架、分布一致性协议实现、健康检查、Key/Value 存储、多数据中心方案	使用ZK节点临时节点来维护服务器列表,ZK支持watch节点变更通知机制
测活	客户端心跳	TCP/HTTP/gRPC/Cmd	自研-客户端心跳
负载均衡	Ribbon	Fabio	自研-负载均衡
雪崩保护	有，灾难态进入自我保护模式	无	自研
自动注销实例	支持	支持	进程不可用，临时节点自动销毁
访问协议	HTTP	HTTP/DNS	自研
监听支持	支持	支持	WATCH NODE变更
多数据中心	支持	支持	不支持
跨注册中心同步	支持	支持	不支持
框架集成	SpingCloud继承	Spring、k8s集成	无
优点	去中心化，高可用	功能相对完善	简单容易实现，适用于初创期
不足	一致性差	可用性无保证	服务可用性无保障 ZK跨机房集群支持不佳
CAP	AP	CP	CP
一致性协议	仅复制，非强一致	raft	zab，一种类paxos协议

0x332 过载保护：降级、熔断与限流

降级：放弃非核心功能或者服务，保证整体可用的一种方案
熔断、限流、开关等都是降级的不同类型

常见降级策略：
（1）读取数据：降级时，不再读取数据库中的数据，而只用缓存数据或者固定数据
（2）轮询：降级时，把轮询的间隔从10s调大10min中
（3）写入数据：同步写入改为异步写入，放弃数据强一致

先说限流，限流是过载保护的手段之一，目的在于保护系统不被超过服务吞吐能力的流量（或突发）打死。常见的限流手段有固定窗口、滑动窗口、令牌桶、漏桶、BBR、brpc自适应限流等。下面挨个介绍每一种限流算法的原理以及优缺点。

第一，固定窗口
原理：维护一个窗口的两个信息：窗口开始时间、经过窗口的请求数。如果窗口内超出限制数则拒绝。如果已经进入新的窗口，则reset计数。
不足：存在临界点（窗口reset前后的瞬时）的qps会飙高，从而打死系统。

第二，滑动窗口
原理：将总的时间窗口划分为N个小格，并单独维护每一个小格的计数。通过这种方式，可以把过去一段时间内的计数信息也用上，从而让限流的统计更精确一些。
不足：窗口不可能无限划分

第三，漏桶
原理：漏桶具有固定容量，出水速率是固定常量（流出请求）如果桶是空的，则不需流出水滴。可以以任意速率流入水滴到漏桶（流入请求）如果流入水滴超出了桶的容量，则流入的水滴溢出（新请求被拒绝）
不足：无法应对突发流量

第四，令牌桶
原理：假如用户配置的平均发送速率为r，则每隔1/r秒一个令牌被加入到桶中。假设桶最多可以存发b个令牌。如果令牌到达时令牌桶已经满了，那么这个令牌会被丢弃。当一个n个字节的数据包到达时，就从令牌桶中删除n个令牌，并且数据包被发送到网络。如果令牌桶中少于n个令牌，那么不会删除令牌，并且认为这个数据包在流量限制之外。算法允许最长b个字节的突发，但从长期运行结果看，数据包的速率被限制成常量r。

上面的几种算法，一定程度上确实能够保护系统不被拖垮, 但不管漏斗桶还是令牌桶, 其防护思路都是设定一个指标, 当超过该指标后就阻止或减少流量的继续进入，当系统负载降低到某一水平后则恢复流量的进入。但其通常都是被动的，其实际效果取决于限流阈值设置是否合理，但往往设置合理不是一件容易的事情。具体有如下几个弊端：

集群增加机器或者减少机器限流阈值是否要重新设置?
设置限流阈值的依据是什么?
人力运维成本是否过高?
当调用方反馈429时, 这个时候重新设置限流, 其实流量高峰已经过了重新评估限流是否有意义？

针对以上

第五，BBR限流

http://www.mianshigee.com/tutorial/incubator-brpc/1778a50865eb3518.md

cpu > 800 && inflight > rt * max_qps 则启用限流

littile’s raw定律：并发 = rt * qps

再说熔断，

hystrix中的熔断器模式：半开、全开、关闭（基于错误数到基于超时率）

google sre

正常时，accepts = requests
当 requests >= K * accepts 开始熔断，丢弃部分请求，按照概率，具体的概率为：

max(0, (request - K * accepts) / (request + 1)

brpc的熔断
可选的熔断由CircuitBreaker实现，在开启了熔断之后，CircuitBreaker会记录每一个请求的处理结果，并维护一个累计出错时长，记为acc_error_cost，当acc_error_cost > max_error_cost时，熔断该节点。

0x333 负载均衡

如何探活？心跳机制

大的分类：
（1）代理类负载均衡
4层LVS + 7层Nginx相结合
LVS：性能好，但是遗憾的是工作在TCP层，并且不能感知下游存货状态
Nginx: 性能差一些，但是能够代理http请求，能够感知下游存活。

（2）客户端类负载均衡

静态策略：RR、WeightedRR、HashByKey、一致性hash

Weighted Round Robin，权重需要人为配置
无法快速摘除有问题的节点、无法均衡后端负载、无法降低整体延迟

一致性哈希，与简单hash的不同之处在于增加或删除机器时不会使分桶结果剧烈变化，特别适合cache类服务。

动态策略（从调用房的角度出发，选择负载最小、最空闲的下游来调用）

best of two random choice

repsonse中附带cpu使用率，信息滞后造成了严重的羊群效应

计算权重分数，每次请求来时我们都会更新延迟，并且把之前获得的时间延迟进行权重的衰减，新获得的时间提高权重，这样就实现了滚动更新

时间衰减系数的滑动平均值：伴随时间，老的均值，权重越来越小，新的response time，越来越高

locality-aware，优先选择延时低的下游，直到其延时高于其他机器，无需其他设置

需要有一个最小权重，否则某一个节点就没有流量了，也就无法探测她的接口耗时了

weight = qps / 耗时;
weight经常变化，需要用double buffer data + weight

传统的经验告诉我们，不能把所有鸡蛋放一个篮子里，而按延时优化不可避免地会把很多流量送到同一个节点，如果这个节点出问题了，我们如何尽快知道并绕开它。
对吞吐和延时的统计都需要统计窗口，窗口越大数据越可信，噪声越少，但反应也慢了，一个异常的请求可能对统计值造不成什么影响，等我们看到统计值有显著变化时可能已经太晚了。
我们也不能只统计已经回来的，还得盯着路上的请求，否则我们可能会向一个已经出问题（总是不回）的节点傻傻地浪费请求。
”按权值分流”听上去好简单，但你能写出多线程和可能修改节点的前提下，在O(logN)时间内尽量不互斥的查找算法吗？

DoubleBufferData TLS + 双缓冲

https://github.com/apache/incubator-brpc/blob/master/docs/cn/lalb.md

0x334 链路追踪

trace_id + span_id来标识链路的调用关系
对trace_id采样，而不要随机采样。

0x335 配置中心

不同的配置类型：节点类型》机房类型》全局配置

配置项的读取-变更推送如何实现：
轮询 + 摘要（简单，实时性略差）
长轮询 + 版本号（复杂，实时性好一些）

配置项的存储-配置系统的高可用
一个小原则：配置系统的旁路化，不要因为配置系统挂了，你的程序启动不了；
可以做两层缓存：内存缓存、文件保存

核心指标在于可用性！！！5个9？

0x336 日志系统

0x337 API网关

入口网关：隔离客户端与微服务，协议转换、安全策略、认证、限流、熔断等
出口网关：调用外部API，统一认证，授权、授权、访问控制等

API设计要点：性能、扩展性（责任链模式）
性能：IO多路复用、异步非阻塞、线程池
隔离性：针对接口对线程池进行分类

0x338 Service Mesh

解决了哪些问题：屏蔽服务化系统的服务治理细节（跨语言无法享用框架微服务能力的问题）、中间件升级难的问题

控制平面（服务治理策略的植入）、数据平面（sidecar,负责数据传输）
sidecar两种植入方式：iptables、轻量级客户端

入口网关：隔离客户端与微服务，协议转换、安全策略、认证、限流、熔断等
出口网关：调用外部API，统一认证，授权、授权、访问控制等

API设计要点：性能、扩展性（责任链模式）
性能：IO多路复用、异步非阻塞、线程池
隔离性：针对接口对线程池进行分类

0x339 监控系统

APM：端到端的监控体系

如何防止消息被篡改：对消息体 + 消息头进行加密，生成一个签名
如何对数据进行加密：

使用非对称加密的公钥对 “对称加密的私钥-OriginPrivate“ 进行加密，得到SecretPrivate
然后服务端利用非对称加密的私钥，对 SecretPrivate进行解密，得到OriginPrivate

然后再使用OriginPrivate对加密之后的消息体（SecretContext)进行解密，得到Contenxt

监控哪些东西：网络卡顿率、做某件事情的失败率等

考虑暂存 + retry来应对网络状况不佳的情况

0x33A 自动化全链路压测系统

压测的原则-尽量模拟真实情况；压测的注意点：
（1）使用线上数据与线上数据
（2）使用线上流量（流量拷贝）
（3）流量应该从尽量靠近用户的CDN发起

如何搭建：
（1）流量的隔离（区分压测流量与正式流量）
（2）风险控制（尽量避免压测对正常用户的影响）

压测数据的产生：
拷贝真实流量（可以从访问日志、可以抓取某个端口的数据等）
打上压测标签
放在合适的机房（尽量接近用户）
数据隔离：
针对读请求，针对某些不能压测（例如推荐、数据分析等）的组件进行mock
对于写请求，把流量产生的数据写入影子库（数据库-拷贝一份库表和数据；缓存-加压测前缀；ES-多搞一份索引）
压力测试的实施
持续放大，做好系统过载的识别（例如超时率、resp time等）

0x34 常见系统设计

系统设计一般会经过几步：

第一，了解业务要实现的功能以及DAU状况（除了需求功能，还要考虑高性能、高扩展性、高可用性）

第二，根据第一步了解的信息，进行初略估计：

（1）估计系统的QPS

（2）估计系统对数据库的QPS以及是否需要缓存

（3）估计系统每天产生的数据量以及累计总量，决定是否需要额外存储

（4）根据以上3点去估计需要几种类型的机器以及每种类型的机器数量。

以上第（4）点提到的估计需要我们对系统的吞吐率比较了解，我们可以看下面的例子：

服务器配置
CPU：Intel(R) Xeon(R) CPU 1.60GHz
内存：4GB
硬盘转速：15k/min

第三，输出系统整体架构以及每个模块的单独设计

首先，我们要罗列出系统中应该要有哪些模块，每一个模块需要哪些数据，存储的数据访问以及存储特点。不同的特点对应着不同的存储：关系型数据库、KV数据库、KV缓存、分布式数据库、ClickHouse、HBase等（这里我们需要知道尽可能多的存储类型以及各自的优缺点）

其次，这些模块对外提供哪些功能，这些功能提供给谁。搞清楚各模块之间的调用关系，注意不要出现环形依赖。如果有必要的话，是否可以借助消息队列来解除耦合。

最后，模块提供的接口QPS是多少？这些QPS是读还是写？支撑读的话是否需要缓存？支撑写的话是否需要队列？

第四，对架构进行进一步优化

（1）业务逻辑上的优化：是不是可以调整业务逻辑来让系统支撑更高的吞吐？

（2）架构优化：性能瓶颈、单点故障、是否可扩展、监控是否到位

以上内容可以参考： https://www.codercto.com/a/72987.html

下面的表格汇总了一些我遇到的常见系统设计题目，供参考。

题目	核心考察点
唯一ID生成器	先号段后ID、雪花算法
短网址	基于自增ID来生成url
秒杀系统	防止超卖、异步扣库存｜
抽奖系统	概率、蓄水池采样｜
PUSH系统	长链接、队列
消息系统	TimeLine ｜
微博系统	TimeLine ｜
定时任务调度系统	定时器｜
分布式日志系统	倒排｜
网站用户在线统计	hash ｜
用户积分排名系统	树形分区、排名数组｜

0x40 计算机方法论

批量处理 Batch

在处理网络、磁盘等高耗时请求时，通过合并一些频繁请求的小资源可以获得更快的加载速度。

预处理 (Pre process)

当某一次计算特别慢时，可以提前算吗？算好了之后把它存起来，下次访问就快了。

checkpoint 检查点

快速恢复存储系统 + log

懒惰思想

延后计算，最终一致。

乐观锁

MVCC

池化

例如：内存池、线程池、连接池。池化实际上是预处理和延后处理的一种应用场景，通过池子将各类资源的创建提前和销毁延后。

Copy On Write

零拷贝（mmap、sendfile)

关于Trade Off

说明：没有对错、只有是否适合场景

一致性换性能

buffer 写入

并不是每次都把请求打到底层的慢速存储，

PageCache

同步访问变异步访问

同步变异步，追求更好的性能。

空间换时间

双缓冲

double buffer

索引

bitmap(磁盘文件管理)、radix tree、红黑树、倒排索引

多级索引

page table

线程局部存储

线程局部分析

thread local

提升复杂度，提高性能

随机读写转顺序读写

WAL （write ahead log）

binlog

LSM tree

局部性原理

缓存

splay tree 将最近访问的节点尽量移向根节点。

正交

各个概念之间可以独立变化

分层

操作系统：硬件 —> 操作系统—> 应用程序—> 应用程序的通信、调用
计算机网络：ISO七层
MVC：Model层—> View层—> Control