服务器开发自我修养专栏-Redis实现原理

Posted on 04-20-2021 | In Self-cultivation

Redis

redis 数据结构有哪些？分别怎么实现的？

String:
- 全是整数的时候用整数编码int
- 当有字符串的时候用简单动态字符串sds编码
HashTable:
- 元素比较少或者元素比较短的时候用压缩表ziplist(key1|val1|key2|val2|…这样存储),
- 其他时候就用字典ht
Set:
- 元素全是整数的时候用整数集合编码(一种特殊的编码, 会使用各种规则来利用位空间, 来节省内存),
- 其他时候用字典ht编码(键为Set的元素, 值都为Null)
List:
- 元素比较少或者元素比较短的时候用压缩表ziplist,
- 其他时候就用双端列表LinkedList编码
ZSet:
- 参考 http://redisbook.com/preview/object/sorted_set.html
- 参考 https://redisbook.readthedocs.io/en/latest/datatype/sorted_set.html
- 元素比较少或者元素比较短的时候用压缩表ziplist(member1|score1|member2|score2|…, 按照score从小到大排列),
- 其他时候就用跳跃表SkipList编码, 这个编码里包含一个字典结构和一个跳表结构, 但这两种数据结构都会通过指针来共享相同元素的成员和分值，所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员或者分值，也不会因此而浪费额外的内存:
  - 字典用于快速查找, 如ZScore查询member成员的 score 值, 或者快速确定是否有某个member
  - 跳表用于zrank/zrange等

zset各种问题

为什么zset用跳表不用红黑树

现在我们看看，对于这个问题，Redis的作者 @antirez 是怎么说的：

There are a few reasons:

They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

可参考: 本博客文章跳表
总结:

平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。
从内存占用上来说，skiplist比平衡树更灵活一些。一般来说，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。
从算法实现难度上来比较，skiplist比平衡树要简单得多。

zset是怎么支持查询排名的

跳表怎么支持查询排名的

延时队列用redis怎么做

用zset，拿时间戳作为score，消息内容作为key调用zadd来生产消息，消费者轮询zset用zrangebyscore指令获取N秒之前的数据轮询进行处理。

ZSET做排行榜时要实现分数相同时按时间顺序排序怎么实现

说了一个将 score 拆成高 32 位和低 32 位，高 32 位存分数，低 32 位存时间的方法。

哈希表渐进式rehash

当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：
- 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 1 ；
- 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 5 ；
  
  根据 BGSAVE 命令或 BGREWRITEAOF 命令是否正在执行，服务器执行扩展操作所需的负载因子并不相同，这是因为在执行 BGSAVE 命令或 BGREWRITEAOF 命令的过程中， Redis 需要创建当前服务器进程的子进程，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可能地避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要的内存写入操作，最大限度地节约内存。
另一方面，当哈希表的负载因子小于 0.1 时，程序自动开始对哈希表执行收缩操作。

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

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

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

因为在进行渐进式 rehash 的过程中，字典会同时使用 ht[0] 和 ht[1] 两个哈希表，所以在渐进式 rehash 进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行：比如说，要在字典里面查找一个键的话，程序会先在 ht[0] 里面进行查找，如果没找到的话，就会继续到 ht[1] 里面进行查找，诸如此类。

另外，在渐进式 rehash 执行期间，新添加到字典的键值对一律会被保存到 ht[1] 里面，而 ht[0] 则不再进行任何添加操作：这一措施保证了 ht[0] 包含的键值对数量会只减不增，并随着 rehash 操作的执行而最终变成空表。

redis 持久化有哪几种方式，怎么选？

混合持久化
- 原因: 重启 Redis 时，我们很少使用 rdb 来恢复内存状态，因为会丢失大量数据。如果使用 AOF 日志重放，性能则相对 rdb 来说要慢很多，这样在 Redis 实例很大的情况下，启动的时候需要花费很长的时间。
- 原理: 混合持久化同样也是通过bgrewriteaof完成的，不同的是当开启混合持久化时，fork出的子进程先将共享的内存副本全量的以RDB方式写入aof文件，然后在将aof_rewrite_buf重写缓冲区的增量命令以AOF方式写入到文件，写入完成后通知主进程更新统计信息，并将新的含有RDB格式和AOF格式的AOF文件替换旧的的AOF文件。
- 简单的说：新的AOF文件前半段是RDB格式的全量数据后半段是AOF格式的增量数据，
rdb
- 优势:
  - RDB文件紧凑，全量备份，非常适合用于进行备份和灾难恢复。
  - 生成RDB文件的时候，redis主进程会fork()一个子进程来处理所有保存工作，主进程不需要进行任何磁盘IO操作。
  - RDB 在恢复大数据集时的速度比 AOF 的恢复速度要快。
- 劣势:
  - 当进行快照持久化时，会开启一个子进程专门负责快照持久化，子进程会拥有父进程的内存数据，父进程修改内存子进程不会反应出来，所以在快照持久化期间修改的数据不会被保存，可能丢失数据。
aof
- 优势:
  - AOF可以更好的保护数据不丢失，一般AOF会每隔1秒，通过一个后台刷盘线程执行一次fsync操作(这种一秒刷盘一次的策略, 可能会造成追加阻塞: 当硬盘资源繁忙时，即主线程发现距离上次fsync时间超过2秒, 为了数据安全性, 主线程会阻塞直到后台刷盘线程执行fsync操作完成)，保证最多丢失1秒钟的数据。所以这也是redis重启优先加载aof的理由
  - AOF日志文件没有任何磁盘寻址的开销，写入性能非常高，文件不容易破损。
  - AOF日志文件即使过大的时候，出现后台重写操作，也不会影响客户端的读写。
  - AOF日志文件的命令通过可读的方式进行记录，这个特性非常适合做灾难性的误删除的紧急恢复。比如某人不小心用flushall命令清空了所有数据，只要这个时候后台rewrite还没有发生，那么就可以立即拷贝AOF文件，将最后一条flushall命令给删了，然后再将该AOF文件放回去，就可以通过恢复机制，自动恢复所有数据
- 劣势:
  - 对于同一份数据来说，AOF日志文件通常比RDB数据快照文件更大
  - AOF开启后，支持的写QPS会比RDB支持的写QPS低，因为AOF一般会配置成每秒fsync一次日志文件，当然，每秒一次fsync，性能也还是很高的

bgsave流程说一下

子进程创建RDB文件, 根据父进程内存生成临时快照文件, 完成后对原有RDB文件进行原子替换. 然后子进程发送信号给父进程表示完成

aof流程说一下以及aof追加阻塞是啥

追加阻塞:

AOF可以更好的保护数据不丢失，一般AOF会每隔1秒，通过一个后台刷盘线程执行一次fsync操作(这种一秒刷盘一次的策略, 可能会造成追加阻塞: 当硬盘资源繁忙时，即主线程发现距离上次fsync时间超过2秒, 为了数据安全性, 主线程会阻塞直到后台刷盘线程执行fsync操作完成)，保证最多丢失1秒钟的数据。

AOF重写的实现

所谓的“重写”其实是一个有歧义的词语, AOF重写并不需要对原有AOF文件进行任何的读取，写入，分析等操作，这个功能是通过读取服务器当前的数据库状态来实现的。
如当前列表键list在数据库中的值就为["C", "D", "E", "F", "G"]。要使用尽量少的命令来记录list键的状态，最简单的方式不是去读取和分析现有AOF文件的内容，，而是直接读取list键在数据库中的当前值，然后用一条RPUSH list "C" "D" "E" "F" "G"代替前面的6条命令

AOF 重写程序可以很好地完成创建一个新 AOF 文件的任务，但是，在执行这个程序的时候，调用者线程会被阻塞。很明显，作为一种辅佐性的维护手段， Redis 不希望 AOF 重写造成服务器无法处理请求，所以 Redis 决定将 AOF 重写程序放到（后台）子进程里执行，这样处理的最大好处是：

子进程进行 AOF 重写期间，主进程可以继续处理命令请求。
子进程带有主进程的数据副本，使用子进程而不是线程，可以在避免锁的情况下，保证数据的安全性。

不过，使用子进程也有一个问题需要解决：因为子进程在进行 AOF 重写期间，主进程还需要继续处理命令，而新的命令可能对现有的数据进行修改，这会让当前数据库的数据和重写后的 AOF 文件中的数据不一致。为了解决这个问题， Redis 增加了一个 AOF 重写缓存，这个缓存在 fork 出子进程之后开始启用， Redis 主进程在接到新的写命令之后，除了会将这个写命令的协议内容追加到现有的 AOF 文件之外，还会追加到这个重写缓存中, 换言之，当子进程在执行 AOF 重写时，主进程需要执行以下三个工作：

处理命令请求。
将写命令追加到现有的 AOF 文件中。
将写命令追加到 AOF 重写缓存中。

当子进程完成 AOF 重写之后，它会向父进程发送一个完成信号，父进程在接到完成信号之后，会调用一个信号处理函数，并完成以下工作：

将 AOF 重写缓存中的内容全部写入到新 AOF 文件中。
对新的 AOF 文件进行改名rename，覆盖原有的 AOF 文件。这就是aof的原子替换.

在整个 AOF 后台重写过程中，只有最后的写入缓存和改名操作会造成主进程阻塞，在其他时候， AOF 后台重写都不会对主进程造成阻塞，这将 AOF 重写对性能造成的影响降到了最低。以上就是 AOF 后台重写，也即是 BGREWRITEAOF 命令的工作原理。

如何做rdb和aof的原子替换的

比如想要将temp文件原子替换origin文件, 则直接rename tmp文件到origin文件即可实现.
rename通过来说, 直接修改 file system metadata, 如inode信息. 在posix标准里, rename实现是原子的, 即:

rename成功, 原文件名指向 temp 文件; 原文件内容被删除.
rename失败, 原文件名仍指向原来的文件内容.

redis 主从同步是怎样的过程？

从redis发出sync要求
主redis开始bgsave(并且一边开启指令buffer来存储bgsave过程中的写指令们记为cmd)
主redis把bgsave生成的rdb发给从redis
把cmd发送给从redis
从服务器完成对快照的载入，开始接收命令请求，并执行来自主服务器缓冲区的写命令

总结:
主从刚刚连接的时候，进行全量同步；全量同步结束后，进行增量同步。当然，如果有需要，slave 在任何时候都可以发起全量同步。redis 策略是，无论如何，首先会尝试进行增量同步，如不成功，要求从机进行全量同步。

redis key 的过期策略

Redis键的过期策略，是有定期删除+惰性删除两种。

定期好理解，默认100ms就随机抽一些设置了过期时间的key，去检查是否过期，过期了就删了。
惰性删除，查询时再判断是否过期，过期就删除键不返回值。

内存淘汰机制

当新增数据发现内存达到限制时，Redis触发内存淘汰机制。

lru
lfu(least frequency used, redis 4新增)
random
ttl

redis的LRU算法说一下

普通的LRU算法:
一般是用哈希表+双向链表来实现的:

基于 HashMap 和双向链表实现 LRU 的整体的设计思路是，可以使用 HashMap 存储 key，这样可以做到 save 和 get key的时间都是 O(1)，而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点. 其核心操作的步骤是:
- save(key, value):
  首先在 HashMap 找到 Key 对应的节点，如果节点存在，更新节点的值，并把这个节点移动队头。如果不存在，需要构造新的节点，并且尝试把节点塞到队头，如果LRU空间不足，则通过 tail 淘汰掉队尾的节点，同时在 HashMap 中移除 Key。
- get(key):
  通过 HashMap 找到 LRU 链表节点，因为根据LRU 原理，这个节点是最新访问的，所以要把节点插入到队头，然后返回缓存的值。
Redis的LRU实现:
- 如果按照HashMap和双向链表实现，需要额外的存储存放 next 和 prev 指针，牺牲比较大的存储空间，显然是不划算的。所以Redis采用了一个近似的做法，就是定时每隔一段时间就随机取出若干个key，然后按照访问时间排序后，淘汰掉最不经常使用的.
- Redis 3.0之后又改善了算法的性能，会提供一个待淘汰候选key的pool，里面默认有16个key，按照空闲时间排好序。更新时从Redis键空间随机选择N个key，分别计算它们的空闲时间 idle，key只会在pool不满或者空闲时间大于pool里最小的时，才会进入pool，然后从pool中选择空闲时间最大的key淘汰掉。

redis哨兵

Redis Sentinel是Redis的高可用实现方案：故障发现、故障自动转移、配置中心客户端通知。
Redis Sentinel从Redis 2.8版本开始才正式生产可用，之前版本生产不可用。
尽可能在不同物理机上部署Redis Sentinel所有节点。
Redis Sentinel中的Sentinel节点个数应该为大于等于3且最好为奇数。
Redis Sentinel中的数据节点与普通数据节点没有区别。
哨兵是一个配置提供者，而不是代理。在引入哨兵之后，客户端会先连接哨兵，再获取到主节点之后，客户端会和主节点直接通信。如果发生了故障转移，哨兵会通知到客户端。所以这也需要客户端的实现对哨兵的显式支持。
Redis Sentinel通过三个定时任务实现了Sentinel节点对于主节点、从节点、其余 Sentinel节点的监控。
Redis Sentinel在对节点做失败判定时分为主观下线和客观下线。
Redis Sentinel实现读写分离高可用可以依赖Sentinel节点的消息通知，获取Redis 数据节点的状态变化。

用文字描述一下故障切换（failover）的过程:

假设主服务器宕机，哨兵1先检测到这个结果，系统并不会马上进行failover过程，仅仅是哨兵1主观的认为主服务器不可用，这个现象成为主观下线。
当后面的哨兵也检测到主服务器不可用，并且数量达到一定值时，就对这个主节点故障达成一致, 这个过程称为客观下线。
这样对于客户端而言，一切都是透明的。然后通过raft算法从哨兵中选出一个哨兵来执行故障转移

redis集群

redis集群是一个由多个主从节点群组成的分布式服务器群，它具有复制、高可用和分片特性。Redis集群不需要sentinel哨兵也能完成节点移除和故障转移的功能。需要将每个节点设置成集群模式，这种集群模式没有中心节点，可水平扩展，据官方文档称可以线性扩展到上万个节点(官方推荐不超过1000个节点)。redis集群的性能和高可用性均优于之前版本的哨兵模式，且集群配置非常简单。
集群模式有以下几个特点：

由多个Redis服务器组成的分布式网络服务集群；
集群之中有多个Master主节点，每一个主节点都可读可写；
节点之间会互相通信，两两相连, 采用gossip协议来通信；
Redis集群无中心节点。
集群的伸缩本质是: 槽数据在节点中的移动

优点

在哨兵模式中，仍然只有一个Master节点。当并发写请求较大时，哨兵模式并不能缓解写压力。我们知道只有主节点才具有写能力，那如果在一个集群中，能够配置多个主节点，缓解写压力，redis-cluster集群模式能达到此类要求。

在Redis-Cluster集群中，可以给每一个主节点添加从节点，主节点和从节点直接遵循主从模型的特性。
当用户需要处理更多读请求的时候，添加从节点开启read-only来读写分离可以扩展系统的读性能。

缺点

Redis 集群不支持那些需要同时处理多个键的 Redis 命令，因为执行这些命令需要在多个 Redis 节点之间移动数据，并且在高负载的情况下，这些命令将降低 Redis 集群的性能，并导致不可预测的行为。
不能用redis事务机制(不过就算不用redis集群一般也不推荐用redis的事务, 毕竟假事务无法回滚嘛, 比如multi之后那些在 EXEC 命令执行之后所产生的错误，并没有对它们进行特别处理：即使事务中有某个/某些命令在执行时产生了错误，事务中的其他命令仍然会继续执行。)。因为一个事务中有涉及到多个key操作的时候，这多个key不一定都存储在同一个redis-server上。

故障转移

Redis集群的主节点内置了类似Redis Sentinel的节点故障检测和自动故障转移功能，当集群中的某个主节点下线时，集群中的其他在线主节点会注意到这一点，并对已下线的主节点进行故障转移。
集群进行故障转移的方法和Redis Sentinel进行故障转移的方法基本一样(也有主观下线和客观下线)，不同的是，在集群里面，故障转移的过程是:

在集群内广播选举消息
集群中其他在线的持有槽的主节点投票到故障主节点的从节点们
被选出来的从节点变成主节点

所以集群不必另外使用Redis Sentinel。

集群分片策略

常见的集群分片算法有：

一般哈希算法
一致性哈希算法
Hash Slot算法

Redis采用的是Hash Slot

一般哈希算法

计算方式：hash(key)%N
缺点：如果增加一个redis，映射公式变成了 hash(key)%(N+1)
如果一个redis宕机了，映射公式变成了 hash(key)%(N-1)
在以上两种情况下，几乎所有的缓存都失效了。

一致性哈希算法

先构造出一个长度为2^32整数环，根据节点名称的hash值（分布在[0,2^32-1]）放到这个环上。现在要存放资源，根据资源的Key的Hash值（也是分布在[0,2^32-1]），在环上顺时针的找到离它最近的一个节点，就建立了资源和节点的映射关系。

优点：一个节点宕机时，上面的数据转移到顺时针的下一个节点中，新增一个节点时，也只需要将部分数据迁移到这个节点中，对其他节点的影响很小
缺点：由于数据在环上分布不均，可能存在某个节点存储的数据比较多，那么当他宕机的时候，会导致大量数据涌入下一个节点中，把另一个节点打挂了，然后所有节点都挂了
改进：引进了虚拟节点的概念，想象在这个环上有很多“虚拟节点”，数据的存储是沿着环的顺时针方向找一个虚拟节点，每个虚拟节点都会关联到一个真实节点

HashSlot算法

Redis采用的是Hash Slot分片算法，用来计算key存储位置的。集群将整个数据库分为16384个槽位slot，所有key-value数据都存储在这些slot中的某一个上。一个slot槽位可以存放多个数据，key的槽位计算公式为：slot_number=CRC16(key)%16384，其中CRC16为16位的循环冗余校验和函数。
客户端可能会挑选任意一个redis实例去发送命令，每个redis实例接收到命令，都会计算key对应的hash slot，如果在本地就在本地处理，否则返回moved给客户端，让客户端进行重定向到对应的节点执行命令(实现得好一点的smart客户端会缓存键-slot-节点的映射关系来获得性能提升).

那为什么是16384个槽呢?

ps:CRC16算法产生的hash值有16bit，该算法可以产生2^16-=65536个值。换句话说，值是分布在0~65535之间。那作者在做mod运算的时候，为什么不mod65536，而选择mod16384？作者解答

在redis节点发送心跳包时需要把所有的槽放到这个心跳包里，以便让节点知道当前集群信息，16384=16k，在发送心跳包时使用char进行bitmap压缩后是2k（2 * 8 (8 bit) * 1024(1k) = 2K），也就是说使用2k的空间创建了16k的槽数。

虽然使用CRC16算法最多可以分配65535（2^16-1）个槽位，65535=65k，压缩后就是8k（8 * 8 (8 bit) * 1024(1k) = 8K），也就是说需要需要8k的心跳包，作者认为这样做不太值得；并且一般情况下一个redis集群不会有超过1000个master节点，所以16k的槽位是个比较合适的选择。

Cache和DB如何一致

详细的请参考: https://segmentfault.com/a/1190000015804406
本博客也有一份: Cache和DB一致性

总结:

使用cache aside pattern
- 对于读请求
  
  先读 cache，再读 db
  如果，cache hit，则直接返回数据
  如果，cache miss，则访问 db，并将数据 set 回缓存
- 对于写请求
  
  先操作数据库，再淘汰缓存（淘汰缓存，而不是更新缓存, 如果更新缓存，在并发写时，可能出现数据不一致。）
Cache Aside Pattern 方案存在什么问题？
- 问题1: 如果先写数据库，再淘汰缓存，在原子性被破坏时：
  1. 修改数据库成功了
  2. 淘汰缓存失败了
    导致，数据库与缓存的数据不一致。
  - 如何解决问题1?
    - 在淘汰缓存的时候，如果失败，则重试一定的次数。如果失败一定次数还不行，那就是其他原因了。比如说 redis 故障、内网出了问题。
- 问题2: 主从同步延迟导致的缓存和数据不一致问题
  - 问题: 发生写请求后（不管是先操作 DB，还是先淘汰 Cache），在主从数据库同步完成之前，如果有读请求，都可能发生读 Cache Miss，读从库把旧数据存入缓存的情况。此时怎么办呢？
  - 解决思路: 在主从时延的时间段内，读取修改过的数据的话，强制读主，并且更新缓存，这样子缓存内的数据就是最新。在主从时延过后，这部分数据继续读从库，从而继续利用从库提高读取能力。
  - 具体解决方案:
    - 写请求发生的时候: 将哪个库，哪个表，哪个主键三个信息拼装一个 key 设置到 cache 里，这条记录的超时时间，设置为 “主从同步时延”, PS：key 的格式为 “db:table:PK”，假设主从延时为 1s，这个 key 的 cache 超时时间也为 1s。
    - 当读请求发生时：这是要读哪个库，哪个表，哪个主键的数据呢，也将这三个信息拼装一个 key，到 cache 里去查询，如果，
      - （1）cache 里有这个 key，说明 1s 内刚发生过写请求，数据库主从同步可能还没有完成，此时就应该去主库查询。并且把主库的数据 set 到缓存中，防止下一次 cache miss。
      - （2）cache 里没有这个 key，说明最近没有发生过写请求，此时就可以去从库查询

缓存雪崩是啥?咋处理?

是指大面积的缓存失效，打崩了DB.

如果缓存挂掉，所有的请求会压到数据库，如果未提前做容量预估，可能会把数据库压垮（在缓存恢复之前，数据库可能一直都起不来），导致系统整体不可服务。
又或者打个比方, 如果所有首页的Key失效时间都是12小时，中午12点刷新的，我零点有个秒杀活动大量用户涌入，假设当时每秒 6000 个请求，本来缓存在可以扛住每秒 5000 个请求，但是缓存当时所有的Key都失效了。此时 1 秒 6000 个请求全部落数据库，数据库必然扛不住.

处理方案:

key随机过期
key永不过期, 比如开个单独线程去定时更新缓存
高可用, 如果Redis是集群部署，将热点数据均匀分布在不同的Redis库中也能避免全部失效的问题
隔离服务, 限流降级

缓存穿透是啥?咋处理?

是指缓存和数据库中都没有的数据，而用户不断发起请求，严重会击垮数据库

我们数据库的 id 都是1开始自增上去的，如发起为id值为 -1 的数据或 id 为特别大不存在的数据。这时的用户很可能是攻击者，攻击会导致数据库压力过大，严重会击垮数据库。

处理方案:

缓存穿透我会在接口层增加校验，比如用户鉴权校验，参数做校验，不合法的参数直接代码Return，比如：id 做基础校验，id <=0的直接拦截等。
布隆过滤器, 把存在的key提前存放好在布隆过滤器中, 当查询的时候快速判断出你这个Key是否在数据库中存在, 不存在则直接return

缓存击穿是啥?咋处理?

是指持续的大并发的访问一个热点数据, 当这个Key在失效的瞬间，持续的大并发就穿破缓存，直接请求数据库

这个跟缓存雪崩有点像，但是又有一点不一样，缓存雪崩是因为大面积的缓存失效，打崩了DB，而缓存击穿不同的是缓存击穿是指一个Key非常热点，在不停的扛着大并发，大并发集中对这一个点进行访问，当这个Key在失效的瞬间，持续的大并发就穿破缓存，直接请求数据库，就像在一个完好无损的桶上凿开了一个洞。

处理方案:

key永不过期, 比如开个单独线程去定时更新缓存
互斥锁, 在key失效的瞬间, 只允许一个查询操作的线程A去查询数据库并重建缓存并上互斥锁, 其他的查询操作线程全部等待线程A操作完了再从缓存里取数据

服务器开发自我修养专栏-编码知识

Posted on 04-18-2021 | In Self-cultivation

编码知识

Base64 的原理？编码后比编码前是大了还是小了。

结论:

大了. 因为Base64 编码本质上是一种将二进制数据转成文本数据的方案。对于非二进制数据，是先将其转换成二进制形式，然后每连续 6 比特（2 的 6 次方 = 64）计算其十进制值，根据该值在上面的索引表中找到对应的字符，最终得到一个文本字符串。也就是说, 每 3 个原始字符编码成 4 个字符，如果原始字符串长度不能被 3 整除，那怎么办？使用 0 值来补充原始字符串。

base64的原理

Base64 编码之所以称为 Base64，是因为其使用 64 个字符来对任意数据进行编码，同理有 Base32、Base16 编码。标准 Base64 编码使用的 64 个字符为：

这 64 个字符是各种字符编码（比如 ASCII 编码）所使用字符的子集，基本，并且可打印。唯一有点特殊的是最后两个字符，因对最后两个字符的选择不同，Base64 编码又有很多变种，比如 Base64 URL 编码。

Base64 编码本质上是一种将二进制数据转成文本数据的方案。对于非二进制数据，是先将其转换成二进制形式，然后每连续 6 比特（2 的 6 次方 = 64）计算其十进制值，根据该值在上面的索引表中找到对应的字符，最终得到一个文本字符串。

假设我们要对 Hello! 进行 Base64 编码，按照 ASCII 表，其转换过程如下图所示：

可知 Hello! 的 Base64 编码结果为 SGVsbG8h ，原始字符串长度为 6 个字符，编码后长度为 8 个字符，每 3 个原始字符经 Base64 编码成 4 个字符，编码前后长度比 4/3，这个长度比很重要 - 比原始字符串长度短，则需要使用更大的编码字符集，这并不我们想要的；长度比越大，则需要传输越多的字符，传输时间越长。Base64 应用广泛的原因是在字符集大小与长度比之间取得一个较好的平衡，适用于各种场景。

是不是觉得 Base64 编码原理很简单？

但这里需要注意一个点：Base64 编码是每 3 个原始字符编码成 4 个字符，如果原始字符串长度不能被 3 整除，那怎么办？使用 0 值来补充原始字符串。

以 Hello!! 为例，其转换过程为：

注：图表中蓝色背景的二进制 0 值是额外补充的。

Hello!! Base64 编码的结果为 SGVsbG8hIQAA 。最后 2 个零值只是为了 Base64 编码而补充的，在原始字符中并没有对应的字符，那么 Base64 编码结果中的最后两个字符 AA 实际不带有效信息，所以需要特殊处理，以免解码错误。

标准 Base64 编码通常用 = 字符来替换最后的 A，即编码结果为 SGVsbG8hIQ==。因为 = 字符并不在 Base64 编码索引表中，其意义在于结束符号，在 Base64 解码时遇到 = 时即可知道一个 Base64 编码字符串结束。

如果 Base64 编码字符串不会相互拼接再传输，那么最后的 = 也可以省略，解码时如果发现 Base64 编码字符串长度不能被 4 整除，则先补充 = 字符，再解码即可。

解码是对编码的逆向操作，但注意一点：对于最后的两个 = 字符，转换成两个 A 字符，再转成对应的两个 6 比特二进制 0 值，接着转成原始字符之前，需要将最后的两个 6 比特二进制 0 值丢弃，因为它们实际上不携带有效信息。

utf8编码和unicode字符集

总结:

unicode是个字符集, 只是一个符号对应表, 它只规定了符号的二进制代码，却没有规定这个二进制代码应该如何存储
utf8是unicode符号具体的编码方式, 规定了该怎么存储

说到utf8，就不得不说一下unicode了。 Unicode是一个很大的集合，每一个unicode对应一个符号，不管是中文的汉字，英文字符，日文，韩文等等。现在的规模可以容纳100多万个符号。每个符号的编码都不一样，比如，U+0639表示阿拉伯字母 Ain，U+0041表示英语的大写字母A，U+4E25表示汉字“严”。具体的符号对应表，可以查询unicode.org，或者专门的汉字对应表。

需要注意的是，Unicode只是一个符号集，它只规定了符号的二进制代码，却没有规定这个二进制代码应该如何存储。

比如，汉字“严”的unicode是十六进制数4E25，转换成二进制数足足有15位（100111000100101），也就是说这个符号的表示至少需要2个字节。表示其他更大的符号，可能需要3个字节或者4个字节，甚至更多。

这里就有两个严重的问题，第一个问题是：如何才能区别unicode和ascii？计算机怎么知道三个字节表示一个符号，而不是分别表示三个符号呢？第二个问题是：我们已经知道，英文字母只用一个字节表示就够了，如果unicode统一规定，每个符号用三个或四个字节表示，那么每个英文字母前都必然有二到三个字节是0，这对于存储来说是极大的浪费，文本文件的大小会因此大出二三倍，这是无法接受的。

它们造成的结果是：

1）出现了unicode的多种存储方式，也就是说有许多种不同的二进制格式，可以用来表示unicode。

2）unicode在很长一段时间内无法推广，直到互联网的出现。

UTF-8

互联网的普及，强烈要求出现一种统一的编码方式。UTF-8就是在互联网上使用最广的一种unicode的实现方式。其他实现方式还包括UTF-16和UTF-32，不过在互联网上基本不用。重复一遍，这里的关系是，UTF-8是Unicode的实现方式之一。

UTF-8最大的一个特点，就是它是一种变长的编码方式。它可以使用1~4个字节表示一个符号，根据不同的符号而变化字节长度。

UTF-8的编码规则很简单，只有二条：

1）对于单字节的符号，字节的第一位（字节的最高位）设为0，后面7位为这个符号的unicode码。因此对于英语字母，UTF-8编码和ASCII码是相同的。
2）对于n字节的符号（n>1），第一个字节的前n位都设为1，第n+1位设为0，后面字节的前两位一律设为10。剩下的没有提及的二进制位，全部为这个符号的unicode码。

下表总结了编码规则，字母x表示可用编码的位。

Unicode符号范围 UTF-8编码方式(十六进制) | （二进制）

—————+———————————————————————
0000 0000-0000 007F | 0xxxxxxx
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

下面，还是以汉字“严”为例，演示如何实现UTF-8编码：
已知“严”的unicode是4E25（100111000100101），根据上表，可以发现4E25处在第三行的范围内（0000 0800-0000 FFFF），因此“严”的UTF-8编码需要三个字节，即格式是“1110xxxx 10xxxxxx 10xxxxxx”。然后，从“严”的最后一个二进制位开始，依次从后向前填入格式中的x，多出的位补0。这样就得到了，“严”的UTF-8编码是“11100100 10111000 10100101”，转换成十六进制就是E4B8A5。

rpclib源码阅读笔记之浅谈cpp func traits

Posted on 04-18-2021 | In Misc

原文出处

0. 导语

大家好，我是光城，欢迎关注公众号：guangcity。在 STL 编程中，容器和算法是独立设计的，即数据结构和算法是独立设计的，连接容器和算法的桥梁就是迭代器了，迭代器使其独立设计成为可能。如下图所示：

上图给出了 STL 的目标就是要把数据和算法分开，分别对其进行设计，之后通过一种名为 iterator 的东西，把这二者再粘接到一起。

设计模式中，关于 iterator 的描述为：一种能够顺序访问容器中每个元素的方法，使用该方法不能暴露容器内部的表达方式。而类型萃取技术就是为了要解决和 iterator 有关的问题的。

它将范型算法 (find, count, find_if) 用于某个容器中, 最重要的是要给算法提供一个访问容器元素的工具，iterator 就扮演着这个重要的角色。

而在算法中我们可能会定义简单的中间变量或者设定算法的返回变量类型，这时候需要知道迭代器所指元素的类型是什么，但是由于没有 typeof 这类判断类型的函数, 我们无法直接获取，那该如何是好？本文就来具体阐述。

对于迭代器来说就是一种智能指针，因此，它也就拥有了一般指针的所有特点——能够对其进行 * 和 -> 操作。但是在遍历容器的时候，不可避免的要对遍历的容器内部有所了解，所以，干脆把迭代器的开发工作交给容器的设计者好了，如此以来，所有实现细节反而得以封装起来不被使用者看到，这正是为什么每一种 STL 容器都提供有专属迭代器的缘故。

而 Traits 在bits/stl_iterator_base_types.h中：

template<class _Tp>
struct iterator_traits<_Tp*>
{
    typedef ptrdiff_t difference_type;
    typedef typename _Tp::value_type value_type;
    typedef typename _Tp::pointer pointer;
    typedef typename _Tp::reference reference;
    typedef typename _Tp::iterator_category iterator_category;
};

看的一脸懵逼吧，没事，看完本节，入门 STL，哈哈~

1.template 参数推导

首先，在算法中运用迭代器时，很可能会用到其相应型别（associated type）（迭代器所指之物的型别）。假设算法中有必要声明一个变量，以 “迭代器所指对象的型别” 为型别，该怎么办呢？

解决方法是：利用 function template 的参数推导机制。

例如：

如果 T 是某个指向特定对象的指针，那么在 func 中需要指针所指向对象的型别的时候，怎么办呢？这个还比较容易，模板的参数推导机制可以完成任务，

template <class I>
inline
void func(I iter) {
    func_impl(iter, *iter); // 传入iter和iter所指的值，class自动推导
}

通过模板的推导机制，我们轻而易举的或得了指针所指向的对象的类型。

template <class I, class T>
void func_impl(I iter, T t) {
        T tmp; // 这里就是迭代器所指物的类别
        // ... 功能实现
}

int main() {
    int i;
    func(&i);
}

但是，函数的 “template 参数推导机制” 推导的只是参数，无法推导函数的返回值类型。万一需要推导函数的传回值，就无能为力了。因此，我们引出下面的方法。

2. 声明内嵌型别

迭代器所指对象的型别，称之为迭代器的 value type。

尽管在 func_impl 中我们可以把 T 作为函数的返回值，但是问题是用户需要调用的是 func。

template <class I, class T>
T func_impl(I iter, T t) {
        T tmp; // 这里就是迭代器所指物的类别
        // ... 功能实现
}
template <class T>
(*T) func(T t) { // !!!Wrong code
    return func_impl(t, *t); // forward the task to func_impl
}
int main() {
    int i  =10;
    cout<<func(&i)<<endl; // !!! Can’t pass compile
}

如果去编译上述代码，编译失败！

这个问题解决起来也不难，声明内嵌型别似乎是个好主意，这样我们就可以直接获取。只要做一个 iterator，然后在定义的时候为其指向的对象类型制定一个别名，就好了，像下面这样：

template <class T>
struct MyIter {
    typedef T value_type; // 内嵌型别声明
    T* ptr;
    MyIter(T* p = 0) : ptr(p) {}
    T& operator*() const { return *ptr; }
};

template <class I>
typename I::value_type
func(I ite) {
    std::cout << "class version" << std::endl;
    return *ite;
}
int main() {
    // ...
    MyIter<int> ite(new int(8));
    cout << func(ite);    // 输出8
}

很漂亮的解决方案，看上去一切都很完美。但是，实际上还是有问题，因为 func 如果是一个泛型算法，那么它也绝对要接受一个原生指针作为迭代器，但是显然，你无法让下面的代码编译通过：

int *p = new int(5);
cout<<func(p)<<endl; // error

我们的 func 无法支持原生指针，这显然是不能接受的。此时，template partial specialization 就派上了用场。

3. 救世主 Traits

前面也提到了，如果直接使用typename I::value_type，算法就无法接收原生指针，因为原生指针根本就没有 value_type 这个内嵌类型。

因此，我们还需要加入一个中间层对其进行判断，看它是不是原生指针，注意，这就是 traits 技法的妙处所在。

如果我们只使用上面的做法，也就是内嵌 value_type，那么对于没有 value_type 的指针，我们只能对其进行偏特化，这种偏特化是针对可调用函数 func 的偏特化，假如 func 有 100 万行行代码，那么就会造成极大的视觉污染。

（1）函数偏特化

函数偏特化：

template <class T>
struct MyIter {
    typedef T value_type; // 内嵌型别声明
    T* ptr;
    MyIter(T* p = 0) : ptr(p) {}
    T& operator*() const { return *ptr; }
};

template <class I>
typename I::value_type
func(I ite) {
    std::cout << "class version" << std::endl;
    return *ite;
}
template <class I>
I
func(I* ite) {
    std::cout << "pointer version" << std::endl;
    return *ite;
}
template <class I>
I func(const I* ite) {
    std::cout << "const pointer version" << std::endl;
    return *ite;
}
int main() {
    // ...
    MyIter<int> ite(new int(8));
    cout << func(ite)<<endl;
    int *p = new int(52);
    cout<<func(p)<<endl;
    const int k = 3;
    cout<<func(&k)<<endl;
}

输出：

class version
8
pointer version
52
const pointer version
3

（2）加入中间层

在 STL 中 Traits 是什么呢？看下图：

利用一个中间层iterator_traits固定了func的形式，使得重复的代码大量减少，唯一要做的就是稍稍特化一下 iterator_tartis 使其支持 pointer 和 const pointer:)

#include <iostream>

template <class T>
struct MyIter {
    typedef T value_type; // 内嵌型别声明
    T* ptr;
    MyIter(T* p = 0) : ptr(p) {}
    T& operator*() const { return *ptr; }
};
// class type
template <class T>
struct iterator_traits {
    typedef typename T::value_type value_type;
};
// 偏特化1
template <class T>
struct iterator_traits<T*> {
    typedef T value_type;
};
// 偏特化2
template <class T>
struct iterator_traits<const T*> {
    typedef T value_type;
};

template <class I>
typename iterator_traits<I>::value_type
// 首先询问iterator_traits<I>::value_type,如果传递的I为指针,则进入特化版本,iterator_traits直接回答;如果传递进来的I为class type,就去询问T::value_type.
func(I ite) {
    std::cout << "normal version" << std::endl;
    return *ite;
}
int main() {
    // ...
    MyIter<int> ite(new int(8));
    std::cout << func(ite)<<std::endl;
    int *p = new int(52);
    std::cout<<func(p)<<std::endl;
    const int k = 3;
    std::cout<<func(&k)<<std::endl;
}

上述的过程是首先询问iterator_traits<I>::value_type，如果传递的 I 为指针, 则进入特化版本,iterator_traits直接回答T; 如果传递进来的I为class type, 就去询问T::value_type.

上述的通俗解释为算法 (func) 问 iterator_traits(我)，但是 iterator_traits(我)发现手上是指针的时候，就由我来替它回答。如果是 class type，iterator_traits(我)就继续问(他 —T::value_type)。

总结：通过定义内嵌类型，我们获得了知晓 iterator 所指元素类型的方法，通过 traits 技法，我们将函数模板对于原生指针和自定义 iterator 的定义都统一起来，我们使用 traits 技法主要是为了解决原生指针和自定义 iterator 之间的不同所造成的代码冗余，这就是 traits 技法的妙处所在。

学习书籍：

侯捷《 STL 源码剖析》

学习文章：

https://juejin.im/post/5b1a43fb51882513bf1795c6
https://www.cnblogs.com/mangoyuan/p/6446046.html
http://www.cppblog.com/nacci/archive/2005/11/03/911.aspx

服务器开发自我修养专栏-Python精要

Posted on 03-27-2021 | In Self-cultivation

python

mro问题
怎么实现一个协程库?
mock是啥: https://zhuanlan.zhihu.com/p/30380243

import流程

当Python的解释器遇到import语句或者其他上述导入语句时,它会先去查看sys.modules中是否已经有同名模块被导入了,
如果有就直接取来用;没有就去查阅sys.path里面所有已经储存的目录.
- sys.path这个列表初始化的时候,通常包含一些来自外部的库(external libraries)或者是来自操作系统的一些库,当然也会有一些类似于dist-package的标准库在里面.这些目录通常是被按照顺序或者是直接去搜索想要的–如果说他们当中的一个包含有期望的package或者是module,这个package或者是module将会在整个过程结束的时候被直接提取出来保存在sys.modules中(sys.modules是一个模块名:模块对象的字典结构).
- 当然，这个 sys.path 是可以修改的（正如上文提到的一种解决办法）。值得注意的是，如果当前目录包含有和标准库同名的模块，会直接使用当前目录的模块而不是标准模块。
- 当在这些个地址中实在是找不着时,它就会抛出一个ModuleNotFoundError错误.
当我们要导入一个模块（比如 foo ）时，解释器首先会根据命名查找内置模块，如果没有找到，它就会去查找 sys.path 列表中的目录，看目录中是否有 foo.py 。sys.path 的初始值来自于：
- 运行脚本所在的目录（如果打开的是交互式解释器则是当前目录）
- PYTHONPATH 环境变量（类似于 PATH 变量，也是一组目录名组成）
- Python 安装时的默认设置

为啥字符串join比加号连接快

字符串是不可变对象，当用操作符+连接字符串的时候，每执行一次+都会申请一块新的内存，然后复制上一个+操作的结果和本次操作的右操作符到这块内存空间，因此用+连接字符串的时候会涉及好几次内存申请和复制。而join在连接字符串的时候，会先计算需要多大的内存存放结果，然后一次性申请所需内存并将字符串复制过去，这是为什么join的性能优于+的原因。所以在连接字符串数组的时候，我们应考虑优先使用join。

is和==的区别

官方文档中说 is 表示的是对象标示符（object identity），而 == 表示的是相等（equality）。is 的作用是用来检查对象的标示符是否一致，也就是比较两个对象在内存中的地址是否一样，而 == 是用来检查两个对象是否相等。

我们在检查 a is b 的时候，其实相当于检查 id(a) == id(b)。而检查 a == b 的时候，实际是调用了对象 a 的 eq() 方法，a == b 相当于 a.eq(b)。

一般情况下，如果 a is b 返回True的话，即 a 和 b 指向同一块内存地址的话，a == b 也返回True，即 a 和 b 的值也相等。

元类

参考: https://www.liaoxuefeng.com/wiki/1016959663602400/1017592449371072

python元类的使用场景, 比如orm框架, ORM全称“Object Relational Mapping”，即对象-关系映射，就是把关系数据库的一行映射为一个对象，也就是一个类对应一个表，这样，写代码更简单，不用直接操作SQL语句。

type()函数既可以返回一个对象的类型，又可以创建出新的类型，比如，我们可以通过type()函数创建出Hello类，而无需通过class Hello(object)...的定义：

\>>> def fn(self, name='world'): # 先定义函数
...     print('Hello, %s.' % name)
...
>>> Hello = type('Hello', (object,), dict(hello=fn)) # 创建Hello class
>>> h = Hello()
>>> h.hello()
Hello, world.
>>> print(type(Hello))
<class 'type'>
>>> print(type(h))
<class '__main__.Hello'>

要创建一个 class 对象，type()函数依次传入 3 个参数：

class 的名称；
继承的父类集合，注意 Python 支持多重继承，如果只有一个父类，别忘了 tuple 的单元素写法；
class 的方法名称与函数绑定，这里我们把函数fn绑定到方法名hello上。

通过type()函数创建的类和直接写 class 是完全一样的，因为 Python 解释器遇到 class 定义时，仅仅是扫描一下 class 定义的语法，然后调用type()函数创建出 class。

正常情况下，我们都用class Xxx...来定义类，但是，type()函数也允许我们动态创建出类来，也就是说，动态语言本身支持运行期动态创建类，这和静态语言有非常大的不同，要在静态语言运行期创建类，必须构造源代码字符串再调用编译器，或者借助一些工具生成字节码实现，本质上都是动态编译，会非常复杂。

metaclass

除了使用type()动态创建类以外，要控制类的创建行为，还可以使用 metaclass。
metaclass，直译为元类，简单的解释就是：
当我们定义了类以后，就可以根据这个类创建出实例，所以：先定义类，然后创建实例。
但是如果我们想创建出类呢？那就必须根据 metaclass 创建出类，所以：先定义 metaclass，然后创建类。
连接起来就是：先定义 metaclass，就可以创建类，最后创建实例。
所以，metaclass 允许你创建类或者修改类。换句话说，你可以把类看成是 metaclass 创建出来的 “实例”。
我们先看一个简单的例子，这个 metaclass 可以给我们自定义的 MyList 增加一个add方法：
定义ListMetaclass，按照默认习惯，metaclass 的类名总是以 Metaclass 结尾，以便清楚地表示这是一个 metaclass：

class ListMetaclass(type):
    def __new__(cls, name, bases, attrs):
        attrs\['add'\] = lambda self, value: self.append(value)
        return type.__new__(cls, name, bases, attrs)

有了 ListMetaclass，我们在定义类的时候还要指示使用 ListMetaclass 来定制类，传入关键字参数metaclass：

class MyList(list, metaclass=ListMetaclass):
    pass

当我们传入关键字参数metaclass时，魔术就生效了，它指示 Python 解释器在创建MyList时，要通过ListMetaclass.__new__()来创建，在此，我们可以修改类的定义，比如，加上新的方法，然后，返回修改后的定义。

__new__()方法接收到的参数依次是：

当前准备创建的类的对象；
类的名字；
类继承的父类集合；
类的方法集合。

测试一下MyList是否可以调用add()方法：

\>>> L = MyList()
>>> L.add(1)
>> L
\[1\]

而普通的list没有add()方法：

\>>> L2 = list()
>>> L2.add(1)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'list' object has no attribute 'add'

装饰器

def log(func):
    def wrapper(*args, **kw):
        print('call %s():' % func.__name__)
        return func(*args, **kw)
    return wrapper

观察上面的log，因为它是一个decorator，所以接受一个函数作为参数，并返回一个函数。我们要借助Python的@语法，把decorator置于函数的定义处：

@log
def now():
    print('2015-3-25')

调用now()函数，不仅会运行now()函数本身，还会在运行now()函数前打印一行日志：

>>> now()
call now():
2015-3-25

把@log放到now()函数的定义处，相当于执行了语句：
now = log(now)
由于log()是一个decorator，返回一个函数，所以，原来的now()函数仍然存在，只是现在同名的now变量指向了新的函数，于是调用now()将执行新函数，即在log()函数中返回的wrapper()函数。

wrapper()函数的参数定义是(args, *kw)，因此，wrapper()函数可以接受任意参数的调用。在wrapper()函数内，首先打印日志，再紧接着调用原始函数。

如果decorator本身需要传入参数，那就需要编写一个返回decorator的高阶函数，写出来会更复杂。比如，要自定义log的文本：

def log(text):
    def decorator(func):
        def wrapper(*args, **kw):
            print('%s %s():' % (text, func.__name__))
            return func(*args, **kw)
        return wrapper
    return decorator

这个3层嵌套的decorator用法如下：

@log('execute')
def now():
    print('2015-3-25')

执行结果如下：

>>> now()
execute now():
2015-3-25

和两层嵌套的decorator相比，3层嵌套的效果是这样的：
now = log('execute')(now)
我们来剖析上面的语句，首先执行log(‘execute’)，返回的是decorator函数，再调用返回的函数，参数是now函数，返回值最终是wrapper函数。

python命令行参数

-u参数的使用：python命令加上-u（unbuffered）参数后会强制其标准输出也同标准错误一样不通过缓存直接打印到屏幕。
-c参数，支持执行单行命令/脚本。如: python -c "import os;print('hello'),print('world')"

`python -m test_folder/test.py`与`python test_folder/test`有什么不同

桌面的test_folder文件夹下有个test.py

test.py

import sys
print(sys.path)

运行看看:

hulinhong@GIH-D-14531 MINGW64 ~/Desktop
$ python test_folder/test.py
['C:\\Users\\hulinhong\\Desktop\\test_folder', 'C:\\Program Files\\Python37\\python37.zip', 'C:\\Program Files\\Python37\\DLLs', 'C:\\Program Files\\Python37\\lib', 'C:\\Program Files\\Python37', 'C:\\Program Files\\Python37\\lib\\site-packages', 'C:\\Program Files\\Python37\\lib\\site-packages\\redis_py_cluster-2.1.0-py3.7.egg']

hulinhong@GIH-D-14531 MINGW64 ~/Desktop
$ python -m test_folder.test
['C:\\Users\\hulinhong\\Desktop', 'C:\\Program Files\\Python37\\python37.zip', 'C:\\Program Files\\Python37\\DLLs', 'C:\\Program Files\\Python37\\lib', 'C:\\Program Files\\Python37', 'C:\\Program Files\\Python37\\lib\\site-packages', 'C:\\Program Files\\Python37\\lib\\site-packages\\redis_py_cluster-2.1.0-py3.7.egg']

细心的同学会发现，区别就是在第一个路径:

python直接启动是把test.py文件所在的目录放到了sys.path属性中。
模块启动是把你输入命令的目录（也就是当前路径），放到了sys.path属性中

所以就会有下面的情况:

目录结构如下

package/
    __init__.py
    mod1.py
package2/
    __init__.py
    run.py

run.py 内容如下

import sys
from package import mod1
print(sys.path)

如何才能启动run.py文件？

直接启动（失败）

➜  test_import_project git:(master) ✗ python package2/run.py
Traceback (most recent call last):
  File "package2/run.py", line 2, in <module>
    from package import mod1
ImportError: No module named package

以模块方式启动（成功）

➜  test_import_project git:(master) ✗ python -m package2.run
['C:\\Users\\hulinhong\\Desktop',
'/usr/local/Cellar/python/2.7.11/Frameworks/Python.framework/Versions/2.7/lib/python27.zip',
...]

当需要启动的py文件引用了一个模块。你需要注意：在启动的时候需要考虑sys.path中有没有你import的模块的路径！
这个时候，到底是使用直接启动，还是以模块的启动？目的就是把import的那个模块的路径放到sys.path中。你是不是明白了呢？

官方文档参考： http://www.pythondoc.com/pythontutorial3/modules.html

导入一个叫 mod1 的模块时，解释器先在当前目录中搜索名为 mod1.py 的文件。如果没有找到的话，接着会到 sys.path 变量中给出的目录列表中查找。 sys.path 变量的初始值来自如下：

环境变量 PYTHONPATH 表示的目录列表中搜索(这和 shell 变量 PATH 具有一样的语法，即一系列目录名的列表)。
Python 默认安装路径中搜索。
实际上，解释器由 sys.path 变量指定的路径目录搜索模块，该变量初始化时默认包含了输入脚本（或者当前目录）， PYTHONPATH 和安装目录。这样就允许 Python程序了解如何修改或替换模块搜索目录。

在python程序中调用cpp的库创建的线程是否受制于GIL?

首先要理解什么是GIL.
Python 的多线程是真的多线程，只不过在任意时刻，它们中只有一个线程能够取得 GIL 从而被允许执行 Python 代码。其它线程要么等着，要么干别的和 Python 无关的事情（比如等待系统 I/O，或者算点什么东西）。

那如果是通过CPP扩展创建出来的线程，可以摆脱这个限制么？
很简单，不访问 Python 的数据和方法，就和 GIL 没任何关系。如果需要访问 Python，还是需要先取得 GIL.

GIL 是为了保护 Python 数据不被并发访问破坏，所以当你不访问 Python 的数据的时候自然就可以释放（或者不取得）GIL。反过来，如果需要访问 Python 的数据，就一定要取得 GIL 再访问。PyObject 等不是线程安全的。多线程访问任何非线程安全的数据都需要先取得对应的锁。Python 所有的 PyObject 什么的都共享一个锁，它就叫 GIL。

`new` 与 `del` 与 `init`

先来看一个单例模式的实现

class Demo:
    __isinstance = False
    def __new__(cls, *args, **kwargs):
        if not cls.__isinstance:  # 如果被实例化了
            cls.__isinstance = object.__new__(cls)  # 否则实例化
        return cls.__isinstance  # 返回实例化的对象

    def __init__(self, name):
        self.name = name
        print('my name is %s'%(name))
    
    def __del__(self):
        print('886, %s'%(self.name))


d1 = Demo('Alice')
d2 = Demo('Anew')
print(d1)
print(d2)

打印:

my name is Alice
my name is Anew
<__main__.Demo object at 0x000001446604D3C8>
<__main__.Demo object at 0x000001446604D3C8>
886, Anew

__new__ 是负责对当前类进行实例化，并将实例返回，并传给__init__方法，__init__方法中的self就是指代__new__传过来的对象，所以再次强调，__init__是实例化后调用的第一个方法。

__del__在对象销毁时被调用，往往用于清除数据或还原环境等操作，比如在类中的其他普通方法中实现了插入数据库的语句，当对象被销毁时我们需要将数据还原，那么这时可以在__del__方法中实现还原数据库数据的功能。__del__被成为析构方法，同样和C++中的析构方法类似。

python垃圾回收

总体来说，在Python中，主要通过引用计数进行垃圾回收；通过 “标记-清除” 解决容器对象可能产生的循环引用问题；通过 “分代回收” 以空间换时间的方法提高垃圾回收效率。

引用计数
标记清除(Mark and Sweep)
分代回收

标记清除咋弄的

参考: https://zhuanlan.zhihu.com/p/83251959

Python 采用了 “标记-清除”(Mark and Sweep) 算法，解决容器对象可能产生的循环引用问题。(注意，只有容器对象才会产生循环引用的情况，比如列表、字典、用户自定义类的对象、元组等。而像数字，字符串这类简单类型不会出现循环引用。作为一种优化策略，对于只包含简单类型的元组也不在标记清除算法的考虑之列)

跟其名称一样，该算法在进行垃圾回收时分成了两步，分别是：

A）标记阶段，遍历所有的对象，如果是可达的（reachable），也就是还有对象引用它，那么就标记该对象为可达；
B）清除阶段，再次遍历对象，如果发现某个对象没有标记为可达，则就将其回收。

如下图所示，在标记清除算法中，为了追踪容器对象，需要每个容器对象维护两个额外的指针，用来将容器对象组成一个双端链表，指针分别指向前后两个容器对象，方便插入和删除操作。python 解释器 (Cpython) 维护了两个这样的双端链表，一个链表存放着需要被扫描的容器对象，另一个链表存放着临时不可达对象。在图中，这两个链表分别被命名为”Object to Scan”和”Unreachable”。图中例子是这么一个情况：link1,link2,link3 组成了一个引用环，同时 link1 还被一个变量 A(其实这里称为名称 A 更好)引用。link4 自引用，也构成了一个引用环。从图中我们还可以看到，每一个节点除了有一个记录当前引用计数的变量 ref_count 还有一个 gc_ref 变量，这个 gc_ref 是 ref_count 的一个副本，所以初始值为 ref_count 的大小。

gc 启动的时候，会逐个遍历”Object to Scan” 链表中的容器对象，并且将当前对象所引用的所有对象的 gc_ref 减一。(扫描到 link1 的时候，由于 link1 引用了 link2, 所以会将 link2 的 gc_ref 减一，接着扫描 link2, 由于 link2 引用了 link3, 所以会将 link3 的 gc_ref 减一…..) 像这样将”Objects to Scan” 链表中的所有对象考察一遍之后，两个链表中的对象的 ref_count 和 gc_ref 的情况如下图所示。这一步操作就相当于解除了循环引用对引用计数的影响。

接着，gc 会再次扫描所有的容器对象，如果对象的 gc_ref 值为 0，那么这个对象就被标记为 GC_TENTATIVELY_UNREACHABLE，并且被移至”Unreachable” 链表中。下图中的 link3 和 link4 就是这样一种情况。

如果对象的 gc_ref 不为 0，那么这个对象就会被标记为 GC_REACHABLE。同时当 gc 发现有一个节点是可达的，那么他会递归式的将从该节点出发可以到达的所有节点标记为 GC_REACHABLE, 这就是下图中 link2 和 link3 所碰到的情形。

除了将所有可达节点标记为 GC_REACHABLE 之外，如果该节点当前在”Unreachable” 链表中的话，还需要将其移回到”Object to Scan” 链表中，下图就是 link3 移回之后的情形。

第二次遍历的所有对象都遍历完成之后，存在于”Unreachable” 链表中的对象就是真正需要被释放的对象。如上图所示，此时 link4 存在于 Unreachable 链表中，gc 随即释放之。

上面描述的垃圾回收的阶段，会暂停整个应用程序，等待标记清除结束后才会恢复应用程序的运行。

为啥标记清除回收无法回收重写了`del`方法的类对象

Circular references which are garbage are detected when the option cycle detector is enabled (it’s on by default), but can only be cleaned up if there are no Python-level __del__() methods involved.

官方文档中表明启用周期检测器时会检测到垃圾的循环引用（默认情况下它是打开的)，但只有在没有涉及 Python __del__() 方法的情况下才能清除。Python 不知道破坏彼此保持循环引用的对象的安全顺序，因此它则不会为这些方法调用析构函数。简而言之，如果定义了 __del__ 函数，那么在循环引用中Python解释器无法判断析构对象的顺序，因此就不做处理。

分代回收

在循环引用对象的回收中，整个应用程序会被暂停，为了减少应用程序暂停的时间，Python 通过“分代回收”(Generational Collection)以空间换时间的方法提高垃圾回收效率。

分代回收是基于这样的一个统计事实，对于程序，存在一定比例的内存块的生存周期比较短；而剩下的内存块，生存周期会比较长，甚至会从程序开始一直持续到程序结束。生存期较短对象的比例通常在 80%～90% 之间，这种思想简单点说就是：对象存在时间越长，越可能不是垃圾，应该越少去收集。这样在执行标记-清除算法时可以有效减小遍历的对象数，从而提高垃圾回收的速度。

python gc给对象定义了三种世代(0,1,2),每一个新生对象在generation zero中，如果它在一轮gc扫描中活了下来，那么它将被移至generation one,在那里他将较少的被扫描，如果它又活过了一轮gc,它又将被移至generation two，在那里它被扫描的次数将会更少。

gc的扫描在什么时候会被触发呢?答案是当某一世代中被分配的对象与被释放的对象之差达到某一阈值的时候，就会触发gc对某一世代的扫描。值得注意的是当某一世代的扫描被触发的时候，比该世代年轻的世代也会被扫描。也就是说如果世代2的gc扫描被触发了，那么世代0,世代1也将被扫描，如果世代1的gc扫描被触发，世代0也会被扫描。

该阈值可以通过下面两个函数查看和调整:

gc.get_threshold() # (threshold0, threshold1, threshold2).
gc.set_threshold(threshold0[, threshold1[, threshold2]])

下面对set_threshold()中的三个参数threshold0, threshold1, threshold2进行介绍。gc会记录自从上次收集以来新分配的对象数量与释放的对象数量，当两者之差超过threshold0的值时，gc的扫描就会启动，初始的时候只有世代0被检查。如果自从世代1最近一次被检查以来，世代0被检查超过threshold1次，那么对世代1的检查将被触发。相同的，如果自从世代2最近一次被检查以来，世代1被检查超过threshold2次，那么对世代2的检查将被触发。get_threshold()是获取三者的值，默认值为(700,10,10).

基于ucontext实现协程

Posted on 03-17-2021 | In Misc

干货写在前面

协程的概念就不详细介绍了,不清楚的同学可以自己google,windows和unix like系统
本身就提供了协程的支持,windows下叫fiber,unix like系统下叫ucontext.

协程是一种用户态的轻量级线程。本篇主要研究协程的 C/C++ 的实现。
首先我们可以看看有哪些语言已经具备协程语义：

比较重量级的有 C#、erlang、golang*
轻量级有 python、lua、javascript、ruby
还有函数式的 scala、scheme 等。

c/c++ 不直接支持协程语义，但有不少开源的协程库，如：
Protothreads：一个 “蝇量级” C 语言协程库
libco: 来自腾讯的开源协程库 libco 介绍，官网
coroutine: 云风的一个 C 语言同步协程库, 详细信息

目前看到大概有四种实现协程的方式：

第一种：利用 glibc 的 ucontext 组件 (云风的库)
第二种：使用汇编代码来切换上下文 (实现 c 协程)
第三种：利用 C 语言语法 switch-case 的奇淫技巧来实现（Protothreads)
第四种：利用了 C 语言的 setjmp 和 longjmp（一种协程的 C/C++ 实现, 要求函数里面使用 static local 的变量来保存协程内部的数据）

本篇主要使用 ucontext 来实现简单的协程库。

. . .

服务器开发自我修养专栏-分布式系统

Posted on 03-15-2021 | In Self-cultivation

分布式系统

分布式系统的就准备:

CAP理论
BASE理论
分布式事务
分布式锁
限流
熔断
一致性选举算法
主从架构
集群架构
异地多活
负载均衡
分层架构
微服务, 服务治理
…

共识

consensus 准确的翻译是共识，即多个提议者达成共识的过程，例如 Paxos，Raft 就是共识算法，paxos 是一种共识理论，分布式系统是他的场景，一致性是他的目标。

一致性（Consistency）的含义比共识（consensus）要宽泛，一致性指的是多个副本对外呈现的状态。包括顺序一致性、线性一致性、最终一致性等。而共识特指达成一致的过程，但注意，共识并不意味着实现了一致性，一些情况下他是做不到的。

一致性的类别

提到分布式架构就一定绕不开 “一致性” 问题，而 “一致性” 其实又包含了数据一致性和事务一致性两种情况，本节主要讨论数据一致性（事务一致性指 ACID）。复制是导致出现数据一致性问题的唯一原因。

关于强和弱的定义，可以参考剑桥大学的 slide.

Strong consistency – ensures that only consistent state can be seen:
- All replicas return the same value when queried for the attribute of an object * All replicas return the same value when queried for the attribute of an object. This may be achieved at a cost – high latency.
Weak consistency – for when the “fast access” requirement dominates:
- update some replica, e.g. the closest or some designated replica
- the updated replica sends up date messages to all other replicas.
- different replicas can return different values for the queried attribute of the object the value should be returned, or “not known”, with a timestamp
- in the long term all updates must propagate to all replicas …….

一致性的详细分类:

强一致性
强一致性集群中，对任何一个节点发起请求都会得到相同的回复，但可能会产生相对高的延迟
- 线性一致性(Linearizability consistency, 也叫原子一致性, 大多数时候我们说强一致性其实是指线性一致性)
- 顺序一致性(Sequential consistency, 比线性一致性稍弱, 但也算是强一致性的一种)
弱一致性
弱一致性具有更低的响应延迟，但可能会回复过期的数据, 导致各个节点拿到的数据不一致。
- 最终一致性(Eventual consistency)
  - 含义: 系统会保证在一定时间内，能够达到一个数据一致的状态。这里之所以将最终一致性单独提出来，是因为它是弱一致性中非常推崇的一种一致性模型，也是业界在大型分布式系统的数据一致性上比较推崇的模型。
- 因果一致性(Causal consistency)
  - 含义: 如果一系列写入按某个逻辑顺序发生，那么任何人读取这些写入时，会看见它们以正确的逻辑顺序出现。
  - 实现: 一种方案是应用保证将问题和对应的回答写入相同的分区
- 读写一致性:
  - 含义: 它可以保证，如果用户刷新页面，他们总会看到自己刚提交的任何更新。它不会对其他用户的写入做出承诺，其他用户的更新可能稍等才会看到，但它保证用户自己提交的数据能马上被自己看到。
- 单调读:
  - 含义: 如果先前读取到较新的数据，后续读取不会得到更旧的数据.
  - 实现: 实现单调读取的一种方式是确保每个用户总是从同一个节点进行读取（不同的用户可以从不同的节点读取），比如可以基于用户 ID 的哈希值来选择节点，而不是随机选择节点。

线性一致性

etcd 读写都做了线性一致，即 etcd 是标准的强一致性保证。

线性一致性又被称为强一致性、严格一致性、原子一致性。是程序能实现的最高的一致性模型，也是分布式系统用户最期望的一致性。CAP 中的 C 一般就指它
顺序一致性中进程只关心大家认同的顺序一样就行，不需要与全局时钟一致，线性就更严格，从这种偏序（partial order）要达到全序（total order）

要求是：

任何一次读都能读到某个数据的最近一次写的数据。
系统中的所有进程，看到的操作顺序，都与全局时钟下的顺序一致。

以下图讨论,

B1 看到 x 的新值，C1 反而看到的是旧值。即对用户来说，x 的值发生了回跳。

在线性一致的系统中，如果 B1 看到的 x 值为 1，则 C1 看到的值也一定为 1。任何操作在该系统生效的时刻都对应时间轴上的一个点。如果我们把这些时刻连接起来，如下图中紫线所示，则这条线会一直沿时间轴向前，不会反向回跳。所以任何操作都需要互相比较决定，谁发生在前，谁发生在后。例如 B1 发生在 A0 前，C1 发生在 A0 后。而在前面顺序一致性模型中，我们无法比较诸如 B1 和 A0 的先后关系。

顺序一致性

举例说明1

下面的图满足了顺序一致，但不满足线性一致。

x 和 y 的初始值为 0
Write(x,4) 代表写入 x=4，Read(y,2) 为读取 y =2

从图上看，进程 P1，P2 的一致性并没有冲突。因为从这两个进程的角度来看，顺序应该是这样的：

Write(y,2), Read(x,0), Write(x,4), Read(y,2)

这个顺序对于两个进程内部的读写顺序都是合理的，只是这个顺序与全局时钟下看到的顺序并不一样。在全局时钟的观点来看，P2 进程对变量 X 的读操作在 P1 进程对变量 X 的写操作之后，然而 P2 读出来的却是旧的数据 0

举例说明2

假设我们有个分布式 KV 系统，以下是四个进程对其的操作顺序和结果:
-- 表示持续的时间，因为一次写入或者读取，客户端从发起到响应是有时间的，发起早的客户端，不一定拿到数据就早，有可能因为网络延迟反而会更晚。
情况 1：

A: --W(x,1)----------------------
B:  --W(x,2)----------------------
C:                      -R(x,1)-   --R(x,2)-
D:                 -R(x,1)-      --R(x,2)--

情况 2：

A: --W(x,1)----------------------
B:  --W(x,2)----------------------
C:                      -R(x,2)-   --R(x,1)-
D:                 -R(x,2)-      --R(x,1)--

上面情况 1 和 2 都是满足顺序一致性的，C 和 D 拿的顺序都是 1-2，或 2-1，只要 CD 的顺序一致，就是满足顺序一致性。只是从全局看来，情况 1 更真实，情况 2 就显得” 错误 “了，因为情况 2 是这样的顺序

B W(x,2) -> A W(x,1) -> C R(x,2) -> D R(x,2) -> C R(x,1) -> D R(x,1)

不过一致性不保证正确性，所以这仍然是一个顺序一致。再加一种情况 3：
情况 3：

A: --W(x,1)----------------------
B:  --W(x,2)----------------------
C:                      -R(x,2)-   --R(x,1)-
D:                 -R(x,1)-      --R(x,2)--

情况 3 就不属于顺序一致了，因为 C 和 D 两个进程的读取顺序不同了。

举例说明3

这也是顺序一致的, 但是可能不满足产品经理要求.

从时间轴上可以看到，B0 发生在 A0 之前，读取到的 x 值为 0。B2 发生在 A0 之后，读取到的 x 值为 1。而读操作 B1，C0，C1 与写操作 A0 在时间轴上有重叠，因此他们可能读取到旧的值 0，也可能读取到新的值 1。注意，C1 发生在 B1 之后（二者在时间轴上没有重叠），但是 B1 看到 x 的新值，C1 反而看到的是旧值。即对用户来说，x 的值发生了回跳。

CAP理论

一个分布式系统不可能同时满足以下三个基本需求，最多只能同时满足其中两项:

一致性（C：Consistency, CAP的C指的是强一致性）
在分布式环境下，一致性是指数据在多个副本之间能否保持一致的特性。在一致性的需求下，当一个系统在数据一致的状态下执行更新操作后，应该保证系统的数据仍然处于一致的状态。

对于一个将数据副本分布在不同分布式节点上的系统来说，如果对第一个节点的数据进行了更新操作并且更新成功后，却没有使得第二个节点上的数据得到相应的更新，于是在对第二个节点的数据进行读取操作时，获取的依然是老数据（或称为脏数据），这就是典型的分布式数据不一致的情况。在分布式系统中，如果能够做到针对一个数据项的更新操作执行成功后，所有的用户都可以读取到其最新的值，那么这样的系统就被认为具有强一致性。
可用性（A：Availability）
可用性是指系统提供的服务必须一直处于可用的状态，对于用户的每一个操作请求总是能够在有限的时间内返回结果。这里的重点是 “有限时间内” 和 “返回结果”。

“有限时间内” 是指，对于用户的一个操作请求，系统必须能够在指定的时间内返回对应的处理结果，如果超过了这个时间范围，那么系统就被认为是不可用的。另外，”有限的时间内” 是指系统设计之初就设计好的运行指标，通常不同系统之间有很大的不同，无论如何，对于用户请求，系统必须存在一个合理的响应时间，否则用户便会对系统感到失望。

“返回结果” 是可用性的另一个非常重要的指标，它要求系统在完成对用户请求的处理后，返回一个正常的响应结果。正常的响应结果通常能够明确地反映出队请求的处理结果，即成功或失败，而不是一个让用户感到困惑的返回结果。
分区容错性（P：Partition tolerance）
系统应该能持续提供服务，即使系统内部有消息丢失（分区）。

网络分区是指在分布式系统中，不同的节点分布在不同的子网络（机房或异地网络）中，由于一些特殊的原因导致这些子网络出现网络不连通的状况，但各个子网络的内部网络是正常的，从而导致整个系统的网络环境被切分成了若干个孤立的区域。需要注意的是，组成一个分布式系统的每个节点的加入与退出都可以看作是一个特殊的网络分区。

cap通俗而精准的解释

一个分布式系统里面，节点组成的网络本来应该是连通的。然而可能因为一些故障，使得有些节点之间不连通了，整个网络就分成了几块区域。数据就散布在了这些不连通的区域中。这就叫分区。

当你一个数据项只在一个节点中保存，那么分区出现后，和这个节点不连通的部分就访问不到这个数据了。这时分区就是无法容忍的。

提高分区容忍性的办法就是一个数据项复制到多个节点上，那么出现分区之后，这一数据项就可能分布到各个区里。容忍性就提高了。

然而，要把数据复制到多个节点，就会带来一致性的问题，就是多个节点上面的数据可能是不一致的。要保证一致，每次写操作就都要等待全部节点写成功，而这等待又会带来可用性的问题。总的来说就是，数据存在的节点越多，分区容忍性越高，但要复制更新的数据就越多，一致性就越难保证。为了保证一致性，更新所有节点数据所需要的时间就越长，可用性就会降低。

cap的一些组合例子

既然一个分布式系统无法同时满足一致性、可用性、分区容错性三个特点，所以我们就需要抛弃一个：

选择	说明
CA	放弃分区容错性，加强一致性和可用性，其实就是传统的单机数据库的选择
AP	放弃一致性（这里说的一致性是强一致性），追求分区容错性和可用性，这是很多分布式系统设计时的选择，例如很多 NoSQL 系统就是如此
CP	放弃可用性，追求一致性和分区容错性，基本不会选择，网络问题会直接让整个系统不可用, 例如 zookeeper和 etcd都是cp的

需要明确的一点是，对于一个分布式系统而言，分区容错性是一个最基本的要求。因为既然是一个分布式系统，那么分布式系统中的组件必然需要被部署到不同的节点，否则也就无所谓分布式系统了，因此必然出现子网络。而对于分布式系统而言，网络问题又是一个必定会出现的异常情况，因此分区容错性也就成为了一个分布式系统必然需要面对和解决的问题。因此系统架构师往往需要把精力花在如何根据业务特点在 C（一致性）和 A（可用性）之间寻求平衡。

BASE 理论

BASE 是

Basically Available（基本可用）
Soft state（软状态, 即中间状态)
Eventually consistent（最终一致性）

三个短语的缩写。BASE 理论是对 CAP 中一致性和可用性权衡的结果，其来源于对大规模互联网系统分布式实践的总结，是基于 CAP 定理逐步演化而来的。BASE 理论的核心思想是：即使无法做到强一致性，但每个应用都可以根据自身业务特点，采用适当的方式来使系统达到最终一致性。接下来看一下 BASE 中的三要素：

基本可用
基本可用是指分布式系统在出现不可预知故障的时候，允许损失部分可用性。注意，这绝不等价于系统不可用。比如：
- 响应时间上的损失。正常情况下，一个在线搜索引擎需要在 0.5 秒之内返回给用户相应的查询结果，但由于出现故障，查询结果的响应时间增加了 1~2 秒
- 系统功能上的损失：正常情况下，在一个电子商务网站上进行购物的时候，消费者几乎能够顺利完成每一笔订单，但是在一些节日大促购物高峰的时候，由于消费者的购物行为激增，为了保护购物系统的稳定性，部分消费者可能会被引导到一个降级页面。
软状态
软状态指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。
最终一致性
最终一致性强调的是所有的数据副本，在经过一段时间的同步之后，最终都能够达到一个一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性。

总的来说，BASE 理论面向的是大型高可用可扩展的分布式系统，和传统的事物 ACID 特性是相反的，它完全不同于 ACID 的强一致性模型，而是通过牺牲强一致性来获得可用性，并允许数据在一段时间内是不一致的，但最终达到一致状态。但同时，在实际的分布式场景中，不同业务单元和组件对数据一致性的要求是不同的，因此在具体的分布式系统架构设计过程中，ACID 特性和 BASE 理论往往又会结合在一起。

服务治理

服务治理主要包括:

服务注册发现
限流
监控
网关
负载均衡
日志采集
链路追踪

详细如下图:

分布式锁

主要有:

etcd/zookeeper(严谨)
redis(遭到质疑, 极限情况有可能有问题, 但因为性能较高且极限情况不容易发生, 也有人用)

分布式锁过期时间到了但业务没执行完怎么办

注册一个定时任务，每隔一定时间就去延长锁超时时间

基于etcd的分布式锁

因为 etcd 使用 Raft 算法保持了数据的强一致性，某次操作存储到集群中的值必然是全局一致的，所以很容易实现分布式锁。锁服务有两种使用方式，一是保持独占，二是控制时序。

保持独占即所有获取锁的用户最终只有一个可以得到。etcd 为此提供了一套实现分布式锁原子操作 CAS（CompareAndSwap）的 API。通过设置prevExist值，可以保证在多个节点同时去创建某个目录时，只有一个成功。而创建成功的用户就可以认为是获得了锁。

基于redis的分布式锁

利用setnx+expire命令 (错误的做法): setnx和expire是分开的两步操作，不具有原子性
使用Lua脚本（包含setnx和expire两条指令）
使用 set key value [EX seconds][PX milliseconds][NX|XX] 命令 (正确做法, 接下来介绍这种)

Redis 在 2.6.12 版本开始，为 SET 命令增加一系列选项：

SET key value\[EX seconds\]\[PX milliseconds\]\[NX|XX\]

EX seconds: 设定过期时间，单位为秒
PX milliseconds: 设定过期时间，单位为毫秒
NX: 仅当 key 不存在时设置值
XX: 仅当 key 存在时设置值

value 必须要具有唯一性，我们可以用 UUID 来做，设置随机字符串保证唯一性，至于为什么要保证唯一性？假如 value 不是随机字符串，而是一个固定值，那么就可能存在下面的问题：

1. 客户端 1 获取锁成功
2. 客户端 1 在某个操作上阻塞了太长时间
3. 设置的 key 过期了，锁自动释放了
4. 客户端 2 获取到了对应同一个资源的锁
5. 客户端 1 从阻塞中恢复过来，因为 value 值一样，所以执行释放锁操作时就会释放掉客户端 2 持有的锁，这样就会造成问题

所以通常来说，在释放锁时，我们需要对 value 进行验证

释放锁时需要验证 value 值，也就是说我们在获取锁的时候需要设置一个 value，不能直接用 del key 这种粗暴的方式，因为直接 del key 任何客户端都可以进行解锁了，所以解锁时，我们需要判断锁是否是自己的，基于 value 值来判断, 这里使用 Lua 脚本的方式，尽量保证原子性。

致命缺陷:
使用 set key value [EX seconds][PX milliseconds][NX|XX] 命令看上去很 OK，实际上在有 Redis 主从结构的时候也会出现问题，比如说 A 客户端在 Redis 的 master 节点上拿到了锁，但是这个加锁的 key 还没有同步到 slave 节点，master 故障，发生故障转移，一个 slave 节点升级为 master 节点，B 客户端也可以获取同个 key 的锁，但客户端 A 也已经拿到锁了，这就导致多个客户端都拿到锁。

RedLock

参考: https://zhuanlan.zhihu.com/p/100140241#RedLock

使用了多个 Redis 实例来实现分布式锁，这是为了保证在发生单点故障时仍然可用。

尝试从 N 个互相独立 Redis 实例获取锁；
计算获取锁消耗的时间，只有时间小于锁的过期时间，并且从大多数（N / 2 + 1）实例上获取了锁，才认为获取锁成功；
如果获取锁失败，就到每个实例上释放锁

分布式锁的高并发优化

先说一个超卖问题的情景, 假设订单系统部署两台机器上，不同的用户都要同时买10台iphone，分别发了一个请求给订单系统。
接着每个订单系统实例都去数据库里查了一下，当前iphone库存是12台。
俩大兄弟一看，乐了，12台库存大于了要买的10台数量啊！
于是乎，每个订单系统实例都发送SQL到数据库里下单，然后扣减了10个库存，其中一个将库存从12台扣减为2台，另外一个将库存从2台扣减为-8台。
现在完了，库存出现了负数！泪奔啊，没有20台iphone发给两个用户啊！这可如何是好。

用分布式锁如何解决库存超卖问题: 只有一个订单系统实例可以成功加分布式锁，然后只有他一个实例可以查库存、判断库存是否充足、下单扣减库存，接着释放锁。
释放锁之后，另外一个订单系统实例才能加锁，接着查库存，一下发现库存只有2台了，库存不足，无法购买，下单失败。不会将库存扣减为-8的。

分布式锁的方案在高并发场景下有什么问题？ 分布式锁一旦加了之后，对同一个商品的下单请求，会导致所有客户端都必须对同一个商品的库存锁key进行加锁。比如，对iphone这个商品的下单，都必对“iphone_stock”这个锁key来加锁。这样会导致对同一个商品的下单请求，就必须串行化，一个接一个的处理,
假设加锁之后，释放锁之前，查库存 -> 创建订单 -> 扣减库存，这个过程性能很高吧，算他全过程20毫秒，这应该不错了。那么1秒是1000毫秒，只能容纳50个对这个商品的请求依次串行完成处理。效率低下.

假如下单时，用分布式锁来防止库存超卖，但是是每秒上千订单的高并发场景，如何对分布式锁进行高并发优化来应对这个场景？
解决方案: 分段加锁

其实说出来也很简单，相信很多人看过java里的ConcurrentHashMap的源码和底层原理，应该知道里面的核心思路，就是分段加锁！

在某些情况下我们可以将锁分解技术进一步扩展为一组独立对象上的锁进行分解，这成为分段锁。其实说的简单一点就是：容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率，这就是ConcurrentHashMap所使用的锁分段技术，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

比如：在ConcurrentHashMap中使用了一个包含16个锁的数组，每个锁保护所有散列桶的1/16，其中第N个散列桶由第（N mod 16）个锁来保护。假设使用合理的散列算法使关键字能够均匀的分部，那么这大约能使对锁的请求减少到越来的1/16。也正是这项技术使得ConcurrentHashMap支持多达16个并发的写入线程。

假如你现在iphone有1000个库存，那么你完全可以给拆成20个库存段，要是你愿意，可以在数据库的表里建20个库存字段，比如stock_01，stock_02，类似这样的，也可以在redis之类的地方放20个库存key。
总之，就是把你的1000件库存给他拆开，每个库存段是50件库存，比如stock_01对应50件库存，stock_02对应50件库存。
接着，每秒1000个请求过来了，好！此时其实可以是自己写一个简单的随机算法，每个请求都是随机在20个分段库存里，选择一个进行加锁。
这样就好了，同时可以有最多20个下单请求一起执行，每个下单请求锁了一个库存分段，然后在业务逻辑里面，就对数据库或者是Redis中的那个分段库存进行操作即可，包括查库存 -> 判断库存是否充足 -> 扣减库存。

有一个坑大家一定要注意：如果某个下单请求，咔嚓加锁，然后发现这个分段库存里的库存不足了，此时咋办？
这时你得自动释放锁，然后立马换下一个分段库存，再次尝试加锁后尝试处理。这个过程一定要实现。

分布式事务解决方案(本文这些都不好, 现在一般用Saga)

参考:

事务有两种:

刚性事务：遵循ACID原则，强一致性。
柔性事务：遵循BASE理论，最终一致性；与刚性事务不同，柔性事务允许一定时间内，不同节点的数据不一致，但要求最终一致。

二阶段提交2PC

大致的流程：

第一阶段（prepare）：事务管理器向所有本地资源管理器发起请求，询问是否是 ready 状态，所有参与者都将本事务能否成功的信息反馈发给协调者；
第二阶段 (commit/rollback)：事务管理器根据所有本地资源管理器的反馈，通知所有本地资源管理器，步调一致地在所有分支上提交或者回滚。

缺点:

同步阻塞：当参与事务者存在占用公共资源的情况，其中一个占用了资源，其他事务参与者就只能阻塞等待资源释放，处于阻塞状态。
单点故障：一旦事务管理器出现故障，整个系统不可用
数据不一致：在阶段二，如果事务管理器只发送了部分 commit 消息，此时网络发生异常，那么只有部分参与者接收到 commit 消息，也就是说只有部分参与者提交了事务，使得系统数据不一致。
不确定性：当协事务管理器发送 commit 之后，并且此时只有一个参与者收到了 commit，那么当该参与者与事务管理器同时宕机之后，重新选举的事务管理器无法确定该条消息是否提交成功。

实战:
目前支付宝使用两阶段提交思想实现了分布式事务服务 (Distributed Transaction Service, DTS) ，它是一个分布式事务框架，用来保障在大规模分布式环境下事务的最终一致性。具体可参考支付宝官方文档：https://tech.antfin.com/docs/2/46887

TCC

关于 TCC（Try-Confirm-Cancel）的概念，最早是由 Pat Helland 于 2007 年发表的一篇名为《Life beyond Distributed Transactions:an Apostate’s Opinion》的论文提出。 TCC 事务机制相比于上面介绍的 XA，解决了其几个缺点：

解决了协调者单点，由主业务方发起并完成这个业务活动。业务活动管理器也变成多点，引入集群。
同步阻塞：引入超时，超时后进行补偿，并且不会锁定整个资源，将资源转换为业务逻辑形式，粒度变小。
数据一致性，有了补偿机制之后，由业务活动管理器控制一致性

TCC(Try Confirm Cancel)

Try 阶段：尝试执行，完成所有业务检查（一致性）, 预留必须业务资源（准隔离性）
Confirm 阶段：确认执行真正执行业务，不作任何业务检查，只使用 Try 阶段预留的业务资源，Confirm 操作满足幂等性。要求具备幂等设计，Confirm 失败后需要进行重试。
Cancel 阶段：取消执行，释放 Try 阶段预留的业务资源 Cancel 操作满足幂等性 Cancel 阶段的异常和 Confirm 阶段异常处理方案基本上一致。

在 Try 阶段，是对业务系统进行检查及资源预览，比如订单和存储操作，需要检查库存剩余数量是否够用，并进行预留，预留操作的话就是新建一个可用库存数量字段，Try 阶段操作是对这个可用库存数量进行操作。
基于 TCC 实现分布式事务，会将原来只需要一个接口就可以实现的逻辑拆分为 Try、Confirm、Cancel 三个接口，所以代码实现复杂度相对较高。

缺点:
TCC 需要事务接口提供 try, confirm, cancel 三个接口，提高了编程的复杂性。依赖于业务方来配合提供这样的接口，推行难度大，所以一般不推荐使用这种方式。

实战:
一般来说和钱相关的支付、交易等相关的场景，也可以用TCC，严格严格保证分布式事务要么全部成功，要么全部自动回滚，严格保证资金的正确性!

本地消息表

本地消息表这个方案最初是 ebay 架构师 Dan Pritchett 在 2008 年发表给 ACM 的文章。该方案中会有消息生产者与消费者两个角色，假设系统 A 是消息生产者，系统 B 是消息消费者，其大致流程如下：

当系统 A 被其他系统调用发生数据库表更操作，首先会更新数据库的业务表，其次会往相同数据库的消息表中插入一条数据，两个操作发生在同一个事务中, 如果本步骤发生操作失败, 则直接事务回滚
系统 A 的脚本定期轮询本地消息往 mq 中写入一条消息，如果消息发送失败会进行重试
系统 B 消费 mq 中的消息，并处理业务逻辑。如果本地事务处理失败，会在继续消费 mq 中的消息进行重试，如果业务上的失败，可以通知系统 A 进行回滚操作

本地消息表实现的条件：

消费者与生成者的接口都要支持幂等
生产者需要额外的创建消息表
需要提供补偿逻辑，如果消费者业务失败，需要生产者支持回滚操作

此方案的核心是将需要分布式处理的任务通过消息日志的方式来异步执行。消息日志可以存储到本地文本、数据库或消息队列，再通过业务规则自动或人工发起重试。人工重试更多的是应用于支付场景，通过对账系统对事后问题的处理。

缺点:
最大的问题就在于严重依赖于数据库的消息表来管理事务,这个会导致高并发场景无力,难以扩展,一般很少用

实战:
跨行转账可通过该方案实现。
用户 A 向用户 B 发起转账，首先系统会扣掉用户 A 账户中的金额，将该转账消息写入消息表中，如果事务执行失败则转账失败，如果转账成功，系统中会有定时轮询消息表，往 mq 中写入转账消息，失败重试。mq 消息会被实时消费并往用户 B 中账户增加转账金额，执行失败会不断重试。

小米海外商城用户订单数据状态变更，会将变更状态记录消息表中，脚本将订单状态消息写入 mq，最终消费 mq 给用户发送邮件、短信、push 等。

可靠消息最终一致性

大致流程如下：

A 系统先向 mq 发送一条 prepare 消息，如果 prepare 消息发送失败，则直接取消操作
如果消息发送成功，则执行本地事务
如果本地事务执行成功，则向 mq 发送一条 confirm 消息，如果发送失败，则发送回滚消息
B 系统定期消费 mq 中的 confirm 消息，执行本地事务，并发送 ack 消息。如果 B 系统中的本地事务失败，会一直不断重试，如果是业务失败，会向 A 系统发起回滚请求
mq 会定期轮询所有 prepared 消息调用系统 A 提供的接口查询消息的处理情况，如果该 prepare 消息本地事务处理成功，则重新发送 confirm 消息，否则直接回滚该消息

该方案与本地消息最大的不同是去掉了本地消息表，其次本地消息表依赖消息表重试写入 mq 这一步由本方案中的轮询 prepare 消息状态来重试或者回滚该消息替代。其实现条件与容错方案基本一致。

实战:
目前市面上实现该方案的只有阿里的 RocketMq。

尽最大努力通知

最大努力通知其实就是定期校对, 是最简单的一种柔性事务，适用于一些最终一致性时间敏感度低的业务，且被动方处理结果不影响主动方的处理结果。

业务活动的主动方，在完成业务处理之后，向业务活动的被动方发送消息，允许消息丢失。主动方可以设置时间阶梯型通知规则，在通知失败后按规则重复通知，直到通知N次后不再通知。主动方提供校对查询接口给被动方按需校对查询，用于恢复丢失的业务消息。业务活动的被动方如果正常接收了数据，就正常返回响应，并结束事务。如果被动方没有正常接收，根据定时策略，向业务活动主动方查询，恢复丢失的业务消息

最大努力通知方案的特点:

用到的服务模式：可查询操作、幂等操作。
被动方的处理结果不影响主动方的处理结果；适用于对业务最终一致性的时间敏感度低的系统, 比如适合跨企业的系统间的操作，或者企业内部比较独立的系统间的操作，比如银行通知、商户通知等；

这个方案的大致意思就是：

系统 A 本地事务执行完之后，发送个消息到 MQ；
会有个专门消费 MQ 的服务 notify_service(即最大努力通知服务) ，这个服务会消费 MQ 并调用系统 B 的接口；
要是系统 B 执行成功就 ok 了；要是系统 B 执行失败了，那么 notify_service (即最大努力通知服务)就定时尝试重新调用系统 B, 反复 N 次，最后还是不行就放弃。

实战:
小米海外商城目前除了支付回调外，最常用的场景是订单数据同步。例如系统 A、B 进行数据同步，当系统 A 发生订单数据变更，先将数据变更消息写入小米 notify 系统（作用等同 mq），然后 notify 系统异步处理该消息来调用系统 B 提供的接口并进行重试到最大次数。

负载均衡算法有哪些

轮询法
　　将请求按顺序轮流地分配到后端服务器上，它均衡地对待后端的每一台服务器，而不关心服务器实际的连接数和当前的系统负载。
随机法
通过系统的随机算法，根据后端服务器的列表大小值来随机选取其中的一台服务器进行访问。由概率统计理论可以得知，随着客户端调用服务端的次数增多，
其实际效果越来越接近于平均分配调用量到后端的每一台服务器，也就是轮询的结果。
源地址哈希法
源地址哈希的思想是根据获取客户端的 IP 地址，通过哈希函数计算得到的一个数值，用该数值对服务器列表的大小进行取模运算，得到的结果便是客服端要访问服务器的序号。采用源地址哈希法进行负载均衡，同一 IP 地址的客户端，当后端服务器列表不变时，它每次都会映射到同一台后端服务器进行访问。
加权轮询法
　　不同的后端服务器可能机器的配置和当前系统的负载并不相同，因此它们的抗压能力也不相同。给配置高、负载低的机器配置更高的权重，让其处理更多的请；而配置低、负载高的机器，给其分配较低的权重，降低其系统负载，加权轮询能很好地处理这一问题，并将请求顺序且按照权重分配到后端。加权轮询算法的结果，就是要生成一个服务器序列。每当有请求到来时，就依次从该序列中取出下一个服务器用于处理该请求。比如针对c权重4, b权重2, a权重1的例子，加权轮询算法会生成序列{c, c, b, c, a, b, c}也有可能是{a, a, a, a, a, b, c}, 有可能不均匀, 前五个请求都会分配给服务器a。在Nginx源码中，实现了一种叫做平滑的加权轮询（smooth weighted round-robin balancing）的算法，它生成的序列更加均匀。比如前面的例子，它生成的序列为{ a, a, b, a, c, a, a}，转发给后端a的5个请求现在分散开来，不再是连续的。这样，每收到7个客户端的请求，会把其中的1个转发给后端a，把其中的2个转发给后端b，把其中的4个转发给后端c。收到的第8个请求，重新从该序列的头部开始轮询。
- 普通加权轮询法
- 平滑加权轮询法
加权随机法
与加权轮询法一样，加权随机法也根据后端机器的配置，系统的负载分配不同的权重。不同的是，它是按照权重随机请求后端服务器，而非顺序。
最小连接数法
最小连接数算法比较灵活和智能，由于后端服务器的配置不尽相同，对于请求的处理有快有慢，它是根据后端服务器当前的连接情况，动态地选取其中当前积压连接数最少的一台服务器来处理当前的请求，尽可能地提高后端服务的利用效率，将负责合理地分流到每一台服务器。

负载均衡的平滑加权轮询算法怎么实现

当我们需要把一份数据发送到一个Set中的任意机器的时候，很容易想到的一个问题是，如何挑Set中的机器作为数据的接收方？显然算法需要符合以下要求：

支持加权，以便在机器故障时可以降低其权重
在加权的前提下，尽可能地把请求平摊到每台机器上

第一点很好理解，而第二点的意思是，比如说我们现在有a, b, c三个选择，权重分别是5, 1, 1，我们希望输出的结果是类似于a, a, b, a, c, a, a，而不是a, a, a, a, a, b, c。

从Github上面可以看到，Nginx以前也是使用和LVS类似的算法，并在某一次提交中修改为当前的算法，该算法大致思想如下：

Upstream: smooth weighted round-robin balancing.

For edge case weights like { 5, 1, 1 } we now produce { a, a, b, a, c, a, a }
sequence instead of { c, b, a, a, a, a, a } produced previously.

Algorithm is as follows: on each peer selection we increase current_weight
of each eligible peer by its weight, select peer with greatest current_weight
and reduce its current_weight by total number of weight points distributed
among peers.

In case of { 5, 1, 1 } weights this gives the following sequence of
current_weight's:

     a  b  c
     0  0  0  (initial state)

     5  1  1  (a selected)
    -2  1  1

     3  2  2  (a selected)
    -4  2  2

     1  3  3  (b selected)
     1 -4  3

     6 -3  4  (a selected)
    -1 -3  4

     4 -2  5  (c selected)
     4 -2 -2

     9 -1 -1  (a selected)
     2 -1 -1

     7  0  0  (a selected)
     0  0  0

该算法除了有权重weight，还引入了另一个变量current_weight，在每一次遍历中会把current_weight加上weight的值，并选择current_weight最大的元素，对于被选择的元素，再把current_weight减去所有权重之和。

假设有 N 台服务器 S = {S0, S1, S2, …, Sn}，默认权重为 W = {W0, W1, W2, …, Wn}，当前权重为 CW = {CW0, CW1, CW2, …, CWn}。在该算法中有两个权重，默认权重表示服务器的原始权重，当前权重表示每次访问后重新计算的权重，当前权重的出初始值为默认权重值，当前权重值最大的服务器为 maxWeightServer，所有默认权重之和为 weightSum，服务器列表为 serverList，算法可以描述为：

找出当前权重值最大的服务器 maxWeightServer；
计算 {W0, W1, W2, …, Wn} 之和 weightSum；
将 maxWeightServer.CW = maxWeightServer.CW - weightSum；
重新计算 {S0, S1, S2, …, Sn} 的当前权重 CW，计算公式为 Sn.CW = Sn.CW + Sn.Wn
返回 maxWeightServer

服务发现是怎么实现的

参考

我们可以考虑用etcd来做,
服务发现要解决的也是分布式系统中最常见的问题之一，即在同一个分布式集群中的进程或服务，要如何才能找到对方并建立连接。本质上来说，服务发现就是想要了解集群中是否有进程在监听 udp 或 tcp 端口，并且通过名字就可以查找和连接。要解决服务发现的问题，需要有下面三大支柱，缺一不可。

一个强一致性、高可用的服务存储目录。基于 Raft 算法的 etcd 天生就是这样一个强一致性高可用的服务存储目录。
一种提供方的注册服务。提供方可以在 etcd 中注册服务，并且对注册的服务设置key TTL，定时保持服务的心跳以达到监控健康状态的效果, 比如每隔 30s 发送一次心跳设置一下这个key使代表该机器存活的节点继续存在，否则当etcd 没有检测到心跳这个key的ttl到了过期了就会把这个键值对删了
需求方可以即时更新提供方服务状态的机制.需求方通过watch机制监听自己需要用到的提供方信息的改动，提供方相关信息有变动的时候需求方就会收到消息,在接收到信息变动的时候立即从etcd获取相应最新的信息即可, 实现方式通常是这样：不同系统都在 etcd 上对同一个目录进行注册，同时设置 Watcher 观测该目录的变化（如果对子目录的变化也有需要，可以设置递归模式），当某个系统更新了 etcd 的目录，那么设置了 Watcher 的系统就会收到通知，并作出相应处理。

下面我们来看服务发现对应的具体场景。
微服务协同工作架构中，服务动态添加。随着 Docker 容器的流行，多种微服务共同协作，构成一个相对功能强大的架构的案例越来越多。透明化的动态添加这些服务的需求也日益强烈。通过服务发现机制，在 etcd 中注册某个服务名字的目录，在该目录下存储可用的服务节点的 IP。在使用服务的过程中，只要从服务目录下查找可用的服务节点去使用即可。
微服务协同工作

熔断是怎么实现的

什么是服务熔断呢？服务熔断：当下游的服务因为某种原因突然变得不可用或响应过慢，上游服务为了保证自己整体服务的可用性，不再继续调用目标服务，直接返回，快速释放资源。如果目标服务情况好转则恢复调用。需要说明的是熔断其实是一个框架级的处理，那么这套熔断机制的设计，基本上业内用的是断路器模式:

最开始处于closed状态，一旦检测到错误到达一定阈值，便转为open状态；
这时候会有个 reset timeout，到了这个时间了，会转移到half open状态；
尝试放行一部分请求到后端，一旦检测成功便回归到closed状态，即恢复服务；

业内目前流行的熔断器很多，例如阿里出的 Sentinel, 以及最多人使用的 Hystrix 在 Hystrix 中，对应配置如下

//滑动窗口的大小，默认为20
circuitBreaker.requestVolumeThreshold 
//过多长时间，熔断器再次检测是否开启，默认为5000，即5s钟
circuitBreaker.sleepWindowInMilliseconds 
//错误率，默认50%
circuitBreaker.errorThresholdPercentage

每当 20 个请求中，有 50% 失败时，熔断器就会打开，此时再调用此服务，将会直接返回失败，不再调远程服务。直到 5s 钟之后，重新检测该触发条件，判断是否把熔断器关闭，或者继续打开。
这些属于框架层级的实现，我们只要实现对应接口就好！

服务降级

降级的本质:
- 降级就是为了解决资源不足和访问量增加的矛盾
- 在有限的资源情况下，为了能抗住大量的请求，就需要对系统做出一些牺牲，有点“弃卒保帅”的意思。放弃一些功能，保证整个系统能平稳运行
降级牺牲的是:
- 强强一致性变成最终一致性
  - 大多数的系统是不需要强一致性的。
  - 强一致性就要求多种资源的占用，减少强一致性就能释放更多资源
  - 这也是我们一般利用消息中间件来削峰填谷，变强一致性为最终一致性，也能达到效果
- 干掉一些次要功能
  - 停止访问不重要的功能，从而释放出更多的资源
  - 举例来说，比如电商网站，评论功能流量大的时候就能停掉，当然能不直接干掉就别直接，最好能简化流程或者限流最好简化功能流程。把一些功能简化掉
降级的注意点:
- 对业务进行仔细的梳理和分析
  - 哪些是核心流程必须保证的，哪些是可以牺牲的
- 什么指标下能进行降级
  - 吞吐量、响应时间、失败次数等达到一个阈值才进行降级处理
如何降级:
- 降级最简单的就是在业务代码中配置一个开关或者做成配置中心模式，直接在配置中心上更改配置，推送到相应的服务。

限流

限流就是通过对并发访问进行限速。限流的实现方式:

计数器:
最简单的实现方式，维护一个计数器，来一个请求计数加一，达到阈值时，直接拒绝请求。
一般实践中用 ngnix + lua + redis 这种方式，redis 存计数值
漏斗模式:
流量就像进入漏斗中的水一样，而出去的水和我们系统处理的请求一样，当流量大于漏斗的流出速度，就会出现积水，水多了会溢出,
漏斗很多是用一个队列实现的，当流量过多时，队列会出现积压，队列满了，则开始拒绝请求。
令牌桶:
看图例，令牌通和漏斗模式很像，主要的区别是增加了一个中间人，这个中间人按照一定的速率放入一些token，然后，处理请求时，需要先拿到token才能处理，如果桶里没有token可以获取，则不进行处理。

熔断-降级-限流三者的关系

熔断强调的是服务之间的调用能实现自我恢复的状态；
限流是从系统的流量入口考虑，从进入的流量上进行限制，达到保护系统的作用；
降级，是从系统内部的平级服务或者业务的维度考虑，流量大了，可以干掉一些，保护其他正常使用；

熔断是降级方式的一种；
降级又是限流的一种方式；
三者都是为了通过一定的方式去保护流量过大时，保护系统的手段。

id生成器如何实现全局递增

参考

介绍一下美团在用的工业级 Leaf-snowflake 方案。

41-bit的时间是毫秒级时间, 可以表示(1L<<41)/(1000L*3600*24*365)=69年的时间，
10-bit机器可以分别表示1024台机器。如果我们对IDC划分有需求，还可以将10-bit分5-bit给IDC，分5-bit给工作机器。这样就可以表示32个IDC，每个IDC下可以有32台机器，可以根据自身需求定义。
12个自增序列号可以表示2^12个ID，理论上snowflake方案的QPS约为409.6w/s，
这种分配方式可以保证在任何一个IDC的任何一台机器在任意毫秒内生成的ID都是不同的
优点：
- 毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。
- 不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的。
- 可以根据自身业务特性分配bit位，非常灵活。
缺点：强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。

解决时钟回拨问题

解决方案:

由于强依赖时钟，对时间的要求比较敏感，在机器工作时 NTP 同步也会造成秒级别的回退，建议可以直接关闭 NTP 同步。
在时钟回拨的时候直接不提供服务直接返回 ERROR_CODE，等时钟追上即可
偏差在5秒之内, 比如就等待2倍的偏差时间(比如比上次的还小3秒, 那我就等6秒)。然后做一层重试, 如果还是小于上次的时间, 就上报报警系统
更或者是发现有时钟回拨之后自动摘除本身节点并报警

代码如下：

//发生了回拨，此刻时间小于上次发号时间
if (timestamp < lastTimestamp) {
    long offset = lastTimestamp - timestamp;
    if (offset <= 5) {
        try {
          //时间偏差大小小于5ms，则等待两倍时间
            wait(offset << 1);//wait
            timestamp = timeGen();
            if (timestamp < lastTimestamp) {
                //还是小于，抛异常并上报
                throwClockBackwardsEx(timestamp);
              }    
        } catch (InterruptedException e) {  
            throw  e;
        }
    } else {
        //throw
        throwClockBackwardsEx(timestamp);
    }
}
 //分配ID

从上线情况来看，在 2017 年闰秒出现那一次出现过部分机器回拨，由于 Leaf-snowflake 的策略保证，成功避免了对业务造成的影响。
Leaf 在美团点评公司内部服务包含金融、支付交易、餐饮、外卖、酒店旅游、猫眼电影等众多业务线。目前 Leaf 的性能在 4C8G 的机器上 QPS 能压测到近 5w/s，TP999 1ms，已经能够满足大部分的业务的需求。每天提供亿数量级的调用量，作为公司内部公共的基础技术设施，必须保证高 SLA 和高性能的服务，我们目前还仅仅达到了及格线，还有很多提高的空间。

服务器开发自我修养专栏-CPP要点

Posted on 03-13-2021 | In Self-cultivation

C++

参考: 看之前一个哥们总结的c++要点 https://interview.huihut.com/

new 和 delete 为什么要配对用:
- class A{
  //...
  };
  A *pa = new A();
  A *pas = new A[NUM]();
- delete []pas; //详细流程: delete[] pas 用来释放pas指向的内存！！还逐一调用数组中每个对象的destructor！！
- delete []pa; //会发生什么, 答案是调用未知次数的A的析构函数. 因为delete[]会去通过pa+offset找一个基于pa的偏移量找一个内存里的数据, 他假定这个内存里放了要调用析构的次数n这个数据, 而这个内存里到底是多少是未知的.
- delete pas; //哪些指针会变成野指针, 答案是pas和A[0]中的指针会变成野指针. 因为只有这两个指针指向的内存被释放了, 也就是说, 仅释放了pas指针指向的这个数组的全部内存空间, 以及只调用了a[0]对象的析构函数
cqq vec set map list
- vector和string的内存分配与使用注意点
- stl关联容器的特性
map的[]和insert的区别?
- insert 含义是：如果key存在，则插入失败，如果key不存在，就创建这个key－value。实例: map.insert((key, value))
- 利用下标操作的含义是：如果这个key存在，就更新value；如果key不存在，就创建这个key－value对实例：map[key] = value
vector的resize和reserve的区别?
- 总结:
  - resize既分配了空间，也创建了对象，可以通过下标访问。当new_size大于原size, 则resize既修改capacity大小，也修改size大小。否则只修改size大小.
  - reserve只分配了空间, 也就是说它只修改capacity大小，不修改size大小, 若 new_cap 小于等于当前的 capacity(), 它啥也不干.
- resize: 重设容器大小以容纳 count 个元素。
  若当前大小大于 count ，则减小容器为其首 count 个元素。
  若当前大小小于 count:
  - 则后附额外的默认插入的元素
  - 则后附额外的 value 的副本
- reserve: 增加 vector 的容量到大于或等于 new_cap 的值。若 new_cap 大于当前的 capacity() ，则分配新存储，否则该方法不做任何事。reserve() 不更改 vector 的 size 。若 new_cap 大于 capacity() ，则所有迭代器，包含尾后迭代器和所有到元素的引用都被非法化。否则，没有迭代器或引用被非法化。
字节对齐
- 对象模型之内存对齐基础

定位new

#include <iostream>
using namespace std;
int main() {
    char buffer[512];   //chunk of memory内存池
    int *p2, *p3;
    //定位new:
    p2 = new (buffer) int[10];
    p2[0] = 99;
    p2[1] = 88;
    cout << "buffer = " <<(void *)buffer << endl; //内存池地址
    cout << "p2 = " << p2 << endl;             //定位new指向的地址
    cout << "p2[0] = " << p2[0] << endl;
    p3 = new (buffer) int[2];
    p3[0] = 1;
    p3[1] = 2;
    cout << "p3 = " << p3 << endl;
    cout << "p2[0] = " << p2[0] << endl;
    cout << "p2[1] = " << p2[1] << endl;
    cout << "p2[2] = " << p2[2] << endl;
    cout << "p2[3] = " << p2[3] << endl;
    return 0;
}

结果发现p3和p2还有buffer都是使用同样的内存地址，符合指定地址的内存块，而且p3在指定位置覆盖了p2的前两处的值。

c++一个空类会生成什么 (答: 默认构造/析构(非虚)/赋值运算符/默认拷贝/取地址/const取地址)

虚函数（virtual）可以是内联函数（inline）吗？

虚函数可以是内联函数，内联是可以修饰虚函数的，但是当虚函数表现多态性的时候不能内联。
内联是在编译器建议编译器内联，而虚函数的多态性在运行期，编译器无法知道运行期调用哪个代码，因此虚函数表现为多态性时（运行期）不可以内联。

inline virtual 唯一可以内联的时候是：编译器知道所调用的对象是哪个类（如 Base::who()），这只有在编译器具有实际对象而不是对象的指针或引用时才会发生。
虚函数内联使用:

// 此处的虚函数 who()，是通过类（Base）的具体对象（b）来调用的，
// 编译期间就能确定了，所以它可以是内联的，
// 但最终是否内联取决于编译器。 
Base b;
b.who();

// 此处的虚函数是通过指针调用的，呈现多态性，
// 需要在运行时期间才能确定，所以不能为内联。  
Base *ptr = new Derived();
ptr->who();

虚函数指针、虚函数表
- 虚函数指针：在含有虚函数类的对象中，指向虚函数表，在运行时确定。
- 虚函数表：在程序内存的只读数据段（.rodata section，见：CPP目标文件内存布局），存放虚函数指针，如果派生类实现了基类的某个虚函数，则在虚表中覆盖原本基类的那个虚函数指针，在编译时根据类的声明创建。
- virtual修饰符:
  如果一个类是局部变量则该类数据存储在栈区，如果一个类是通过new/malloc动态申请的，则该类数据存储在堆区。
  如果该类是virutal继承而来的子类，则该类的虚函数表指针和该类其他成员一起存储。虚函数表指针指向只读数据段中的类虚函数表，虚函数表中存放着一个个函数指针，函数指针指向代码段中的具体函数。
内存泄漏的工具 vargrid..? 还有啥工具
了解ASAN查找内存越界问题
cpp找找冰川, 大梦龙图的面试题，网上常用题
gdb怎么切换线程
C++ 的动态多态怎么实现的？
C++ 的构造函数可以是虚函数吗？
无锁队列原理是否一定比有锁快?(不一定, 如果临界区小因为有上下文切换则mutex慢, 再来看lockfree的spin，一般都遵循一个固定的格式：先把一个不变的值X存到某个局部变量A里，然后做一些计算，计算/生成一个新的对象，然后做一个CAS操作，判断A和X还是不是相等的，如果是，那么这次CAS就算成功了，否则再来一遍。如果上面这个loop里面“计算/生成一个新的对象”非常耗时并且contention很严重，那么lockfree性能有时会比mutex差。另外lockfree不断地spin引起的CPU同步cacheline的开销也比mutex版本的大。关于ABA问题)

编译过程

预处理(Preprocessing): 做一些类似于将所有的#define删除，并且展开所有的宏定义的操作, 然后生成hello.i
编译(Compilation): 编译过程就是把预处理完的文件进行一系列的词法分析，语法分析，语义分析及优化后生成相应的汇编代码。得到hello.a
汇编(Assembly): 汇编器是将汇编代码转变成机器可以执行的命令，每一个汇编语句几乎都对应一条机器指令。汇编相对于编译过程比较简单，根据汇编指令和机器指令的对照表一一翻译即可。得到hello.o
链接(Linking): 通过调用链接器ld来链接程序运行需要的一大堆目标文件，以及所依赖的其它库文件，最后生成可执行文件
- 静态链接: 指在编译阶段直接把静态库加入到可执行文件中去，这样可执行文件会比较大
- 动态链接: 指链接阶段仅仅只加入一些描述信息，而程序执行时再从系统中把相应动态库加载到内存中去。

目标文件

编译器编译源代码后生成的文件叫做目标文件。目标文件从结构上讲，它是已经编译后的可执行文件格式，只是还没有经过链接的过程，其中可能有些符号或有些地址还没有被调整。

可执行文件（Windows 的 .exe 和 Linux 的 ELF）、动态链接库（Windows 的 .dll 和 Linux 的 .so）、静态链接库（Windows 的 .lib 和 Linux 的 .a）都是按照可执行文件格式存储（Windows 按照 PE-COFF，Linux 按照 ELF）

目标文件格式:

Windows 的 PE（Portable Executable），或称为 PE-COFF，.obj 格式
Linux 的 ELF（Executable Linkable Format），.o 格式
Intel/Microsoft 的 OMF（Object Module Format）
Unix 的 a.out 格式
MS-DOS 的 .COM 格式

PE 和 ELF 都是 COFF（Common File Format）的变种

CPP目标文件内存布局

段	功能
File Header	文件头，描述整个文件的文件属性（包括文件是否可执行、是静态链接或动态连接及入口地址、目标硬件、目标操作系统等）
.text section	代码段，执行语句编译成的机器代码
.data section	数据段，已初始化的全局变量和局部静态变量
.bss section	BSS 段（Block Started by Symbol），未初始化的全局变量和局部静态变量（因为默认值为 0，所以只是在此预留位置，不占空间）
.rodata section	只读数据段，存放只读数据，一般是程序里面的只读变量（如 const 修饰的变量）和字符串常量
.comment section	注释信息段，存放编译器版本信息
.note.GNU-stack section	堆栈提示段

服务器开发自我修养专栏-Linux内存管理

Posted on 03-08-2021 | In Self-cultivation

Linux内存管理

为什么需要虚拟内存

虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。

为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。

从上面的描述中可以看出，虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。例如有一台计算机可以产生 16 位地址，那么一个程序的地址空间范围是 0~64K。该计算机只有 32KB 的物理内存，虚拟内存技术允许该计算机运行一个 64K 大小的程序。

MMU工作原理

内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。

一个虚拟地址分成两个部分:

一部分存储页面号，
一部分存储偏移量。

上图的页表存放着 16 个页，这 16 个页需要用 4 个比特位来进行索引定位。例如对于虚拟地址（0010 000000000100），前 4 位是存储页面号 2，读取表项内容为（110 1），页表项最后一位表示是否存在于内存中，1 表示存在。后 12 位存储偏移量。这个页对应的页框的地址为（110 000000000100）。

主机字节序

主机字节序又叫 CPU 字节序，其不是由操作系统决定的，而是由 CPU 指令集架构决定的。主机字节序分为两种：

记忆技巧: 低序地址存了高序字节就叫大端, 反之就小端
大端字节序（Big Endian）：高序字节存储在低位地址，低序字节存储在高位地址, 目前主要是ARM/PowerPC在用
小端字节序（Little Endian）：低序字节存储在低位地址, 高序字节存储在高位地址，目前主要是Intel在用

存储方式:
32 位整数 0x12345678 是从起始位置为 0x00 的地址开始存放，则：

内存地址	0x00	0x01	0x02	0x03
大端	12	34	56	78
小端	78	56	34	12

网络字节序

网络字节顺序是 TCP/IP 中规定好的一种数据表示格式，它与具体的 CPU 类型、操作系统等无关，从而可以保证数据在不同主机之间传输时能够被正确解释。

网络字节顺序采用：大端（Big Endian）排列方式。

Linux虚拟地址空间如何分布

Linux 使用虚拟地址空间，大大增加了进程的寻址空间，由低地址到高地址(下图中从下到上即为从低到高)分别为(口诀: 文初堆栈)：

文本段(只读段)：该部分空间只能读，不可写；(包括：代码段、rodata 段(C常量字符串和#define定义的常量) )
数据段(初始化数据段与未初始化数据段)：保存初始化了的与未初始化的全局变量、静态变量的空间；
堆：就是平时所说的动态内存， malloc/new 大部分都来源于此。其中堆顶的位置可通过函数 brk 和 sbrk 进行动态调整。
文件映射区域：如动态库、共享内存等映射物理空间的内存，一般是 mmap 函数所分配的虚拟地址空间。
栈：用于维护函数调用的上下文空间，一般为 8M ，可通过 ulimit –s 查看。
内核虚拟空间：用户代码不可见的内存区域，由内核管理(页表就存放在内核虚拟空间)。上图是 32 位系统典型的虚拟地址空间分布(来自《深入理解计算机系统》)。

brk函数

先了解：brk()和sbrk()函数

int brk( const void *addr )
void* sbrk ( intptr_t incr );

这两个函数的作用主要是扩展heap的上界brk。第一个函数的参数为设置的新的brk上界地址，如果成功返回0，失败返回-1。第二个函数的参数为需要申请的内存的大小，然后返回heap新的上界brk地址。如果sbrk的参数为0，则返回的为原来的brk地址。

mmap

虚拟内存系统通过将虚拟内存分割为称作虚拟页 (Virtual Page，VP) 大小固定的块，一般情况下，每个虚拟页的大小默认是 4096 字节。同样的，物理内存也被分割为物理页(Physical Page，PP)，也为 4096 字节。

在 LINUX 中我们可以使用 mmap 用来在进程虚拟内存地址空间中分配地址空间，创建和物理内存的映射关系。

映射关系

映射关系可以分为两种

文件映射
磁盘文件映射进程的虚拟地址空间，使用文件内容初始化物理内存。
匿名映射
初始化全为 0 的内存空间。

而对于映射关系是否共享又分为

私有映射 (MAP_PRIVATE)
多进程间数据共享，修改不反应到磁盘实际文件，是一个 copy-on-write（写时复制）的映射方式。
共享映射 (MAP_SHARED)
多进程间数据共享，修改反应到磁盘实际文件中。

因此总结起来有 4 种组合

私有文件映射
多个进程使用同样的物理内存页进行初始化，但是各个进程对内存文件的修改不会共享，也不会反应到物理文件中
私有匿名映射
mmap 会创建一个新的映射，各个进程不共享，这种使用主要用于分配内存 (malloc 分配大内存会调用 mmap)。
例如开辟新进程时，会为每个进程分配虚拟的地址空间，这些虚拟地址映射的物理内存空间各个进程间读的时候共享，写的时候会 copy-on-write。
共享文件映射
多个进程通过虚拟内存技术共享同样的物理内存空间，对内存文件的修改会反应到实际物理文件中，他也是进程间通信 (IPC) 的一种机制。
共享匿名映射
这种机制在进行 fork 的时候不会采用写时复制，父子进程完全共享同样的物理内存页，这也就实现了父子进程通信 (IPC).

这里值得注意的是，mmap 只是在虚拟内存分配了地址空间，只有在第一次访问虚拟内存的时候才分配物理内存。
在 mmap 之后，并没有在将文件内容加载到物理页上，只上在虚拟内存中分配了地址空间。当进程在访问这段地址时，通过查找页表，发现虚拟内存对应的页没有在物理内存中缓存，则产生 “缺页”，由内核的缺页异常处理程序处理，将文件对应内容，以页为单位 (4096) 加载到物理内存，注意是只加载缺页，但也会受操作系统一些调度策略影响，加载的比所需的多。

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
int munmap(void *addr, size_t length);

这里要注意的是fd参数，fd为映射的文件描述符，如果是匿名映射，可以设为-1；

mmap函数第一种用法是映射磁盘文件到内存中；而malloc使用的是mmap函数的第二种用法，即匿名映射，匿名映射不映射磁盘文件，而是向映射区申请一块内存。
munmap函数是用于释放内存，第一个参数为内存首地址，第二个参数为内存的长度。接下来看下mmap函数的参数。

由于brk/sbrk/mmap属于系统调用，如果每次申请内存，都调用这三个函数中的一个，那么每次都要产生系统调用开销（即cpu从用户态切换到内核态的上下文切换，这里要保存用户态数据，等会还要切换回用户态），这是非常影响性能的；其次，这样申请的内存容易产生碎片，因为堆是从低地址到高地址，如果低地址的内存没有被释放，高地址的内存就不能被回收。

malloc和free原理

malloc:

当申请小内存的时，malloc使用sbrk分配内存
当申请大内存时，使用mmap函数申请内存
但是这只是分配了虚拟内存，还没有映射到物理内存，当访问申请的内存时，才会因为缺页异常，内核分配物理内存。
将所有空闲内存块连成链表，每个节点记录空闲内存块的地址、大小等信息
分配内存时，找到大小合适的块，切成两份，一分给用户，一份放回空闲链表
free时，直接把内存块返回链表
解决外部碎片：将能够合并的内存块进行合并

malloc函数的实质体现在：它有一个将可用的内存块连接为一个长长的列表的所谓空闲链表。调用malloc函数时，它沿连接表寻找一个大到足以满足用户请求所需要的内存块。然后，将该内存块一分为二（一块的大小与用户请求的大小相等，另一块的大小就是剩下的字节）。接下来，将分配给用户的那块内存传给用户，并将剩下的那块（如果有的话）返回到连接表上。

这里注意，malloc找到的内存块大小一定是会大于等于我们需要的内存大小，下面会提到如果所有的内存块都比要求的小会怎么办？

调用free函数时，它将用户释放的内存块连接到空闲链上。到最后，空闲链会被切成很多的小内存片段，如果这时用户申请一个大的内存片段，那么空闲链上可能没有可以满足用户要求的片段了。于是，malloc函数请求延时，并开始在空闲链上翻箱倒柜地检查各内存片段，对它们进行整理，将相邻的小空闲块合并成较大的内存块。

在对内存块进行了 free 调用之后，我们需要做的是诸如将它们标记为未被使用的等事情，并且，在调用 malloc 时，我们要能够定位未被使用的内存块。因此， malloc返回的每块内存的起始处首先要有这个结构：

这就解释了，为什么在程序中free之后，但是堆的内存还是没有释放。

内存控制块结构定义

struct mem_control_block {
    int is_available;
    int size;
};

现在，您可能会认为当程序调用 malloc 时这会引发问题 —— 它们如何知道这个结构？答案是它们不必知道；在返回指针之前，我们会将其移动到这个结构之后，把它隐藏起来。这使得返回的指针指向没有用于任何其他用途的内存。那样，从调用程序的角度来看，它们所得到的全部是空闲的、开放的内存。然后，当通过 free() 将该指针传递回来时，我们只需要倒退几个内存字节就可以再次找到这个结构。

关于 malloc 获得虚存空间的实现，与 glibc 的版本有关，但大体逻辑是：

若分配内存小于 128k ，调用 sbrk() ，将堆顶指针向高地址移动，获得新的虚存空间。
若分配内存大于 128k ，调用 mmap() ，在文件映射区域中分配匿名虚存空间。

接着： VSZ为虚拟内存 RSS为物理内存

VSZ 并不是每次 malloc 后都增长，是与上一节说的堆顶没发生变化有关，因为可重用堆顶内剩余的空间，这样的 malloc 是很轻量快速的。
但如果 VSZ 发生变化，基本与分配内存量相当，因为 VSZ 是计算虚拟地址空间总大小。
RSS 的增量很少，是因为 malloc 分配的内存并不就马上分配实际存储空间，只有第一次使用，如第一次 memset 后才会分配。
由于每个物理内存页面大小是 4k ，不管 memset 其中的 1k 还是 5k 、 7k ，实际占用物理内存总是 4k 的倍数。所以 RSS 的增量总是 4k 的倍数。
因此，不是 malloc 后就马上占用实际内存，而是第一次使用时发现虚存对应的物理页面未分配，产生缺页中断，才真正分配物理页面，同时更新进程页面的映射关系。这也是 Linux 虚拟内存管理的核心概念之一。

vmalloc和kmalloc和malloc的区别

kmalloc和vmalloc是分配的是内核的内存,malloc分配的是用户的内存
kmalloc保证分配的内存在物理上是连续的,vmalloc保证的是在虚拟地址空间上的连续,malloc不保证任何东西(这点是自己猜测的,不一定正确)
kmalloc能分配的大小有限,vmalloc和malloc能分配的大小相对较大
内存只有在要被DMA访问的时候才需要物理上连续
vmalloc比kmalloc要慢

对于提供了MMU（存储管理器，辅助操作系统进行内存管理，提供虚实地址转换等硬件支持）的处理器而言，Linux提供了复杂的存储管理系统，使得进程所能访问的内存达到4GB。

进程的4GB内存空间被人为的分为两个部分–用户空间与内核空间。用户空间地址分布从0到3GB(PAGE_OFFSET，在0x86中它等于0xC0000000)，3GB到4GB为内核空间。

内核空间中，从3G到vmalloc_start这段地址是物理内存映射区域（该区域中包含了内核镜像、物理页框表mem_map等等），比如我们使用的 VMware虚拟系统内存是160M，那么3G～3G+160M这片内存就应该映射物理内存。在物理内存映射区之后，就是vmalloc区域。对于 160M的系统而言，vmalloc_start位置应在3G+160M附近（在物理内存映射区与vmalloc_start期间还存在一个8M的gap 来防止跃界），vmalloc_end的位置接近4G(最后位置系统会保留一片128k大小的区域用于专用页面映射)

一般情况下，只有硬件设备才需要物理地址连续的内存，因为硬件设备往往存在于MMU之外，根本不了解虚拟地址；但为了性能上的考虑，内核中一般使用kmalloc(),而只有在需要获得大块内存时才使用vmalloc，例如当模块被动态加载到内核当中时，就把模块装载到由vmalloc（）分配的内存上。

kmalloc:
kmalloc申请的是较小的连续的物理内存，内存物理地址上连续，虚拟地址上也是连续的，使用的是内存分配器slab的一小片。申请的内存位于物理内存的映射区域。其真正的物理地址只相差一个固定的偏移。而且不对获得空间清零。可以查看slab分配器
kzalloc:
用kzalloc申请内存的时候，效果等同于先是用 kmalloc() 申请空间 , 然后用 memset() 来初始化 ,所有申请的元素都被初始化为 0.
vmalloc:
vmalloc用于申请较大的内存空间，虚拟内存是连续。申请的内存的则位于vmalloc_start～vmalloc_end之间，与物理地址没有简单的转换关系，虽然在逻辑上它们也是连续的，但是在物理上它们不要求连续。
malloc:
malloc分配的是用户的内存。除非被阻塞否则他执行的速度非常快，而且不对获得空间清零。

Buddy（伙伴）分配算法

参考: https://zhuanlan.zhihu.com/p/149581303

伙伴系统用于管理物理页，主要目的在于维护可用的连续物理空间，避免外部碎片。所有关于内存分配的操作都会与其打交道，buddy是物理内存的管理的门户

Linux 内核引入了伙伴系统算法（Buddy system），什么意思呢？就是把相同大小的页框块用链表串起来，页框块就像手拉手的好伙伴，也是这个算法名字的由来。

具体的，所有的空闲页框分组为11个块链表，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256，512和1024个连续页框的页框块。最大可以申请1024个连续页框，对应4MB大小的连续内存。

伙伴系统:
因为任何正整数都可以由 2^n 的和组成，所以总能找到合适大小的内存块分配出去，减少了外部碎片产生。

分配实例:
比如：我需要申请4个页框，但是长度为4个连续页框块链表没有空闲的页框块，伙伴系统会从连续8个页框块的链表获取一个，并将其拆分为两个连续4个页框块，取其中一个，另外一个放入连续4个页框块的空闲链表中。释放的时候会检查，释放的这几个页框前后的页框是否空闲，能否组成下一级长度的块。

Slab分配器

伙伴系统和slab不是二选一的关系，slab 内存分配器是对伙伴分配算法的补充

slab的目的在于避免内部碎片。从buddy系统获取的内存至少是一个页，也就是4K，如果仅仅需要8字节的内存，显然巨大的内部碎片无法容忍。

slab从buddy系统申请空间，将较大的连续内存拆分成一系列较小的内存块。

用户申请空间时从slab中获取大小最相近的小块内存，这样可以有效减少内部碎片。在slab最大的块为8K，slab中所有块在物理上也是连续的。

上面说的用于内存分配的slab是通用的slab，主要用于支持kmalloc分配内存。

slab还有一个作用就是用作对象池，针对经常分配和回收的对象比如task_struct，可以分配一个slab对象池对其优化。这种slab是独立于通用的内存分配slab的，在内核中有很多这样的针对特定对象的slab。

在内核中想要分配一段连续的内存，首先向slab系统申请，如果不满足（超过两个页面，也就是8K），直接向buddy系统申请。如果还不满足（超过4M，也就是1024个页面），将无法获取到连续的物理地址。可以通过vmalloc获取虚拟地址空间连续，但物理地址不连续的更大的内存空间。

malloc是用户态使用的内存分配接口，最终还是向buddy申请内存，因为buddy系统是管理物理内存的门户。申请到大块内存后，再像slab一样对其进行细分维护，根据用户需要返回相应内存的指针。

fork内存语义

共享代码段, 子指向父 : 父子进程共享同一代码段, 子进程的页表项指向父进程相同的物理内存页(即数据段/堆段/栈段的各页)
写时复制(copy-on-write) : 内核会捕获所有父进程或子进程针对这些页面(即数据段/堆段/栈段的各页)的修改企图, 并为将要修改的页面创建拷贝, 将新的页面拷贝分配给遭内核捕获的进程, 从此父/子进程可以分别修改各自的页拷贝, 不再相互影响.

虽然fork创建的子进程不需要拷贝父进程的物理内存空间, 但是会复制父进程的空间内存页表. 例如对于10GB的redis进程, 需要复制约20MB的内存页表, 因为此fork操作耗时跟进程总内存量息息相关

零拷贝

参考 https://juejin.im/post/6844903949359644680

“先从简单开始，实现下这个场景：从一个文件中读出数据并将数据传到另一台服务器上？”
大概伪代码如下:

File.read(file, buf, len);
Socket.send(socket, buf, len);

可以看出, 这样效率是很低的.

下图分别对应传统 I/O 操作的数据读写流程，整个过程涉及 2 次 CPU 拷贝、2 次 DMA 拷贝总共 4 次拷贝，以及 4 次上下文切换，下面简单地阐述一下相关的概念。

上下文切换：当用户程序向内核发起系统调用时，CPU 将用户进程从用户态切换到内核态；当系统调用返回时，CPU 将用户进程从内核态切换回用户态。
CPU拷贝：由 CPU 直接处理数据的传送，数据拷贝时会一直占用 CPU 的资源。
DMA拷贝：由 CPU 向DMA磁盘控制器下达指令，让 DMA 控制器来处理数据的传送，数据传送完毕再把信息反馈给 CPU，从而减轻了 CPU 资源的占有率。

传统读操作

当应用程序执行 read 系统调用读取一块数据的时候，如果这块数据已经存在于用户进程的页内存中，就直接从内存中读取数据；如果数据不存在，则先将数据从磁盘加载数据到内核空间的读缓存（read buffer）中，再从读缓存拷贝到用户进程的页内存中。

read(file_fd, tmp_buf, len);

复制代码基于传统的 I/O 读取方式，read 系统调用会触发 2 次上下文切换，1 次 DMA 拷贝和 1 次 CPU 拷贝，发起数据读取的流程如下：

用户进程通过 read() 函数向内核（kernel）发起系统调用，上下文从用户态（user space）切换为内核态（kernel space）。
CPU利用DMA控制器将数据从主存或硬盘拷贝到内核空间（kernel space）的读缓冲区（read buffer）。
CPU将读缓冲区（read buffer）中的数据拷贝到用户空间（user space）的用户缓冲区（user buffer）。
上下文从内核态（kernel space）切换回用户态（user space），read 调用执行返回。

传统写操作

当应用程序准备好数据，执行 write 系统调用发送网络数据时，先将数据从用户空间的页缓存拷贝到内核空间的网络缓冲区（socket buffer）中，然后再将写缓存中的数据拷贝到网卡设备完成数据发送。

write(socket_fd, tmp_buf, len);

复制代码基于传统的 I/O 写入方式，write() 系统调用会触发 2 次上下文切换，1 次 CPU 拷贝和 1 次 DMA 拷贝，用户程序发送网络数据的流程如下：

用户进程通过 write() 函数向内核（kernel）发起系统调用，上下文从用户态（user space）切换为内核态（kernel space）。
CPU 将用户缓冲区（user buffer）中的数据拷贝到内核空间（kernel space）的网络缓冲区（socket buffer）。
CPU 利用 DMA 控制器将数据从网络缓冲区（socket buffer）拷贝到网卡进行数据传输。
上下文从内核态（kernel space）切换回用户态（user space），write 系统调用执行返回。

sendfile

sendfile 系统调用在 Linux 内核版本 2.1 中被引入，目的是简化通过网络在两个通道之间进行的数据传输过程。sendfile 系统调用的引入，不仅减少了 CPU 拷贝的次数，还减少了上下文切换的次数，它的伪代码如下：

sendfile(socket_fd, file_fd, len);

复制代码通过 sendfile 系统调用，数据可以直接在内核空间内部进行 I/O 传输，从而省去了数据在用户空间和内核空间之间的来回拷贝。与 mmap 内存映射方式不同的是， sendfile 调用中 I/O 数据对用户空间是完全不可见的。也就是说，这是一次完全意义上的数据传输过程。

基于 sendfile 系统调用的零拷贝方式，整个拷贝过程会发生 2 次上下文切换，1 次 CPU 拷贝和 2 次 DMA 拷贝，用户程序读写数据的流程如下：

用户进程通过 sendfile() 函数向内核（kernel）发起系统调用，上下文从用户态（user space）切换为内核态（kernel space）。
CPU 利用 DMA 控制器将数据从主存或硬盘拷贝到内核空间（kernel space）的读缓冲区（read buffer）。
CPU 将读缓冲区（read buffer）中的数据拷贝到的网络缓冲区（socket buffer）。
CPU 利用 DMA 控制器将数据从网络缓冲区（socket buffer）拷贝到网卡进行数据传输。
上下文从内核态（kernel space）切换回用户态（user space），sendfile 系统调用执行返回。

相比较于 mmap 内存映射的方式，sendfile 少了 2 次上下文切换，但是仍然有 1 次 CPU 拷贝操作。sendfile 存在的问题是用户程序不能对数据进行修改，而只是单纯地完成了一次数据传输过程。

“这样确实改善了很多，但还没达到零拷贝的要求（还有一次cpu参与的拷贝），还有其它黑技术？”
“对的，如果底层网络接口卡支持收集(gather)操作的话，就可以进一步的优化。”
“怎么说？”
“继续看下一小节”

sendfile + DMA gather copy

Linux 2.4 版本的内核对 sendfile 系统调用进行修改，如果底层网络接口卡支持收集(gather)操作的话, 为 DMA 拷贝引入了 gather 操作。它将内核空间（kernel space）的读缓冲区（read buffer）中对应的数据描述信息（内存地址、地址偏移量）记录到相应的网络缓冲区（ socket buffer）中，由 DMA 根据内存地址、地址偏移量将数据批量地从读缓冲区（read buffer）拷贝到网卡设备中，这样就省去了内核空间中仅剩的 1 次 CPU 拷贝操作，sendfile 的伪代码如下：

sendfile(socket_fd, file_fd, len);

复制代码在硬件的支持下，sendfile 拷贝方式不再从内核缓冲区的数据拷贝到 socket 缓冲区，取而代之的仅仅是缓冲区文件描述符和数据长度的拷贝，这样 DMA 引擎直接利用 gather 操作将页缓存中数据打包发送到网络中即可，本质就是和虚拟内存映射的思路类似。

基于 sendfile + DMA gather copy 系统调用的零拷贝方式，整个拷贝过程会发生 2 次上下文切换、0 次 CPU 拷贝以及 2 次 DMA 拷贝，用户程序读写数据的流程如下：

用户进程通过 sendfile() 函数向内核（kernel）发起系统调用，上下文从用户态（user space）切换为内核态（kernel space）。
CPU 利用 DMA 控制器将数据从主存或硬盘拷贝到内核空间（kernel space）的读缓冲区（read buffer）。
CPU 把读缓冲区（read buffer）的文件描述符（file descriptor）和数据长度拷贝到网络缓冲区（socket buffer）。
基于已拷贝的文件描述符（file descriptor）和数据长度，CPU 利用 DMA 控制器的 gather/scatter 操作直接批量地将数据从内核的读缓冲区（read buffer）拷贝到网卡进行数据传输。
上下文从内核态（kernel space）切换回用户态（user space），sendfile 系统调用执行返回。

sendfile + DMA gather copy 拷贝方式同样存在用户程序不能对数据进行修改的问题，而且本身需要硬件的支持，它只适用于将数据从文件拷贝到 socket 套接字上的传输过程。

Mike

🚙 🚗 💨 💨 If you want to create a blog like this, just follow my open-source project, "hexo-theme-neo", click the GitHub button below and check it out ^_^ . It is recommended to use Chrome, Safari, or Edge to read this blog since this blog was developed on Edge (Chromium kernel version) and tested on Safari.

GitHub Spotify

Redis

redis 数据结构有哪些？分别怎么实现的？

zset各种问题

为什么zset用跳表不用红黑树

zset是怎么支持查询排名的

延时队列用redis怎么做

ZSET做排行榜时要实现分数相同时按时间顺序排序怎么实现

哈希表渐进式rehash

redis 持久化有哪几种方式，怎么选？

bgsave流程说一下

aof流程说一下以及aof追加阻塞是啥

AOF重写的实现

如何做rdb和aof的原子替换的

redis 主从同步是怎样的过程？

redis key 的过期策略

内存淘汰机制

redis的LRU算法说一下

redis哨兵

redis集群

优点

缺点

故障转移

集群分片策略

一般哈希算法

一致性哈希算法

HashSlot算法

Cache和DB如何一致

缓存雪崩是啥?咋处理?

缓存穿透是啥?咋处理?

缓存击穿是啥?咋处理?

编码知识

Base64 的原理？编码后比编码前是大了还是小了。

base64的原理

utf8编码和unicode字符集

UTF-8

0. 导语

1.template 参数推导

2. 声明内嵌型别

3. 救世主 Traits

python

import流程

为啥字符串join比加号连接快

is和==的区别

元类

metaclass

装饰器

python命令行参数

python -m test_folder/test.py与python test_folder/test有什么不同

在python程序中调用cpp的库创建的线程是否受制于GIL?

__new__ 与 __del__ 与 __init__

python垃圾回收

标记清除咋弄的

为啥标记清除回收无法回收重写了__del__方法的类对象

分代回收

干货写在前面

分布式系统

共识

一致性的类别

线性一致性

顺序一致性

举例说明1

举例说明2

举例说明3

CAP理论

cap通俗而精准的解释

cap的一些组合例子

BASE 理论

服务治理

分布式锁

分布式锁过期时间到了但业务没执行完怎么办

基于etcd的分布式锁

基于redis的分布式锁

RedLock

分布式锁的高并发优化

分布式事务解决方案(本文这些都不好, 现在一般用Saga)

二阶段提交2PC

TCC

本地消息表

可靠消息最终一致性

尽最大努力通知

`python -m test_folder/test.py`与`python test_folder/test`有什么不同

`new` 与 `del` 与 `init`

为啥标记清除回收无法回收重写了`del`方法的类对象