ARTS 打卡第 2 周

1. Algorithm

题目的来源于 leetcode:https://leetcode.cn/problems/implement-rand10-using-rand7。主要利用的是概率和拒绝采样，代码实现如下：

class Solution {public:    int rand10() {            while(true) {                        /**            * (rand_X() - 1) × Y + rand_Y() ==> 可以等概率的生成[1, X * Y]范围的随机数即实现了rand_XY()            **/             int num = (rand7() - 1) * 7 + rand7(); // 等概率生成[1,49]范围的随机数            if(num <= 40) return num % 10 + 1; // 拒绝采样，并返回[1,10]范围的随机数        }    }};

2. Review

我将继续第一周时对于 redis cluster 的章节的翻译。原文链接：https://redis.io/docs/reference/cluster-spec/中的 Configuration handling, propagation, and failovers。

Replica rank

从节点级别

As soon as a master is in FAIL state, a replica waits a short period of time before trying to get elected. That delay is computed as follows:

一旦一个主节点进入到 FAIL 状态。从节点会在尝试进行选举之前等待一个短暂的时间。这个延迟时根据以下的方式计算的：

$$DELAY=500milliseconds+randomdelaybetween0and500milliseconds+REPLIC{A}_{R}ANK\ast 1000milliseconds.$$

The fixed delay ensures that we wait for the FAIL state to propagate across the cluster, otherwise the replica may try to get elected while the masters are still unaware of the FAIL state, refusing to grant their vote.

这个固定的延迟确保我们在等待“FAIL”状态在集群中传播，否则从节点可能会在主节点仍然不知道“FAIL”状态的情况下尝试进行选举，而主节点会拒绝给此选举进行投票。

The random delay is used to desynchronize replicas so they're unlikely to start an election at the same time.

随机延迟用于使从节点的选举时间不同步，以免它们在相同的时间开始选举。

The REPLICA_RANK is the rank of this replica regarding the amount of replication data it has processed from the master. Replicas exchange messages when the master is failing in order to establish a (best effort) rank: the replica with the most updated replication offset is at rank 0, the second most updated at rank 1, and so forth. In this way the most updated replicas try to get elected before others.

"REPLICA_RANK" 是指该从节点相对于从主节点复制的数据量而言的排名。当主节点发生故障时，从节点交换消息以建立一个（尽最大努力的）排名：具有最新复制偏移的从节点排名为 0，其次为 1，依此类推。这样，最新的从节点会在其他从节点之前尝试进行选举。

Rank order is not strictly enforced; if a replica of higher rank fails to be elected, the others will try shortly.

排名顺序并不严格执行；如果排名更高的从节点未能成功当选，其他从节点会很快尝试进行选举。

Once a replica wins the election, it obtains a new unique and incremental configEpoch which is higher than that of any other existing master. It starts advertising itself as master in ping and pong packets, providing the set of served slots with a configEpoch that will win over the past ones.

一旦一个从节点当选成功，它会获取一个新的独特且递增的 configEpoch，该值高于任何其他现有主节点的 configEpoch。它会在 ping 和 pong 数据包中开始将自己作为主节点进行广播，提供了一组使用了将取胜于过去的 configEpoch 的服务的槽位。

In order to speedup the reconfiguration of other nodes, a pong packet is broadcast to all the nodes of the cluster. Currently unreachable nodes will eventually be reconfigured when they receive a ping or pong packet from another node or will receive an UPDATE packet from another node if the information it publishes via heartbeat packets are detected to be out of date.

为了加快其他节点的重新配置，一个 pong 数据包会广播到集群中的所有节点。当前无法连接的节点最终会在它们从另一个节点接收到 ping 或 pong 数据包时重新配置，或者如果通过心跳包发布的信息被检测为过时，它们将从另一个节点接收到 UPDATE 数据包来更新配置。

The other nodes will detect that there is a new master serving the same slots served by the old master but with a greater configEpoch, and will upgrade their configuration. Replicas of the old master (or the failed over master if it rejoins the cluster) will not just upgrade the configuration but will also reconfigure to replicate from the new master. How nodes rejoining the cluster are configured is explained in the next sections.

其他节点会检测到有一个新的主节点为相同的槽位提供服务，但其 configEpoch 值更大，然后它们将升级其配置。旧主节点的副本（或者如果故障转移的主节点重新加入集群，则为新的主节点）不仅会升级配置，还会重新配置以从新的主节点进行复制。节点重新加入集群的配置方法在接下来的章节中有详细说明。（未完待续...）

3. Technique/Tips

backtrace()函数

• 作用

用于获取函数运行过程中经过的栈帧信息。我目前主要的应该场景是用于查找旧项目（C/C++）代码的内存泄露。

• 例子

/*** backtrace类函数声明头文件**/#include <execinfo.h>
int func(){    void *arry[10] = {NULL};    size_t size;        char **strings;    size_t i;
        /**    * 函数原型：int backtrace(void **buffer,int size)    * buffer --指针数组,保存函数栈帧调用过程中的函数指针    * size -- 允许保存函数指针的最大个数    * return -- 保存的函数指针的个数    **/    size = backtrace (array, 10);        /**    *  函数原型：char ** backtrace_symbols (void *const *buffer, int size)    * buffer -- 调用栈帧中的函数指针    * size -- buffer保存的函数指针个数    * return -- 字符串数组，函数指针对应的函数名，函数的偏移地址,和实际的返回地址    **/    strings = backtrace_symbols(array, size);        /**    * 需要显式释放    **/    free (strings);        /**    * void backtrace_symbols_fd (void *const *buffer, int size, int fd)    * 函数将对应的函数指针对于的函数信息写入到fd指定的文件中    **/    //backtrace_symbols_fd(void *const *buffer, int size, int fd)}

4. Share

• 坚持学习，滴水穿石，铁杵磨成针，都是在说明坚持带来的能量

• Steve Jobs ：Stay Hungry, Stay Foolish.