“无序的环状链表要么使用额外的哈希表存储已经遍历过的 item，要么使用双指针增加遍历范围直至指针重合而退出”
不对吧，只要和列表头的地址比较不就好了，如果和头一致就说明遍历结束
换句话说，插入一个 dummy node

@fenglangjuxu 如果你需要的是高并发系统，那我非常怀疑你是否真的需要绝对的 C 。
同时我也很怀疑你是否真的应该用分布式锁实现这个目的。你去看实际生产中用的多的分布式的储存系统，以高性能为卖点的，其中有多少是强一致，又有多少用的是锁。不用锁，也有很多办法能保证程序的正确与高效，如何选择合适的分布式算法，这需要相关领域的知识。
该请人的时候就得请人。

@itskingname
@trlove
非常同意
我是材料工程和 CS 双学位。目前也是从事系统底层的工作，实践为主。说几个事情，恶心一下楼主：
1. 工程课教授：c 是一个经验常数，一般取 3
2. 工程课教授：这个公式的结果通常比实际稍大，但是没关系，我们下一步会取 10 倍安全余量
3. 工程课教授：这一大坨公式我们直接约等于 3
4. 老板：这个 corner case 你先别管，上线再说
5. 老板：这个 bug 我们都知道，但是很少见而且后果很小，先不修它
6. 老板：灰度上线跑了一个月了，有没有问题？没问题我们就放量了。
7. 我们之前都好好的啊，怎么到你这里就出 bug 了？

楼主呢，无非是想掉个书袋子，秀秀优越感。诚然，瞎 JB 用的傻逼是有，还不在少数。但是：
1. 如我楼上所说，垃圾文章到处都有，不局限于中文
2. 工程实现很多时候就是这么脏
3. 闻道有先后，术业有专攻

@Blueming 证明有 bug 很简单：举出一个 bug 就行。证明没有 bug 则是恶魔的证明。除非形式化论证，否则无法保证没有 bug 。
ZK 和 ETCD 是有设计模型的。虽然代码可能有 bug，但算法理论上是没问题的。
而 Redlock 的算法设计就是没有 C 的。

@sampeng Google：distributed lock library
1. Distributed locks with Redis – Redis
2. madelson/DistributedLock: A .NET library for ... - GitHub
其中 Redis 部分就是 Redlock
3. Kleppmann's blog 之前提到的
4. Everything I know about distributed locks | by Davide Cerbo
推荐了 ShedLock, 和 ZK 、ETCD 没细看 ShedLock，但是看起来不是 Redlock 衍生物
5. Distributed lock manager - Wikipedia
Redis can be used to implement the Redlock Algorithm for distributed lock management.[10]
呵呵
6. The Top 7 Distributed Locks Open Source Projects
猜猜 Redlock 出现了几次
7. Distributed Locks are Dead; Long Live Distributed Locks
看起来是没啥问题。
8. Everything I Know About Distributed Locks - DZone Database
和 4 一样
9. Building Distributed Locks with the DynamoDB Lock Client
没有细看。看到 heartbeat every 10 seconds 就说明和 Redlock 是一个意思
10. distributed locking - npm search
猜猜这里面有几个 redis ？又有几个 Redlock ？

这就是 Google 第一页。你觉得这够不够垃圾？
垃圾文哪都有，英文社区也不比中文社区少。

至于多少钱需要考虑可靠性的问题，我就提几个：
1. 阿里抢月饼
2. 2010 flash crash，有一说是高频交易程序出 bug，或者 fat finger，然后触发做市商程序挂起。请问这种事情是多少概率？
3. Ariane 5，就问这个 bug 贵不贵？
事实就是，这个世界并不是这么的可靠。有相当多的人其实根本无法理解其重要性。同时也有相当多的人理解但选择忽视。当然咱不是故意去写 bug 。但是如果一共也就几万块钱的系统，管的是不那么重要的东西，你觉得老板会希望你多花一个月时间去实现一个可以提供形式验证的软件吗？你一个月工资也要几千了。
还有电商搞促销活动，抢占市场重要还是不被撸 bug 重要？大不了事后砍单就是了。甚至还有故意塞漏洞就是吸引你来撸的。
任何事情，都有其机会成本。实践中，重点不是绝对无 bug，而是在某些关键节点做好 damage control，同时完善日志，确保出了问题以后能够查到原因。很多时候，这就够了。

@Makuma 要证明不安全只需要一个反例。
要证明安全则必须要靠推导。所以真的需要绝对正确的软件，那得先写出数学推导，然后把数学算法转换成代码，再证明数学模型和代码等价。这样做是可以保证没用 bug 的（只要硬件不出问题）。

当然，实际上需要这么干的软件非常非常少。大部分程序员就是写几个 test case，然后上线的时候灰度上线就算了。如果真的是这个行业的人，也不可能不看文档，只看一篇百度就瞎 JB 用。

@nagatoism 你说的垃圾技术文章问题，和中文无关。英文的垃圾文章也多了去了。只不过作为中文 native speaker，既然都在看英文文章了，大部分还是会去看官方文档的人。Aka，英文是个门槛。
但是如果完全脱离中文，直接就搜英文，你有非常大的概率会搜到垃圾英文文章。
比如有人今天手上就有个 redis，就想要个锁，你猜 Google 第一条是啥？
这是中文的锅吗？这明明是不看文档的锅。

@nagatoism
@sampeng
1000 万美金的系统还用 Redlock 那是自己作死。人家文档里都说了无法保证 C，不看文档能怪谁。上千万的系统没个设计文档没个安全审计，逗谁呢？都搞上千万的分布式系统了，还请不起一个专业搞分布式的来审计一下算法？技术负责人干什么用的？就是拍板负责用的啊。谁是老板谁负责。

什么情况下可以用？
1. 东西不值钱，不存在你说的 1000 万。
2. 活该傻逼不看文档
3. 不要求强一致，再维护一套 ZK 集群又太麻烦。比如楼上某些人提到的，第三方 API 限制频率。偶尔 miss 一次不是不能接受，但是不挡一下又不好。既然已经在用 Redis，那用个现成的 Redlock 实现也是顺理成章的事情。

说到底：不看文档就瞎用自己不懂的算法那就是活该。谁用谁负责。

@pisc 我也再最后重复一次：逻辑上全局一致的时间戳是可以实现的。linearizability 也是可以实现的。
但是你不可能在一个分布式的储存系统里，在处理请求的瞬间就确定，这是最新的 token 。
Martin 的文章里自己就写了。我说的和 Martin 说的不矛盾，OK ？所以他文中 making the lock safe with fencing 的方法是无效的。而他就是为了说明这个方法无效而写的这一段。

@sprite82 p 不是 performance，是 partition safety 。
你说的性能问题其实并不是 cap 三者任一。或者，最多就是和 a 沾点边。但是 a 只要系统不死锁，再慢都是合格的。
为了性能的分布式系统通常会适当放弃 C，比如设计模型就是实现最终一致性。

然后你说的节点挂掉的问题，其实也不是绝对的。通常是保证过半节点存活时，系统还可以保证 A 。如果不过半的话真的很难保证 P 。

@pisc 我上面就说了，全局时间戳是可以实现的，但全局时钟是不存在的。靠全局时间戳常见是实现最终一致性。
你在写入的瞬间无法知道这个写入是否成功。而是只能事后再去观测系统的状态。Martin 自己都说了，这个前提是 database 能够做到 reject 过期 token，问题是怎么实现呢？如果你可以实现这一点，你从一开始就不需要分布式锁。

我觉得一个程序员应该有阅读文档的能力并为理解一个算法的局限性。你说警告，Redis 的官方文档里是有警告的。

@nagatoism 我理解他的话。但是这是设计系统时瞎 jb 用算法而不看说明的锅，而不是算法没有做到 promise 。我们俩的意思是一样的，但是角度不同。我的意思是这个问题无解，但是算法在适当的情况下还是可以用。你和 Martin 的意思是这个问题无解，所以应该用其他算法。

@liudaolunhuibl 但是放弃 A 还是放弃 C，不是你所决定。具体系统设计要具体看待。
Martin 的意思是，既然你都用上分布式锁了，你也就别指望啥性能了。A 保也是白保，不如放弃 A 保 C，搞个强一致。
你要是能接受弱一致，大概率是不需要全局锁的。

@nagatoism 然而没有 c 的分布式系统却很正常。
你要放弃 a 或者 p 去换 c 可以。用别的算法就行了。
我说的，martin 指出的问题是真实存在的。但他提出的解是无效的。
如果你觉得他提出的解有效，不妨找个实现出来。即可以 reject 旧 token 的分布式储存系统。

@pisc 分布式系统中不存在一致的全局时钟，这是基本的基本。
但是可以有算法实现全局一致的时间戳。但这个时间戳是只有事后才会知道。而你不可能知道现在是什么时间。
换句话说，Martin 提出的，数据库自动拒绝无效的 token，这是无法做到的。

实践中，分布式的储存系统可以选择 eventual consistency 。而不依赖全局锁。

至于 cap 的取舍，这得看需求。你怎么就钦定了 a 就比 c 重要呢？小白 p 都不懂那就不该瞎 jb 用。就这么简单。用户 p 都不懂就得给用户擦屁股？ redlock 那篇文章一开始就写了时间限制，自己不看说明还怪别人？

@Zzdex 博士又怎么了。隔行如隔山。他又不是搞分布式系统的，至少简历上不是。
但凡学过点分布式都知道分布式系统的 cap 定理。Martin 那篇文章就是外行什么都想要。
redlock 的说明里就写了，它所提供的是有限时间的 correctness 。自己程序 gc 时间太长这是实现的问题而不是算法的问题。

@liudaolunhuibl Martin 提出的问题是真实存在的，但是是无解的。
他提出的解决方法是无效的。
他提出，由服务器维护一个计数器，然后 request 只有携带比当前计数器高的 token 才能被执行。

那么问题是，谁来维护这个计数器呢？如何维护这个计数器呢？如何保证这个全局计数器的 cap 呢？如果有办法实现这个计数器，那直接找服务器要 token 不就完事了，有什么必要用另一个锁呢？

这就有点 ex machina 的味道了。搞不定某问题，直接假设一个神奇的全局一致计数器，然后说问题解决了.

@emSaVya
@monsterxx03
如果你们说的系统时钟问题是指系统时间可能前后调整，那么你们的担心是不必要的。CLOCK_MONOTONIC 是基于硬件时间，通常是开机时间，调整系统时间不影响。
开机时间够用了，因为你不是真的在乎现在是几点几分，只是在检测时间是否流逝而已。

@iseki “感觉这个问题根本是逻辑上不能避免的”
正解，cap 定理决定了总得放弃一个

@lxy42 其实 ntp 不是问题。用 CLOCK_MONOTONIC 就可以，基于机器时间而无关实际时钟
然后分布式一致性就是有 cap 问题，不可能什么都要。cap 总得适当放松一个。这里我们选择适当放松 c，仅此而已
如果要保证 c 放弃 a 那也好办啊：不设置超时。虽然这个算法没什么用而已。

国外读书，毕业直接就业
留学生优先是因为 1. 很明显语言水平没有问题
2. 留学生毕业通常有一段工作签 /实习期。
这一点在美国尤为重要。因为 h1b 不仅要等到次年 10 月，还需要抽签。留学生可以用 opt 工作然后慢慢抽 h1b 。同时美国研究生学历抽签有加成。

@bowser1701 因为你不应该关心。OSI 分层就是为了隔离实现细节。底层实现可以自由选择分几个包。我写个内核模块。一个包一字节，或者一个包发三次，应用层都不应该有正确性的问题，因为无论底层分几个包发几次，对应用层来说，只要提供了“可靠的字节流”这一功能，就是正确的协议。

上层关心底层实现的情况通常是性能调优。

@LeeReamond 问题一二已在 1 楼的链接给出。
问题三的答案就是“TCP 是字节流”