书接上文 - Multi Paxos

在上一篇文章中，我们提到了Basic Paxos和Multi Paxos的异同。在Paxos Made Simple论文中，作者提到了Multi Paxos的一种实现。这个实现允许我们对一个连续的数 …

一致性协议 - Paxos

在分布式系统当中，我们往往需要保持节点之间的一致性。在绝大多数情况下，我们需要让系统中的节点相 …

背景

之前一直在用七牛云的存储做图床（简称白嫖）。但是免费的午餐必然不会长久，七牛要求所有bucket都要绑定备案过的域名，否则就停掉你的bucket的外链。这 …

什么是容斥原理

容斥原理是一种计数手段。例如在下图中，我们想不重复、不遗漏的求出包含在ABC三个集合中所包含的元素的个数，应该使用怎么样的方法 …

240414更新：后续补充了一篇勘误文章，见这里

目标

实现一个多读多写的无锁消息队列。

cmpxchg - 比较并替换

比较并替换（compare-and-swap, CAS）是一个用于 …

Update[220504]: 原来这种数据结构叫珂朵莉树啊，真神奇。。。

我们要解决什么问题

区间交问题，是我们在做题中经常遇到的问题。

例如，Insert …

ARS 与 Bw-Tree

nosql数据库从本质上说，都属于ARS（Atomic Record Stores，“原子记录存储”）。

最常见的“原子记录存储”一种实现就是朴素的Hash表：通过一个特定的key，来读写一条 …

加机器就是一把梭

没有什么问题是加一千台机器解决不了的，如果有，就再加一千台。
—— 《21天精通分布式系统》

分布式系统在设计之初，是为了解 …

throughput and window size

The wisdom of STUP protocol is all about the window size. The throughput of a TCP communication is limited by two windows: the congestion window and the receive window. The congestion window can determine how many bytes that can be send a simple piece of time …

STUP Packet Structure

Brief Introduction of TCP & UDP Packet Structure

STUP pretend itself as a protocol at the Transmission Layer, but actually it’s absolutely an Application Layer protocol. So before we start, I’d like to recall some knowledge of two important Transmission Layer protocol: TCP & UDP.

It is …