Posted on | In

这是一份 mac 折腾配置以及各种改造的精华笔记, 可以帮你从头到尾打造一个极为顺手的 mac.

在Windows端配合sux 可以统一 win & mac 的使用体验.

. . .

Posted on | In

Akka/Erlang 的 actor 模型与 Go 语言的协程 Goroutine 与通道 Channel 代表的 CSP(Communicating Sequential Processes) 模型有什么区别呢？

首先这两者都是并发模型的解决方案，我们看看 Actor 和 Channel 这两个方案的不同：

Actor 模型

在 Actor 模型中，主角是 Actor，类似一种 worker，Actor 彼此之间直接发送消息，不需要经过什么中介，消息是异步发送和处理的：

Actor 模型描述了一组为了避免并发编程的常见问题的公理:

  1. 所有 Actor 状态是 Actor 本地的，外部无法访问。
  2. Actor 必须只有通过消息传递进行通信。　　
  3. 一个 Actor 可以响应消息: 推出新 Actor, 改变其内部状态, 或将消息发送到一个或多个其他参与者。
  4. Actor 可能会堵塞自己, 但 Actor 不应该堵塞它运行的线程。

更多可见 Actor 模型专题

. . .

Posted on | In

etcd

Raft选主过程

动画演示Raft选主
前提知识:

  • Election timeout选举周期: The election timeout is the amount of time a follower waits until becoming a candidate.
  • heartbeat timeout心跳时间间隔

. . .

Posted on | In

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 的详细步骤：

  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 而带来的庞大计算量。

因为在进行渐进式 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 重写时， 主进程需要执行以下三个工作：

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

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

  1. 将 AOF 重写缓存中的内容全部写入到新 AOF 文件中。
  2. 对新的 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 主从同步是怎样的过程？

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

总结:
主从刚刚连接的时候，进行全量同步；全量同步结束后，进行增量同步。当然，如果有需要，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进行故障转移的方法基本一样(也有主观下线和客观下线)，不同的是，在集群里面，故障转移的过程是:

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

所以集群不必另外使用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 | In

编码知识

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。

Posted on | In

原文出处

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