Neo's Blog

0xFF 写在前面

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

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

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

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

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

0. 协程优缺点

协程是使用同步的编程思想，达到异步的效率

核心点：

1.使用异步IO未就绪，就切换到已经准备就绪的IO去操作
解决了异步代码逻辑复杂，同步效率低的问题，效率接近异步

2.协程的栈可以设置比线程更小，使得更加容易

解决了线程占用栈空间更大的问题，硬件的使用率更高，同异步的效率，硬件成本会更低

3.线程的创建代价和调度代价相对比较高

缺点 ：

1. 缺点是无法利用多核资源，本质是单核的，它不能同时将单个CPU的多个核用上，协程需要和进程配合才能运行在多CPU上。
2. 跨平台性挑战较大

A、accept 惊群
以多进程为例，在主进程创建监听描述符listenfd后，fork()多个子进程，多个进程共享listenfd，accept是在每个子进程中，当一个新连接来的时候，会发生惊群。

在内核2.6之前，所有进程accept都会惊醒，但只有一个可以accept成功，其他返回EGAIN。

在内核2.6及之后，解决了惊群问题，办法是在内核中增加了一个互斥等待变量。一个互斥等待的行为与睡眠基本类似，主要的不同点在于：
a）当一个等待队列入口有 WQ_FLAG_EXCLUSEVE 标志置位, 它被添加到等待队列的尾部。若没有这个标志的入口项，则添加到队首。

b）当wake up被在一个等待队列上调用时,它在唤醒第一个有 WQ_FLAG_EXCLUSIVE 标志的进程后停止。
执行步骤：
对于互斥等待的行为，比如对一个 listen 后的socket描述符，多线程阻塞 accept 时，系统内核只会唤醒所有正在等待此时间的队列的第一个，队列中的其他人则继续等待下一次事件的发生。这样就避免的多个线程同时监听同一个socket描述符时的惊群问题。

B、epoll惊群
epoll惊群分两种：

a)是在fork之前创建 epollfd，所有进程共用一个epoll。

b)是在fork之后创建 epollfd，每个进程独用一个epoll。

a)fork之前创建epollfd(新版内核已解决)

主进程创建 listenfd，创建epollfd;

主进程 fork多个子进程;

每个子进程把listenfd，加到epollfd 中。

当一个连接进来时，会触发epoll惊群，多个子进程的epoll同时会触发。

这里的epoll惊群跟 accept 惊群是类似的，共享一个 epollfd，加锁或标记解决，在新版本的epoll中已解决，但在内核2.6及之前是存在的。

b)fork之后创建epollfd(内核未解决)

主进程创建 listendfd;

主进程创建多个子进程;

每个子进程创建自已的epollfd;

每个子进程把listenfd加入到epollfd中;

当一个连接进来时，会触发epoll 惊群，多个子进程epoll同时会触发。

因为每个子进程的epoll是不同的epoll, 虽然listenfd是同一个，但新连接过来时,accept会触发惊群。因为内核不知道该发给哪个监听进程，因为不是同一个epoll。所以这种惊群内核并没有处理，惊群还是会出现。
————————————————
版权声明：本文为CSDN博主「84岁带头冲锋」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/L2111533547/article/details/125982204

本文我们探讨如何成为一个出色的工程师？

按照SKA模型，我的答案会分为三大块：

• 第一，正确的态度(Attitude)或者思维方式。
  当遇到问题时，你会用什么样的态度去应对处理它？当你尝试去解决一个问题时，你又是如何思考的？
• 第二，尽可能娴熟的必要技能(Skill)。
  当你知晓了如何去思考问题之后，我们需要借助很多技能去把问题解决。例如，沟通协作技能、编程能力、问题排查能力等。
• 第三，尽可能完备的知识(Knowledge)体系。
  很多时候有些人知道问题的答案或者解决方案,仅仅是由于他知道一块我们不知道的知识。

0. NAT简介

NAT(Network Address Translation ，网络地址转换) 是一种广泛应用的解决IP 短缺的有效方法， NAT 将内网地址转和端口号换成合法的公网地址和端口号，建立一个会话，与公网主机进行通信。

0. 主存储

dpdk高性能

轮询机制

在包处理时，采用轮询机制，而避免中断，有利于减少上下文切换的开销，规避不必要的内存拷贝和系统调用。

亲和性与独占

特定任务可以被指定只在某个核上工作，避免线程在不同核间频繁切换，保证更多的cache命中

设置CPU亲和性，让程序近运行在指定的核上，仅读取指定网卡的指定队列，从而避免数据竞争

无锁循环队列

并行指令，从而加速访问

0. 主从复制机制

binlog

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

   (1)redis全内存，单线程，无锁。

   (2)redis Rehash 渐进式hash,双缓冲 + 分而治之思想

   关于写入，仅写ht[1]，不再写入ht[0]；关于读取，优先读ht[1], 没有的话，再读取ht[0]

   渐进式迁移的过程中，一次迁移一个bucket。包括用于解决冲突的hash链。

   以下是哈希表渐进式 rehash 的详细步骤：

（1）为 ht[1] 分配空间， 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
（2）在字典中维持一个索引计数器变量 rehashidx ， 并将它的值设置为 0 ， 表示 rehash 工作正式开始。
（3）在 rehash 进行期间， 每次对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增一。
（4）随着字典操作的不断执行， 最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1] ， 这时程序将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。

渐进式 rehash 的好处在于它采取分而治之的方式， 将 rehash 键值对所需的计算工作均滩到对字典的每个添加、删除、查找和更新操作上， 从而避免了集中式 rehash 而带来的庞大计算量。

1. Redis提供了哪些数据结构；每一种数据结构的使用场景、大致实现（编码方式、内存占用、时间复杂度）

八种编码方式

INT 64 位有符号整数类型的时候将会采用 INT 编码。 值在[0,1000)之间。 如果存入整数的值在[0,1000)中Redis将不会创建新的对象,而是直接指向共享对象,键值不额外占用空间。

EMBSTR(EmbeddedString， 当存储的字符串长度较短时(len<=44 字节),Redis将会采用 embstr 编码，避免再次分配内存， 复用redis object)。这个长度是咋计算出来的呢？ 跟redis的底层内存池（jcmalloc）有关系。 64字节减去一些元数据。

RAW 原始字符串

ZIPLIST (压缩列表，连续内存，内存利用率高，增删改查效率低下；当hash、zset、list元素少且内容不大时使用该编码),

压缩列表是一块连续的内存空间，元素之间紧挨着存储，没有任何冗余空隙。每次有写操作的时候，会重新分配内存，例如insert, remove等操作。

QUICK_LIST（list元素较多时使用）

double list of ziplist

INTSET(整数集合，当set元素较少且都为整数时，使用该编码,从小到大的顺序存储，方便做交、并、差集运算。

intset是一个由整数组成的有序集合，从而便于在上面进行二分查找，用于快速地判断一个元素是否属于这个集合

ziplist可以存储任意二进制串，而intset只能存储整数。
ziplist是无序的，而intset是从小到大有序的。因此，在ziplist上查找只能遍历，而在intset上可以进行二分查找，性能更高。
ziplist可以对每个数据项进行不同的变长编码（每个数据项前面都有数据长度字段len），而intset只能整体使用一个统一的编码（encoding）。

HASH（hash元素较多时使用） 渐进式扩容缩容策略

SKIPLIST（跳表，zset元素多时使用）

数据结构与编码关系

实际上，Redis中sorted set的实现是这样的：

当数据较少时，sorted set是由一个ziplist来实现的。
当数据多的时候，sorted set是由一个dict + 一个skiplist来实现的。简单来讲，dict用来查询数据到分数的对应关系，而skiplist用来根据分数查询数据（可能是范围查找）。

Redis中的skiplist是什么样子的

score字段是数据对应的分数。

backward字段是指向链表前一个节点的指针（前向指针）。节点只有1个前向指针，所以只有第1层链表是一个双向链表。

level[]存放指向各层链表后一个节点的指针（后向指针）。每层对应1个后向指针，用forward字段表示。另外，每个后向指针还对应了一个span值，它表示当前的指针跨越了多少个节点。span用于计算元素排名(rank)，这正是前面我们提到的Redis对于skiplist所做的一个扩展。需要注意的是，level[]是一个柔性数组（flexible array member），因此它占用的内存不在zskiplistNode结构里面，而需要插入节点的时候单独为它分配。也正因为如此，skiplist的每个节点所包含的指针数目才是不固定的，我们前面分析过的结论——skiplist每个节点包含的指针数目平均为1/(1-p)——才能有意义。

假设我们在这个skiplist中查找score=89.0的元素（即Bob的成绩数据），在查找路径中，我们会跨域图中标红的指针，这些指针上面的span值累加起来，就得到了Bob的排名(2+2+1)-1=4（减1是因为rank值以0起始）。需要注意这里算的是从小到大的排名，而如果要算从大到小的排名，只需要用skiplist长度减去查找路径上的span累加值，即6-(2+2+1)=1。

可见，在查找skiplist的过程中，通过累加span值的方式，我们就能很容易算出排名。相反，如果指定排名来查找数据（类似zrange和zrevrange那样），也可以不断累加span并时刻保持累加值不超过指定的排名，通过这种方式就能得到一条O(log n)的查找路径。

skiplist与平衡树、哈希表的比较

skiplist和各种平衡树（如AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个key的查找，不适宜做范围查找。所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点。

在做范围查找的时候，平衡树比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比平衡树要简单得多。

Redis的可靠存储

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

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

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

AOF，定期（通常是s级别）append 写操作命令到文件中，只是简单的写一次磁盘，所以性能较好，如果新的命令append到aof之间发生宕机，丢失的数据也比较少。缺点是每次基于AOF恢复数据会比较慢。

AOF缓冲数据的写入策略：NO（依赖操作系统的flush盘机制）、always（性能最差，安全性最好）、everySecond（最多丢失1～2秒数据）

AOF重写【BGREWRITEAOF】，AOF 重写缓冲区

把主线程的内存拷贝一份给fork出来的 bgrewriteaof 子进程，这里面包含了Redis中最新的数据。

下表是完整的AOF后台重写过程：

时间 服务器进程（父进程） 子进程

T1 执行命令 SET K1 V1
T2 执行命令 SET K1 V1
T3 执行命令 SET K1 V1
T4 创建子进程，执行AOF文件重写 开始AOF重写
T5 执行命令 SET K2 V2 执行重写
T6 执行命令 SET K3 V3 执行重写
T7 执行命令 SET K4 V4 完成AOF重写，向父进程发送信号
T8 接收到信号，将T5 T6 T7 服务器的写命令追加到新的AOF文件末尾
T9 用新的AOF替换旧的AOF

T8 T9执行的任务会阻塞服务器处理命令。

https://www.51cto.com/article/694868.html

Redis 3.0 基于checkpoint思想的新持久化方式

Redis的高可用性

redis tw代理模式与cluster集群模式分别是如何工作的？ 哪一种模式使用了一致性Hash?

两者都是为了解决单机数据存不下的问题。数据存不下，只能通过多台来存。

客户端通过tw代理模式访问redis集群，数据分片使用了一致性hash，以尽可能减少某台redis机器不可用造成的影响，但是还是会丢数据。

官方的cluster集群方案是由客户端sdk来维护slot分布，数据分片分片是通过CRC32(key)%16834来实现。无中心化，node之间通过gossip协议来进行通信，选主等。

另外，redis cluster还尝试解决高可用的问题，但是由于CAP理论，他选择了可用性，丢失了一致性。 丢失一致性的点在于：1）异步复制；2）网络分区。

另外值得一提的是Redis哨兵模式。这种模式只能解决高可用的问题（并不能保证数据不丢失），但是无法解决数据太大的问题。

Redis 实现分布式锁

1. 如何通过Redis实现一个“可靠”的分布式锁？

分布式锁的特性：排他性、无死锁、高可用。

先说加锁，setnx命令，支持cas操作，并且支持设置超时时间。通过设置超时时间这个功能点，可以避免加锁后进程挂掉造成的锁没法释放的问题。但是这种加锁方案还有一个缺点，那就是超时时间很难设置的很合理，设置过短可能会引起加锁时间内不足以完成业务逻辑；设置过长又导致宕机恢复时间过长。这种情况下，我们可以额外启动一个WATCH-dog线程来监视这些锁，如果锁快要到期了，就调用expire命令对锁进行续期；业务完成时禁用watch-dog即可。

再说解锁unlock，理想情况下，解锁时只要通过del命令来把锁定的key删除即可。但是实际情况可能会更复杂一些。第一个问题，如果删除的key不是加的锁怎么办？ 容易想到，加锁时，设置key的value为一个unique id。 解锁删除时，先get一下key，看看key对应的value是不是跟预期的id相符，如果相符，del；否则，noop，说明我正准备删除别人加的锁。但是刚才的方案，还有一个缺陷那就是get跟del两个操作不是一个原子的，中途可能会被打断。如果真的被打断，还是会出现误解锁的过程。此时我们可以借助lua脚本将刚才的两个步骤原子化。至此，解锁操作才算基本完成。

上面的方案还有啥问题呢？ 如果主从同步未完成，而主挂掉了，从上位之后，会导致之前加的锁失效。 这个问题，官方给的解决方案是使用redis cluster的红锁来解决。

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

redis key过期的方式

• 惰性淘汰：在key请求时，判断key是否失效，失效就淘汰

• 定时策略：每隔100毫秒检测一次， 移除所有已过期的键
  如果发现超过25%的键过期，会重复执行。

redis 淘汰策略

当 Redis 的运行内存已经超过 Redis 设置的最大内存之后，则会使用内存淘汰策略删除符合条件的 key，以此来保障 Redis 高效的运行。

2个维度的组合：

1. 回收哪些：仅仅回收有TTL的（volatile）、所有的、空集
2. 如何替换哪个： LRU、LFU、最短TTL、随机

最多一共有$3^3$种组合，只是有一些没有意义。例如空集 + LRU、所有的 + 最短TTL。 剩下的有意义的包括：

• noeviction:返回错误当内存限制达到，并且客户端尝试执行会让更多内存被使用的命令。
• volatile-lfu:
• volatile-lru: 尝试回收最少使用的键（LRU），但仅限于在过期集合的键,使得新添加的数据有空间存放。

• volatile-random: 回收随机的键使得新添加的数据有空间存放，但仅限于在过期集合的键。

• volatile-ttl: 回收在过期集合的键，并且优先回收存活时间（TTL）较短的键,使得新添加的数据有空间 存放。

• allkeys-lru: 尝试回收最少使用的键（LRU），使得新添加的数据有空间存放。
• allkeys-lfu: Least Frequently Used 最近最不常用的
• allkeys-random: 回收随机的键使得新添加的数据有空间存放。

事务

事务，但 Redis 提供的不是严格的事务，Redis 只保证串行执行命令，并且能保证全部执行，但是执行命令失败时并不会回滚，而是会继续执行下去。

1. 命令入队报错，全部回滚，没有任何影响
2. 命令执行时报错，不会回滚，而是会继续执行余下的命令

watch机制

watch 一个变量， multi exec 根据中间有没有其他线程更改watched的变量来决定，是commit事务还是rollback事务，有点像CAS操作，只是Redis的watch机制并没有ABA问题

高级用法

Bitmap :
位图是支持按 bit 位来存储信息，可以用来实现 布隆过滤器（BloomFilter）；

HyperLogLog:
供不精确的去重计数功能，比较适合用来做大规模数据的去重统计，例如统计 UV；

Geospatial:
可以用来保存地理位置，并作位置距离计算或者根据半径计算位置等。有没有想过用Redis来实现附近的人？或者计算最优地图路径？

这三个其实也可以算作一种数据结构，不知道还有多少朋友记得，我在梦开始的地方，Redis基础中提到过，你如果只知道五种基础类型那只能拿60分，如果你能讲出高级用法，那就觉得你有点东西。

pub/sub：
功能是订阅发布功能，可以用作简单的消息队列。

Pipeline：
可以批量执行一组指令，一次性返回全部结果，可以减少频繁的请求应答。

Lua：
Redis 支持提交 Lua 脚本来执行一系列的功能。

我在前电商老东家的时候，秒杀场景经常使用这个东西，讲道理有点香，利用他的原子性。

参考：http://zhangtielei.com/posts/blog-redis-ziplist.html

变量&类型相关

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

func main() {
    var a = []interface{}{1, 2, 3}

    //变参函数忘记...展开
    fmt.Println(a)
    fmt.Println(a...)
} 

func main() {
    x := [3]int{1, 2, 3}

    //在函数调用参数中，数组是值传递，无法通过修改数组类型的参数返回结果。
    func(arr [3]int) {
        arr[0] = 7
        fmt.Println(arr)
    }(x)

    fmt.Println(x)
}


func Foo() (err error) {
    if err := Bar(); err != nil {
        return
    }
    return
}

//map是一种hash表实现，每次遍历的顺序都可能不一样。
func main() {
    m := map[string]string{
        "1": "1",
        "2": "2",
        "3": "3",
    }

    for k, v := range m {
        println(k, v)
    }
}

数据库、缓存一致性问题

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

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

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

  2. 另外一点，很多时候，在复杂点的缓存场景，缓存不单单是数据库中直接取出来的值，也就是说update的value是什么我无法简单得知。

  3. 懒加载思想： 更新了，但是没有读请求就白白浪费内存了。

• 先写DB还是先写缓存？

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

  出现并发问题的时序如下：

  1. 如果读的时候，key不存在，回源头读ReadDB
  2. 写操作，UpdateDB
  3. 写操作，删除缓存
  4. 读操作，将第一步读到的数据写入缓存（此时，缓存已经过期）

• 高并发下，关于缓存的一致性会出现什么问题？

  case1, case2中提到了在高并发的情况下，会出现某种并发逻辑错误，导致数据不一致。

• 是否听说过订阅数据库binlog变更去清理缓存的方法？这个方法的使用场景是啥？

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

CacheAside模式

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

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

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

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

解决方案：

1. updateDB + updateCache(With Lock)
2. 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，而其他线程等待，可以一定程度上避免缓存穿透问题。

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

如何解决缓存并发穿透呢？
（1）热点发现，定时续期
（2）对于极热点，启用本地缓存

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

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

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

缓存雪崩

最后谈一下缓存雪崩。

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

热key重建

高并发多线程的情况下，热Key重键是使用redis比较典型的一个问题：

解决方案：

1. 加锁重键（互斥锁）：
2. 热键不过期：在缓存中创建一个时间戳，先判断时间戳是否过期，如果没有过期返回原数据，过期了则访问数据源