Lecture 4 Semantics | newrain-zh博客

type

status

date

slug

summary

At-Least-once

至少一次

requires operation idempotency 需要操作具有幂等性

example: read() request on locked object or read-only object

example: current_stock_price(MSFT)

Semantics of operation allows any valid price after issue of request of request to be returned 操作语义允许在发出请求后返回任何有效价格

implementation can be completely stateless on server side 在服务器端可以实现完全无状态

even sequence numbering to detect duplication can be avoided 甚至可以避免为检测重复而进行序列编号

exactly-once > at-most-once > at-least-once

Safety and Liveness Properties

安全性和活性

Together , safety properties confirm that bad things don’t happen 安全性能共同确保坏事不会发生

Liveness property: characterizes timely execution progress

(e.g.,”This code is deadlock-free”) (例如，"本代码无死锁"）。

(e.g.,”This code is starvation-free”) (例如，"本代码无饥饿"）。

Together ,liveness properties confirm that “good things will eventually happen” 这些特性共同证实了 "好事终会发生"。

“Exactly-once Semantics” → safety property

Existence of timeout in at-most-once RPC → liveness property 最多一次 RPC 中超时的存在 → 活性属性

Real-world design has to balance safety and liveness 现实世界的设计必须权衡安全性和活性

📑

Safety（安全性） 和 Liveness（活性） 是两个最基础且正交的系统属性概念，由 Leslie Lamport 首次明确定义。它们构成了分布式算法设计的基石，理解其区别至关重要：

Safety："坏的事情永远不会发生"即系统在任何执行过程中永远不会进入非法状态，（简单理解为强一致性）

Liveness："好的事情终将发生"即系统最终会达到期望状态（但不确定何时发生）（简单理解为最终一致性）

示例：

Kafka 消费者组:

Safety: 每个分区只被一个消费者实例占用 (防重复处理)

Liveness: 消费者故障后，分区最终会重新分配；滞后消息最终被消费

Placement of Functionality

What are you promising versus what can you deliver?

aka “Protocol Layering” 又名 "协议分层

What Can TCP Do For RPC?

TCP timeout → we still have to reconnect

new TCP connection unaware of old 新的 TCP 连接不知道旧的 TCP 连接

→ server must keep higher level sequence #s 服务器必须保持更高级别的顺序

server must do duplicate elimination 服务器必须消除重复

orphans still possible 孤儿计算仍然有可能

exactly-once RPC no easier with TCP

TCP can simplify at-most-once RPC TCP 可简化最多一次的 RPC

if timeouts are rare , handing can be out of band(e.g phone call)

avoids need to implement retransmission and duplicate elimination

absence of TCP failure ⇒ exactly-once RPC 没有 TCP 故障 ⇒ 恰好一次 RPC

on TCP failure , declare RPC failure(at most once RPC) TCP失败时，声明RPC失败（最多一次RPC）

higher level(e.g. user) invokes out of band mechanism to handle failure 更高级别（例如用户）调用带外机制来处理故障

即使基于 TCP 去实现 exactly-once RPC 也是一件困难的事情。

Use of TCP hurts best-case performance 使用 TCP 会损害最佳性能

TCP uses independent acks in each direction TCP在每个方向上使用独立的ACK

client→server: request; server→client:ack
server→client:reply; client→server:ack

4 packets for best case

but RPC on UDP only uses 2 packets!

reply is an implicit ack

End-to-End Reasoning

端到端论证

Layering RPC transport on TCP rather than UDP 在TCP而不是UDP上分层RPC传输

does not simplify exactly-once implementation 不简化 exactly-once 实现

worsens performance in best case 在最佳情况下会降低性能

does simplify at-most once implementation 最多简化至多一次实现

This is an example of and end-to-end argument

most important structuring principle for distributed systems 分布式系统最重要的结构原则

helps designer place functionality in modules 帮助设计者在模块中放置功能

For given functionality (typically pertaining to safety)

correctness is expressed relative to two endpoints(safety) 正确性是相对于两个端点（安全）而言的

implementation requires support of those two end points 实现需要支持这两个端点

support below end points cannot suffice

at best, lower-level support many improve performance(liveness)

论文： End-To-End Arguments in System Design

在许多情况下，底层机制能够提供性能优化的可能性，它们还能使代码变得更加简洁。

Example: Large file Transfer

Consider transfer of larger file

network unreliable

remote processor and software unreliable

Method 1

ship entire file via TCP(which has ACKS in its implementation) 通过 TCP 发送整个文件（其实现中有 ACKS）

write file to disk at remote site 将文件写入远程站点的磁盘

crash can occur during disk write 磁盘写入时可能发生崩溃

hence TCP’s guarantees count for little 因此，TCP 的保证意义不大

higher level confirmation needed 需要更高级别的确认

ship back file (or checksum) and compare 运回文件（或校验和）并进行比较

Method 2

blast entire file via UDP 通过 UDP 发送整个文件

write file to disk at remote site 将文件写入远程站点的磁盘

read back file , blast back file(or checksum) via UDP to first site 读回文件，通过 UDP 将文件（或校验和）发送到第一个站点

compare original file with returned file (or compare checksums) 比较原始文件和返回文件（或比较校验和）

match guarantees successful transmission! 匹配可确保成功传输！

Benefit of Method1 方法1的好处

only missing parts of file need to be reshipped 只需重新发送文件的缺失部分

results in better performance on flaky links 在链路不稳定时性能更佳

in other words , better worst-case performance 换句话说，更好的最差表现

Why are Distributed Systems Slow?

Processing delay

Queueing delay

Transmission delay

Iron Law of Queueing Theory

排队理论的铁律

for any shared resource

Utilization(利用率) (aka ”efficiency”: % use of CPU , network ,disk , etc.)

Latency（延迟）（aka “response time” or “agility”: user experience）响应时间

Freedom (自由度) (arrival discipline : orchestrated or un-ochestrated )

You can optimize at most 2 out of 3

you can’t have all 3 no amount of cleverness helps best you can achieve is satisfactory traedoff

最多可以优化 3 项中的 2 项，无法同时优化 3 项。

如果优化 1、3，那么付出的代价是 2 ，依次类推…