DDIA Ch8

Unreliable Clocks

这一章重点就是clock synchronization is tricky (even for NTP) there is leap second etc

主要是VM的问题，因为VM通常是由host来分配时间片，那么咋没有轮到他的时候，他的clock是虚拟的，然后轮到他的时候他就会看到自己的时间jump forward

• In virtual machines, the hardware clock is virtualized, which raises additional challenges for applications that need accurate timekeeping [50]. When a CPU core is shared between virtual machines, each VM is paused for tens of milli‐ seconds while another VM is running. From an application’s point of view, this pause manifests itself as the clock suddenly jumping forward

这一段话很好的总结了第八章前一段都在说什么

So far in this chapter we have explored the ways in which distributed systems are different from programs running on a single computer: there is no shared memory, only message passing via an unreliable network with variable delays, and the systems may suffer from partial failures, unreliable clocks, and processing pauses.

Knowledge, Truth, and Lies

The Truth Is Defined by the Majority

在分布式系统中，事实都是有大多数node 决定的，通过quorum （最少需要人数来确认一件事是否valid）来进行

Instead, many distributed algorithms rely on a quorum, that is, voting among the nodes：decisions require some minimum number of votes from several nodes in order to reduce the dependence on any one particular node.

Fencing tokens

![[DDIA-Figure-8-4.png]]
这张图就很好的解释了fencing token，所以不需要其他的论述了
跟snapshot isolation 是一个思想，就是用一个单调递增的id来看你的transaction是否valid

Byzantine Faults

这个问题就是当node故意犯错，

Distributed systems problems become much harder if there is a risk that nodes may "lie" (send arbitrary faulty or corrupted responses)--for example, if a node may claim to have received a particular message when in fact it didn't. Such behavior is known as a , and the problem of reaching consensus in this untrusting environment is known as the

The Byzantine Generals Problem is a generalization of the so-called Two Generals Problem, which imagines a situation in which two army generals need to agree on a battle plan. As they have set up camp on two different sites, they can only com‐ municate by messenger, and the messengers sometimes get delayed or lost (like pack‐ ets in a network)

所以拜占庭将军问题是一个generalized version of

In the Byzantine version of the problem, there are n generals who need to agree

从两个generalized 成n个

System Model and Reality

分布式算法也是建立在System Model 上面的，它assume certain kinds of faults are expect to happen

We do this by defining a , which is an abstraction that describes what things an algorithm may assume

Synchronous model

The synchronous model assumes bounded network delay, bounded process pauses, and bounded clock error. This does not imply exactly synchronized clocks or zero network delay; it just means you know that network delay, pauses, and clock drift will never exceed some fixed upper bound [88]. The synchronous model is not a realistic model of most practical systems, because (as discussed in this chapter) unbounded delays and pauses do occur.

Spanner 应该就是Synchronous Model

Partially synchronous model

Partial synchrony means that a system behaves like a synchronous system most of the time, but it sometimes exceeds the bounds for network delay, process pauses, and clock drift [88]. This is a realistic model of many systems: most of the time, networks and processes are quite well behaved—otherwise we would never be able to get anything done—but we have to reckon with the fact that any timing assumptions may be shattered occasionally. When this happens, network delay, pauses, and clock error may become arbitrarily large.

大多数分布式是这种model？

Asynchronous model

In this model, an algorithm is not allowed to make any timing assumptions—in fact, it does not even have a clock (so it cannot use timeouts). Some algorithms can be designed for the asynchronous model, but it is very restrictive.

Common System model for nodes

Crash-stop faults

就是说这个model assume node只会crash，所以一旦node 没有反应，我们认为它就不会恢复了

In the crash-stop model, an algorithm may assume that a node can fail in only one way, namely by crashing. This means that the node may suddenly stop responding at any moment, and thereafter that node is gone forever—it never comes back.

Crash-recovery faults

这个model assume node 任何时候都可能crash， 并且之后可能会自我恢复（unknown time) In this model, nodes are assumed to have stable storage (这里就是说node 可以恢复，因为有stable storage) that is preserved across crashes, while the in-memory state is assumed to be lost.

We assume that nodes may crash at any moment, and perhaps start responding again after some unknown time. In the crash-recovery model, nodes are assumed to have stable storage (i.e., nonvolatile disk storage) that is preserved across crashes, while the in-memory state is assumed to be lost.

Byzantine(arbitrary) faults

Nodes may do absolutely anything, including trying to trick and deceive other nodes, as described in the last section.

大多数分布式系统就用 paritially sync 跟 crash-recovery model 就可以了

Proving an algorithm correct does not mean its implementation on a real system will necessarily always behave correctly.

总结

这一章讨论了分布式系统经常会出现的问题， 包括：

1. network问题 (packet loss, delayed, reply loss, deplayed)
2. node's clock may be significantly out of sync with other nodes (despite your efforts to set up NTP)
3. process pause (GC stop the world pause). Then process is declared dead by other nodes and then come back to life without realizing that it was paused

这些partial failures can occur is the defining chaaracteristic of distributed systems.

Whenever software tries to do anything involving other nodes, there is the possibility that it may occasionally fail, or randomly go slow, or not respond at all.

所以分布式系统 build partial failures tolerance into software. So that the system as a whole may continue functioning even when some of its constituent parts are broken.

Detecting

most distributed algorithms use timeouts to determine the remote node is still available.

Quorum

once failure is detected, we need quorum to decide next step because we cannot trust single node to make decision