Paper Note: Time, clocks, and the ordering

Happened Before 关系 论文先从事件之间的 Happened Before 关系开始讲起 结合上图我们举例解释一下「Happened Before」关系: 同一进程内部先后发生的两个事件之间,具有「Happened Before」关系。比如,在进程 Q 内部,q_2 表示一个消息接收事件,q_4表示另一个消息的发送事件,q_2 排在 q_4 前面执行,所以 q_2 → q_4。 同一个消息的发送事件和接收事件,具有「Happened Before」关系。比如,p_1 和 q_2分别表示同一个消息的发送事件和接收事件,所以 p_1→ q_2;同理, q_4→ r_3。 「Happened Before」满足传递关系。比如,由 p_1→ q_2, q_2→_q_4和 q_4→ r_3,可以推出 p_1 → r_3。 作者然后说明了并发的概念: Two distinct events a and b are said to be concurrent if a !→ b and b !→ a. 同时作者也描述了与因果性的关系: Another way of viewing the definition is to say that a→b means that it is possible for event a to causally affect event b. Two events are concurrent if neither can causally affect the other. ...

November 4, 2023 · 3 min · KKKZOZ

DDIA: Chapter 8 The Trouble with Distributed Systems

Faults and Partial Failures An individual computer with good software is usually either fully functional or entirely broken, but not something in between. Thus, computers hide the fuzzy physical reality on which they are implemented and present an idealized system model that operates with mathematical perfection. In a distributed system, there may well be some parts of the system that are broken in some unpredictable way, even though other parts of the system are working fine. This is known as a partial failure. The difficulty is that partial failures are nondeterministic: if you try to do anything involving multiple nodes and the network, it may sometimes work and sometimes unpredictably fail. ...

November 2, 2023 · 16 min · KKKZOZ

Talk about Redlock

最近看了下之前业界关于 Redlock 的争论,发现还是挺有意思的,正好把自己最近学的知识串了起来,这里就简单总结一下。 Martin 的观点 使用分布式锁的目的 Martin 表示,你必须先清楚你在使用分布式锁的目的是什么? 他认为有两个目的。 第一,效率。 使用分布式锁的互斥能力,是避免不必要地做同样的两次工作(例如一些昂贵的计算任务)。如果锁失效,并不会带来「恶性」的后果,例如发了 2 次邮件等,无伤大雅。 第二,正确性。 使用锁用来防止并发进程互相干扰。如果锁失效,会造成多个进程同时操作同一条数据,产生的后果是数据严重错误、永久性不一致、数据丢失等恶性问题,就像给患者服用了重复剂量的药物,后果很严重。 他认为,如果你是为了前者——效率,那么使用单机版 Redis 就可以了,即使偶尔发生锁失效(宕机、主从切换),都不会产生严重的后果。而使用 Redlock 太重了,没必要。 而如果是为了正确性,Martin 认为 Redlock 根本达不到安全性的要求,也依旧存在锁失效的问题。 NPC 问题 这些异常场景主要包括三大块,这也是分布式系统会遇到的三座大山:NPC。 N:Network Delay,网络延迟 P:Process Pause,进程暂停(GC) C:Clock Drift,时钟漂移 Martin 用一个进程暂停(GC)的例子,指出了 Redlock 安全性问题: 客户端 1 请求锁定节点 A、B、C、D、E 客户端 1 的拿到锁后,进入 GC(时间比较久) 所有 Redis 节点上的锁都过期了 客户端 2 获取到了 A、B、C、D、E 上的锁 客户端 1 GC 结束,认为成功获取锁 客户端 2 也认为获取到了锁,发生「冲突」 ...

November 2, 2023 · 5 min · KKKZOZ

Paper Note: Chubby

FAQ What is an advisory lock? An “advisory lock” is simply a tool/API provided by Postgres to create arbitrary locks that can be acquired by applications. These locks, however, are not enforced in any meaningful way by the database – it’s up to application code to give them meaning (the same way any other non-database distributed lock would work). What is a write-through cache? A write-through cache is a caching strategy where data is simultaneously written into the cache and the corresponding database or backing store. ...

October 31, 2023 · 6 min · KKKZOZ

Paper Note: BigTable

FAQ What is a single-row transaction? 在 Bigtable 变更(例如读取、写入和删除请求)中,行级更改始终属于原子操作。这包括对单行中的多个列进行的变更,前提是它们包含在同一变更操作中。Bigtable 不支持以原子方式更新多个行的事务。 但是,Bigtable 支持某些需要在其他数据库中执行事务的写入操作。实际上,Bigtable 使用单行事务来完成这些操作。这些操作包括读取和写入操作,且所有读取和写入均以原子方式执行,但仍然只是在行级的原子操作: 读取-修改-写入 (Read-modify-write) 操作(包括增量和附加)。在读取-修改-写入 (read-modify-write) 操作中,Cloud Bigtable 会读取现有值,对现有值进行增量或附加操作,并将更新后的值写入表中。 检查并更改 (Check-and-mutate) 操作(也称为条件更改或条件写入)。在检查并更改 (check-and-mutate) 操作中,Bigtable 会对行进行检查以了解其是否符合指定条件。如果符合条件,Bigtable 则会将新值写入该行中。 What is SSTable format? SSTable (Sorted Strings Table) is a file format used in Apache Cassandra, a popular NoSQL database. An SSTable is a data structure that provides a persistent, ordered immutable map from keys to values, where both keys and values are arbitrary byte streams. It contains a series of key-value pairs sorted by keys, which enables efficient lookup and range queries. It’s used to store and retrieve data in a highly optimized manner. The SSTable also supports internal indexing, which makes accessing a particular data point faster. ...

October 30, 2023 · 5 min · KKKZOZ