令牌桶（token bucket）是最常用的限流算法。它用两个数描述一条规则：令牌补充的速度，和桶最多能存多少个令牌。它要解决的问题是：既把长期的平均速度压住，又允许短时间内的一阵突发。 限流、熔断、降级三者的关系见 限流、熔断与降级，这篇只讲令牌桶。 原理 想象一个桶： 系统以恒定速度 r 往桶里放令牌，比如每秒 5 个； 桶最多装 b 个令牌，比如 60 个，满了再放的令牌直接丢掉； 每个请求进来先从桶里取一个令牌，取到就放行，桶空了就拒绝（或者排队等）。 所以 r 管的是长期平均速度，b 管的是一次最多能连发多少。b 也叫突发容量（burst）。 用 r = 5/s、b = 60 走一遍： 时刻 发生了什么 桶里的令牌 0 秒 用户闲了很久，桶是满的 60 0 秒 一口气发了 40 个请求，全部放行 20 0～4 秒 没有请求，每秒补 5 个 40 4 秒 又连发 50 个：前 40 个放行，后 10 个被拒 0 4 秒之后 每 0.2 秒补 1 个，只能按每秒 5 个的速度继续 0～1 停 12 秒 补满 60 规律： ...
字符串匹配算法总结 KMP虽然经典,但是理解起来极其复杂,好不容易理解好了,便起码来巨麻烦！ 老子就是今天图书馆在写了几个小时才勉强写了一个有bug的、效率不高的KMP,特别是计算next数组的部分。 其实,比KMP算法速度快的算法大把大把,而且理解起来更简单,为何非要抓住KMP呢？笔试出现字符串模式匹配时直接上sunday算法,既简单又高效,何乐而不为？ 说实话,想到sunday算法的那个人,绝对是发散思维,绝对牛。当我在被KMP折磨的够呛的时候,我就琢磨,有没有别的好算法呢？？琢磨了半天也没想出个所以然来。笨啊,脑子不够发散。 下面贴上一位兄弟写的算法总结,很简单 (建议KMP部分就不用看了,看了费脑子) 。 参见: http://hi.baidu.com/willamette/blog/item/02bd0b5599c8b4c0b645ae06.html 趁着做Presentation的功夫,顺便做一个总结 字符串匹配: -willamette 在匹配串中寻找模式串是否出现,注意和最长公共子序列相区别(LCS: Longest Common Substring) **-: ** Brute Force(BF或蛮力搜索) **算法: ** 这是世界上最简单的算法了。 首先将匹配串和模式串左对齐,然后从左向右一个一个进行比较,如果不成功则模式串向右移动一个单位。 速度最慢。 那么,怎么改进呢？ 我们注意到Brute Force 算法是每次移动一个单位,一个一个单位移动显然太慢,是不是可以找到一些办法,让每次能够让模式串多移动一些位置呢？ 当然是可以的。 我们也注意到,Brute Force 是很不intelligent 的,每次匹配不成功的时候,前面匹配成功的信息都被当作废物丢弃了,当然,就如现在的变废为宝一样,我们也同样可以将前面匹配成功的信息利用起来,极大地减少计算机的处理时间,节省成本。^_^ 注意,蛮力搜索算法虽然速度慢,但其很通用,文章最后会有一些更多的关于蛮力搜索的信息。 **-: KMP算法 ** 首先介绍的就是KMP 算法。 原始论文: Knuth D.E., Morris J.H., and Pratt V.R., Fast pattern matching in strings, SIAM Journal on Computing, 6(2), 323-350, 1977. 这个算法实在是太有名了,大学上的算法课程除了最笨的Brute Force 算法,然后就介绍了KMP 算法。也难怪,呵呵。谁让Knuth D.E. 这么world famous 呢,不仅拿了图灵奖,而且还写出了计算机界的Bible 《The Art of Computer Programming》( 业内人士一般简称TAOCP). 稍稍提一下,有个叫H.A.Simon 的家伙,不仅拿了Turing Award ,顺手拿了个Nobel Economics Award ,做了AI 的爸爸,还是Chicago Univ 的Politics PhD ,可谓全才。 ...
本文整理一般二叉树、二叉搜索树（BST）与平衡树的概念；BST 的插入、查找、删除与中序遍历的 Go 实现见我的 leetcode 仓库 下的 tree/（bst.go、bst_test.go）。 二叉树 (Binary Tree) 二叉树 (Binary Tree) 是包含 n 个节点的有限集合，该集合或者为空集（此时，二叉树称为空树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。 二叉树中的节点至多包含两棵子树，分别称为左子树和右子树，而左子树和右子树又分别至多包含两棵子树。由上述的定义，二叉树的定义是一种递归的定义。 graph TD n1((1)) n2((2)) n3((3)) n4((4)) n5((5)) n7((7)) n10((10)) n11((11)) n14((14)) n1 --> n2 n1 --> n3 n2 --> n4 n2 --> n5 n3 --> n7 n5 --> n10 n5 --> n11 n7 --> n14 满二叉树 Full Binary Tree 对于一棵二叉树，如果每一个非叶子节点都存在左右子树，并且二叉树中所有的叶子节点都在同一层中，这样的二叉树称为满二叉树。 graph TD n1((1)) n2((2)) n3((3)) n4((4)) n5((5)) n6((6)) n7((7)) n8((8)) n9((9)) n10((10)) n11((11)) n12((12)) n13((13)) n14((14)) n15((15)) n1 --> n2 n1 --> n3 n2 --> n4 n2 --> n5 n3 --> n6 n3 --> n7 n4 --> n8 n4 --> n9 n5 --> n10 n5 --> n11 n6 --> n12 n6 --> n13 n7 --> n14 n7 --> n15 完全二叉树 Complete Binary Tree 对于一棵具有 n 个节点的二叉树按照层次编号，同时，左右子树按照先左后右编号，如果编号为 i 的节点与同样深度的满二叉树中编号为 i 的节点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。 ...
二叉搜索树 红黑树本质上就是一棵二叉搜索树（Binary Search Tree, BST）。BST 的定义、性质与退化成链表后性能变差的问题，见 二叉树与二叉搜索树 §二叉搜索树 Binary Search Tree。 红黑树的性质 红黑树在二叉搜索树的基础上增加了着色和相关的性质，使得树相对平衡，从而保证查找、插入、删除的时间复杂度最坏为 O(log n)。要保证一棵有 n 个结点的红黑树的高度始终保持在 O(log n)，需要满足以下 5 条性质： 每个结点要么是红色，要么是黑色。 根结点是黑色。 每个叶结点（即树尾端的 NIL 指针或 NULL 结点）是黑色。 如果一个结点是红色，那么它的两个子结点都是黑色。 对于任一结点，其到叶结点的每一条路径都包含相同数目的黑色结点。 正是这 5 条性质，使得一棵有 n 个结点的红黑树始终保持 O(log n) 的高度，从而解释了上面"查找、插入、删除的时间复杂度最坏为 O(log n)“这一结论的原因。 示例：一棵合法的红黑树 下面几张图都用同一套配色：红色底色代表红色节点，深色底色代表黑色节点（NIL 叶子也按黑色处理）；后面删除修复的例子里还会多一种"双重黑"的颜色，专门标出来。 graph TD classDef red fill:#d64545,stroke:#333,color:#fff; classDef black fill:#2c2c2c,stroke:#333,color:#fff; r((10)):::black a((5)):::red b((3)):::black c((7)):::black d((15)):::black e[NIL]:::black f((20)):::red r --> a r --> d a --> b a --> c d --> e d --> f 对照上面的 5 条性质检查这棵树：根 10 是黑色；红色节点 5、20 的子节点都是黑色（5 的子节点 3、7 是黑色，20 的两个子节点是图中未画出的 NIL，同样按黑色计）；从根到任意一条路径上的黑色节点数都是 3（例如 10 → 5 → 3 → NIL 与 10 → 15 → 20 → NIL 都是 3 个黑色节点），满足黑高一致。 ...
AVL 树是最早出现的自平衡二叉搜索树，由 G.M. Adelson-Velsky 和 E.M. Landis 于 1962 年在论文《An algorithm for the organization of information》中提出，因此得名 AVL（发明者姓氏首字母），也叫高度平衡树。 平衡二叉树的通用定义（平衡因子、失衡、单旋恢复平衡的例子）见 二叉树与二叉搜索树 §平衡二叉树 Balanced Binary Tree，本文只讲 AVL 特有的部分：严格平衡条件、四种失衡情况的旋转、插入删除的复杂度，以及和其他平衡树、常见平衡树家族的关系。 严格平衡条件 一棵 AVL 树满足以下条件（递归定义）： 左子树和右子树都是 AVL 树。 左子树和右子树的高度差不超过 1。 相比红黑树用颜色规则换取的"相对平衡"，AVL 树是严格平衡：任意结点的平衡因子（左子树高度 − 右子树高度）只能取 -1、0、1。这带来的好处是查找效率稳定，代价是插入、删除时更容易触发再平衡。 树高的维护 判断是否失衡需要知道每个结点的子树高度，通常在结点里额外记一个 height 字段： 空结点（NIL）的高度记为 -1 叶子结点的高度为 0 非叶子结点的高度 = max(左子树高度, 右子树高度) + 1 插入或删除一个结点后，从该结点沿父指针回溯到根，逐层重新计算高度；一旦某个祖先的平衡因子超出 [-1, 1]，该结点就是失衡点，需要旋转恢复平衡。 失衡的四种情况与旋转 失衡点的位置只有 4 种可能，分别对应不同的旋转方式： 情况 触发位置 旋转方式 LL（左左） 左子树的左子树过高 对失衡点做一次右旋 RR（右右） 右子树的右子树过高 对失衡点做一次左旋 LR（左右） 左子树的右子树过高 先对左子树左旋，再对失衡点右旋（双旋） RL（右左） 右子树的左子树过高 先对右子树右旋，再对失衡点左旋（双旋） RR 单旋的完整示例见 二叉树与二叉搜索树 §插入示例，LL 是它的镜像。下面补充一个 LR 双旋的例子。 ...
一句话 DAG = Directed Acyclic Graph，中文常叫有向无环图。它是一种图：边有方向，且沿着方向走永远走不回起点。 先说「图」 图（Graph）由两类东西组成： 节点（Node / Vertex）：事物本身，比如「编译模块 A」「跑测试」「部署」 边（Edge）：节点之间的关系，比如「A 完成后才能做 B」 边如果没有方向（A—B 和 B—A 一样），叫无向图；边有方向（A → B 表示从 A 到 B），叫有向图（Directed Graph）。 Directed：边有方向 在任务依赖、数据流水线里，方向通常表示「先后」或「依赖」： 写接口 ──► 写单测 ──► 跑 pytest 意思是：写接口完成之后才能写单测；单测就绪之后才能跑 pytest。反过来走没有意义——不能「先跑 pytest 再写接口」。 Acyclic：不能有环 「无环」是说：沿着箭头走，不会绕回已经走过的节点。 有环的例子（这不是 DAG）： A ──► B ▲ │ └─────┘ A 等 B，B 又等 A，两边永远等不到对方。包管理里的循环依赖、构建系统里的互相引用，本质都是环带来的死锁。 无环的例子（这是 DAG）： ┌──► B ──► D A ───┤ └──► C ──► E 从 A 出发可以走到 B、C、D、E，但没有任何一条路径能回到 A。因此一定存在至少一个「没有入边的起点」，以及至少一个「没有出边的终点」。 ...
Xorshift 是什么 Xorshift 是 George Marsaglia 在 2003 年发表的一类伪随机数生成算法（PRNG，Pseudo-Random Number Generator），核心思路是反复对一个整数状态做"自己和自己移位后的版本"做异或（XOR），只用异或和移位两种运算就能生成看起来随机的数字序列。 它属于线性反馈移位寄存器（LFSR，Linear Feedback Shift Register）的一种变体，相比传统的线性同余法（LCG，Linear Congruential Generator，也就是很多语言标准库 rand() 背后的算法）不需要乘法和取模，只用位运算，速度快很多；相比更复杂的 Mersenne Twister（java.util.Random 用的不是这个，但 Python、PHP 等语言的默认随机数用的是它），实现更简单、状态更小。 代价是随机质量不如 Mersenne Twister，不能用于密码学场景（不是 CSPRNG，Cryptographically Secure PRNG），但对哈希表、游戏、模拟、需要"看起来随机就行"的场景完全够用，且速度优势明显。 基本算法 最经典的 32 位 xorshift 只需要一个非零的整数状态 x 和三次移位异或： uint32_t xorshift32(uint32_t x) { x ^= x << 13; x ^= x >> 17; x ^= x << 5; return x; } 每次调用把上一次的输出作为下一次的输入（状态），就能生成一串伪随机序列。三个移位量 (13, 17, 5) 不是随便选的——Marsaglia 在论文里给出了一批能保证生成的序列覆盖 2^32 - 1 个非零状态（即最大周期）的移位量组合，(13, 17, 5) 是其中常用的一组。如果移位量选得不好，会导致序列过早循环或者分布不均匀。 64 位状态的版本同理，只是移位量不同： uint64_t xorshift64(uint64_t x) { x ^= x << 13; x ^= x >> 7; x ^= x << 17; return x; } 为什么异或和移位比乘除法快 xorshift 只用异或和移位，LCG 需要乘法，还常常需要取模——这两类操作在 CPU 上的实际开销差距很大，不只是"位运算听起来更底层"这种直觉。 ...
LCG 是什么 线性同余生成器（LCG，Linear Congruential Generator）是历史最悠久、实现最简单的一类伪随机数算法（PRNG，Pseudo-Random Number Generator）。1949 年由 D. H. Lehmer 提出雏形，此后几十年里几乎所有编程语言标准库的 rand() 都是它的某个变体。 它的核心是一条递推公式：给定当前状态 seed，用一次乘法、一次加法、一次取模算出下一个状态，同时把这个状态作为输出。相比 Mersenne Twister 随机数算法 和 Xorshift 伪随机数算法，LCG 实现最简单、状态最小，但随机质量也最差，且不是密码学安全的随机数生成器（不是 CSPRNG，Cryptographically Secure PRNG），不能用在密钥生成、令牌生成等安全场景。 递推公式 X(n+1) = (a * X(n) + c) mod m 四个参数决定了一个具体的 LCG： X(0)：种子（seed），初始状态 a：乘数（multiplier） c：增量（increment） m：模数（modulus） c = 0 的特例叫乘同余生成器（multiplicative congruential generator，也叫 Lehmer RNG）；c != 0 时才是完整的（mixed）LCG。取模运算保证了状态永远落在 [0, m) 区间内，序列迟早会回到某个之前出现过的状态并开始循环——这个循环长度就是"周期"，LCG 的周期上限是 m。 参数怎么选：Hull–Dobell 定理 不是随便选四个数字就能得到一个"好"的 LCG。如果参数选得不好，序列可能远没跑到 m 就开始循环，或者呈现明显的规律。Hull–Dobell 定理给出了 c != 0 时序列能达到最大周期 m（即遍历 [0, m) 里所有整数才循环）的充要条件： ...
Mersenne Twister 是什么 Mersenne Twister（简称 MT，梅森旋转算法）是松本真（Makoto Matsumoto）和西村拓士（Takuji Nishimura）在 1997 年发表的伪随机数生成算法（PRNG），名字来自它的周期长度——最常用的变体 MT19937 的周期是 2^19937 - 1，这是一个梅森素数（Mersenne prime，形如 2^p - 1 的素数）。 它是目前应用最广泛的通用 PRNG 之一：Python、PHP、R、Ruby、Excel 的默认随机数生成器用的都是 MT19937；C++11 标准库 <random> 里的 std::mt19937 也是它。相比 Xorshift 伪随机数算法 和 Java Random 随机数 里的线性同余法（LCG），MT 的随机质量（统计意义上的均匀性、独立性）好得多，周期也长得多，代价是内部状态更大、实现更复杂。 和 xorshift、LCG 一样，MT 不是密码学安全的随机数生成器（不是 CSPRNG）：观察连续 624 个输出就能反推出完整的内部状态，从而预测后续所有输出，所以不能用在密钥生成、令牌生成等安全场景，这些场景要用专门的 CSPRNG（比如 Java 的 java.security.SecureRandom）。 核心设计 状态：624 个 32 位整数 MT19937 的内部状态是一个长度 624 的 32 位整数数组，一共 624 * 32 = 19968 位，比 xorshift（几十到几百位状态）或 LCG（48 位状态）大得多——这也是"随机质量更好"的代价之一：状态越大，能表达的不同序列就越多，越不容易在短序列内暴露周期性规律。 生成流程分两步 状态推进（twist）：每消耗完 624 个输出后，对整个状态数组做一次"扭转"变换，生成下一批 624 个新状态。扭转的核心是对相邻状态做位组合，再乘上一个固定的常数矩阵（用移位和异或实现，不是真正的矩阵乘法，效果类似线性反馈移位寄存器）。 输出提炼（tempering）：每次取值时，不直接返回状态数组里的原始整数，而是先对它做一轮固定的移位、掩码、异或组合（tempering），目的是消除原始状态里明显的统计规律，让直接输出的比特看起来更均匀。 这种"大状态 + 定期批量刷新 + 每次输出前额外处理"的设计，是 MT 和 xorshift/LCG 这类"每次输出就是一次状态更新"的算法的主要区别。 ...
Swiss Table 是什么 Swiss Table 是 Google 在 2017 年前后公开的一种高性能哈希表设计（最早用在 Abseil 库的 absl::flat_hash_map 里），本质上是开放地址法的一个工程变体：在经典的线性探测 / 二次探测之上，加入了按"组"批量比较的机制，充分利用 CPU 的 SIMD 指令与缓存局部性。基本的开链法、开放地址法概念见 开链法与开放地址法。 它已经被多个主流项目采纳：Rust 的 hashbrown（std::collections::HashMap 自 1.36 起的底层实现）就是 Google SwissTable 的 Rust 移植版；Go 1.24 内置的 map 也从桶+溢出桶的实现换成了基于 Swiss Table 思路的新实现（细节见 开链法与开放地址法#在-go-语言中的应用）。 核心设计 控制字节（control byte） Swiss Table 给每个槽位（slot）配一个额外的 1 字节"控制字节"，不存实际数据，只存槽位的状态和一段哈希指纹： 槽位状态：EMPTY（从未用过）、DELETED（曾经用过、已删除，即墓碑标记）、FULL（当前有效数据）。 如果槽位是 FULL，控制字节里还会存一段哈希指纹，Abseil 里称为 h2，取的是 key 完整哈希值的低 7 位。 h1 和 h2：哈希值一分为二 Swiss Table 把 key 的哈希值拆成两部分： h1：哈希值的剩余高位，用来计算这个 key 应该落在哪一个"组"（group），即决定探测起点，作用类似前文开放地址法里的 root = hash(key) % m。 h2：哈希值的低 7 位，存进控制字节，作为一个廉价的"预筛选"指纹。 分组批量比较 控制字节在内存中是连续排列的，按组打包（Abseil/hashbrown 里一组 16 个，Go 1.24 里一组 8 个，打包进一个 64 位控制字）。查找时： ...
开链法与开放地址法，Separate Chaining and Open Addressing 哈希表在插入元素时，如果两个不同的 key 计算出的哈希值落到了数组的同一个位置，就发生了哈希冲突（hash collision）。解决哈希冲突主要有两种思路：开链法（Separate Chaining）和开放地址法（Open Addressing）。Java 的 HashMap 用的是开链法；Python 的 dict 用的是开放地址法。Java 里也有用开放地址法的例子，比如 IdentityHashMap 和 ThreadLocal.ThreadLocalMap，详见后文「在 Java 中的应用」一节。 开链法，Separate Chaining 开链法是一种二维结构：第一维是一个数组，数组的每个槽位（bucket）挂着一个链表（第二维）。插入元素时，先用 hash 函数算出该 key 应该落在数组的哪个槽位，然后直接把这个 key（连同 value）作为一个节点追加到该槽位的链表上。 当多个不同的 key 计算出相同的槽位时，它们并不会互相覆盖或者被挪到别处，而是全部挂在同一个槽位的链表里，按顺序排列。查找时，先定位到槽位，然后遍历该槽位的链表，逐个比较 key 是否相等，直到找到目标或者遍历到链表末尾。 优点 实现简单，冲突处理直观，槽位之间互不影响。 删除操作非常简单，只需要从链表中把对应节点摘除即可，不会影响其它元素的查找路径。 负载因子（元素个数 / 数组长度）可以大于 1，只是链表会变长，查找退化为线性扫描。 负载因子，Load Factor 负载因子的英文是 load factor，公式为 load factor = 哈希表中总元素个数 / 数组长度（槽位数）。这里的"元素个数"指的是整个哈希表中的元素总数，而不是某一个槽位对应的元素个数；某个槽位挂了多少个元素（链表长度）反映的是 hash 分布是否均匀，是另一个维度的问题。例如数组长度为 16，哈希表中一共存了 12 个元素，此时 load factor 就是 0.75。 开链法下即使 load factor 大于 1（元素个数超过数组长度）也不会出错，只是链表会变长；而开放地址法由于只有一个数组，load factor 不能超过 1（数组会满）。 ...
大 O 表示法（Big O Notation） 大 O 符号用来描述算法的时间复杂度：输入规模增长时，算法运行时间的增长趋势。 最直观的两种复杂度是： O(1)：一次操作即可直接取得目标元素，例如字典（哈希表）的查找 O(n)：需要逐一检查 n 个元素才能找到目标，例如遍历数组查找 那么 O(log n) 是什么意思？ O(log n) 的由来：二分查找 O(log n) 最常见的例子是二分查找。二分查找最好情况下复杂度是 O(1)（第一次就命中中间元素），最坏情况下是 O(log n)。下面从最坏情况推导这个结论。 假设有 16 个元素的有序数组，要查找的目标值小于数组中间的元素。每比较一次中间元素，搜索范围就减半： 16 个元素 → 取中间元素比较，目标在前一半 → 剩余 8 个元素 8 个元素 → 剩余 4 个元素 4 个元素 → 剩余 2 个元素 2 个元素 → 剩余 1 个元素，查找结束 也就是说，从 16 个元素中定位目标，最多需要将数组对半分割 4 次： $$ \frac{16}{2^4} = 1 $$推广到 n 个元素，设需要分割 k 次才能剩下 1 个元素： ...
Paxos paxos Paxos (Greek: Παξοί, pronounced Paksi in English ) 又名Paxi是希腊西南部一个风景如画的小岛。而Paxos算法则是现在很火的分布式一致性算法,为何以一个希腊小岛名字算法？Lamport这样解释道: I thought, and still think, that Paxos is an important algorithm. Inspired by my success at popularizing the consensus problem by describing it with Byzantine generals, I decided to cast the algorithm in terms of a parliament on an ancient Greek island. Leo Guibas suggested the name Paxos for the island. 为描述 Paxos 算法,Lamport 虚拟了一个叫做 Paxos 的希腊城邦,这个岛按照议会民主制的政治模式制订法律,但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员,议长或者传递纸条的服务员都不能承诺别人需要时一定会出现,也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题 (Byzantine failure,即虽然有可能一个消息被传递了两次,但是绝对不会出现错误的消息) ；只要等待足够的时间,消息就会被传到。另外,Paxos 岛上的议员是不会反对其他议员提出的决议的[1]。 ...
Gossip（流言 / 八卦）协议是一种用于在分布式系统中传播消息的通信协议，灵感来自瘟疫扩散、社交网络这类「一传十、十传百」的过程。Redis Cluster、Consul、Apache Cassandra 等系统都用它来做节点间的信息同步。 基本思想 一个节点想把某条信息分享给网络中的其他节点时，并不会一次性广播给所有人，而是周期性地随机挑选若干个节点把消息发过去；收到消息的节点接下来做同样的事，再随机转发给另一些节点。如此一轮轮扩散，消息最终会传遍整个网络。 每次随机发送的目标节点数量记作 fanout（扇出）。比如 fanout = 4，就是每个被「感染」的节点每个周期向 4 个随机节点传播消息。 它的名字和「社交网络」的联想，背后是著名的「六度分隔」现象：1967 年哈佛大学 Stanley Milgram 通过连锁信实验发现，你和任意一个陌生人之间间隔的人通常不超过六个。若每人平均认识 260 人，理论上 260⁶ 已远超全球人口——这种指数级扩散正是 Gossip 的雏形。 用途 主要用于信息的传播与扩散，常见场景包括：数据库复制、配置 / 状态扩散、集群成员关系维护、故障探测等。典型系统有 Apache Cassandra、Redis（Cluster 模式）、Consul 等。 特点 可扩展（scalable）：把消息传遍所有节点大约只需 O(log N) 个周期。发送时不需要等待对方确认（ack），即使个别消息丢失也不用补偿——节点会反复多次分享同一条消息，丢一两次不影响最终所有节点收到。在 fanout 固定时，节点数从 20 翻到 40、80、160，所需周期数也只是缓慢增长。 失败容错（fault-tolerant）：网络故障等情况下依然能工作。即使暂时连不上某个节点，其他被「感染」的节点也会继续尝试向它传播。 健壮（robust）：没有 leader 之类的特殊角色，任何节点随时上下线都不会破坏整体服务质量。 局限 Gossip 也有不完美的地方，比如难以应对拜占庭问题（Byzantine）：如果存在一个恶意传播错误消息的节点，普通 Gossip 协议的系统就会出问题——它假定节点只是可能失联，而不会主动作恶。 参考 阿飞的博客（简书）：https://www.jianshu.com/p/54eab117e6ae https://cloud.tencent.com/developer/article/1662426 维护记录 时间 修改内容 原因 2026-06-30 给「拜占庭问题」加内链指向 byzantine-generals-problem；标签由 Inbox 改为 distributed-systems/remix/AI-assisted，新增 lastmod 与拜占庭将军问题一文互链；规范标签 2026-06-30 从 inbox/Gossip.md 移到 cs/gossip.md；文件名改小写、title 改为「Gossip Protocol 流言协议」、url 改为 gossip（旧 Gossip 入 aliases）；分类 inbox→Algorithm、补 gossip 标签；重排为 ## 小标题、清掉无图的残留图注、改写为自有表述 文件原在未分类 inbox、文件名大写、结构零散，整理归类
接触区块链，多少会听到「某某算法解决了拜占庭将军问题」。它其实是分布式系统一致性（distributed consensus）领域一个很经典的抽象问题，由 Leslie Lamport（2013 年图灵奖得主，分布式系统领域奠基人之一，逻辑时钟、Paxos、LaTeX 的作者）与 Robert Shostak、Marshall Pease 在 1982 年的论文 《The Byzantine Generals Problem》 中提出。 什么是拜占庭将军问题 它也被叫作「拜占庭容错问题」。用一个比喻来描述： 拜占庭帝国派出 10 支军队去包围一个敌人。这个敌人能抵御 5 支常规军队的同时袭击，所以至少要有 6 支军队（过半）同时进攻才能取胜。这些军队分散在敌国四周，只能靠通信兵骑马互相传递消息来约定「进攻意向」和「进攻时间」。 麻烦在于：将军中可能有叛徒。叛徒会擅自篡改进攻意向或时间。那么，在可能存在叛徒的情况下，忠诚的将军们要如何达成一致、保证有多于 6 支军队在同一时间发起进攻？ 需要注意，这个问题里假定信道本身是可靠的（消息不会丢失、不会被截获）。至于「在可能丢消息的不可靠信道上，靠消息传递达成一致是不可能的」，那是另一个经典结论——两将军问题（Two Generals’ Problem），由 Akkoyunlu 等人在 1975 年提出并证明无解、Jim Gray 1978 年将其命名，是第一个被证明无解的计算机通信问题。它常被误记为 Lamport 的成果，其实和拜占庭将军问题是两回事：前者讲「信道不可靠」，后者讲「节点会作恶」。所以拜占庭将军问题把信道问题排除在外，焦点放在「节点（将军）本身可能作恶」上。 问题分析 先看没有叛徒的情况：将军 A 提一个进攻提议（「明天下午 1 点进攻，你加入吗？」），通过通信兵告诉其他将军。如果他收到 6 个以上将军的同意，就能发起进攻。但如果其他将军同时也在发不同的提议（2 点、3 点……），由于消息到达有时间差，不同将军收到并认可的提议可能不一样，于是出现 A 提议 3 票、B 提议 4 票、C 提议 2 票这种分裂局面。 再加入叛徒就更复杂了：一个叛徒会向不同的将军发出不同的提议（告诉 A 是 1 点、告诉 B 是 2 点），也可能同时同意多个互相冲突的提议。 叛徒发送的这种前后不一致、互相矛盾的信息，就叫「拜占庭错误（Byzantine fault）」。 ...
概念 优先级队列（Priority Queue）是一种特殊的队列，队列中每个元素都附有一个"优先级"。出队时，不再遵循普通队列的 FIFO（先进先出）原则，而是优先级最高（或最低）的元素先出队。 直观类比：医院的急诊室——无论谁先到，病情最重的患者优先就诊。 核心特性 插入（insert / enqueue）：将元素连同优先级一起加入队列 取最值（peek）：查看优先级最高的元素，不移除 取出最值（poll / dequeue）：取出并移除优先级最高的元素 不保证全局有序：内部结构只保证堆顶（最值）正确，其余元素顺序不确定 内部实现：二叉堆 绝大多数语言的标准库都用**二叉堆（Binary Heap）**实现优先级队列。 堆的结构 用完全二叉树表示，通常以数组存储 最小堆（Min-Heap）：父节点 ≤ 子节点，根为最小值 最大堆（Max-Heap）：父节点 ≥ 子节点，根为最大值 数组索引关系（从 0 开始）： 节点 索引 父节点 (i-1) / 2 左子节点 2*i + 1 右子节点 2*i + 2 核心操作：上浮与下沉 上浮（Sift Up）：插入新元素时，将其放在数组末尾，然后与父节点比较，不满足堆性质则交换，直到满足为止。 下沉（Sift Down）：取出堆顶后，将末尾元素移到堆顶，然后与子节点比较，不满足堆性质则与较小（或较大）的子节点交换，直到满足为止。 时间复杂度 操作 时间复杂度 插入 $O(\log n)$ 取出最值 $O(\log n)$ 查看最值 $O(1)$ 建堆（heapify） $O(n)$ 两种变体 最小优先级队列（Min Priority Queue） 优先级数值最小的元素最先出队。例如：Dijkstra 最短路径算法中，每次选取距离最小的节点。 最大优先级队列（Max Priority Queue） 优先级数值最大的元素最先出队。例如：任务调度中，优先执行优先级最高的任务。 ...
Raft 一致性算法 raft是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。在这里强调了是在工程上，因为在学术理论界，最耀眼的还是大名鼎鼎的Paxos。但Paxos是：少数真正理解的人觉得简单，尚未理解的人觉得很难，大多数人都是一知半解。 raft的论文，两位研究者也提到，他们也花了很长的时间来理解Paxos，他们也觉得很难理解，于是研究出了raft算法。 raft是一个共识算法 (consensus algorithm），所谓共识，就是多个节点对某个事情达成一致的看法，即使是在部分节点故障、网络延时、网络分割的情况下。这些年最为火热的加密货币 (比特币、区块链）就需要共识算法，而在分布式系统中，共识算法更多用于提高系统的容错性，比如分布式存储中的复制集 (replication），在带着问题学习分布式系统之中心化复制集一文中介绍了中心化复制集的相关知识。raft协议就是一种leader-based的共识算法，与之相应的是leaderless的共识算法。 本文基于论文In Search of an Understandable Consensus Algorithm对raft协议进行分析，当然，还是建议读者直接看论文。 本文地址：https://www.cnblogs.com/xybaby/p/10124083.html raft算法概览 回到顶部 Raft算法的头号目标就是容易理解 (UnderStandable），这从论文的标题就可以看出来。当然，Raft增强了可理解性，在性能、可靠性、可用性方面是不输于Paxos的。 Raft more understandable than Paxos and also provides a better foundation for building practical systems 为了达到易于理解的目标，raft做了很多努力，其中最主要是两件事情： 问题分解 状态简化 问题分解是将"复制集中节点一致性"这个复杂的问题划分为数个可以被独立解释、理解、解决的子问题。在raft，子问题包括，leader election， log replication，safety，membership changes。而状态简化更好理解，就是对算法做出一些限制，减少需要考虑的状态数，使得算法更加清晰，更少的不确定性 (比如，保证新选举出来的leader会包含所有commited log entry） Raft implements consensus by first electing a distinguished leader, then giving the leader complete responsibility for managing the replicated log. The leader accepts log entries from clients, replicates them on other servers, and tells servers when it is safe to apply log entries to their state machines. A leader can fail or become disconnected from the other servers, in which case a new leader is elected. ...
“SkipList, 跳表, 跳跃表” SkipList SkipList(跳表)这种数据结构是由 William Pugh 于1990年在在 Communications of the ACM June 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees，在其中详细描述了他的工作。由论文标题可知，SkipList 的设计初衷是作为替换 平衡树 的一种选择。 我们都知道，AVL树有着严格的O(logN)的查询效率，但是由于插入过程中可能需要多次旋转，导致插入效率较低，因而才有了在工程界更加实用的红黑树。 但是红黑树有一个问题就是在并发环境下使用不方便，比如需要更新数据时，SkipList 需要更新的部分比较少，锁的东西也更少，而红黑树有个平衡的过程，在这个过程中会涉及到较多的节点，需要锁住更多的节点，从而降低了并发性能。 SkipList还有一个优势就是实现简单，SkipList的实现只花了2个小时，而红黑树，我可能得2天。 时隔将近三十多年，SkipList 这种数据结构仍在许多途径有用武之地，比如Redis, 还有Google的著名项目 Bigtable, leveldb 原理及实现 其实跳表就是在普通单向链表的基础上增加了一些索引，而且这些索引是分层的，从而可以快速地查的到数据。 比如我们要查找key为19的结点，那么我们不需要逐个遍历，而是按照如下步骤: 从header出发，从高到低的level进行查找，先索引到9这个结点，发现9 < 19,继续查找(然后在level==2这层)，查找到21这个节点，由于21 > 19, 所以结点不往前走，而是level由2降低到1 然后索引到17这个节点，由于17 < 19, 所以继续往后，索引到21这个结点，发现21>19, 所以level由1降低到0 在结点17上，level==0索引到19,查找完毕。 如果在level==0这层没有查找到，那么说明不存在key为19的节点，查找失败 https://zhuanlan.zhihu.com/p/33674267 skiplist, 红黑树 skiplist 的复杂度和红黑树一样，而且实现起来更简单。 在并发环境下红黑树在插入和删除时需要 rebalance，性能不如跳表。 http://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.html
“延时队列” https://zhuanlan.zhihu.com/p/266156267 延迟队列 首先，队列这种数据结构相信大家都不陌生，它是一种先进先出的数据结构。普通队列中的元素是有序的，先进入队列中的元素会被优先取出进行消费； 延时队列相比于普通队列最大的区别就体现在其延时的属性上， 普通队列的元素是先进先出，按入队顺序进行处理， 而延时队列中的元素在入队时会指定一个延迟时间，表示其希望能够在经过该指定时间后处理。从某种意义上来讲，延迟队列的结构并不像一个队列，而更像是一种以时间为权重的有序堆结构。 应用场景 我在开发业务需求时遇到的使用场景是这样的，用户可以在小程序中订阅不同的微信或者 QQ 的模板消息，产品同学可以在小程序的管理端新建消息推送计划，当到达指定的时间节点的时候给所有订阅模板消息的用户进行消息推送。 这里不太懂…. 把要发送的模板消息加到延时队列里？ 如果仅仅是服务单一的小程序，那也许起个定时任务，或者甚至人工的定时去执行能够最便捷最快速的去完成这项需求，但我们希望能够抽象出一个消息订阅的模块服务出来给所有业务使用，这时候就需要一种通用的系统的解决方案，这时候便需要使用到延迟队列了。 除了上述我所遇到的这样的典型的需求以外，延迟队列的应用场景其实也非常的广泛，比如说以下的场景: 新建的订单，如果用户在 15 分钟内未支付，则自动取消。 公司的会议预定系统，在会议预定成功后，会在会议开始前半小时通知所有预定该会议的用户。 安全工单超过 24 小时未处理，则自动拉企业微信群提醒相关责任人。 用户下单外卖以后，距离超时时间还有 10 分钟时提醒外卖小哥即将超时。 对于数据量比较少并且时效性要求不那么高的场景，一种比较简单的方式是轮询数据库，比如每秒轮询一下数据库中所有数据，处理所有到期的数据，比如如果我是公司内部的会议预定系统的开发者，我可能就会采用这种方案，因为整个系统的数据量必然不会很大并且会议开始前提前 30 分钟提醒与提前 29 分钟提醒的差别并不大。 但是如果需要处理的数据量比较大实时性要求比较高，比如淘宝每天的所有新建订单 15 分钟内未支付的自动超时，数量级高达百万甚至千万，这时候如果你还敢轮询数据库怕是要被你老板打死，不被老板打死估计也要被运维同学打死。 按时间戳排序，每秒查询15分钟之内创建的订单? 这种场景下，就需要使用到我们今天的主角 —— 延迟队列了。延迟队列为我们提供了一种高效的处理大量需要延迟消费消息的解决方案。那么话不多说，下面我们就来看一下几种常见的延迟队列的解决方案以及他们各自的优缺点。 实现方案 Redis ZSet 我们知道 Redis 有一个有序集合的数据结构 ZSet，ZSet 中每个元素都有一个对应 Score，ZSet 中所有元素是按照其 Score 进行排序的。 那么我们可以通过以下这几个操作使用 Redis 的 ZSet 来实现一个延迟队列: 入队操作: ZADD KEY timestamp task, 我们将需要处理的任务，按其需要延迟处理时间作为 Score 加入到 ZSet 中。Redis 的 ZAdd 的时间复杂度是O(logN)，N是 ZSet 中元素个数，因此我们能相对比较高效的进行入队操作。 起一个进程定时 (比如每隔一秒) 通过 ZRANGEBYSCORE 方法查询 ZSet 中 Score 最小的元素，具体操作为: ZRANGEBYSCORE KEY -inf +inf limit 0 1 WITHSCORES ...
循环冗余校验 (CRC) 从奇偶校验说起 所谓通讯过程的校验是指在通讯数据后加上一些附加信息，通过这些附加信息来判断接收到的数据是否和发送出的数据相同。比如说RS232串行通讯可以设置奇偶校验位，所谓奇偶校验就是在发送的每一个字节后都加上一位，使得每个字节中1的个数为奇数个或偶数个。比如我们要发送的字节是0x1a，二进制表示为0001 1010。 采用奇校验，则在数据后补上个0，数据变为0001 1010 0，数据中1的个数为奇数个 (3个) 采用偶校验，则在数据后补上个1，数据变为0001 1010 1，数据中1的个数为偶数个 (4个) 接收方通过计算数据中1个数是否满足奇偶性来确定数据是否有错。 奇偶校验的缺点也很明显，首先，它对错误的检测概率大约只有50%。也就是只有一半的错误它能够检测出来。另外，每传输一个字节都要附加一位校验位，对传输效率的影响很大。因此，在高速数据通讯中很少采用奇偶校验。奇偶校验优点也很明显，它很简单，因此可以用硬件来实现，这样可以减少软件的负担。因此，奇偶校验也被广泛的应用着。 奇偶校验就先介绍到这来，之所以从奇偶校验说起，是因为这种校验方式最简单，而且后面将会知道奇偶校验其实就是CRC 校验的一种(CRC-1)。 累加和校验 另一种常见的校验方式是累加和校验。所谓累加和校验实现方式有很多种，最常用的一种是在一次通讯数据包的最后加入一个字节的校验数据。这个字节内容为前面数据包中全部数据的忽略进位的按字节累加和。比如下面的例子: 我们要传输的信息为: 6、23、4 加上校验和后的数据包: 6、23、4、33 这里 33 为前三个字节的校验和。接收方收到全部数据后对前三个数据进行同样的累加计算，如果累加和与最后一个字节相同的话就认为传输的数据没有错误。 累加和校验由于实现起来非常简单，也被广泛的采用。但是这种校验方式的检错能力也比较一般，对于单字节的校验和大概有1/256 的概率将原本是错误的通讯数据误判为正确数据。之所以这里介绍这种校验，是因为CRC校验在传输数据的形式上与累加和校验是相同的，都可以表示为: 通讯数据 校验字节 (也可能是多个字节) CRC 算法 CRC 算法的基本思想是将传输的数据当做一个位数很长的数。将这个数除以另一个数。得到的余数作为校验数据附加到原数据后面。还以上面例子中的数据为例: 23、4 可以看做一个2进制数: 0000011000010111 00000010 假如被除数选9，二进制表示为: 1001 CRC即循环冗余校验码 (Cyclic Redundancy Check) : 是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。循环冗余检查 (CRC) 是一种数据传输检错功能，对数据进行多项式计算，并将得到的结果附在帧的后面，接收设备也执行类似的算法，以保证数据传输的正确性和完整性。 CRC32简介 CRC校验实用程序库 在数据存储和数据通讯领域，为了保证数据的正确，就不得不采用检错的手段。在诸多检错手段中，CRC是最著名的一种。CRC的全称是循环冗余校验。 CRC32检错能力极强，开销小，易于用编码器及检测电路实现。从其检错能力来看，它所不能发现的错误的几率仅为0.0047%以下。从性能上和开销上考虑，均远远优于奇偶校验及算术和校验等方式。因而，在数据存储和数据通讯领域，CRC无处不在：著名的通讯协议X.25的FCS (帧检错序列）采用的是CRC-CCITT，ARJ、LHA等压缩工具软件采用的是CRC32，磁盘驱动器的读写采用了CRC16，通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。 crc golang m_data := []byte{0x01,0x02,0x03,0x04} //创建Byte切片 checksum := CheckSum(m_data) //调用计算CRC函数 CheckSum fmt.Printf("check sum:%X \n",checksum) https://blog.csdn.net/liyuanbhu/article/details/7882789 ...