导论

什么是系统

系统就是指一堆 component，通过一些接口互相连接，和周围的 environment 有一个边 界。系统的定义并没有很清晰，一个系统可能是一个大系统中的子系统。系统是可以不断增加的。 我们发现了很矛盾的地方，系统可以不断增加，但是人的大脑对复杂性的理解是很有限的。如果我们需要搞定每个 component 的工作机制才能去理解，那么大脑是不能理解 的。Linux kernel 几千万行。这时就要用到系统的方法，描述气体分子的属性就需要用到宏观统计量。

超级计算机几百万个 cpu，就会有新的特性。并发几百和几千万对系统的冲击是完全不一样的。

计算机系统的十四个特性

Correctness, Latency, Throughput, Scalability, Utilization, Performance Isolation, Energy Efficiency, Consistency, Fault Tolerance, Security, Privacy, Trust, Compatibility, Usability.

Correctness(正确性)

怎么定义一个系统的正确的：做它该做的事情。 其实在实际中是很难定义它的。很难定义是 bug 还是 feature。Eg：在 linux 中以点开头的文 件是隐藏文件 需要 ls -a。

在 C 的规范中，指针的溢出是 undefined behavior，编译器会认为这不会发生这种情况，因此把这段代码删除掉了。

解决方法：强制类型转换为 int，再做操作，再判断溢出，再转化回来。

latency（时延）

系统的时延是很麻烦的事情，因为吞吐量可以通过花钱添加服务器来增加。 但是要缩短每个人访问的时延是很难的，它受限于物理物理原因，哪怕是光速时间延迟也会很大。

Troughput（吞吐量）

一旦我们的芯片密度不能越来越高，它势必会越来越大。一旦物理达 到极限以后，软件的作用也就越来越大。

Scalability

真实的 arm 测试 spin lock，到 12 个核的时候，性能下降了

32 个核的时候和 1 个核的时候差不多，这是因为大家都在抢 spin lock。Spin lock 是内存中的一个 bit。随着 cpu 越多，争抢锁的消耗越大。

performance isolation

Eg：一台机器跑了 benchmark，情况 1：一个人自己跑，情况 2：背后还跑了一个 while(1)， 加上这个 noisy neighbour，影响是对于 99%的 latency 会增加 42%，非常非常 noisy 的情况， latency 会增加 29 倍。虽然 CPU 可以运行多个程序，但是 neighbour 的情况影响是很大的。

Utilization（利用率）

对于云来说，Google 数据中心的 CPU 利用率是 30%。对于要求快速响应的服务器，需 要预留很多资源，所以云端的服务器都开着虽然耗着电，但是利用率并没有拉满。

energy efficiency（节能）

这又是一个 trade-off，数据中心最大的开销是电费（服务器电费、空调电费），尤其现在是碳中和，对用电产生了很大的挑战。在服务质量不变的情况下，怎么压缩用电量。

compatibility（兼容性）

安腾处理器是 inter 从 32 转 64 的重大选择。导致之前所有的 x86 代码都需要重新编译 才能跑

Usability

左边是 window mobile，直到 iphone 第一代出现。用户的易用性也很重要

Consistency

一致性非常重要。为了容错，我们需要多个备份，但是备份之间就会出现数据不一致这个问题，对于支付宝来说，不能接受数据不一致的情况。比如用不同的服务器一笔钱花 了两次或者一个订单扣了两次钱。为了性能一定会有多个副本在多种 cache 中，所以一定会有这个问题

Fault Tolerance

Cisco 路由器厂商的 bug report，由于宇宙辐射造成的 bug。

在我们的内存中，存储模式是先定位行再定位列，内存需要为这一行进行充电操作，在 充电的时候，临近两行的电就会弱一点点。如果我们频繁地读 row1 和 row3 会导致 row2 的 电量下降，下降到一定程度的时候，row2 的 1 就会变成 0

在我们的内存中，存储模式是先定位行再定位列，内存需要为这一行进行充电操作，在 充电的时候，临近两行的电就会弱一点点。如果我们频繁地读 row1 和 row3 会导致 row2 的 电量下降，下降到一定程度的时候，row2 的 1 就会变成 0

Security

以手机为例，里面有一堆关键的数据和账号。内存在掉电之后，数据不会马上丢失。放在非常冷的环境下，可以延缓这个过程。手机内存芯片其实就是一个 SSD，可以直接读只是数据加密了。数据加密的密钥放在 DDM。内存里是明文，加密到硬盘里是密文。现在保护数据基本上是保护硬盘上的数据，而不保护内存上的数据。

Privacy

当我们使用隐私模式浏览网页时，理论上来说，无论在访问网站之前还是之后，用户的本地设备都不会留下任何明显的访问痕迹。然而，在实际运行过程中，如果系统物理内存不足，操作系统可能会通过内存转储（OS dump）或将部分内存数据交换（swap）到硬盘的方式释放内存空间。这些操作不会区分数据的类型，因此隐私模式中的数据也有可能被写入到硬盘中，留下不可避免的痕迹。

Trust

在传统的银行系统中，用户的钱并不是以实物现金的形式存放在银行里。实际上，这些钱只是以数字的形式记录在银行的服务器中，银行依赖自身的信任体系和管理系统来确保资金的流通和使用。这种模式依赖于对银行机构的信任：我们相信银行会妥善管理和兑现我们的资金。

而去中心化的货币（如比特币等）进一步减少了对信任的依赖。它不需要依靠某个特定的机构、国家或权力机构（如军队）来保障货币的价值和运行。相反，它通过分布式账本技术（如区块链）在全球范围内由多个节点共同维护数据的真实性和一致性。这样，信任不再集中于某一个机构，而是分散在整个网络中，从而降低了对单点失败或中心化控制的依赖。

传统工程与计算机系统设计之间存在很大的不同，尤其是在复杂性控制方面。传统工程（如建筑工程）已经积累了大量成熟的理论和经验，比如 constructive theory，为设计和建造提供了明确的指导。然而，在计算机系统中，复杂性的控制还缺乏足够的经验积累。因此，当我们面对复杂系统时，往往需要从实际案例研究（case study）中提取一些显著的特征，分析现有系统是如何应对复杂性的。

控制复杂性的重要方法

复杂性控制的关键在于明确系统的边界，并选择适当的维度进行优化。例如，如果我们过于精细地研究每个细节（比如模拟每个气体分子的方向和动量），系统将变得不可控。同样地，在软件开发中，如果深入到代码、CPU、流水线、甚至电路板布局的每个层面，也会让我们无法专注于核心问题。因此，必须在大多数情况下相信某些工具和抽象（例如编译器），来限制调试和设计的边界。

在复杂性控制中，主要依赖以下四个方法（M.A.L.H）：

Modularity（模块化）

在 linux 内核中，通过估算大约每一千行有一个 bug。对于我们自己的代码，预估的是一 个没有发现的东西，比较难以估算。 Debug 的时间等于代码的行数*bug 数量，所以就是 O(代码行数） ，拆分成 K 个小模块之后，总的时间复杂度就可以除以 K。

模块化通过将复杂系统拆分为多个子模块来实现“分而治之”。对于模块化的设计，要注重以下几点：

• 高内聚、低耦合：模块内部功能相关性强，模块之间尽可能减少相互依赖。
• 良好的抽象和接口：模块的接口应该清晰明确，方便其他模块调用。

Abstraction（抽象）

抽象是模块化的重要基础，设计抽象时需要遵循以下原则：

• 遵循自然的边界：例如，当抽象用户时，自然行为包括“购物”“浏览网页”等。
• 减少交互：模块之间的交互越少，复杂性越低。
• 将错误控制在模块内：抽象应该尽量防止错误传播到系统的其他部分。 需要注意的是，虽然增加模块数量（k）可以降低复杂度，但过多的模块可能导致频繁的交互，反而增加系统复杂性。

Layering（分层）

系统的分层设计能够控制模块之间的交互范围。例如，在网络中，采用分层协议（如 7 层或 4 层协议）使得每一层只需处理相邻层的问题，减少了调试和设计时的复杂度

Hierarchy（层级化）

当系统由多个模块组成时，可以通过层级结构对外统一呈现一个模块的形式。比如，访问亚马逊的服务器时，中间可能需要经过多个路由器，但我们只需记录到美国的路由信息，而不需要记录每台服务器的 IP 地址。

软件的复杂性

与传统工程不同，软件系统没有物理定律限制其复杂性。在数字世界中，只要想象力足够，理论上就可以创造出极其复杂的系统。因此，软件设计的极限往往是人脑理解的极限。而不同开发者的理解能力参差不齐，导致生产力差距巨大。一些优秀程序员的生产力甚至远远超过新手，这是因为他们更善于控制复杂性。

错误与调试

当系统变得复杂时，错误不可避免。通过模块化设计，可以在模块内捕获和隔离错误。调试时有以下关键点：

• 检查返回值：调用函数时需要明确验证其返回值是否正确，防止错误扩散。
• 对输入的严格校验：系统（如操作系统）在接收用户输入时，要假设应用可能是恶意的。比如：

1. 当用户请求将一段数据从某个内存地址复制到另一个地址时，操作系统必须检查地址是否合法，否则可能泄露敏感信息。
2. 用户请求操作系统打印数据时，系统需要确认数据是否指向内核区域，否则可能将内核信息暴露给用户。

模块化和分层在这里起到了关键作用，减少了模块间的错误传播范围。

系统设计的难点

尽管 M.A.L.H 四个方法可以有效降低复杂性，但找到“正确的模块化/抽象/分层/层级方法”仍然充满挑战。在许多情况下，必须针对具体的场景进行逐案分析（case-by-case）。以网络系统为例，从早期的一台设备、数百行代码发展到如今几百万台设备、数千万行代码、成千上万用户时，系统的复杂性呈指数级增长。

因此，复杂系统的设计依赖于经验、良好的架构方法论以及清晰的调试边界。课程所教授的内容正是基于这些原则，帮助我们从实践中逐步积累应对复杂性的经验。

案例：淘宝优化架构的心路历程

构建像淘宝、支付宝这样高度可扩展的网站，需要解决系统性能和稳定性问题，尤其在处理高并发时。以淘宝双十一为例，一天需处理 22.5 亿订单，这对系统提出了极高要求。

像商品介绍图这种数据，一般是以PNG/JPG等格式保存在文件系统或者文件服务器里。为什么不用数据库？因为图片是非结构化数据，文件服务器对这种大文件的存储和读取效率更高，更适合这种用途。图片的数据量通常比较大，但它是固定的，只需要在用户打开页面时提供给他们，不需要频繁修改或者实时更新，所以文件服务器更合适。

再说价格，这个数据就很重要了。它的变化频率虽然低，但不能出错！价格是用户下单时的核心依据，如果出问题，可能会直接导致经济损失或者客户投诉。所以，价格需要存储在数据库中，因为数据库不仅能很好地存储结构化数据，还能提供可靠的持久化机制，确保价格的准确性和一致性。无论用户什么时候访问，看到的价格都应该是统一且可信的。

而“人气”（比如浏览量）就不一样了。它是动态数据，变化频率很高，但重要性没那么大。比如你看到的“人气”是10,883，别人看到的可能已经变成10,900了，这完全没问题。即使某一瞬间丢了一点数据，也不会影响整体体验。人气值可以放在内存里实时计算，或者通过键值对存储简单记录。它不像价格那样需要精确和一致，所以存储方式可以随意一些，甚至可以牺牲一些可靠性，优先保证效率。

每次点击都会导致淘宝内部数以千计的服务器的协作。

在很久很久以前，使用 LAMP 机制，是建站的首选。

最初的单体架构：简单但不可扩展

最初，所有东西都在一台服务器上运行，数据库存放数据，文件系统存图片，CPU负责计算。这个架构简单，但问题是扩展性非常差：

• 内存最多256GB，硬盘最多40T，无法支持海量用户。
• 像Facebook每周上传10亿张图片，显然单台服务器无法承载。

---

第一步：从单体到基础的分布式架构

解决思路：改架构+堆服务器

• 用三台便宜服务器替代一台昂贵的大服务器：
• 一台跑webserver，负责处理页面请求。
• 一台跑fileserver，存图片等文件。
• 一台跑database，存重要数据。

优点：架构可扩展了，可以加更多服务器。
问题：

1. 网络传输比本地磁盘慢，影响时延。
2. database变大后查询变慢，成了瓶颈。

第二步：引入缓存，提升速度

解决思路：加一层缓存（Redis/Memcached）

• 用户请求数据时，先查缓存：
• 找到就直接返回。
• 找不到再去database查询，查询结果同时写回缓存。

技术细节：缓存分布问题

• 内存比硬盘少得多，缓存不可能装下所有数据。
• 把数据分布在多个缓存服务器上，用哈希算法定位数据存储的位置。
• 如果增加新服务器，普通哈希算法会导致大部分数据重新分布，miss率高。
• 解决办法：一致性哈希（后面讲了），通过优化哈希算法，把miss率从75%降低到25%。

第三步：Application无状态化

解决思路：让webserver无状态，易扩展

• 无状态化：所有用户状态信息都存到fileserver或database中，webserver只负责解析URL并返回内容。
• 优点：如果一台webserver挂了，随时可以用另一台替换，支持横向扩展。
• 负载均衡：引入load balancer，把请求分发到不同的webserver上，挂掉的机器会被及时剔除。

第四步：Database的优化

当application server数量增多时，database server成为瓶颈。

• 读写分离
  • 主数据库（primary）负责写入。
  • 从数据库（secondary）负责读取。
  • 主库会定期把数据同步到从库。
• 数据库分表
  • 数据量过大时，把一张表拆分到多台服务器上（如一张大表分成10张小表）。
  • 这种方式需要解决数据一致性管理问题，比如事务的处理。

第五步：Fileserver的优化

当数据库的server变成多台时，fileserver也需要扩展，演变为分布式文件系统：

• 典型例子：NFS、GFS、HDFS。
• 外部表现还是一个统一的接口，但内部数据分布到多台服务器上，支持从1台扩展到100台。

第六步：引入CDN，减少时延

当用户分布在全国时，访问服务器的时延很大，比如广州用户访问杭州服务器会很慢。

• 解决方案：引入CDN（内容分发网络）。
• 在全国各地部署缓存服务器，把用户访问频繁的数据（如图片）缓存在本地。
• 用户访问时，直接从离自己最近的CDN节点取数据，减少时延。

图片处理流程：

1. 图片URL存储在webserver中，用户请求时返回CDN的地址。
2. 用户从CDN下载图片。

第七步：拆分微服务

随着业务变复杂，单一的webserver架构已经无法满足需求，尤其是淘宝和支付宝的场景差异很大：

• 淘宝需要推荐系统（比如千人千面、热搜）。
• 支付宝需要高安全性和实时性（比如信用卡欺诈检测）。

解决方案：微服务化

• 把大块的代码拆分成多个微服务，每个微服务只负责一个功能（比如推荐系统、支付系统）。
• 服务之间的交互可以用：
• 消息队列（MQ）：用于快速、高效的异步通信。
• 数据库或文件系统：用于慢速、稳定的通信。

Fault

大的数据中心的数据，在全球不同的地方都会有数据中心。 那么这么复杂的系统组成在一起最大的挑战是什么呢？ 最大的挑战就是 fault

Fault 是Error的原因。Error 是 fault 的结果，failure 就是很大的失败。当我们的系统不出错的情况，一百万台机器都不出错是不太可能的。因为总体中有一台机器的出错率是随着机器数量指数增加的。

我们不可能打造一个所有机器不出错分布式系统，我们希望用不可靠的组件组合在一起 组成一个可靠的分布式系统。我们希望同时断掉 90%机器的电，其他的机器还能 work。这就是容错能力

当一个用户发送数据到 service，原因

• 1. 网络丢包
• 2. 请求在网络上排队（路由器包满了在排队，但是你的耐心到了）
• 3. 远端服务器可能挂了
• 4. 远端服务器没挂，但是暂时停止了响应，java 的内存回收机制 jc，需要 jvm 暂停住。
• 5. 其实处理了操作，但是在返回的时候挂了，比如连点了两次处理了两笔转账。

Lamport 提出了很多很多分布式理论，2013 图灵奖。

MTTF、MTTR、MTBF

• MTTF：连续多久不宕机的平均时间。
• MTTR：出错以后修复的平均时间。
• MTBF：两次出错的平均间隔时间。

MTBF = MTTF + MTTR

计算方法

这里的 λ 是失效率（failure rate），也称为故障率。它表示系统或模块在单位时间内发生故障的概率

R(t) 是系统可靠性（ system reliability）

对于串联的情况：MTTF 是各项倒数和的倒数

对于并联，对于最低执行要求是 M 个，目前有 N 的组件的情况

MTBF 的一张表

CAP定理

CAP 定理：一致性（Consistency）、可用性（Availability）、划分的容错（Partition）三者只能选二。 Partition tolerance：就算网络被鲨鱼咬了，一个网络变两个网络了，也能正常运行。CAP 这三个同时只能满足两个。

• CA（一致性 + 可用性）：单点数据库，当网络分区时无法工作，但保证数据一致且请求可用。
• CP（一致性 + 分区容错性）：HBase，在网络分区时拒绝请求，保证数据一致性，但牺牲可用性。
• AP（可用性 + 分区容错性）：DNS，即使网络分区时依然返回结果，但可能数据不一致。

Inode-based file system

在单机上文件系统的实现是 inode-base file system，我们先对单体文件系统解剖，最后再扩展到分布式文件系统。

什么是一个文件？

• 第一个特性：durable，它是一段放在存储设备上的可以保存的数据。它不会因为你 关机而消失。
• 第二个特性：文件是有名字的，我们可以去命名一个文件，我们也可以通过一个名字去 指定对应的文件。

系统对于文件来说，这两个特性都是为了让程序员和用户在使用的时候更方便一点。在 一个大的 bigpicture 里面，内核在磁盘和内存之上，抽象出文件的 abstraction，也就是要发 明出文件的接口。把硬件提供的接口，经过 os 的组织和包装变成一组新的接口，用户使用起来更便捷的接口。

文件提供什么 api 呢？Open，读写文件，关闭文件，同步文件到磁盘，文件的元数据， 可读可写可执行，改变文件拥有权，创建目录，改变目录，mount （挂载）和 unamount。

A Naive File System

我们先来看一个简单的文件系统怎么设计。一个磁盘就是一个很大的数组。每个 block 早期是 512 字节，后来变成了 4k。如果我现在有一个文件要放在磁盘上，既然放在磁盘上 了，肯定就有 durable 特性了。 名字这么设置？我们可以把文件顺序的放在磁盘上，存放的第一个 block 存放文件的名字。这种简单的计有什么问题呢？

• 1. 因为连续存放，增删后存在碎片
• 2. 文件 copy 到另一个磁盘以后，可能就不是 107 编号了。因为名字和磁盘本身耦合 的太多了。

我们需要在磁盘之上，做层层软件的抽象，把它变成容易使用的。

分为 3+3+1，上面三层让人来用

Block Layer

block layer，你给我一个 block number，我给你一个 block data，这是磁盘提供的。我们32 要 107 号，你给我 4k 数据。但是显然不够，我们需要知道每个 block 多大，是 4k 还是 512b； 哪些 block 被用了，哪些是 free 的；有用的数据从什么地方开始；

所以我们就需要在 block 这一层放一个特殊的 superblock，它一般来说第一个是用来启 动的。Superblock 中包含了 block 的大小，free block 的数量，所以 superblock 中记录了很多 原信息。它怎么记录一个 block 是用了还是没用呢？它会预留一块用来记录 bitmap，这就是 一串 010101010,0 表示 free，1 表示 used，每个 01 就是针对了一个后面的 block 是用了还是 没用。Block size 是一个 trade-off，软件可以修改 block size，如果这个 block size 太小了。这 意味着磁盘分的太碎了。太大的话就容易浪费掉。需要合理设置长度。

接下来就是记录哪些是 free 的。如果我们每个 block 前面加了一位，我们的 block 是 4095 的 size，导致读取到的数据是不对齐的。所以我们在这个文件系统内我们是使用 bitmap 来 存储这个信息的。4k 的 block 可以存放 8*4096=32K 个 block 的是否使用过。所以一个 4K 的 bitmap 就可以对应到 32K*4K = 128M 的磁盘空间，效率还是很高的。有了这些以后，我们就 有了第一层。

File Layer

File Layer 负责将文件的逻辑视图与底层存储块的实际位置映射，并管理元数据索引与访问。

第二层：一旦有了 block 之后，如果我们保证每个文件都小于 4k，我们就可以直接使用 block_id 作为文件的 name，但是文件必然比 4k 大，一个文件占 block 的数量就会超过 1

planA:文件连续存放

planB：文件不连续存放，这个效率更高。但是怎么记录不连续的 block number 呢？我 们就引入了 index node。假设文件包含了 8 个 block，如果是连续的就记录第一个 id+长度， 如果不连续，我们把 8 个 block id 记录在 index node 里。这里面包含了 block number，这个 N 的大小很有讲究。如果这个 size 记录的是 block 的数量，文件的大小必须是 4k 的整数倍， 肯定有问题。所以这个 size 是文件的 byte 数量，最后一个 block 可能没用完。 如果我们的 N 是一个定值，那么 Inode 支持的文件的最大大小是多少呢？怎么提高呢？

如果 N 是 1000，文件大小最多才 1000*4K，显然是不够的。我们不能用线性的数组的记录 这个 block number。如果我们想支持 4G 大小的文件，那么 4G/4KB * 64B（磁盘的 block_id 的长度）=8M，为了支持一个 4G 的文件，光是存它的 index 就要用到 8M，如果一个 Inode 8M， 如果我们用一半的磁盘存这个 Inode，比如这个磁盘 8T，用 4T 来存 Inode，4T/8M = 50 万个 文件。我们计算机中的文件毫无疑问是百万级别，最大支持的文件才 4G，这些都满足不了 我们的需求。

如果我们的文件没那么大，我们预留了一个 8M 的 inode，就本末倒置了。我们要预留 成可伸缩的结构。我们把数据的前面几位设置成指向 block 的。后面几位指向一个二级的34 block。其中每一项都是指向一个 block_index。二级的 block 是 4k，每一项是 8 个 byte，可 以指向 512 个 block。这个和页表做的事情是很像的。如果二级也用满了，我们可以再加一 级。那么就是 512*512 个指向 block 的 block_index。这样对于小文件，就只需要用到前面几 个。对于大文件就可以一点点增长出来。

对于 layer2，其中可以作为 double indirect block 和 triple indirect block 对于第一层来说 是无所谓的。

有了第二层之后，就有了 inode。页表的话所有统一是 4 级页表。要解决的本质问题其 实就是映射。有了第二层之后，只要告诉我们 inode 在哪，和需要数据在文件中的 offset， 我们就可以找到对应 block 在哪，返回给用户。

Inode Number Layer

以记录一个 free 的 inode 的链 表串起来。

所以给了一个 Inode number 就可以得到文件的所有信息。这对获取文件是足够的，但是它对于人类是比较难的。而且 copy 的时候，inode-number 是会变动的

File Name Layer

第四层，我们需要一个 user-friendly 的 name，怎么把字符串和 inode-number 做一 个映射呢，最简单数据结构就是一个 dict 映射。

这个表最后在硬盘上就是这么存的，它存在一个文件里，它是文件系统规定的格式，这 个文件就叫做目录。也就是里面文件的名字是什么，文件的 inode-number 是多少。Foulder 这个词是很误导的，这个文件夹只是包含了其中文件的 inode-numer，而不是包含了所有文 件内容。所以我们倾向用目录这个词，更加准确。

访问文件方式：给一个文件名，给一个目录，去目录里找这个文件名，找到对应的 Inode-number，就可以再找到文件了。

这样就产生了 lookup 的方式：

到这一步为止，整个文件系统都完备了，每个文件都有一个字符串的文件名。但是还有 缺点，我们现在只有一个目录，这个目录下有很多很多文件（几百万个），ls 有好几个屏幕， 都不能重名的。所以我们应该有一个 path name 层，如果目录也当做一个文件，那么目录就 可以被包含在另一个文件里面。目录也有一个 Inode-number，目录和文件在 inode 这一层是 没有区别的。就像 inode 和 data 在下层都是 block 一样。

Path Name Layer

既然不区分，我们就可以有了 path name，我们可以创建 projects/paper，我们先去当前 目录下找 projects，找到以后再以 projects 为目录找 paper。

接下来一个问题就是目录名太深了，要打好几层目录。在我们前面说的目录结构里面， 并没有任何地方组织我们把一个文件名对应的 inode-number 设置成同一个。也就是不同文件名对应到同一个 inode-number。如果我们为一个 inode 创建多个 name，我们就可以为一 个很深目录的文件名创建一个很短的文件名，最后对应的 inode 是一个。说明这个文件只有一个。

假设一个文件有两个名字，当我们删掉一个名字的时候，用另一个去访问是能访问还是 不能访问呢？

什么是删文件：本质操作只是删除目录中的helloworld.txt -> 12删除掉，并不是删除block 中的数据，因为可能别的地方还引用了。所以我们要在 inode 中维护一个 reference counter， 如果删除完 reference counter == 0 就可以删除了。同时我们还需要加一个 type 来标识是一个 普通文件还是目录。

假设 inode 有个 x，记录了目录 a，目录 a 中记录了目录 b。假设我们现在来 link 把/a/b/c 对 应到/a，也就是在 a 的子目录下建立了一个指向 a 的 link。a 现在有两个人指向它，也就是 /a 和/a/b/c，它的 ref count 是 2。现在我们尝试删除/a，它的 ref 是 1，但是从 x 再也找不到 a 了。因为它唯一的名字被删除了。它既没有被删掉，又不能被另外的地方访问到。所以就 会成为内存垃圾。所以禁止指向目录。

当我们删除一个非空目录的时候，其实我们是递归删除的，在真实的 linux 里面，我们 已经考虑了这个问题了，但这个 rm -r 在 unix 第 6 版是不存在的。

当我们去 rename 的时候，改文件名是文件系统中非常复杂的事情。假设我们要去做改 文件名的操作，比如 mv (from,to)，这一个指令牵涉到 3 件事情。

• 1. 把 to 删了，to 的 ref count 变成 0.
• 2. 把 from 加一个 to 的名字，from 的 ref count 变成 2.
• 3. 再把 from 的 ref count 变成 1

在这个过程中一旦发生了一次 crash。比如在 1 和 2 之间发生了断电，我们发现少了 to 这个文件。所以这就是我们 atomic（原子性）的问题。原子性就是不管中间断电的什么情况， 回复到正常情况以后，要么就是全做，要么就是没做，不存在中间的情况。

Absolute Path Name Layer

有了这个之后，我们现在有了目录了，一台机器有很多人要登录，我们看到我的文件，38 你看到你的文件，文件之间是没有任何文件渠道去沟通的。为了解决这个问题，就引入了根 目录，有了根目录之后，一台机器上的文件都可以根据根目录开始索引。根目录最后就定义 为/，根目录的.和..都指向它自己。

整个过程分为以下几个步骤，清晰地展示了从根目录定位到 /programs/pong.c 文件的路径解析过程：

1. 定位根目录

• 根目录的约定地址：根目录是文件系统的起点，它的 inode 编号约定为 1。
• 通过 super block 找 inode table：文件系统的 super block 中记录了 inode table 的起始地址。我们通过这个信息找到 inode table。
• 找到根目录的 inode：在 inode table 中定位 inode 编号为 1 的 inode 条目，读取其对应的数据 block。

2. 解析根目录内容

• 读取 block 14：根目录的 inode 指向的数据 block 是 block 14。因此我们读取 block 14 的内容，发现它是一个目录文件。
• 定位 programs 条目：在 block 14 中，找到名为 programs 的目录条目，它的 inode 编号为 7。

3. 定位 programs 目录

• 通过 inode table 查找 inode 7：回到 inode table，找到第 7 个 inode 条目。
• 读取 inode 7 指向的数据块：inode 7 指向的数据块是 block 7，我们读取该 block 的内容。

4. 解析 programs 目录

• 定位 pong.c 条目：在 block 7 的内容中，找到名为 pong.c 的文件条目，它的 inode 编号为 9。

5. 定位 pong.c 文件

• 通过 inode table 查找 inode 9：再次回到 inode table，找到第 9 个 inode 条目。
• 读取 inode 9 指向的数据块：inode 9 指向的数据块是 block 61。

6. 读取 pong.c 文件的内容

• 找到 block 61：通过读取 block 61 的数据，我们最终得到了文件 /programs/pong.c 的内容。

整个路径解析是从根目录开始，依次通过 inode 和数据 block 的指针不断解析每一层的目录，直到最终定位到目标文件的数据 block，完成了文件访问。

我们可以列出 temp 目录的 inode 号是多少。我们变成 16 进制以后就是这个。我们可以用 debug 的方式打出这个文件。这就是目录在磁盘上的数据。

我们重新排序后就可以看出，每一行对应的就是文件名。2e 就是.，2e2e 就是..。 0102 就是目录的意思。0c00 就是长度。c40f 就是最后一项到头了。前面红色的部分就是 inode-number。我们就通过这个实验看到了这个真的目录长这个样子。

有了下面三层之后， 整个文件系统已经成立了，但是光用 inode-number 做名字不是很友好。所以需要用 inode 和文件名对应，我们记录在单独的一个文件里。这个文件不是我们随意可以通过read-write 修改的，因为这个文件是一个目录文件。它对于文件系统来说是元数据。对于 Inode 来说， 目录所有的数据都保存在数据区，和一般的文件没什么区别。但是从用户的角度来看，目录就是一个元数据，不能通过open/read/write 来修改目录，只能通过 ls。然后有了目录之后， 再往上递归地树状组织结构。接下来还有 link 的概念，link 其实就是文件名。

我们创建一个指向 a.txt 的 a.ln link。我们发现现在多了一个文件 a.ln。我们发现它们的 时间、大小一起变了。所以上述的 2 是 reference count，当 ref cnt 变为 0 的时候，inode 和 data 就会被 free 掉。6 就是文件 size 的大小。

当我们知道 link 的时候，如果我们现在插了一个 u 盘到了电脑中。如果我们想在主机中 创建一个指向 u 盘的 link，这本身是两个文件系统，inode-number、space 都是不一样的。 我们不能直接使用 u 盘文件系统中的 Inode-number。所以不能创建跨文件系统的 link。

Symbolic Link Layer

而第七层 symbolic link layer，我们在文件系统中创建了一个新的文件，内容是一个字符 串，指向需要链接的文件路径和文件名。它不会仅仅停留在打开 symbolic link 本身，它会读 取出数据，并且指向进一步的操作。所以在 inode_type 中要添加 symbolic link。

我们创建 s-link 的信息的时候，我们发现是指向/tmp/abc 的。我们可以通过命令 readlink 来读出 symbolic link 文件的内容。8 是/tmp/abc 的大小，它其实不需要去存/0。如果我们尝 试使用 cat 来读取数据的时候，会报错。当我们把 hello, world 重定向到/tmp/abc 的时候， 才会读到 hello, world。所以这个告诉我们哪怕原先的路径的文件不存在的话，我们也可以为 那个不存在的文件创建一个 symbolic link，但是对于 hard link 来说，我们不能为不存在的文 件创建一个 hard link，因为 inode 都不存在。

我们可以通过上图来审视一下 hard link 和 symbolic link。Hard link 是通过 inode-number 绑定，而 symbolic link(soft link)是通过路径和文件名来绑定。Symbolic link 是可以指向目录的， 而 hard link 除了.和..是不能指向目录的。

有一个/Scholarly/programs/www，我们觉得太长了，我们创建一个 symbolic link /CSE-web。 我们使用 cd CSE-web; cd ..; 我们因为答案是/Scholarly/programs。事实上，答案是根目录。

这是 bash 自己做的优化，它认为这样跟符合直觉。

我们简单做一个总结，前面 7 层里面有几个和直觉不符合的地方。

1.文件名和文件是没有关系的。文件相关的数据分为元数据（存在 inode 里）和数据 （inode 指向 block 中）。而文件名是存在目录里的。所以文件的文件名和文件并没有直接 的关系，这也是我们可以通过 hardlink 给一个文件赋予多个文件名。所以任何一个指向 Inode 的文件名是等价的，新创建的 hard link 和原先的文件索引是等价的。

2.以及目录的大小是很小的，只和文件名的长短有关系。

讲完文件的结构以后，我们已经知道了磁盘中静态文件是怎么组织的。我们接下来看文 件是怎么被读写、访问、同步的。

这些操作都是通过 system call 的方式提供给用户的应用程序的。而用户通常还要通过 lib42 的封装来调用。

我们之前学过 C，C 是不是一个跨平台的语言呢？我们 include 不同头文件的时候会有不 同的环境。我们用 C 的 lib 是 fopen，在 linux 下是对应的 open 的 syscall。Fopen 是返回一个 file*，而 open 是返回一个 int 的 syscall。

userid 和 groupid 去做访问控制。然后是可读可写可执行，还要三个 time, last access, last modification, last change of inode。

Mtime 说的是 data 改动，ctime 说的是 inode 改动（link 改动 refcount，修改权限）。

Open 文件的时候，先要看文件是归属于哪个用户的。匹配 userid 和 groupid，如果权 限不匹配也不会让你打开，然后更新 last access time。然后返回一个 fd（文件被打开之后就 会有 fd）。

Fd 同样可以被命名打开的设备。比如我们打开一个键盘。读的话就是得到键盘正在输入的 字母。每个 process 都有我们自己的 fd namesapce。现在提一个问题。为什么我们要用 fd 来 作为返回的文件呢？为什么不返回 Inode 给用户呢？

我们希望用户不能访问内核的数据结构，如果我们直接返回 inode 的指针，那么就把内 核数据直接暴露给用户了。Non-byassability: inode 指针可能绕过 open，因为 open 的时候拿 到的是一个文件名，之后再返回 fd。但是如果我们返回的是 inode，第二次之后的 Open 就 可以随时随地拿第一次的 Inode 返回的指针去用了，可以绕过 OS 在 open 的时候的权限检查。 这样应用程序就没有任何部分绕过权限检查。

Fd 还记录了 cursor，也就是当前的文件。

File_table 是整个系统一张表，而 fd_table 是一个进程一张表。

不同进程中的 fd_table，哪怕 fd 相同，指向的 file_table 中的位置是不一样的。C 是 B fork 出来的，继承了所有数据。换句话说，两个进程既可以共享 fd_table（file cursor 相同），也 可以不共享（独立 file_cursor）。

实际上我们在 print 的时候，就会遇到共享 fd_table 的情况，如果不共享，child process 可能就把 parent process 的输出覆盖掉。 注意 file_table 里的 ref count 是表示多有少个 fd 指向它。

注意 FIND_UNUSED_ENTRY，是选择当前没有用过的 fd 中最小的一个。 接下来我们看实际的磁盘上的结构：

在磁盘的头部我们放一个:free inode bitmap，还有一个 data bitmap，最头上是一个 Superblock，其中记录了一些元数据。

当我们去打开一个文件/foo/bar 的时候，我们应该先去读 root_inode（约定俗成的地方， 第一个 inode 的地方），我们就去读根目录对应的 block number 的 block，读到了根目录下 的文件，找到了 foo 的 inode，找到 foo 的数据，找到了 bar 的 inode。读的时候，找到 bar 的 block 读，读完了以后修改一下 inode 的 access time。

我们发现在 read 的时候，我们不得不去 write 一次磁盘为了更新 access time。在 linux 的时候，加载文件系统启动的时候默认会添加 noatime 选项。我们弱化 atime 的更新，也就 是当我们 close 的时候才会更新 atime，而不要读一次更新一次，尽可能减少磁盘的写操作。

简单说，这个过程的核心是因为磁盘操作是基于 块（block） 而不是单独的字节，涉及到文件系统如何高效管理和更新数据块。

1. 首先：找到 /foo 的信息

• 文件路径解析先从根目录开始，逐层查找。
• 找到 /foo 时：
  • 读 /foo 的 inode：从 inode 中知道 /foo 的数据块编号。
  • 读 /foo 的数据块：获取里面的内容（如文件名和 inode 编号的对应关系）。

2. 准备创建 bar

1. 分配新的 inode：

• 读 inode 位图（inode bitmap）：找到一个空闲的 inode。
• 分配这个 inode 作为 bar 的 inode。

1. 更新 /foo 的数据块：

• 读取 /foo 的数据块，找到合适位置写入 bar 文件名和它的 inode 编号。

3. 为什么创建时要“读”？

这个 “读” 操作主要是因为磁盘 物理层 的特性：

（1）磁盘按块操作

• 磁盘的最小操作单位是 块（block），通常是 4K 大小。
• 如果 /foo 的数据块是 4K，但我们只想往其中写入 bar 的条目（比如几十字节），磁盘不能直接写这几十字节。
• 必须把 整个 4K 块读上来，修改其中一部分，再写回磁盘。

（2）写入时保护原始数据

• 为了保证不会覆盖未改变的部分，写磁盘前需要确保：
• 数据已经在内存中完整修改好。
• 这就是 “先读后写” 的原因。

4. 更新 bar 的 inode

1. 分配数据块：

• 读数据块位图（data bitmap）：找到一个空的块。
• 这个块将存储 bar 的文件内容。

1. 写 inode：

• 在 bar 的 inode 中，记录下这个数据块编号。

5. 总结为什么要读

• 磁盘按块操作：不能直接写几个字节，必须先读整个块。
• 需要完整性：修改目录条目（如 /foo 的数据块）时，必须确保原来的其他部分不丢失。
• 位图的读取：为了找到空闲的 inode 和数据块，也需要读取 inode 位图和数据块位图。

所以，创建文件的过程虽然看起来是“写”，但实际上离不开 读操作，这是为了协调 磁盘物理操作 和 文件系统的逻辑管理。

接下来我们就可以来写了，从 data_bit_map 中找一个空的写回去。然后写回对应的 block 后就再把 block number 写回 inode。

这里我们发现在前面的过程中，最难的事情也就是一旦发送了 failure 就会导致严重的问题。

我们直接回到刚才这个 write 操作，一次 write 需要写 3 次磁盘（data_bit_map, inode, data）。那么问题来了，当我们在做这个操作的时候断电了，会发生 3 2 情况，也就是 000,001,010，…，111，

• 1. data 写了，而 data_bit_map,inode 没写。元数据啥都没更新，属于 nothing 的情况。
• 2. Data_bit_map 写了，而其他两个没写。引入了垃圾，没有任何文件的 inode 指向这 块区域。我们可以通过把整个 inode 扫描一遍得到 list，然后做匹配，更新一下 bit map。
• 3. inode 更新了，而 block 和 data_bitmap 没更新。我们发现数据是错的，有可能访问 到权限文件引发安全问题，可用性也有问题。这个问题是最大的。
• 4. Data 没写，会导致安全性问题。
• 5. Data_bitmap 没写，会被另一个文件共用一个 block。
• 6. Inode 没写，产生浪费。

如果让我们排序的话，我们会先写 data，再写 data_bit_map，再写 inode。因为 inode 非常重要。

Order 没办法保证，因为我们发送操作的数据可能是按照顺序的，但是 cache 的情况我 们不可控。

为了避免这个问题，这时候我们就要用到 SYNC，把内存中的所有东西 flush 到盘上。

如果我们把一个打开的文件删掉了，如果 file_table 中的 ref_cnt 不为 0，需要等待 inode 在进程 close 的时候把它删掉。

除了 inode，我们还可以怎么组织数据呢？为什么我们不适用链表呢？FAS32 就是 一个链表。

FAT32 使用 file allocation table 来记录文件的第一个 block-number。它没有 Inode number。 FAT 表其实就是一个 64byte 的表。当我们把这个表串起来，我们就可以把对应数据串起来。 freelist 一路上把所有 freeblock 串在一起。我们要新加一个 block 的时候，我们就把 free_list 指向它的 next，多出来一个 free，然后改 file32 的最后一个指向 free block。

那么这么一种设计有什么特点呢？对于随机读写，需要遍历一遍这个 linked_list，而我 们的 Inode 只需要读一遍三级索引的链。如果 linked_list 有一个地方坏了，那么全部都坏了。 三级间接索引坏了也会导致大量数据没有，但是概率小一点。

NAT 适合顺序读写。所以适合用来做数码相机的存储介质。

由于 fat 表没有 inode，所以我们还是要记录一些元数据。是记录在 directory entry（目 录项）中。inode 的结构是 name: inode-number。而 FAT 中是 name :第一个 block 的 number， size，….，各种元数据的信息。就算有 ref count，我们也不知道在哪，需要扫描一遍所有的 目录。所以 FAT 不支持 hard link 的。核心就是 name 是文件的元数据的一部分，于是我们就不能让两个 name 指向一个数据。

如果我们把 U 盘格式化成 FAT，最大支持的大小是 4G，这个 4G 是由什么决定的？是因 为元数据中的 size 只有 32 位，最大只能表示 4G 的文件。而 Inode-based file system 是由有 多少级 indirect-block 决定的。如果我们在一个文件系统里面，我们现在要存大量的文件， 但每个文件小于 1k，平均 256byte。而一个 i-node 就有 1k，于是我们为了这个每个文件的 存储分配一个 4k 的 block 和 1k 的 inode。事实上我们今天的磁盘中，有很多 4k 的数据没有 存完，这个地方是由 size 决定的。最后会留下一些空隙的。我们有什么办法把利用率提高呢? 一个简单的办法是直接把数据放在 inode 中。为了避免文件系统误解为 blocknumber，再加 几个 flag 就行了。这样文件利用率 就提高了

场景：战地记者带手机，进过一个区域，进出都有一个哨兵。这个哨兵非常懂文件系统， 记者不能让文件系统有任何的变化，就可以用文件系统中每个文件的最后一个 block 多余的 空间。这个方法不仅战地记者也会用，黑客也会用，病毒如果放在这个区域就扫描不出来了。 动态地修改 inode 中的 size，就可以在想用的时候调用到病毒的代码。

分布式文件系统

RPC

我们希望把 file system 从单个扩展到多个。这个在接近 40 年前就有人做了。SUN 公司 希望开发没有硬盘的计算机，数据是不是都能全部来自网络。对用户是透明的，最底层的核 心技术就是 RPC。RPC 不仅仅是用来提供 Open,Write,Read 接口，RPC 还能实现跨机器的函数 调用。

传统的，如果我们不用 RPC，大家要调用网络的时候，就要使用 socket，打开一个 socket， 服务端要 listen，然后可以 accept 得到一个 fd，然后在双方之间做交互，我们需要写很多 glue code，不是很方便，我们希望有更加简单的操作，client 的代码可以直接写一个 fool()调用的 是服务器端的函数，返回值就是对应的返回值。换句话说我们希望 RPC 和 PC（procedure call） 是一样的，我们不需要 care 它是 local 还是 remote 的。除了在 framework 级别，在语言级别 甚至都包含了 RPC 相似的机制，比如 Java 中的 RMI（remote method invocation）。说明 RPC 是一个非常非常基础的作用。

这个 mesure 函数是用来测量 func 的运行时间。Get_time 就是根据传入的单位返回对应 单位的时间。如果我们把 GET_TIME 放到服务器上，比如我们本地的时钟不正确，该怎么去 做呢？

网络延迟该怎么办？我们之后会讨论对时的算法。 最简单的就是多 ping 几次，取均值，我们假设了网络时延基本上不变，并且假设了过 去的时间等于回来的时间。一旦在谈到分布式的时候，我们会发现时钟是看起来简单但是背 后是一个非常大的问题，因为没有两个人的时钟是一样的。

我们需要把 second 参数 convert 一下，因为网络上的数据是 big-endian，然后传一个 Get time 打包成一个 Message 发送给服务器，得到 response。然后再 convert 回来。

得到 request 后，对其做解析得到 opcode 和 unit。得到数据以后，返回一个 response（OK 和 bad request 两种可能）。 我们看到它来来回回做了很多别的事情，很多内容是可以模块化的。

这些都是可以放在 RPC 的 stub（桩代码，不用程序员管的）中，全部用库的方式去封装起 来。

在 stub 中会实现 GET_TIME 并且发送给远端得到 response。Stub 就很好地封装了底层网络通 讯的细节。对于 server 来说一样，我们实现了底下的一层。

这是非常经典的解耦方式，程序员不用考虑函数是在本地还是在远端，当然这是在不出 异常的情况。

我们需要把数据用合理的方式 marshal 排队发到网上去（serialize）。我们来详细看一下， 在 1984 这篇论文中提出的 RPC 包含了什么内容:

• 1. Xid，X 是 transaction 的缩写，它是用告诉 server 请求是发过了还是没发过，在出 错的时候非常有用
• 2. Call/reply53
• 3. RPC version，意味着可以支持多个 version，一台单机的应用程序和库通常是合在一 起的，但是 client 和 server 的版本可能不相同，要考虑到兼容性
• 4. Program, program version, procedure，可能调用一个可执行文件所提供的函数
• 5. Auth stuff，来做验证
• 6. Arguments，参数

同样在 reply 的时候也有几个不同的参数

• 1. Accepted
• 2. Success，accepted 和 success 的区别是什么呢？Accepted 是和 RPC 相关的，而 Success 是和我们调用的 serveice 相关的。换句话说如果 accepted 是 false，说明 RPC 阶段就错了， 没有调用到程序，而 success 是说明 RPC 之间是可以正常对话，但是具体执行的时候出错了
• 3. Results
• 4. Auth stuff 怎么让 client 和 server 互相绑定呢？

Client 该怎么知道这个端口呢？所以在系统中，main discovery 服务注册端口，可以列出 所有 service 的端口。所谓的服务发现也是在分布式系统是很重要的组成部分。我们需要把 数据发送给 server，这件事情看似简单还挺复杂的，在现代的 rpc 系统中由于数据在不同的 格式中转换，其时间损失要占据 20%以上。我们在传 paramater 的时候，必须 pass by value 而不是 pass by reference。

如果实现 pass by reference 我们只需要让在 page fault 的时候，从另一台电脑的对应虚 拟地址 copy 过来就可以了。这个就是 DSM（distributed shared memory），这个技术在体育 馆中的电视墙用的最多。在屏幕矩阵上，用 DSM 来共享内存对应一块块屏幕的显存即可。

参数传递

Server 重新在自己的程序中创建 pointer。那么传参到底有什么挑战呢？核心就是每台 机子对数字的理解是不一样的，比如 IEEE 754 的浮点解释标准……etc。是 64 位还是 32 位 还是更大，包括对齐方式等，否则我们的数据就会发生丢失，为了解决这些问题，就必须要 有一些标准，大家统一满足什么规范。一旦 server 更新了 message field，而 client 没有更新， 那么就会出现不一致。

所以，我们需要考虑 backward compatibility（新代码可以去读旧代码写的数据），forward compatibility（旧代码可以去读新代码写的数据），我们就要用 encoding 的方式，最早的 SUN 公司提出了 XDR，今天我们用的很多的是 JSON，还有一些 google protocol buffers。为什么不 用 language specific format 呢？比如 java 提供了原生的 serializable 接口，一旦继承了它，就 可以变成序列化，Python 也有 pickle，但是缺点就是把我们自己绑死在某个语言上了，并且 兼容性也不好。

这种格式的好处：human-readable，easy to debug。

缺点：

1. 关键的数据结构的 encoding 会出现二义性，比如 12 这个数字我们不知道 type 是什 么，是 signed 还是 unsigned 之类的。

2. 就是要支持 binary 的文件该怎么办，我们不得不转换成基于 base64 的格式，但是 这又是手动要做这样的一个转换。

3. 冗余 在 linux 里有个原则，不希望构造复杂的程序而希望构造出一系列小程序，通过管道的 形式去拼在一起。在管道传输的时候必须使用 asc2 来做传输。

当我们把两个 procedure 拆分成分布式的时候，我们 把拆的方式细化到了函数的粒度，把不同服务器的函数串在一起。这是我们以后要学的 function as a service，函数可以在服务器上任意的来回部署或迁移，就可以提升资源利用率， 函数怎么拆是一个关键，拆的不好就会把交互频繁的两个函数从 function call 拆成 rpc 降低55 性能。

在传输数据的时候，不同机器对数据的解释是不相同的，所以我们要对数据重新去做序 列化。与此相对的就是 binary format，好处就是很容易压缩、很紧凑，很快就可以变成内存 中的数据结构；缺点就是人类要读懂就很难。

我们可以进一步去压缩，为什么要把 type 放在最头上呢，这个顺序是很关键的，当我 们在做一个 server 收到一个 request，一开始什么都不知道，读到的第一个 byte 就很关键， 告诉我们后面是一个 string，这个 string 是一个 1 号（username），接下来串一个 length=6， 后来是传 6 个 byte。然后是 i64 类型……，真正有用的数据都是 data，前面这些数据都是 metadata，为了组织这些数据，metadata 是必需的。

1. 把 3 个 byte 变成一个 byte，因为 tag 不会太大

2. Length 很浪费，我们可以用一个变长的 8 位 list，也就是每 8 位如果第一位为 1， 说明剩余 7 位中有数字。

最后结果如下：

通过这种方式可以把 tag 和 type 压缩成一个 byte，最后就是 34 个 byte 就是这么来的。

Forward compatibility：我们只想要保证 field tag 和 field type 是兼容性即可，跳过不认识 的字段。

我们简单来看一下参数传递的小节：human-readable 和效率的权衡、最短越好、保证兼 容性。整个序列化的过程是自动的。用户只需要提供 IDL 去写这个结构。在最底下还要考虑 是 TCP 还是 UDP，不容易丢包的情况下就可以使用 UDP。

甚至可以使用 RDMA（direct memory access）。当用户使用的时候，我们不用关系底层 的网络实现。

遇到 Failure

当 RPC 遇到 FAILURE 怎么办？对于一个 local 的 procedure call 的情况下，failure 的情况 下是很少的，如果调用函数的情况都出错了说明机器已经出了很大的问题。Call 就是把地址 压栈跳转到对于的函数地址去执行，如果这种情况下都出错了，说明这个计算机有很大的问 题了，这个程序基本上会被 kill 掉，一般来说我们不去考虑 call 带来的问题。那么如果变成 了 RPC，遇到问题的概率远远大于本地的调用。序列化出错、RPC 版本出错、对方 server crash、 网络出错，当一个 RPC 调用没有得到任何返回的时候，有以下情况

• 1. 网络问题，包没有到 server。
• 2. Server 的 response 没有回到 client。 我们没有办法区分出上面两者。
• 3. 远程 crash
• 4. Request 队列
• 5. 远程执行了，但是你超时了
• 6. 执行了，还在 delay 等待 RPC 调用以后等多久？这个时间就很 tricky，只能根据经验来设置。

对于 RPC 来说，会 return 一个错误 status。RPC 的期望结果，exactly once，我们会遇到： 0 次，server 没执行 1 次，正常 1 次或多次，client 可能等不及了再发一次。 所以 RPC 一般提供 at least once（没收到 response 就重试，直到 ok）和 at most once（只 发送一次） 幂等性：我们希望实现 at most once，我们能不能让一个操作执行一次和执行两次是一 样的。比如按电梯：按三次和按一次是一样的，但是存钱不是幂等的。如果实现不了幂等性， 怎么实现 at most once 呢，我们要有别的机制去记录。Server 可以把执行成功的 xid 记录下 来，如果发现已经做过了那就返回 OK。

RPC 有很多 component，在网络上传输的格式要有标准，我们通过 lib 来实现底层细节 stub，定义完了 IDL 后，我们就可以自动产生一些 stub code，然后去做序列化，server 就是 去 reply，server 的 framework 会把 message dispatch 到不同的 server 中。 超时方案：要设置一个超时时间。

NFS

• NFS 是什么：NFS 是一种分布式文件系统协议，允许客户端通过网络访问远程服务器上的文件，像操作本地文件一样使用这些文件。
• 基本原理：客户端将远程服务器的文件系统“挂载”到本地，通过网络进行文件的读取、写入等操作。
• 无状态设计：NFS 服务器不保留客户端的状态信息，每次请求独立处理，服务器崩溃后无需恢复客户端状态。
• 缓存机制：为了提高性能，客户端可以缓存文件数据，减少访问服务器的次数。

问题

• 容量限制：只能依赖单个服务器上的磁盘，容量有限。
• 可靠性问题：如果服务器崩溃，远程文件将无法访问。
• 性能问题：文件的性能受限于单个文件的操作以及单一的网络带宽。

GFS

GFS（Google File System）是专为分布式大规模数据存储设计的文件系统，解决了在传统文件系统中难以应对的容量、可靠性和性能问题。其实现方式可以分为以下几个关键点：

总体实现

1. 分布式架构

GFS 采用分布式文件系统架构。文件被分割成多个较大的数据块（通常为64 MB），每个块存储在不同的服务器（称为Chunkserver）上。这样，通过将文件分布到多个服务器，可以大幅提升系统的存储容量和性能，轻松扩展整个集群的容量。

2. 主节点管理

GFS 使用一个主节点（Master node）来管理文件与块（Chunk）之间的映射关系。主节点存储了文件目录和每个文件块的位置，客户端通过与主节点的交互找到所需的文件块后，直接与 Chunkserver 进行数据交换。这种设计简化了文件的查找和管理。

3. 多副本机制

为了提高可靠性，每个文件块在不同的 Chunkserver 上有多个副本（通常为3个）。当一个服务器发生故障时，客户端可以从其他副本中获取数据，保证文件不会因为单点故障而丢失。这种副本机制让 GFS 在面对硬件故障时依然能够保持高可用性。

4. 并行读写

GFS 支持并行读写操作，多个客户端可以同时从不同的 Chunkserver 读取文件块。通过并行化读写，GFS 大大提高了文件访问的效率，尤其在处理大文件时，能够充分利用网络带宽和服务器的计算能力。

5. 松散一致性模型

GFS 采用了一种 松散一致性模型 ，允许在一定时间内数据处于不一致状态。这种模型通过主节点协调写操作，确保数据最终能够在多个副本之间达成一致性。虽然放宽了一部分一致性要求，但这种设计能够提高系统的写入性能。

6. 容错和恢复机制

GFS 具有很强的容错能力，系统会定期检测 Chunkserver 的状态，如果发现某个副本丢失或服务器故障，主节点会自动指派其他服务器重新创建该副本，保证数据的完整性和可用性。

操作

GFS 没有标准的操作系统级别 API，也没有完整的 POSIX API。它提供的是 用户级 API 。

支持的操作：

• 基本操作：create/delete/open/close/read/write（创建、删除、打开、关闭、读取、写入）。
• 额外操作：snapshot/append（快照、追加）。

不支持的操作：

• 链接（link）、符号链接（symlink）、重命名（rename）。

相关问题

GFS只用一个master，为什么？

可以使得设计简单，因为Google每一个块大小64M，所以需要维护的块数量不大，可以做到内存就完成任务。

• 所有元数据存储在主节点的内存中
  • 超快速访问
• 名称到块的映射
  • 使用内存中的树结构存储
  • 同时在磁盘上的操作日志中持久化（比如主机挂了，仍然可以恢复，后续章节会讨论）
• 块ID到块位置的映射
  • 存储在内存中，不需要日志记录
  • 启动时从所有块服务器查询（询问块的信息，快速掌握每一个ChunkSercer信息）
  • 保持最新状态 ： 主节点负责管理所有内容

交互模型

读操作

1. 联系主节点（master）
   • 客户端首先与主节点通信获取文件的相关信息。
2. 获取文件的元数据（metadata）：块句柄（chunk handles）
   • 主节点返回文件的元数据，特别是块句柄的信息。如果元数据已经被缓存，此步骤可以被跳过。
     获取每个块句柄的位置（location）
3. 客户端获取这些块所在的服务器位置。每个块可能在多个副本服务器（chunkserver）上有存储副本。
   • 联系任何可用的块服务器（chunkserver）获取块数据（多个服务器中任意一个即可，因为备份过）
4. 客户端从任意可用的块服务器请求并获取所需的数据块。（真正开始读）

写操作

• 写操作的复杂性：与读取相比，写操作不太频繁，但更复杂，因为需要处理一致性问题。
• 一致性模型：GFS 采用了一种松散一致性模型，使得实现更加简单高效。（可能没有读到刚写入的东西，或是同时写一个东西时候，二者产生了冲突）
• 设计目标：
  • 每个副本最终拥有相同的数据。（最终一致模型）
  • 减少与主节点的通信。

为保证一致性需要协调写操作

为什么需要协调？

• 考虑到并发写入的情况，多个客户端可能同时对同一个块进行写操作，如果不进行协调，可能会导致数据不一致。因此，必须由一个主副本来协调写入顺序。

如何选择主副本？

• 我们不能直接指定一个主副本，因为主副本可能会发生故障。

解决方案

• 主节点（Master）会向某个副本授予一个块租约（Chunk Lease），让这个副本成为主副本（Primary Chunkserver）。
  • 这个主副本是唯一能够修改块（chunk）的副本。因此，所有的写修改都将要发到这里。
• 如果需要，主副本可以请求延长租约的时间。
  • 主节点会增加该块的版本号，并通知其他副本进行同步。

具体过程

阶段 1：发送数据

• 传输数据，但不写入文件。
• 客户端会得到一个副本列表，标识主副本（Primary）和次级副本（Secondary）。
• 客户端将数据写入最近的副本。
• 管道式转发：副本服务器通过流水线方式转发数据。（可以减小单个传输数据压力）
• 块服务器将数据存储在缓存中（内存中）。

阶段 2：写入数据

• 将数据添加到文件中（提交）。
• 客户端等待所有副本确认已经收到数据。
• 客户端向主副本（Primary）发送写请求。
• 主副本（Primary）负责序列化写操作（先应用写操作，然后转发给其他副本）。
• 当所有确认（ack）都收到后，主副本向客户端发送确认。

总结

数据流（阶段 1）和控制流（阶段 2）是不同的

• 数据流（Phase 1）
  • 路径：客户端（Client）→ 块服务器（Chunkserver）→ 块服务器（Chunkserver）→ …（通过流水线方式转发数据）
  • 顺序：数据流的顺序无关紧要，数据可以在不同的副本间自由传递。
• 控制流（Phase 2）
  • 路径：客户端（Client）→ 主副本（Primary）→ 所有次级副本（Secondaries）
  • 顺序：必须保持顺序，尤其是在多个客户端同时进行写操作时，主副本负责保证写操作的顺序。

块版本号

• 用于检测某个副本是否有过期数据。
• 主副本（Primary Chunkserver）维护块的版本号。（重启时候可以判断替换）
• 如果检测到某个副本的数据是过期的，它将被替换。

总结

• 大多数文件是追加的，而不是覆盖：
  • 原因：例如向 Google 的全球存储中添加新的网页数据，通常是追加而不是覆盖已有数据。（同时写还是会有问题，可能会有覆盖情况）
• 文件内的随机写入非常少见：
  • 这意味着我们需要提供高效的追加操作。
• 追加操作始终是一致的：
  • 即使 GFS 采用的是一个较弱的一致性模型，所有文件最终都会保持一致（所有副本都会保持相同）。

也正因为如此，GFS 没有目录的数据结构。

例如，目录文件通常包含目录中所有文件的名称，但在 GFS 中并不存在这种结构。
没有别名（即不支持硬链接或符号链接）。
命名空间是一个单一的查找表，将路径名映射到元数据。
类似于今天描述的键值存储（key-value store）。

问题

松散一致性模型（只保证最终结果一致）：

• 对于并发修改的结果（除了追加操作），其结果是未定义的，也就是说并发修改可能导致数据不一致。

单节点主控节点（Single-node master）：

• GFS 使用单一主节点，这是一个潜在的单点故障问题（下一代 GFS 通过更高级的技术对这一问题进行了改进）。

尽管有这些限制，GFS 在 Google 的数据中心工作负载中表现良好，满足了当时的需求。

HDFS

—–another popular (open-source) DFS

基本和GFS一模一样，区别就是名字不同

KVS

基本介绍

KVS: 键值存储（Key-Value Storage, KVS）系统

存储抽象：

• 每个数据（Value）对底层存储/数据库是不透明的，存储系统并不关心数据的具体结构。
• 键（K）和值（V）都可以是任意的字节序列（如 JSON、整数、字符串等）。
• 数据通过键（K）进行索引，键本身也是一种数据。

存储方式：

• 数据存储在磁盘上，以便容错和支持大容量存储。
• 也可以选择将数据存储在内存中，以提高访问速度。

应用级接口（API）：

• Get(K) -> V：根据键K获取对应的值V。
• Scan(K, N)：从键K开始，获取后续N个键值对。（新加入的API，可以用于快速日志查询）
• Update(K, V)：更新键K对应的值为V。
• Insert(K, V)：插入一个新的键值对。
• Delete(K, V)：删除键K对应的值。

存储抽象的重新映射：

• Key（键）：映射为文件名（可能包含路径）。
  • 假设键不是很长，可以将键作为文件的名称。
• Value（值）：映射为文件内容。
  • 因此，可以将每个键值对（K, V）存储为一个文件。

应用级接口（API）对应：

• Get(K) -> V：类似于文件的 OPEN(…) + READ(…) 操作。
• Insert(K, V)：类似于 CREATE(…) + WRITE(…)，用于创建新文件并写入内容。
• Delete(K, V)：类似于 DELETE(…)，用于删除文件。
• Update(K, V)：类似于 OPEN(…) + WRITE(…)，用于更新文件内容。

这种映射使得键值存储系统可以与文件系统进行类比，实现简化的文件操作与存储管理。

在文件系统上实现KVS的效率很低

冗余的系统调用容易导致的性能问题

示例：

• Get(K,V) 需要两个系统调用：OPEN(…) + READ(…)。
• 理想情况下，我们希望通过一次系统调用，甚至是零次系统调用来查询数据，以减少系统开销。

空间放大问题：

• 文件数据存储在固定大小的块中（例如，512B 到 4096B）。
  • 这样做是为了匹配底层设备的块大小，同时便于管理元数据。
• 问题：键值存储系统中的值（Value）可能很小，比如只有 64B。
  • 由于文件系统存储文件时采用固定大小的块，这可能导致存储小的键值对时浪费空间，即实际存储空间远大于实际需要的大小，造成空间放大。

Idea：使用一个或几个文件来存储键值存储数据

• 不同的Key-Values可以打包到同一个磁盘块中
• 减少系统调用开销：打开文件一次，然后处理所有请求

为什么要建立在文件系统之上？

• 我们仍然需要一个与磁盘硬件交互的系统！虽然现代KVS也可以绕过文件系统，但并不常见。

修改策略

一般使用 append 而不是直接修改，因为append是顺序访问的，磁盘中顺序读取速率明显高于在随机读取再去修改。（见下表格）

不同存储介质的访问速度总结（顺序和随机访问）

访问类型	典型访问延迟	单位	特点	顺序/随机访问
CPU 访问 L1 缓存	1-3	纳秒（ns）	最高速的存储层，CPU 与缓存紧密耦合	顺序和随机访问都非常快
CPU 访问 L2 缓存	3-14	纳秒（ns）	比 L1 稍慢，仍然非常快速	顺序和随机访问都非常快
CPU 访问 L3 缓存	10-30	纳秒（ns）	多核处理器共享的缓存，较慢但容量更大	顺序和随机访问都非常快
CPU 访问内存（RAM）	50-100	纳秒（ns）	比缓存慢，主要用于存储当前运行的程序和数据	顺序和随机访问都较快
内存访问 SSD	50-100	微秒（μs）	固态硬盘，比内存慢数百倍，但比 HDD 快很多	顺序访问较快，随机访问稍慢（约2-5倍）
内存访问 HDD	5-10	毫秒（ms）	机械硬盘，适用于大量数据的长期存储	顺序访问较快，随机访问非常慢（慢10-100倍）
网络访问（LAN）	0.1-1	毫秒（ms）	局域网内的传输速度，延迟较低	顺序和随机访问都较慢
网络访问（WAN）	10-500	毫秒（ms）	广域网（互联网）传输，延迟高，受距离和网络状况影响	顺序和随机访问都非常慢

实现方式

Log-structured file

特点

append only，所有的修改都只是追加，不产生修改

函数	功能	简要描述
Update	更新操作	将更新数据以追加的方式写入日志，不直接修改原数据块。
Insert	插入操作	新数据顺序写入日志末尾，记录新的元数据指向此位置。
Delete	删除操作	通过附加一个NULL条目，实际数据保留，等待段清理回收空间。

问题

读取速率十分缓慢，需要顺序读取找到目标 Complexity: O(n)

解决方式：使用索引，加速获取。

Log + in-memory hash index

索引策略

在内存中保留一个哈希映射，映射日志文件中的键->字节偏移量

问题

索引必须在内存RAM里面

只擅长：当工作负载有很多更新但没有插入时

• 例如，过多的插入会耗尽内存RAM（存取大量数据时候，索引表全部在内存是不现实的）

Log + on-disk hash

基于链表的哈希索引（Linked-list based hash index）

原理：通过哈希映射，根据对应的值去找块，发生冲突就从头往后寻找

• 优点：实现简单。
• 缺点（对于最简单的实现）：
  • 读性能差：在发生哈希冲突时，读取性能差，需要在随机 I/O 中遍历链接的桶。
  • 插入性能差：同样在哈希冲突时，插入性能也很差，问题与读取类似。

问题：如何改进？

• 简单的想法：将同一个哈希桶的条目放在同一个文件块中，以减少链的长度。

Cuckoo hashing

Get()

在 Cuckoo Hashing 中，Get(key) 操作非常高效，因为每个键只能存储在两个位置之一：

1. 使用哈希函数 H0 和 H1 分别计算出键的两个可能位置：
   • Buckets0[H0(key)] 或
   • Buckets1[H1(key)]
2. 先检查 Buckets0[H0(key)] 是否包含该键：
   • 如果找到，则返回对应的值。
3. 如果 Buckets0 中没有找到该键，则检查 Buckets1[H1(key)]：
   • 如果找到，则返回对应的值。
4. 如果两个位置都没有找到该键，返回键不存在的结果。

Insert（）

计算键的两个哈希值，找到它可以存放的位置：Buckets0[H0(key)] 或 Buckets1[H1(key)]。
如果其中一个桶是空的，将键插入该位置。
如果目标位置已经被占用，则将原有的键“踢出”，并尝试将被踢出的键重新插入到它的另一个哈希桶中（相当于搬迁键）。
这个过程会不断重复，直到找到空位或者达到重新哈希的限制。

Update（）

1. 使用哈希函数 H0 和 H1 查找键的位置。
2. 如果在任意一个桶中找到该键，直接更新其对应的值即可。
3. 如果没有找到键，则需要执行插入操作。

优点

• 查找时间为常数 O(1)，因为键最多只能在两个位置之一。
• 减少哈希冲突的链长度问题。

缺点

• 插入过程中可能会发生“搬迁”操作，导致性能不稳定。
• 如果冲突过多，可能需要重新调整哈希表的大小（rehashing）。

Method	Update/Insert efficient	Get efficient	Range Query	Support large dataset
Log	Yes	No	No	Yes
Log + in-memory hash index	Yes	Yes	No	No
Log + on-disk hash	No	Medium	No	Yes
B+Tree	No	Medium	Yes	Yes
LSM tree	Yes	Yes	Medium	Yes

问题

• 可以放在磁盘上，但需要谨慎重新设计哈希方案，或者仔细选择合适的哈希方案，权衡利弊。
• 日志文件不断增长 -> 可能导致磁盘空间耗尽问题。
• 缺乏范围查询支持（效率极低）
  • 例如，无法高效地扫描某个范围内的所有键（如从 “kitty00000” 到 “kitty99999” 的键）。

如何防止日志文件无限增长？

Log-structured 设计使更新操作非常快速，因为只需要将数据追加到文件中。然而，文件会不断增长，最终会耗尽磁盘空间。

• 问题：日志文件中会有许多重复记录，导致浪费空间。同时，删除的数据仍然保留在文件中。

解决方案：压缩（Compaction）

• 压缩过程：扫描整个文件，删除重复记录，将剩余的数据写入一个新文件。
• 问题：如果文件太大，压缩整个文件会非常耗时。

改进方案：分段压缩（Compaction with Segmentation）

• 分段：将文件分为固定大小的段（segments）。
• 写入新段：如果某个段已满，就创建一个新的文件来进行插入操作。
• 控制压缩粒度：通过调整段的大小，可以控制压缩操作的粒度，避免一次处理过大的文件。

如何处理删除

• append一个NULL的entry
• Garbage-collected 在 compaction 期间

LSM_TREE

索引结构B树总结

• 1.可以支持范围查找
• 2.Get(K), Insert(K,V) and Update(K,V) are relative slow

LSM优势

• 1. Searching a given key in a SSTable is efficient (no brute force)
• 2.

分布式系统

Consistency model

强一致性模型

It’s easy for users to reason about correctness assuming（在程序员视角等价于一个单线程）

• Everything has only one-copy（只有一个拷贝）
• The overall behavior is equivalent to some serial behavior（等价于单线程行为）
• The overall behavior can be viewed as a system that never fails

等价于线性，但不符合人类直觉

global issuing order

强一致性模型，严格按照操作时间顺序

• All the concurrent execution is equivalent to a serial execution
• The order of each op matches the global wall clock time

问题：没有办法在分布式系统实行

无法确定P0，P1具体开始时间，导致无法具体执行指令，同时不同设备时间戳也不同

Per-process issuing/completion order

• All the concurrent execution is equivalent to a serial execution
• The order of each op matches per-process issuing/completion order（按照到达时间）

Primary-backup model

• Primary forwards writes to all the replicas
  M0 executes writes locally (in order)
  Respond OK

一致性模型和最终一致性

逻辑性保持正确性的原因

• 每个数据项只有一个副本。
• 整个系统的行为等同于某种串行行为。
• 整个系统的行为可以被视为一个从不失败的系统

这三种一致性模型在分布式系统中定义了不同的顺序关系

1. 全局发起顺序（严格一致性）

• 定义：所有操作在全局上按照时间顺序进行，所有进程都对操作的顺序有完全一致的视图。
• 特点：任何一个操作的结果必须在所有后续操作之前可见，确保系统状态在所有用户看来是完全一致的。
• 局限性：实现严格一致性通常需要较高的延迟和复杂的协调机制。

2. 每个进程的发起/完成顺序（顺序一致性 sequential consistency）

• 定义：每个进程的操作在本地是按照其发起的顺序可见，但不同进程之间的顺序可能不一致。
• 特点：用户可以看到自己发起的操作的顺序，但对于其他进程的操作的顺序没有全局视图。
• 局限性：允许某些操作的并行性，但可能导致不同进程看到的系统状态不一致。

3. 全局“完成-发起”顺序（线性化 linearizability）

• 定义：在一个逻辑时间点上，所有操作的完成时间与发起时间都有一个一致的顺序，即每个操作都有一个唯一的时间戳，且所有操作在时间上是顺序排列的。
• 特点：用户在任何时候看到的系统状态都是一致的，且可以通过一个虚拟的线性化时间轴来理解。
• 局限性：比严格一致性宽松，允许更高的并发性，但仍然要求系统能够在逻辑上进行一致的操作顺序。

实现线性化 linearizability

对于写操作：
主节点（Primary）将写操作转发给所有副本（Replicas）。
主节点在本地按顺序执行写操作。
执行完后，主节点返回“OK”给客户端。

对于读操作：
主节点直接返回其本地数据的副本给客户端。

Implementing linearizability: Primary-backup approach

Primary-Backup Model的缺点
性能问题：

读取性能：每次读取操作都需要额外的往返时间（RTT）来联系主节点（Primary）。这增加了延迟，尤其是在高负载的情况下。
写入性能：写操作不仅需要与主节点进行通信，还需要与所有副本（Backups）联系，这导致更多的RTT，进一步增加了延迟。
可扩展性问题：

主节点可能成为性能瓶颈。随着客户端请求的增加，主节点需要处理所有的读写操作，可能导致负载过重，影响整体系统的响应时间和吞吐量。
可靠性问题：

如果主节点或某个副本崩溃，系统的可靠性会受到影响。虽然可以设计冗余机制，但在主节点崩溃的情况下，系统可能会变得不可用，尤其是如果没有有效的故障转移机制。

我们可以允许read读取任意副本吗？

对于写操作：

1. 主节点（Primary）转发写请求：主节点将写操作转发给所有副本（Replicas）。
2. 本地执行：主节点（M0）在本地按顺序执行写操作。
3. 响应：执行完后，主节点返回“OK”给客户端，表示写入成功。

对于读操作：

返回副本数据：任何副本都可以返回其本地数据的副本给客户端。这种设计允许从多个副本进行读取，以提高可用性和性能。

问题，此时P0阅读产生问题

通过分区来优化Primary-Backup系统的性能，特别是解决了可扩展性问题。每个Primary节点处理不同对象的读写请求，有效分散了负载，减少了单节点成为瓶颈的风险。

Eventual consistency

特点：

最终一致性（Eventual consistency ）：所有服务器最终都会收到所有写操作，拥有相同写操作的服务器将有一致的数据内容。因此，如果数据没有新的更新操作，最终所有的访问都会返回最后一次更新的值。

优化的读写操作：

读操作：返回服务器上的最新本地副本数据，这样可以提高读操作的性能，减少延迟。
写操作：写操作首先在本地执行并直接返回，写入的数据会在后台传播到所有服务器（例如通过同步操作）。这是性能最优的实现方式，因为写操作不会因为等待同步而延迟。

GFS 的最终一致性模型

GFS 使用一种类似最终一致性的模型，即“每个副本最终会有相同的数据”。GFS 通过使用主节点来协调写操作，实现最终一致性。这种方式适用于数据中心的场景。

GFS 适合聊天应用吗？

显然不适合，原因如下：

1. 高延迟：GFS 的主节点协调和同步过程可能导致较高延迟，无法满足聊天应用的实时性需求。
2. 副本同步问题：聊天应用需要快速同步数据，GFS 的最终一致性模型可能导致消息不同步。
3. 设计目标不同：GFS 主要为大规模存储设计，不适合需要低延迟、高一致性的聊天应用场景。

我们想在聊天类应用程序中读/写什么

方法：直接写入离客户端最近的服务器，服务器确认写入后，再将更新传播给其他服务器。服务器可以和客户端在同一位置。

问题：

在这种设置下，可能出现的问题：

一个常见的异常现象叫做写-写冲突。当多个服务器在不知道彼此的情况下同时更新相同的数据时，会发生这种情况。

结果：数据出现分歧。例如，一个服务器先添加 X 后添加 Y，而另一个服务器顺序相反，最终的数据就不一致，无法保证只有一个正确的版本。

Linearizability vs. Eventual Consistency 对比表

特性	线性化（Linearizability）	最终一致性（Eventual Consistency）
冲突处理方式	悲观的冲突处理	乐观的冲突处理
冲突写入的常见性	冲突写入是常见情况	冲突写入是罕见情况
更新生效时间	更新在序列化之前不会生效	允许更新发生，稍后再对数据进行序列化
最终目标	数据需要在多个设备之间保持一致	最终目标相同：数据在多个设备之间保持一致

需要处理的异常：

1.写-写冲突（Write-write conflict）：

解决方法：在本地写入后，将写操作以后台任务的方式发送到所有服务器。每个服务器会应用这些写操作，并在必要时解决冲突。

问题 #1：如何应用更新？

是否可以直接覆盖原始内容？例如，使用键值存储（KVS）的 put() 操作来覆盖？

聊天数据保存在一个键值存储中，值是一个向量。

• 覆盖原始内容：例如 chat[cid] = [ …, new_sid]，直接将新的内容写入，覆盖旧的内容。会导致数据丢失

初步方案：直接用新的写入替换旧的值

• 不能。这样做会丢失应用语义，从而导致“不一致”。虽然最终的值可能看起来相同，但它不会符合应用程序的预期逻辑或意图。

解决方案：将更新操作定义为函数

更新操作是一个函数，而不是一个新值：在处理写操作时，用户提供一个函数来更新数据，而不是直接提交新的值。（1. allocate a sid; 2. chat[cid].append(sid)）

同时函数必须是确定性的：函数的执行结果必须是确定性的（即相同输入必须得到相同的输出），以确保所有服务器在应用此函数时得到相同的结果。

新的问题，顺序如何保证

e.g. Client发送X ， iPhone发送Y ， 没有保证二者相同的顺序

有序更新列表处理方案

1. 记录更新操作：每个节点将更新操作记录在日志中。
2. 更新排序：根据某种规则（如时间戳）对日志中的更新进行排序。
3. 延迟更新：在确定更新能按正确顺序执行前，暂缓应用更新操作。
4. 同步机制：确保所有节点的日志一致，保证每个节点都有相同的更新。

此时的要点是，保证第二步的规则出来的顺序是一致的。

问题：二者的时间戳恰好就是相等

解决方案：为更新分配唯一ID

1. 更新ID：每次更新分配一个唯一的ID，格式为 <时间 T, 节点 ID>。
   • 时间 T：表示创建更新时的时间戳。
   • 节点 ID：表示创建该更新的节点，用于在时间戳相同时打破平局。
2. 更新ID的分配：
   • 每个更新由创建该更新的节点分配唯一的ID。
3. 更新排序：
   • 如果有两个更新（X 和 Y），我们可以通过时间戳 T 来排序；
   • 如果时间相同，则使用节点ID来决定优先顺序，确保更新有唯一的顺序。

问题1：我们能否使用 <节点 ID, 时间 T> 作为唯一ID？

• 排序更新：没有问题，仍然可以根据时间戳排序。
• 用户体验（因果关系保留）：不太好。比如，如果我在iPhone上比iPad上更早发布一条消息，使用 <节点 ID, 时间 T> 会导致我总是先看到iPhone的数据，哪怕实际上iPad上的消息更早。

问题2：<时间 T, 节点 ID> 能防止上述用户体验问题吗？

• 能否解决问题：取决于节点的时钟时间。如果所有节点的时钟同步良好，<时间 T, 节点 ID> 可以避免因果关系错乱的问题。
• 挑战：在分布式系统中，传统系统组件的时钟不同步，导致时钟偏差。因此，基于时钟时间的方案会面临时间不一致的问题，可能无法完全解决用户体验上的因果关系问题。

这样就可以保持结果一致性

问题，什么时候再更新到数据库上

1.每一次更新就直接上传到数据库，问题是因为服务器的初始状态不同！

回滚同步前的所有更新

1. 清空存储：将存储重置为空状态。
2. 重新运行所有更新函数：从空的存储状态开始，重新应用所有更新。
3. 同步后：Srv1 和 Srv2 具有相同的更新集合（有序日志），并达成相同的最终状态。

目标：时钟时间反映真实的（墙上时钟）更新顺序

我们希望更新顺序能够与真实的墙上时钟时间一致。也就是说，如果你先在iPhone上发布一条消息，然后在iPad上发布另一条消息，iPhone上的时间应该小于iPad的时间。然而，现实中的计算机节点之间的时钟并不是完全同步的，这会导致问题。

更新顺序是否能与墙上时钟时间一致？

• 理想情况：如果所有节点的时钟完全同步，那么更新的顺序会与真实的时间保持一致。iPhone的消息会先于iPad的消息。
• 实际情况：在分布式系统中，节点的时钟可能不同步，导致时间戳不准确。即使iPhone先发布消息，由于时钟误差，iPad的消息可能会有更早的时间戳，从而打乱了顺序。

示例

• 场景：你在iPhone上先发送了一条消息，然后在iPad上发送了另一条消息。
• 预期行为：iPhone的消息应该先显示，iPad的消息后显示。
• 实际行为：由于iPhone和iPad的时钟不同步，iPad的时钟可能比iPhone快。因此，iPad的消息可能会被认为先发生，即使它实际上是在iPhone之后发布的。这导致了不符合因果关系的更新顺序。

例如此处，add<X,Srv1>先出来，但时间戳大，删除X后发生，但时间戳小，同步时候就会出现问题。

因果关系的定义：

在分布式系统中，事件 X 和事件 Y 存在因果关系（X -> Y）当且仅当：

1. 单节点上的顺序：X 和 Y 在同一个节点上创建，并且 X 发生在 Y 之前（单线程执行）。
2. 跨节点的因果关系：X 和 Y 由不同节点（如节点 i 和节点 j）创建，且 X “引发” 了 Y 的发生。
   • 这意味着 X 的结果影响了 Y。

示例：

• X 是添加一条聊天消息（add chat），Y 是删除该聊天消息（delete chat）。
• 因果链：如果存在一个事件 Z，使得 X -> Z -> Y（即 X 导致 Z，Z 再导致 Y），那么 X 和 Y 之间存在因果关系。

问题：<时间, ID> 不能保持因果顺序

• 原因：由于节点的时钟不同步，直接使用物理时钟（即 <时间, ID>）来排序无法保证因果关系的正确顺序。例如，某个事件的实际发生时间可能比另一个晚，但由于时钟不同步，时间戳可能会错误地反映顺序，导致因果关系混乱。

目标

• 目标：时钟应当反映因果顺序，也就是说，如果事件 X 导致了事件 Y，那么 X 的时间戳应该小于 Y 的时间戳，保持事件的因果关系。

思路：使用逻辑时钟

Lamport clock algorithms

• 每个服务器维护一个时钟T。
• 随着实际时间的推移，T递增，例如每秒增加1。
• 如果从其他服务器看到T’，则更新T为 T = Max(T, T' + 1)。

Lamport clock的问题

Lamport时钟能给所有事件一个全序吗？

• 不能，因为会有相同的时间戳。

如何解决平局？

• 我们可以通过添加额外的顺序来解决，比如使用 <逻辑时间, 节点ID>。
• 这样可以保证全序保持因果关系。

为什么全序理想？

• 如果副本按照全序应用写操作，那么它们的状态会最终一致（收敛）。

对于每一对事件，我们都可以比较它们的时间戳，例如 T(e1) < T(e2) 或 T(e1) > T(e2)。

问题：这种顺序可能过于严格。

对于不相关的事件，顺序可能与外部观察者的顺序不一致。
例如：我先给Alice添加了一句话，然后独立地给Bob添加了一句话，系统可能用Lamport时钟将Bob的事件排在前面，尽管它们是无关的。

时钟表示为一个向量（每个服务器一个条目）。

• 每个条目对应服务器上的本地Lamport时钟。
• 随着实际时间的推移，本地时钟T递增，例如每秒增加1。
• 如果从其他服务器看到时间戳T，则更新 Ti = Max(Ti, Ti' + 1)。

Lamport 时钟 vs. Vector时钟 对比表

特性	Lamport 时钟	Vector时钟
因果关系捕获	捕获因果关系	捕获因果关系
顺序类型	全序（Total Order）	部分序（Partial Order）
使用场景	适用于大多数场景	用于需要更严格因果关系的场景
事件排序	能够为所有事件提供顺序	提供部分事件的因果顺序
存储需求	节省空间，仅需存储单个时间戳	需要更多存储空间，每个节点一个条目
复杂性	较低	较高

总结：

• Lamport 时钟：在许多场景下已足够，能够为事件排序，并节省存储空间。
• Vector时钟：提供更细粒度的因果关系跟踪，但需要更多的存储空间和复杂性。

问题回顾

为了提升性能，我们会立即在本地节点执行写操作。然而，这些写操作可能是不稳定的（我们称为暂定写入）。之前的解决方案是重新从空存储状态开始，重新运行所有更新函数，但这种做法效率低下。

目标

1. 避免重新运行所有更新函数：我们希望避免每次都从头重新执行所有的更新操作，这样可以减少不必要的计算开销。
2. 减少日志的大小：优化日志系统，减少日志文件的存储大小，以提高系统的整体性能和资源利用率。

下一步的方案可能涉及增量更新、检查点机制或压缩日志来提高效率。

方案：区分暂定写入和稳定写入

每个服务器的日志由两部分组成：

1. 稳定写入（Stable writes）
2. 暂定写入（Tentative writes）

稳定写入在同步时不会被回滚，而暂定写入可能在同步时被修改或回滚。

问题：如何确定哪些写入是稳定的？

• 答案：使用Lamport时钟来判断写入是否稳定。
• 一个更新 WWW 是稳定的，当且仅当没有任何条目的Lamport时间戳小于 WWW 的时间戳。这意味着在所有节点的事件序列中，已经没有新的事件可能会在 WWW 之前发生，保证了因果关系。

提交（写入）方案

• 更新 <10, A> 是稳定的，前提是所有节点都已看到了所有时间戳小于等于 10 的更新。
  • 因为根据 Lamport 时钟的规则，它永远不会再看到时间戳小于 10 的更新。

问题：

即使如此，在重新连接时，仍然有许多写操作可能会被回滚。

解决方法方向：

为了减少回滚次数，可以进一步优化同步策略，如使用增量同步、优化暂定写入的处理机制等，以减少断连后的回滚操作。

方案

1. 主节点：指定一个服务器为“主节点”来管理写入操作的提交。
2. 分配全局提交顺序（CSN）：为每个写操作分配一个全局的提交顺序编号（CSN）。
   • 完整时间戳：每个写操作的完整时间戳由 <CSN, 本地时间戳, 服务器ID> 组成。
3. 稳定写入：任何拥有已知CSN的写入操作都是稳定的。
   • 顺序规则：所有稳定写入都会排列在暂定写入之前。
4. CSN交换：服务器之间交换CSN以共享提交顺序信息。
5. CSN定义全局顺序：CSN定义了已提交更新的全局顺序，确保所有已提交的写操作在各个服务器上按照一致的顺序应用。

课堂问题

If TS(event #1) < TS(event #2), what does it say about event #1 (create on node #1) and event #2 (created on node #2)?

Event #1 occurred at a physical time earlier than event #2

Node #1 must have communicated with Node #2

If event #1 has been synced to node #2, then event #1 must have occurred at a physical time earlier than event #2

冲突下保证原子性

Consistency under crash：All-or-nothing atomicity

Centralized approach

一台服务器被指定为“主服务器”。

• 为每次写操作分配一个总的提交顺序号（CSN）。
• 完整的时间戳格式为：<CSN, local-TS, SrvID>
• 任何具有已知CSN的写操作都是稳定的。

所有稳定的写操作都排在临时写操作之前。

CSN在服务器之间交换。

• CSN定义了已提交更新的全局顺序。

一台服务器请求主服务器为所有临时写操作分配CSN（包括从其他服务器接收到的写操作）。
即，主服务器可以为依赖的写操作分配更大的CSN。

问题：
完整时间戳是否总是与临时顺序匹配？

不全是。如果信息的更新两者之间没有依赖关系，就可能会不同。

日志可以长时间保留而无需修剪。
当节点接收到新的CSN时，可以丢弃所有已提交的日志条目，直到该点为止。
结果：不需要保留多年的日志数据。

强一致性模型（ strong consistency model ）

在出错情况下，要保持函数要么全执行，要么全都不执行（all-or-nothing）

对于用户来说，推理系统的正确性很容易，假设：

• 所有数据只有一个副本。
• 整体行为等价于某种串行行为。
• 需要在原子单元中执行的操作（通常称为事务中的操作）在一台机器上执行，并且要么完全发生，要么完全不发生（全有或全无的原子性）。

全有或全无（all-or-nothing）的原子性使得推理失败情况变得更加容易。

• 只需考虑操作发生或不发生的后果，而不需要考虑操作部分发生的情况。

实现方法

shadow copy

确保一组写入文件的操作是全有或全无的，例如将记录a和b写入银行文件。
高级思路（写时复制）：

• 不要修改旧副本（始终保留一个一致的副本）。
• 只有当所有写入操作成功时，才用更新替换原始文件。

问题：如果在fcopy或fsync过程中发生崩溃，会发生什么？

• 原始bank文件始终保持一致
• 我们可以删除bank_temp，这样转账就不会发生了

问题：如果重命名过程中发生崩溃，会发生什么？

• 对于银行转账，它是一致的（任务没成功，回退）

文件系统状态如何？

• 取决于文件系统的内部实现，如下图所示

简单的解决方法：

要求应用程序删除不必要的索引节点
应用程序知道应该删除“bank_temp”

问题：1.恶意攻击无法避免 2.复杂文件系统难以实现

好的解决方法：Journaling

总结

将数据写入新副本，然后可以原子性地切换到新副本。

转换是一个all-or-nothing的操作

• 使用日志记录重命名文件。

仅需文件系统的简单恢复过程

• 恢复后删除临时文件。
• 文件系统通过日志记录保持一致性。
  • 即，文件系统本身有恢复过程。

影子复制的缺点

• 只能一次进行一个操作。
  • 轻率地执行并发传输可能会导致一致性问题。
  • 即使这些操作理论上可以并行运行。
• 很难推广到多个文件或目录。
  • 必须将所有文件放在一个目录中，或者重命名子目录。
• 任何（小的）更改都需要复制整个文件。

Journaling

实现过程：

更新前的记录过程：

1. 记录更改到日志（Journal）。
2. 提交日志。
3. 执行更新。

崩溃前的情况：

• 提交前崩溃：没有数据被更改，丢弃日志。

崩溃后的情况：

• 提交后崩溃：日志完整，重做日志中的更改。

Journaling的缺点

所有内容都需要写入磁盘两次：

• 一次写入日志（journal）。
• 另一次写入最终存储位置（home location）。

当文件较大时，这种方式会变得问题重重。

Logging for atomicity

关键思想（与日志记录非常相似）：

• 避免更新磁盘状态，直到我们可以在故障后恢复它。

如何在影子复制或日志记录中实现这一点？

• 影子复制将更新缓冲在原始文件的副本中。
• 日志记录将更新缓冲在扇区中（可以看作是一个小日志）。

我们可以通过将所有更新存储在日志中来推广日志记录：

• 日志文件：一个仅包含更新结果的文件。
• 日志条目：包含一个原子单元的更新值（例如，传输）。

日志记录和影子复制的主要思想是，在操作完成之前不要直接修改磁盘状态，以确保故障恢复时的可靠性。影子复制通过在原始文件的副本上进行更改，而日志记录通过将更改缓存在一个小的日志（通常是扇区）中。在日志记录的通用方法中，所有的更新都存储在日志文件中，保证系统一致性

事务和提交点

我们称一组需要原子性的操作为“事务”。

事务通常为应用程序提供接口，以标记操作的原子性粒度：

• TX.begin()（事务开始）
• TX.commit()（事务提交）

在begin()和commit()之间的每次更新都存储在日志条目中：

• 可以通过重放日志中的每个条目来重新执行。

提交点

• 提交点是我们确定操作已经“全部完成”的时刻。

事务是一种确保一组操作要么全部完成，要么全部不完成的机制，维护了操作的原子性。通过事务开始 (TX.begin()) 和提交 (TX.commit()) 来定义操作的范围，日志记录了这期间的所有更改，便于在出现故障时通过日志重放恢复数据。当事务到达提交点时，操作被认为已经完整执行。

Redo-only

在更新新状态前，记录要更新的值到日志

重启后，我们需要将系统恢复到一致状态

• 基于存储在日志文件中的日志条目进行恢复。

方法

• 从头到尾遍历日志。
• 重新应用完整日志条目中记录的更新。

到目前为止，redo-only日志记录的优缺点

优点

• 提交操作非常高效：只有一个文件附加操作（带有更新的数据）。
  • 其他方法，如影子复制，会复制整个文件。

缺点

• 浪费磁盘I/O：所有磁盘操作必须在提交点进行。
• 所有更新必须在事务提交之前缓存在内存中。
• 日志文件会持续增长，虽然大多数更新已经被刷新到磁盘上（除非机器重启或崩溃，我们需要进行恢复）。

基本解决方案

• 我们允许事务直接将未提交的值写入磁盘。
  • 在提交点之前，这可以释放内存空间并利用磁盘I/O。

如何防止未提交事务的部分更新？

• 使用日志记录来撤销未提交事务的更新！

Undo-Redo

问题：我们是否需要redo条目？

• 取决于我们是否等待记录[a]写入磁盘（例如，sync）。
• 通常是的：等待两次磁盘同步很慢！
  • 尤其是对于非日志写入：日志是快速的顺序磁盘写入。

日志条目 vs. 日志记录

Redo-only日志记录将日志条目附加到日志文件中：

• 包含事务的所有更新。

Undo-redo日志记录将日志记录附加到日志文件中：

• 包含单个操作的更新。
• 来自不同事务（TX）的日志记录可能交错出现。
  • 例如，操作系统可能将事务调度暂停。
  • 因此，我们需要指针来追踪同一事务的操作。

恢复过程读取日志并根据其内容恢复状态。

恢复规则

1. 从末尾开始向前遍历。
2. 标记所有没有提交日志（CMT）的事务记录，并追加中止日志（ABORT）。
3. 从末尾开始向前撤销（UNDO）中止日志。
4. 从头到尾重做（REDO）提交日志。

解释： 在崩溃恢复过程中，系统通过读取日志来确定哪些操作已经完成，哪些未完成。通过这些恢复规则，未完成的事务会被标记并撤销，而已完成的事务则会被重做，以确保系统的一致性。

检查点（Checkpoint）

作用：确定哪些日志可以丢弃，然后丢弃它们。

问题：

• redo-only日志记录和undo-redo日志记录会将所有更新追加到日志文件中，导致日志文件不断增长，尽管大多数更新已经刷新到磁盘上。
• 大型日志文件不仅浪费存储空间，还会使系统恢复变慢。

挑战与观察：

• 简单方法的问题：直接运行recovery process虽然可以丢弃日志文件，但速度太慢，影响系统性能。
• 观察：未提交的更新通常只存在于内存中的页缓存中。如果将缓存内容刷新到磁盘，可以安全地丢弃这些日志。
• 关键问题：如果有正在进行的事务（TX）怎么办？需要确保正在进行的事务的日志被保留，以免丢失未完成的操作。

改进方案：

• 在进行检查点时，写入一个包含所有正在进行事务及其日志的检查点记录（CKPT），确保恢复时能够保留这些未完成的事务，防止数据丢失。

解决方案：检查点（Checkpoint）

• 目的：通过检查点机制，确定哪些日志已经不再需要，减少日志文件的大小。
• 检查点的基本步骤：

1. 等待没有操作在进行。
2. 将检查点（CKPT）记录写入日志，包含所有正在进行事务及其日志的列表。
3. 刷新页缓存，将未提交的更新写入磁盘。
4. 丢弃除检查点记录外的所有日志记录。

恢复过程

• 对于T1已经完成，都不需要做
• T2，需要对checkpoint以后的部分，进行恢复
• T3，从自己的log entries重新恢复
• T4，根据CKP和Log entries一起恢复
• T5，直接从log里面
• T1: do nothing
  T2: redo its update based on the log in its checkpoint
  T3: redo its updates based on the log entries
  T4: undo its updates based on the log in both CKP & log entries
  T5: undo its updates based on the log entries

对比总结

Redo-only日志记录：

• 执行期间：相比于Undo-redo日志记录，Redo-only日志记录需要的磁盘操作更少，因此更快。
• 恢复期间：只需要一次扫描整个日志文件，恢复速度也相对较快。
• 应用场景：Redo-only日志记录通常是首选，除非遇到包含大量内存状态的事务。

Undo-only日志记录：

• 日志规则：
  • 在修改持久状态之前，先追加Undo日志记录。
  • 状态修改必须在事务提交之前被刷新到磁盘。
  • 没有Redo阶段。
• 应用频率：很少使用。
  • 执行期间：比Undo-Redo日志记录慢得多。
  • 恢复期间：恢复速度较快。

Before-or-after atomicity

The overall behavior is equivalent to some serial behavior

对于多线程，可以等价成为一个单线程，不仅是读写。

race condition问题

经典问题，多个人对一个值同时加，且没有注意到另一个人修改，没有保证加的原子性。比如说微信接龙，也有这样的问题。

• 必须确保所有可能的调度都是安全的。
  • 可能的调度排列数量巨大。
  • 有些不良调度会导致系统崩溃，有些则不会，情况有时是不稳定的。
• 在调用之间的小时间变化可能导致不同的行为，这可能隐藏了错误（例如，Therac-25事故）。
• 这些错误也被称为“海森bug”（Heisenbugs），源自海森堡的不确定性原理。
  • 可能的系统解决方案-1：DMT（确定性多线程）。
  • 可能的系统解决方案-2：记录和重放。
• 这两种解决方案在正确性或成本方面都很难实现，或者两者都有问题。

before-or-after atomictity

为了防止由竞态条件（race condition）引发的危险，我们需要一组读/写操作是原子的。

• 例如，不能看到或覆盖并发操作的中间状态。
• 一个并发操作可能包含多个可以线性化的读/写。

并发操作具有前后属性，如果从调用者的视角来看，操作的效果就像是完全在另一个操作之前或之后发生的，而不是部分重叠。

与Linearizability区别

符合Linearizability，但不符合before-or-after

我们将一组需要原子化的操作称为“事务”。

事务通常为应用程序提供接口，以标记操作的原子性粒度：

• TX.begin()
• TX.commit()

因此，通常情况下，事务必须同时提供“全有或全无”（all-or-nothing）和“前后原子性”（before-or-after）的特性，也就是 ACID。

解决方式

使用锁来实现前后原子性：全局锁

锁：一种数据结构，允许在任意时刻只有一个CPU获取该锁。

• 程序可以获取（acquire）和释放（release）锁。
• 如果获取失败，则CPU将等待直到成功获取锁。
• 示例：pthread_mutex。

全局锁：

• 操作在执行前必须获取全局锁，完成后释放全局锁。

代码示例

左侧是原始的deposit函数代码：

plaintext复制代码Deposit(bank, acct, amt):
    bank[acct] += amt

右侧是添加全局锁后的代码：

plaintext复制代码Deposit(bank, lock, acct, amt):
    acquire(lock)
    bank[acct] += amt
    release(lock)

每个共享数据都有一个锁，称为fine-grained locking

但对于中间情况，不可以读，不然还是会有问题

核心问题：

• 简单的细粒度锁并不能防止中间结果的暴露。

见解：

• 我们需要延迟每个共享数据的锁释放时间，直到所有事务的更新完成。

Two-phase locking (2PL)

2PL锁获取规则：
该操作必须在访问共享数据之前获取其锁，并释放它，直到所有操作完成

总占用锁时间明显减少

序列

尽管最终结果是对的，但是中间结果不一定对，具体还是要看用户，要符合串行的结果，为了区别不同的，定义了三种Serializability模型

Final-state serializability

如果一个调度的最终写入状态与某个串行调度的最终状态相同，那么这个调度是最终状态串行化的。

Conflict serializability（最常用）

在以下情况下，两个操作会发生冲突：

• 它们对同一数据对象进行操作，以及
• 其中至少有一个是写的，并且
• 它们属于不同的交易

冲突可串行化

如果一个调度的冲突顺序（即冲突操作发生的顺序）与某个串行调度中的冲突顺序相同，那么这个调度是冲突可串行化的。

conflict关系，通过conflict关系，可以构建一个图

冲突图

• 节点表示事务，边是有向的。
• 如果且仅如果以下两点都成立，则在Ti和Tj之间存在一条边：
  1. Ti​和Tj​之间存在冲突。
  2. 冲突的第一个步骤发生在Ti中。

一个调度是冲突可串行化的，当且仅当：

• 它的冲突图是无环的。

冲突等价

冲突等价的核心是比较两个调度中冲突操作的相对顺序，而不是操作的具体内容。只要两个调度的冲突顺序一致，它们就可以被认为是等价的

View serializability

几乎没人用，比较难判别

T1、T2 和 T3 之间的冲突关系。由于依赖关系形成了一个循环（cyclic），因此这个调度 不是冲突可串行化的，因为无法找到一个无循环的顺序来解决冲突。

如果一个调度的最终写入状态以及中间的读取操作与某个串行调度相同，那么这个调度是视图可串行化的。

正式定义：

• 两个调度 S 和 S′ 是视图等价的（View Equivalent），当以下条件满足：
  • 在调度 S 中，如果事务 Ti 读取了某个数据项 X 的初始值，那么在 S′中 Ti也要读取X的初始值。
  • 在调度 S 中，如果事务 Ti读取了由事务 Tj写入的数据项 X，那么在 S′ 中 Ti 也必须读取由 Tj​ 写入的 X。
  • 在调度 S 中，如果事务 Ti是对 X 做出最终写入的事务，那么在 S′ 中也要是 Ti 对 X 做最终写入。

Proof of 2PL

假设：

• 假设 2PL 不能生成冲突可串行化的调度。

冲突图（Conflict Graph）：

• 假设在执行 2PL 的过程中产生了一个循环冲突图。
• 假设有一组事务 T1→T2→…→Tk→T1 构成一个循环依赖关系。

共享变量（冲突资源）：

• 每两个相邻的事务 Ti​ 和 Ti+1​ 之间存在一个共享变量 xi 引发了冲突。
• 这些共享变量用 x1,x2,…,xk​ 表示。

锁获取过程：

• 每个事务依次获取共享变量的锁。例如：
  • T1 获取 x1​ 的锁。
  • T2 获取 x1和 x2​ 的锁。
  • T3 获取 x2​ 和 x3​ 的锁。
  • 以此类推，直到 T_k 获取 xk−1​ 和 xk​ 的锁。

违反 2PL 的情况：

• 如果 T1 在完成某些操作后释放了 x1​ 的锁（如图所示），这就会违反 2PL，因为在两阶段锁协议中，事务在释放任何锁之后，不允许再获取新的锁。
• 这里 T1 释放了 x1 的锁，但之后又尝试获取 xkx_kxk​ 的锁，这违反了 2PL 的规则。

结论：

• 因此，这种情况不可能发生，因为它会导致 2PL 协议的违反。
• 由于 2PL 保证不会产生这种循环的冲突图，所以可以得出结论： 2PL 实际上可以生成冲突可串行化的调度，从而反证了最初的假设是错误的。

幻读问题（Phantom Problem）：

1. 问题描述：
   • 虽然锁住了数据，无法修改，但是如果插入队列，在获取队列时候就会有问题
2. 冲突定义：
   • 两个操作发生冲突的条件是它们访问相同的数据项，且至少其中一个是写操作。
   • 数据项 的定义是抽象的，它可以是某个具体数据，也可以是整个数据库。因此，锁定机制应当能够捕捉所有可能的冲突，确保事务的先后顺序不被打破。
3. 解决方案：
   • 谓词锁（Predicate Locking）：基于条件锁定满足特定谓词的数据项。例如，锁定所有“工资 > 5000”的记录，防止其他事务插入新的符合条件的数据项。
   • B-树索引中的范围锁（Range Locks in a B-tree index）：假设在某个属性（如“工资”）上有索引，可以锁定一个范围，防止其他事务在此范围内插入新的数据；或者，直接锁定整个表。
   • 有时在实践中被忽略：在实际应用中，幻影问题有时会被忽视，尤其是在一些对一致性要求较低的场景中。

2PL 可以保证冲突可串行化，但必须确保冲突通过锁机制得到妥善协调。

Deadlock

在继续执行之前，每个事务（TX）必须等待冲突的事务释放锁。

由于 2PL 的悲观特性，在两个操作间，如果一个事务在等待另一个事务释放锁（例如，两个事务都试图同时访问 a 和 b，但顺序不同），可能会出现 死锁 的情况。

解决方法

1. 按照预定义顺序获取锁（预防方法）
   • 不支持通用的事务：事务在执行前必须知道其读/写的集合，因为降低了速率
2. 通过计算冲突图来检测死锁（检测方法）
   • 如果存在循环，那么一定有死锁。
   • 终止一个事务来打破循环。
   • 一般使用比较少，因为检测的成本较高。
3. 使用启发式（heuristics）方法（例如时间戳）预先中止事务（重试方法）
   • 可能会出现误判或活锁的情况。

死锁：在实际中，死锁通常很难预防和检测。
锁开销：锁带来的额外开销（包括获取锁和等待锁释放的时间）。

上述 2PL（两阶段锁协议）问题的根本原因是：

• 2PL 通过一种悲观的方式来避免竞争条件（Race Conditions）。

Optimistic concurrency control

OCC（乐观并发控制）以三个阶段执行事务

1. 第一阶段：并发的本地处理
   • 将读取的数据存入“读取集”。
   • 将写入操作暂存到“写入集”中。
2. 第二阶段：在关键区中验证串行化
   • 验证是否保证了串行化（事务独立性）。
   • 检查“读取集”中的数据是否被修改过。
3. 第三阶段：在关键区中提交结果或中止
   • 如果验证失败，则中止事务。
   • 如果验证通过，则将“写入集”中的数据写入数据库，并提交事务。

优势

OCC（乐观并发控制）分为三个步骤，确保事务在无锁的情况下并发执行，避免了锁带来的开销和死锁问题：

• 第一阶段：事务开始时，在本地进行数据读取和写入的暂存，不对实际数据库做改动，减少了锁的使用。
• 第二阶段：在事务提交之前，进入关键区进行检查，确保读取的数据没有被其他事务修改，从而保证一致性。如果检测到冲突，则回滚该事务。
• 第三阶段：根据验证结果，决定提交或中止事务。如果通过验证，将暂存的数据写入数据库，否则放弃该事务。

这种方法适用于低冲突的环境，通过推迟锁操作来提高系统性能。

第一阶段：并发的本地处理

• 读取操作：将读取的数据加入“读取集”。
• 写入操作：将写入操作暂存到“写入集”中。

问题：如果在同一事务中第二次读取同一个数据项（如 A）怎么办？

• 答案：直接从读取集中读取，因为读取集中可能已经包含了当前事务的修改值。
• 例如，如果事务先写入 A，然后再读取 A，系统会从读取集中获取最新值，以确保读取的是该事务写入的值。

第二阶段：在关键区内验证串行化

比如遇到ABA问题，数据被其他线程修改后又修改回正确的值，这时候需要读取变化

• 事务进入关键区，验证其操作的串行化，确保没有冲突。
• 检查“读取集”中的所有数据项是否在事务执行期间被其他事务修改过。
  • 如果任何数据在读取集中发生了变化，则该事务无法保证串行化，需要中止。

第三阶段：在关键区内提交或中止事务

• 中止：如果第二阶段的验证失败，则中止该事务。
• 提交：如果验证成功，则将写入集中的数据写入数据库，提交该事务。

注意：第二阶段和第三阶段必须在关键区内执行。

问题与解决方式

第二阶段和第三阶段必须在关键区内执行。否则，如果在验证和提交之间有其他事务修改了数据，可能导致数据不一致。

全局锁

• 第二阶段和第三阶段的执行时间通常很短。
  • 这两个阶段仅包含验证逻辑，而不涉及事务的实际执行逻辑。

代码示例：

python复制代码def validate_and_commit():  # 第二阶段和第三阶段
    global_lock.lock()  # 获取全局锁
    for d in read_set:
        if d has changed:
            abort()  # 如果读取的数据发生改变，则中止
    for d in write_set:
        write(d)  # 将写入集的数据写入数据库
    global_lock.unlock()  # 释放全局锁

使用两阶段锁实现关键区（Phase 2 & 3）

使用两阶段锁（2PL）：通过两阶段锁可以增加并发性。
问题：使用两阶段锁可能会带来死锁问题。

代码示例：

python复制代码def validate_and_commit():  # Phase 2 & 3
    for d in read_set:
        d.lock()  # 对读取集中的每个数据项加锁
        if d has changed:
            abort()  # 如果数据已变更，则中止事务并释放所有已获取的锁
    for d in write_set:
        d.lock()  # 对写入集中的每个数据项加锁
        write(d)  # 执行写操作
    # 释放所有锁

通过排序来避免死锁

使用排序方法来避免死锁：在加锁之前，将读取集和写入集合并并排序，然后按照顺序依次加锁，这样可以减少死锁的风险。
进一步优化的思考：是否需要对读取集的每个数据项都加锁？

python复制代码def validate_and_commit():  # Phase 2 & 3
    for d in sorted(read_set + write_set):
        d.lock()  # 按顺序加锁，减少死锁发生的可能性
    for d in read_set:
        if d has changed:
            abort()  # 如果读取的数据发生改变，则中止事务
    for d in write_set:
        write(d)  # 执行写操作
    # 释放所有锁

两阶段锁 + 读取验证

如何实现第二和第三阶段的关键区？

观察（关于读取集）：

如果验证通过，那么似乎不需要在读取集中持有锁。

python复制代码def validate_and_commit():  # Phase 2 & 3
    for d in sorted(write_set):
        d.lock()  # 仅对写入集中的数据项加锁
    for d in read_set:
        if d has changed:
            abort()  # 如果读取的数据项发生变化，则中止事务
    for d in write_set:
        write(d)  # 执行写操作
    # 释放所有锁

在该示例中，事务 T1 和 T2 在并发执行过程中展示了锁缺失的问题。

• 阶段 1：
  • T1 读取数据项 A_T0 和 B_T0。
  • T2 也读取数据项 A_T0 和 B_T0。
• 阶段 2：
  • T1 对数据项 A 加锁并验证 B_T0。
  • T2 对数据项 B 加锁并验证 A_T0。 这里的缺陷是，T1 和 T2 之间的锁没有相互协调，导致可能的数据冲突。特别是，T1 没有锁定 B，而 T2 没有锁定 A，从而引发并发冲突。

为了解决上述问题，可以采用两阶段锁与读取验证相结合的方法：

• 策略：
  • 仅锁定写入集：对 write_set 中的每个数据项加锁。
  • 读取验证：检查读取集中数据项的状态，确保没有被修改或加锁。

代码示例：

def validate_and_commit():  # Phase 2 & 3 with before-or-after
    for d in sorted(write_set):
        d.lock()  # 对写入集排序后逐个加锁
    for d in read_set:
        if d has changed or d has been locked:
            abort()  # 如果数据项已变更或被加锁，则中止事务
    for d in write_set:
        write(d)  # 执行写操作
    # 释放所有锁

• 锁定写入集：只对 write_set 中的数据项加锁，这样可以减少锁的数量，提高并发性。
• 读取验证：在写入之前，检查 read_set 中的每个数据项，确保这些数据项在当前事务执行期间没有被其他事务修改或加锁。这样可以避免数据不一致的情况。

总结：这种方法通过锁定写入集并验证读取集，既保证了数据一致性，又减少了锁的使用，提高了系统的并发性和效率。

结论

OCC 的优势

• 主要场景：适合只读数据访问多于写操作的情况。

OCC（乐观并发控制）在理想情况下（即没有中止）的操作：

• 1次读取：读取数据值。
• 1次验证读取：验证数据值是否已被更改（以及是否被加锁）。

2PL（两阶段锁）的操作：

• 1次操作：获取锁（通常是一个原子 CAS 操作）。
• 1次读取：读取数据值。
• 1次写入：释放锁。
  • 由于单个 CPU 写入是原子的，因此不需要进行额外的原子 CAS 操作。

总结

• 锁定操作的成本较高，特别是与读取操作相比。
• OCC 的优势在于减少锁操作，更适合读取多于写入的场景，因为它仅在提交时才需要验证冲突，大大降低了锁的开销。相比之下，2PL 需要每次获取和释放锁，带来额外的性能开销。

锁机制初步

1. 锁的设计目标与研究背景

• 多线程环境下的锁机制实现目标是优化性能和扩展性，这是系统研究中的活跃课题。
• 许多不同的实现方式不断发展，以提高系统的并发处理能力。

2. 基础锁机制设计

• 使用一个简单的标志位（flag）来表示锁的状态（是否被持有）。
• 获取锁的基本步骤：
  • 当线程尝试获取锁时，首先读取标志位。
  • 如果标志位显示锁未被占用，则线程将其设置为“锁定”状态，以持有锁。

3. 同步问题与竞争条件

• 在多线程环境中，如果两个线程同时读取到锁未被持有的状态，则会产生竞争条件。
• 问题：两个线程可能同时尝试获取锁，导致锁状态的不一致。
• 解决方法：需要确保操作的前后顺序，使得只有一个线程成功获取锁。简单的标志位不足以应对多线程并发竞争，需要更高级的同步机制。

4. 硬件支持的原子性操作：Compare and Swap

• 硬件原语提供了保障操作原子性（不可分割）的机制，使得锁状态的更新操作可以原子性完成。
• 常用的硬件原子操作：
  • Compare-and-swap（在 SPARC 架构上）
  • Compare-and-exchange（在 x86 架构上）
• 锁前缀（Lock prefix）：在 x86 中，使用锁前缀可以确保指令在特定内存地址上的原子执行，避免数据竞争。

5. CompareAndSwap 函数示例

• 函数 CompareAndSwap(int *ptr, int expected, int new) 的基本逻辑：
  • 读取指针当前值并存储为 actual。
  • 如果 actual 等于 expected，则将 *ptr 更新为 new，并返回 actual 值。
• 硬件通过锁前缀（Lock prefix）保证此操作的原子性，从而确保竞争条件下的安全性。

int CompareAndSwap(int *ptr, int expected, int new) {  // 使用锁前缀
    int actual = *ptr;
    if (actual == expected)
        *ptr = new;
    return actual;
} // 硬件通过锁前缀确保原子性

锁前缀的使用使得指令执行时不会受到其他线程的干扰，从而确保了锁定操作的原子性。

// 定义自旋锁结构体
typedef struct __lock_t {
    int flag;  // 0 表示锁可用，1 表示锁已被持有
} lock_t;

// 初始化锁，将 flag 设为 0 表示锁可用
void init(lock_t *lock) {
    lock->flag = 0;
}

// 获取锁，使用 CompareAndSwap 实现自旋锁
void lock(lock_t *lock) {
    while (CompareAndSwap(&lock->flag, 0, 1) == 1)
        ;  // 自旋等待，直到锁可用
}

// 释放锁，将 flag 设为 0
void unlock(lock_t *lock) {
    lock->flag = 0;
}

Hardware Transactional Memory

1. CPU保证了读/写内存操作的“先或后原子性”：
   • 也就是说，操作之间没有竞态条件（即不会出现并发冲突），也不需要“二阶段锁”（2PL）或软件实现的“乐观并发控制”（OCC）。
2. Intel的HTM（硬件事务内存）被称为RTM（限制性事务内存）：
   • RTM是一种限制性事务内存（Restricted Transactional Memory）技术。
   • 这种技术首次在Haswell处理器中引入。

使用方式

1. ISA对事务内存的支持：
   • ISA（指令集架构）对事务的支持和之前描述的事务（TX）很相似。
2. 回顾：在软件中编写事务：
   • 使用TX.begin来标记事务的开始。
   • 使用TX.commit来提交事务。
3. 在RTM中的概念是类似的（新的汇编代码）：
   • 使用xbegin来标记RTM执行的开始。
   • 使用xend来标记RTM的结束。

使用示例

1. 如果事务成功启动：
   • 执行受RTM保护的工作，然后尝试提交事务。
2. CPU检测竞态条件并在必要时中止：
   • 如果事务被中止，CPU会回滚到xbegin行，并返回一个中止代码。
3. 在事务内手动中止：
   • 在代码示例中，使用_xbegin()来开始事务。如果条件满足，可以使用_xabort()手动中止事务。事务的关键代码在_xend()之前运行，以确保在整个过程中事务的原子性。
   • 如果事务没有成功开始，执行备用代码路径（fallback routine）。

if (_xbegin() == _XBEGIN_STARTED) {
    if (condition) {
        _xabort(); // 手动中止
    }
    // 关键代码
    _xend(); // 结束事务
} else {
    // 备用代码
}

优缺点

RTM的优点

在xbegin()和xend()之间的内存操作满足“先或后”原子性：

• 这意味着在事务内的操作要么全部完成，要么全部回滚，确保数据一致性，避免并发冲突。

比起“两阶段锁（2PL）”或“乐观并发控制（OCC）”，编程更为简单（在大多数情况下）：

• 使用RTM可以减少复杂的锁机制和冲突处理代码，让编程变得更直接。

在某些情况下，性能更好：

• RTM可以减少锁的使用，从而减少线程间的等待和资源争用，提升并发性能。

示例代码

extern std::vector<u64> data; // 多线程共享的数据
if (_xbegin() == _XBEGIN_STARTED) {
    data.push(12); // 将数据加入共享向量
} else {
    // 如果事务开始失败，在这里处理回退操作
}

• 代码解释：这里尝试用_xbegin()开启一个事务，并在事务内将数据12推入共享的data向量。若事务启动失败，可以通过else语句处理失败的情况（比如锁定操作等）。

缺点

不能保证事务成功执行：

• RTM不能确保事务在所有情况下都能成功完成。事务可能因为资源冲突、硬件限制或其他原因被中止，需要编写备用逻辑处理这种情况。

关于RTM实现的事实

1. Intel通过乐观并发控制（OCC）实现RTM：

• OCC本身无法保证成功执行事务，因此在竞争激烈或冲突频繁的环境中，事务可能会被中止。

1. RTM的OCC在CPU硬件上实现，有一定限制：

• 使用CPU缓存来追踪CPU读/写集合，监测哪些内存区域被事务访问。
• 使用缓存一致性协议来检测冲突，确保多个线程访问共享资源时的一致性。

RTM的受限工作集

1. CPU缓存容量有限：

• 如果事务的读/写集合超过了缓存大小，RTM会无条件中止事务。

1. RTM的读/写集合有多大？

• 读/写集合大小取决于硬件设置（如缓存大小）、访问模式（读或写）。
• L1缓存跟踪所有写操作，L2或L3缓存跟踪所有读操作。
• 图中显示了工作集大小与中止率的关系：随着工作集大小的增加，中止率显著上升。例如，写集合的最大支持大小为31KB，而读集合的最大支持大小为4MB。

RTM有其独特的并发控制优势，但存在硬件限制和成功率问题。大型工作集或频繁冲突时，事务可能中止，因此在编写RTM代码时，需要特别考虑这些硬件特性和限制，以避免活锁和高中止率。

RTM 的有限执行时间

事务执行时间越长，事务中止的概率越高：

• 这是因为CPU中断会无条件中止事务。

中断为什么会导致RTM中止？

• CPU中断导致上下文切换，这会污染缓存，从而破坏事务的隔离性。

示例数据：

• 图中展示了事务执行时间与中止率的关系：最大执行时间为3.9毫秒，随着执行时间增加，中止率迅速上升。

总结：

RTM事务需要在有限的时间内完成，因为较长的事务执行时间更容易导致中止，主要原因是CPU中断会破坏事务的原子性。这意味着RTM适用于较短的事务，长时间事务需要特别小心。

备用路径：使RTM最终提交

问题：RTM不能保证事务成功：

• 类似于乐观并发控制（OCC），RTM中的事务代码由于冲突可能会频繁中止。
• 硬件限制也是中止的潜在原因。

必须在多次重试后切换到备用路径：

• 例如，使用计数器记录重试次数，当超过某个次数后，改用锁等悲观同步机制。
• 如果频繁使用备用路径，会导致性能下降。

代码示例：

• 使用_xbegin()尝试启动事务，如果当前有锁被持有，则中止事务（xabort()），否则执行关键代码，最后用_xend()结束事务。
• 如果事务无法成功，则进入else分支，获取锁执行备用代码。

在RTM编程中，事务中止是不可避免的。为了确保程序稳定运行，通常需要在多次重试后切换到备用路径（例如锁）。这是一种平衡性能和可靠性的策略，但如果频繁中止，RTM的性能优势将不复存在。

以下是对两张图的简单翻译和解释。

OCC 和 RTM 的简要总结

1. OCC（乐观并发控制）：

• OCC是一种经典的协议，用于实现“先或后”原子性（即事务要么全部完成，要么不完成）。
• OCC的理念甚至被硬件设计者采用，用于优化并发控制。

1. 事务内存的硬件支持：

• 为程序员提供了简便的编程模型，无需使用锁。
• 只要程序员在内存中进行计算（如内存数据库操作），就能获得良好的性能。
• 使用得当时性能良好，避免了锁和原子操作的需求。
• 然而，程序员仍需谨慎处理可能存在的陷阱，如处理中止和回滚。

总结

OCC和RTM都为并发控制提供了新的途径。OCC主要是软件实现的思想，但也影响了硬件设计；RTM则是硬件实现，简化了并发编程，但程序员需注意其使用限制。

当事务包含大量长时间运行的读操作时，OCC 和 2PL 表现不佳

1. OCC：如果读验证失败，事务会中止，这对长时间的读操作不友好。
2. 2PL（两阶段锁协议）：读操作将持有锁，阻塞其他操作，降低系统的并发性能。
3. 在实际应用中，读操作非常普遍：

• 例如，在淘宝等电商平台，用户操作往往以大量的读操作为主，添加项目的操作相对较少。
• 场景示例：在运行长时间的分析任务或读取大数据集时，偶尔需要更新一小部分数据。

结论

OCC和2PL在处理长时间运行的只读或读为主的事务时表现不佳，容易导致中止或阻塞。对于这种场景，可能需要采用其他更适合并发读操作的控制方法，以提高系统性能和响应速度。

multi-versioning concurrency control

多版本并发控制的理念

多版本并发控制（MVCC）：

MVCC的核心思想是保留数据的多个历史版本，方便并发事务读取一致性视图，并避免因更新引发的冲突。

• 每个数据都有多个版本，而不是只有单一版本。
• 一组版本代表数据库的一个快照（snapshot），例如 ( A_{T0} ) 和 ( B_{T0} ) 表示在时间点 ( T0 ) 的数据快照。
• 版本号接近于事务（TX）进行更新的时间。

数据结构示例：

• Data：包含一个值和一个锁。
• VersionedData：包含多个数据版本的列表以及一个锁。
• 每个版本的数据（如 ( X_0 ) 和 ( X_1 )）会有一个独立的版本号，用于标识数据的历史状态。

读写操作的规则

读操作：

• 只能从某个起始时间的一致性快照（a consistent snapshot）中读取。

snapshot

• 图中左侧显示了一个“全局计数器” (Global counter)，初始值为0。
• 事务T1和T2需要操作共享变量A和B，分别赋值并读取变量。

事务 T1：

• T1 事务的目的是打印 ( A + B )。它在时间戳 1 时刻读取变量A和B的值。

事务 T2：

• T2 事务修改变量A和B的值。根据图中的描述，T2 事务首先通过FAA(g) (Fetch-And-Add) 获取一个commit_time时间戳，并在此时间戳下写入B的新值。
• 写完B之后，再写入A的新值。这样T2在时间顺序上依次更新了B和A的值。

部分快照问题：

• T1 事务在时间戳 2 通过 start_time = FAA(g) 获取了一个开始时间戳，并开始读取变量A和B。
• 在读取时，T1读到了A的旧值 ( A_0 ) 和B的新值 ( B_1 )。
• 由于T1在读取时看到的是一个不完整的状态（即A和B的值不一致），导致了“部分快照”问题。这种情况不符合“原子性”，因为T1读取到的数据并非一个一致的快照。

缺失的原子性和解决需求：

• T2 的写操作应该是“原子”的，也就是说，T1 要么看到T2完成后的所有新值（A和B），要么看到T2开始之前的所有旧值（A和B），而不应该看到部分更新的状态。
• 图中红色文字指出，这种不一致的问题来源于T2的写操作缺少“先后”原子性。

总结： 这个图说明了部分快照问题的存在，并表明为了解决这个问题，需要让T2的写操作对T1表现出“全有或全无”的行为，即T2的写入操作要么全部完成，要么T1读取的还是旧的快照。

写操作：

• 在写入时创建数据的新版本，而不是覆盖现有版本。
• 新版本的时间戳约等于事务的提交时间。

目标：

• 避免在读取快照时发生竞态条件，确保读取到的数据始终是一致的。

获取开始和提交时间

要求：

• 计数器必须反映事务的顺序执行顺序。
• 例如，如果事务 T1 在 T2 之前完成，则 T1 应有较小的开始和提交时间戳。
• 对于只读事务，不需要计数器，但对写操作非常关键。

最简单且最常用的解决方案：全局计数器：

• 使用原子操作（FAA）获取事务的开始和提交时间。
• 事务开始：使用FAA获取开始时间。
• 事务提交：使用FAA获取提交时间。

未来的改进：

• 更高级的时间戳将在之后引入。由于分布式时间（例如物理时间）不同步，因此不使用全局计数器会更具挑战性。

尝试 #1：使用MV（多版本）优化OCC（乐观并发控制）

1. 获取开始时间：
   • 在事务开始时获取一个时间戳，表示读取操作开始的时间。
2. 阶段1：并发的本地处理：
   • 从最接近开始时间的快照中读取数据，以确保一致性。
   • 将写操作缓冲到写集合中，而不是立即应用到数据库中。
3. 获取提交时间：
   • 在进入提交阶段之前，获取提交时间。
4. 阶段2：在关键区段中提交结果：
   • 将写集合中的更改提交到数据库中，并标记为提交时间的版本。
   • 与传统OCC不同，这里不需要验证步骤，因为使用了多版本机制，避免了读写冲突。

Commit(tx):
   for record in tx.write_set: 
       lock(record)
   let commit_ts = FAA(global_counter)//拿时间戳
   for record in tx.write_set:
       record.insert_new_version(commit_ts, ...) //加一个新版本
       unlock(record) 

Get(tx, record):
   while record.is_locked()://被锁了，不让拿
         pass
   for version,value in record.sort_version_in_decreasing()://按照时间戳从高到低排序
       if version <= tx.start_time: //小于等于事务开始时间的版本，即可返回该版本的值。这样确保了读取的值是事务开始时存在的，符合事务隔离性要求。
          return value 

Multi-site transaction

多站点数据存储背景：

• 由于数据量巨大，单个站点（服务器）无法存储所有数据，因此数据必须分布在多个机器上。
• 在这个例子中，假设我们处理银行账户数据，无法将所有账户都存储在一个站点。

系统架构：

• 系统由客户端、协调器（前端服务器）、和两个存储服务器组成。
• 客户端（例如iPhone）通过协调器与服务器交互。
• 两个服务器分别处理不同的账户范围：
  • 服务器A负责账户A-M
  • 服务器B负责账户N-Z
• 每个服务器维护日志来确保单个站点的事务原子性，即每个服务器可以独立保证自己本地事务的原子性。

目的：

• 这种架构的目的是分布式地处理数据，同时保持事务的完整性和一致性。协调器负责管理多站点事务，使其在分布式环境中保持一致性。

事务处理过程：

• 这个例子中，协调器发送多个存款请求到不同的服务器，目的是同时更新Alice和Jack的账户余额。
• 协调器通过远程过程调用（RPC）发送这些请求给各个服务器。
• 事务的伪代码为：遍历账户列表，依次调用deposit(bank, acct, amt)，即对每个账户执行存款操作。

原子性问题：

• 关键问题在于一个服务器提交事务而另一个服务器回滚事务的情况。这种情况可能发生在网络异常、服务器故障或其他导致事务不一致的场景中。
• 图中显示了一个红色的闪电符号，表示通信失败或事务失败。

潜在问题与疑问：

• 在分布式环境中，如何保证事务的原子性和一致性是一个关键挑战。如果一个服务器成功提交而另一个服务器回滚，那么系统会出现不一致状态。
• 这里提出的问题是：如果一个服务器提交，而另一个服务器回滚，该如何处理？ 这种情况要求有一种机制来协调多站点事务，确保所有相关服务器的操作要么都提交要么都回滚，以保证事务的原子性。

two-phase commit

两阶段提交 (Two-phase Commit) 协议是一个常用的机制，用于保证分布式系统中的事务原子性，即在多个站点（服务器）之间确保所有子事务要么全部提交，要么全部回滚。

阶段1：准备 / 投票

1. 延迟低层事务的提交：在第一阶段中，不直接提交低层事务，而是进入“暂定提交”状态。
2. 低层事务选择中止或暂定提交：各个参与的低层事务会报告它们是否能够暂时提交（即它们的执行无误，可以提交）。
3. 高层事务评估情况：高层事务收集所有低层事务的反馈，评估是否可以整体提交。

阶段2：提交

1. 决定是否提交或中止：高层事务根据第一阶段的反馈，决定所有低层事务是“最终提交”还是“中止”。
2. 协调提交或回滚：高层事务通知各个低层事务，进行最终提交或回滚。

状态转换图解释

• 执行 (Execution)：事务执行过程中，进入第一阶段。
• 暂定提交 (Tentative commit)：在第一阶段，如果低层事务确认暂时可以提交，则进入暂定提交状态。
• 提交 (Commit)：高层事务确认可以提交时，事务进入最终提交状态。
• 中止 (Abort)：如果在第一阶段任何一个低层事务无法暂定提交，事务将被整体中止。

这个流程保证了跨站点事务的一致性，即在多个站点之间确保事务的所有部分要么一起成功，要么一起失败。

好的，这两张图展示了两阶段提交协议（Two-Phase Commit Protocol）如何确保多站点（多数据库或分布式系统）事务的原子性。以下是详细的中文解释：

高层事务的两阶段提交（确保多站点原子性）

这个图展示了如何使用两阶段提交协议来确保一个高层事务的多站点原子性。主要包括以下两个方法：

1. high_begin：标记高层事务的开始。系统通过 high_begin 表示即将开始一个分布式的高层事务操作。比如，系统可能会在多个账户中进行 deposit（存款）操作。
2. high_commit：在完成所有操作后（例如每个账户的存款操作），事务进入 high_commit 阶段，启动两阶段提交过程。这一过程分为：

• 准备阶段（Prepare Phase）：高层事务会向所有涉及的子事务（例如每个存款操作）发送“准备”消息，检查它们是否都可以提交。
• 提交阶段（Commit Phase）：如果所有子事务都表示可以提交，那么高层事务会指示每个子事务正式提交。如果任何一个子事务无法提交，那么整个事务会中止。

通过这个两阶段提交过程，系统可以确保高层事务中的所有操作要么全部成功，要么全部失败，从而在多站点中保持事务的原子性。

多站点事务的两阶段提交

多站点设置下，客户端、协调者（Coordinator）、和两台服务器（A-M 和 N-Z）之间的交互流程，展示了如何在多站点环境中应用两阶段提交协议：

1. 客户端请求：客户端发起一个事务请求，该请求随后由协调者（Coordinator）在多个站点之间协调（例如，负责不同数据范围的服务器）。
2. 协调者的角色：协调者负责确保该事务在所有站点上都能被提交。协调者在这里充当管理者的角色，负责决定该事务是否可以提交。
3. 两阶段提交过程：

• 准备阶段：协调者向两个服务器（A-M 和 N-Z）发送“准备”消息，确认它们是否可以提交。
• 提交阶段：如果所有服务器都返回“OK”，协调者就会发送“提交”消息，指示各服务器正式提交事务。如果任何服务器在准备阶段失败，整个事务会在所有站点上被中止，以保证数据一致性。

在这两个图中，两阶段提交协议通过“准备阶段”和“提交阶段”来确保分布式事务的原子性。这样可以保证分布式系统中的事务要么在所有节点上完全执行，要么完全不执行。通过这个机制，系统能够在多站点或多个数据库中可靠地处理分布式事务。若事务的某一部分失败，则整个操作会回滚，以防止部分提交，从而确保数据的一致性。

问题：是否可以直接在低层次的事务（Low-layer TX）中使用日志？

• 回顾（Redo-only Logging）： 在之前提到，日志记录可以在“提交点”时向日志中添加一条提交记录。
• 问题：能否直接将提交记录附加到低层次事务的日志中？
• 答案：不可以！ 因为高层次的事务可能会中止。如果高层事务中止，那么之前低层事务的提交日志会导致数据不一致。

在两阶段提交（2PC）下的日志规则

• 低层事务：
  • 使用“Redo-Undo”日志记录条目，如常规操作。
  • 提交日志条目是一个“临时提交”日志条目（标记为“准备状态”）。
  • 临时提交条目中包含对高层事务的引用，以便在失败时可以通过询问高层事务的协调器决定是否提交。
• 高层事务： 负责低层事务的最终提交。它会将“准备”日志作为提交的一部分记录。
• 挑战：日志可能会变得部分化。例如，如果两个工作节点都已临时提交，高层事务是否可以最终提交？

基于（可能）部分日志的提交决策

• 目标： 实现多站点的原子性。
• 原则：根据协调器的决策，记录足够的状态来容忍失败。
• 协调器的职责：
  • 如果收集到“中止”或没有响应，则选择“中止”或重试。
  • 如果所有节点都选择“提交”，则整体提交。
• 工作节点的反应：
  • 如果没有接收到来自协调器的消息，就等待。
  • 如果收到“提交”消息，就提交该事务。

具体事例

我们发现 N-Z Server 心跳包没了，那么 coordinator 就 abort。在 commit point 前发生了 crash，所以我们没有必要等待 N-Z Server 重启，直接 abort 即可。

发完 ok 以后发现 commit 的 message 丢了，要么让 coordinator 主动重发，要么就是 server 主动问一下 coordinator 为什么没有消息了（因为已经 prepared 了，所以 Server 是知道自己 在中间状态的）。

如果 coordinator 没有收到 A-M server 的 ACK，就 coordinator 再问一次。

此时我们已经在 commit point 后了，不能够 abort，worker 在 prepare 的时候就需要把 prepare 的 log 写到硬盘上，重启以后发现 transaction 处在 prepare 状态，worker 因为不知道 自己该怎么办就可以问一下 coordinator 刚才那个 transaction 到底是 commit 还是 abort。

重启完发现 commit 的事务并没有收到任何的 prepared，所以 coordinator 重启以后就直 接发送 abort 给 server 即可。

重启以后再发一遍 commit 到两个 server 即可

两阶段提交的总结

1. 两阶段提交（2PC）：实现多站点原子性。即使事务需要与多个机器通信，也可以保持原子性。
2. 在两阶段提交过程中，如果在提交点之前发生故障，事务可以被中止。如果工作节点（或协调器）在提交点之后发生故障，那么它们会恢复到准备（PREPARED）状态，并完成事务。
3. 剩余挑战：协调器故障下的可用性：
   • 遵循协调器的决策可以简化实现多站点原子性，但如果协调器长时间宕机该怎么办？
   • 我们将在下一讲中探讨如何提高协调器的可用性。

悲观复制 (Pessimistic Replication)

• 有些应用程序可能不愿意容忍不一致性：
  • 比如，一个复制的锁服务器，或用于两阶段提交（2PC）的复制协调器。
  • 最好不要两次分配同一个锁。
  • 比如，最好在事务提交上有一个一致的决策。
• 权衡：
  • 悲观复制提供更强的一致性，但会导致：
  • 可用性比乐观复制更低。
  • 等待与其他副本同步的性能开销更大。

乐观的情况：允许出现 out-of-sync 的情况，让人和机器去判定，简单的方法就是时间戳，但是带来的问题就是怎么去维护机器间的时间戳，那么我们可以用一个 vector 去维护 不同机器间的时间戳，如果存在偏序关系，那么我们可以直接覆盖；如果不存在偏序关系的情况，就产生了 conflict，需要我们手动 merge 的情况。

悲观的情况：我们不允许出现任何 conflict 的情况，single-copy（对外产生的效果和一个 copy 是一样的。）我们想了一个办法叫做 Quorum，每次写的时候都等到有若干个请求返回 才成功。我们读写都是 n 次，但是我们等到对应数量的请求返回即认为 ACK 了。比如我们 写了三台，其他两台没有回复，我们也继续往下走。我们只需要保证Qr+Qw > replica 即 可，如果一个服务器告诉我们值是 2，两个服务器告诉我们值是 3，怎么办？比如原来的值 是 3，我们要写 2 进去。读 3 个的情况我们读到了“2,3,3”，我们不会认为是 3.这和投票没 有关系，必须要三个相同的情况下，我们才能认为读到了正确的数据。因为机器会 recovery， 所以 3 最终是会变成 2 的，所以我们的 client 需要再去读它，直到读到的数据符合条件。

目标：单一副本一致性 (线性化)

• 乐观方式的问题： 副本之间可能不同步。
  • 一个副本写入数据，但另一个副本可能看不到这个变化。
  • 在单一服务器中不可能出现这种情况。
• 理想目标：单一副本一致性
  • 指的是：系统外部可见的行为表现得像只有一个数据副本。
  • 操作看起来好像是在单一副本上执行的。
  • 内部可能会有故障或不一致性，但需要我们屏蔽这些情况。

时间同步

我们在生活中有很多设备，比如我们做了一个 PPT，这就涉及到在台式机和笔记本上怎 么确定文件的新旧，一个最简单的方法就是通过文件的时间戳。时间在分布式系统中被用到 的是非常多的，比如 DNS cache 的有效期是 24 小时，百度如果要换 ip 的时候，需要保证原 先 ip 可以工作 24 小时。还有一种是做计量，计算一个操作花了多久。日历时间：当前的时间是多少，给事件打上时间戳做排序。 既然时间很重要，那么怎么样测量时间呢？

石英可以非常稳定地产生固定频率的晶振，比如 1MHz 的振荡器产生 1000 个 cycle 的时 间就是 1 毫秒。所以我们在计算机中就可以把时间记录成从 1970.1.1 到现在这个时刻经过了 多少秒。当我们把计算机关掉的时候，这个时间并不会消失。在我们主板上有一个小电池支 撑这个时间不断往前走。这个时间并不是非常的准，晶振不是人类想的那么完美，振动的次 数是存在误差和偏移的。 NTP 对外提供对时服务。

过去的时间和回来的时间可能是不一样的，这样我们计算的时间就不准了。

操作系统内部维护的就是这么一段代码，但是是有问题的。如果调时间这么调会有什么 后果？比如我们时间慢了十秒钟。t_end 可能比 t_begin 小，delay 可能变成负数或者巨大的 数字。

应用程序假设时间是不会往回走的。

我们在更新时钟的情况下，我们每次更新的时候少加一点，这样我们的时钟就慢下来了。 我们不能一次性地去调整，需要渐渐地去调整。 有了这个时间戳以后，我们就可以拿到一个比较准的时间。 Reconciliation 就是解决冲突和中断。文件产生冲突的核心原因就是版本不一样，最简单的方法就是文件 inode 中的 m_time。

如果两台机器开始时间是一样的，如果对同一个文件在两台机器修改，单纯看 m_time 是不够的，我们不能用 m_time 来覆盖另一台电脑上的文件的修改。我们的目标是写的数据 不能丢，解决这个问题的方法就是 vector_timestamp，每个文件中维护了一个时间戳向量， 记录了在每台机器上的时间戳。只有在时间向量可以比较的时候，才去做比较。在一个节点 上的时间戳永远只和自己比较。

这就是乐观带来的问题。

Quorum

悲观的情况怎么处理？我们不希望产生任何 conflict。我们最后的目标想到达 single-copy-consistency。 1. 加锁，同时只有一个人可以改，但是性能会受到影响 一个 client 给向两个 server 发请求，一旦一个挂了，那么就发给另一个。但是因为网络 关系可能导致 network partition

我们现在有三个服务器，写的时候我们同时写三份，一旦两个服务器回复写完了，那么 我们就认为写完了。在读的时候，如果从正好挂了的服务器读，那么就有问题了，所以我们 也要发 3 个请求，收到两个数据是相同的，那么就认为读到了。 在这种情况下，我们可以保证读到的一定是最近写进去的数据，这可以容忍一个 server 发送 failure 的情况。这就是 Quorum，要求读进去的数量（Qr）和写进去的数量（Qw）必须大于 replica 数量 N（2+2>3）。这样保证我们读到的 replica 一定有新的。

写 4 读 2 显然是对读友好，我们可以很快地读。写的时候只允许 1 个 crash，读的时候 我们允许 3 个 crash。

注意 Qw = 2并不是说只写两个，而是 5 个都要写，但是有 2 个返回写完就继续往下走了。写两个的话，latency 比写 5 个收到 4 个的 latency 要低。 那么如果我们通过这种方法，也可以优化 availability，也就是每次写都收到响应，这就 要求写的操作相对比较少。 Quorum 的思路是非常简单的，但是写都要写 5，读的时候就可以读 2 个之类的。

RSM

如果机器开始是一样的，输入、输入的顺序都是一 样的，操作都是 deterministic 的，那么最终结果是一样的。

我们通过网络发过去请求，我们认为输入是可以一样的。但是顺序很难保证。
Deterministic 呢？相同的代码如果里面有锁、CPU 多核调度等都会影响 deterministic。所以 确保 the same order 是根植于分布式的问题。 既然它问题的根源在分布式，我们可以改为一台机器 coordinator-worker 的形式，我们 想保证 input 的 order，我们不需要让一台机器的 coordinator 去执行这个 input，它只被用来 给 input 打上 order 标记。

如果出现了一个 network partition，也就是对于 coordinator2 来说，它认为 primary server S1 挂了，coordinator2 要立即把 S2 变成 primary server。

此时 S1 和 S2 之间一定数据不一致了，S1 和 S2 信息不一样并且不能覆盖。要解决这个， 我们就要加一个 view server，它记录谁是 primary，谁是 backup。View server 会通知服务， 你是 backup 还是 primary。View server 只有一个，来避免不一致的情况。

Coordinator 开始问 view server 现在谁是 primary，回答是 S1，那么 coordinator 就直接 和 S1 打交道。S1 和 S2 定期地向 View server 发送心跳。这个 view server 只有一台机器，也 会面临各种各样的问题。

1. S1 挂了，view server 立即发现 S1 的心跳没了。那么 view server 任命 S2 变成 primary。 然后 coordinator 问的时候，返回 S2，这是 view server 的正常容错。在 S2 只要自己是 primary 之前，它会 reject 来自 client 和 coordinator 的任何请求，为了防止两个 primary 同时出现的 情况。

2. Network partition failure，S1 其实没挂，但是心跳没有到 view server，所以 view server 误以为 primary server S1 挂了。在这种情况下，它就只能认为 S1 挂了，它会把 S2 设为 primary。 它设置 primary S2 的消息，还在 fly 的时候。Coordinator 给 S1 发送消息，它还会继续往下执 行，还会和 S2 同步，并且 S2 同步成功。在还在 fly 的时候，coordinator 知道 primary S2 了， 还是因为任命状还没到 S2 会 reject 掉 coordinator 的请求。任命状到 S2 以后，此时 S1 和 S2 都是 primary。虽然此时 coordinator 最新的请求都会发到 S2，如果 coordinator 没收到新的 是 S2，还是给 S1 发了就会导致不一致。

所以我们现在加一条新的规则，需要等到其他 backup server 发送 ACK 给 primary server 才继续执行操作。S2 因为当前没有 backup，因为 S1 还不知道自己不是 primary，所以 S2 在 这个短暂时间内是没有 backup 的，这种情况也是允许的。所以此时 S2 作为 primary server， 它知道当前自己没有小弟（backup-server），所以 S2 不需要收到别人的 ACK 就可以继续执 行别的操作。 这里面最大的薄弱的点就是 VS，于是我们就需要多台 VS，但是我们为了解决数据的一 致性，我们才希望 view server 是一台，现在多台又不能保证一致性了，这时候我们就引入 了 paxos。

Paxos

Paxos 要保证是数据是对的，所有参与的 viewserver 要讨论出一个一致的结果。第二个 目标就是 fault-tolerance，这个系统中不依赖某个节点挂了与否都可以正常运行。

PAXOS 不能保证 termination，也就是它可能不能讨论出最终的结果，如果讨论不出结果， 那就再讨论一次，但是在实际实践中，还是可以保证 termination 的。

分成若干个角色，有 Proposer：提议把 S2 变成 primary，acceptor 说同意，而 learner 就是学习最新的节点。一台机器在不同 round 里面可能扮演不同的角色。Paxos 最难的是不 同轮可能嵌套在一起，因为每个人通过网络连接，所以它直接导致了不同轮可能嵌套在一起。 这是 Paxos 很多人吐槽太难懂了的情况。

目标：所有的 acceptor 同意一个 proposal 的 value 是 （v proposal: 2:S2），比如 S2 是 primary server。

我们直接看这个例子，整个过程首先有一个 proposer，它想成为一个 leader。Leader 会 proposal 一个 value v 发给所有人，收集所有人是不是 agree，如果 major 的 acceptor agree 以后就宣布 result。

2-phase-commit 要收集所有人的 commit 才 commit，而这里 leader 只需要收集到 majority 的 acceptor 的 agree，就可以 announce。如果不是 majority，五个机器说等于 v1 和五个机器 说等于 v2，那就不好解决。

如果有多余一个人希望变成 leader 怎么办呢？我们需要让所有人同意你变成 leader，这 本身就是我们需要解决的问题。所以最终一个屋子里乱糟糟的，很多地方都在 propose 出新 的 proposal。并且数据包也会丢，leader 也 crash 了怎么办呢？

如果一个 leader 收集到 majority， 刚想和大家说自己是 leader，但是自己挂了怎么办？ 为什么叫 PAXOS，这是一个希腊的小岛，上面住了很多人选 leader，有一些人出来 proposal，大家就骑着小车送消息。它是有 round 的，轮和轮之间是异步的，第二轮不需要 等第一轮结束才开始，因为大家不知道第一轮什么时候算结束，每一轮又分成若干个异步的阶段。

Client 让 proposer 开始，然后有一个 proposer 变成了 leader，它需要说“我就是 leader”， 不需要等别人同意，他可以创建一个 proposal 叫做 N，N 的特点就是比它见过的所有 proposal 都要大。然后就把 proposal N 发给其他人。

对于 acceptor，如果收到的 proposal 大于它见过的所有 proposal，那么它就把之前见过 的最大的 proposal 的记录发给 Leader。比如它现在收到的是 5 号，而之前收到的是 4 号+value 的，它就会把 4 号+value 发给 leader，它会承诺未来忽略掉接收到的所有小于 N 的这些 proposal。

所以 acceptor 就做这个事情。

如果 leader 收到了足够多（majority）的 promise，它就会选择一个 value V 发给所有的 promise 给它的 acceptor 的节点。在这里需要注意的是，如果收到的所有 promise 里面是没 有 value 的，那就自己挑一个新的 v。如果带了 value，那么它就会直接选这个 value。

Acceptor 收到这个新的消息之后，如果 promise 依然是，那么它就记录最新的 N 和 value， 记下来以后，就给 leader 发一个 accept。记下来一个这个 leader 就定下来了，这个 learner 就可以回复给 client 我们定下来的 view server 是谁。

在整个 paxos 的节点中，每个节点都可以同时充当多个身份，需要维护一些数据。

Na 和 Va 就是接收到的最大的 n 和 v 是多少，还有见过的最大的 n 是多少，还有就是自 己的 proposal number 是多少。

它选择一个比见过的所有 proposal 都大的 proposal number 发给其他所有节点。对于 acceptor 来说，如果比见过的所有 proposal number 都大，那么就返回 < Na , Va >

如果 V 不等于 null，那么就设置为最大的 Na 对应的 Va。然后发给所有 acceptor。对于 acceptor，如果有大的，那么就拒绝，否则就直接设置成 leader 发过来的值。

如果 leader 收不到 majority，那么就要等一轮期待下轮能够收到。

一次没有出现任何情况的 paxos

我们为什么要多个 acceptor 呢？如果只有一个，acceptor 挂了就会影响整体，为什么不 接受第一个 proposal，因为多个 leader 同时在，有没有可能两个 leader 同时见到 majority 呢？

A 想要成为 proposer，它发起 proposal N= 1，同时发给 A、B、C，发给 B 的消息丢了， 那么 A 就收到 2 个 promise，然后把发给了两个人，然后 A 挂了，B 又活了， 然后 B 挑了一个 proposal N=2，此时因为 A 挂了，B 只能收到 B 和 C 的 promise。于是 B 就 会继续发送，而 B 不能自说自话发送。

这样设计的好处就是如果 B 再挂了出现一个 D，那么后面的 leader 不管你是谁，都得到 的是 foo。这样 foo 是在第一个人发 foo 到 C 的时候就决定了。

如果现在有 7 个节点，A 收到了 51%的节点的 promise，但是在发 accept 的时候只发到 了 C 就挂了，另外的节点都没有拿到这个 foo。另外五个人可是 majority，然后 C 也挂了。 此时就没有人知道 foo 了，于是另外五个人可以决定 value=bar。我们现在的问题是，什么 时刻 foo 成为了最后结果？如果有 7 个节点，C 收到 foo 是不够的，而只有当 majority 收到 的时候，才是真正的一个 commit point，后面的任何人的 proposal 里，收到 的 promise 里的 majority 里一定有一个 foo。换句话说，上一轮 accept 的 majority 和下一轮 promise 的 majority 一定有一个交集 foo。

五个人里面大家又 proposal 一个 bar，收到了 4 个 promise。有人 proposal bar，刚刚有 一个人收到了 bar，此时 A 和 C 又活了。此时 C 记录了同意过 foo，B 同意过 Bar，此时 E propose 一个新的 N。此时 E 收集到了一些 null, foo, bar，他就要选最大的见过的，也就是 bar。此时 这个值并没有确定下来，需要把发给所有人，然后等 majority 收到才真正是 commit point。所以 paxos 里面 commit point 是所有人决定的，commit point 是 majority 收到 了 accept 并且记录到 log 中。所以是没有人知道 commit point 在哪里的。这就是 paxos 和其 他的不一样的地方，正因为没有人知道，所以它并不依赖于某一个节点。

有了 paxos，我们就可以保证一旦返回给了一个 client 一个值，那么一定是 majority 同 意的情况，这就可以实现之前的 RSM 的情况。

在实践中 Paxos 实现比较困难，后来就有人提出了 raft 算法。

Raft

实现过程

• Leader election
  • 选取一个服务作为leader，有且只有1个
  • 检测问题，重新选举
• Log replication (normal operation)
  • Leader接收客户请求，添加log
  • Leader将自己的log复制给其他server(或覆盖)
• Safety
  • 保证数据一致性
  • 仅有日志足够新的服务器才能成为leader

三个角色

• Leader: 响应用户请求，复制Follower的日志(active)。每时每刻只能有一个Leader
• Follower: 只对发过来的RPC请求进行响应(passive被动的接收)
  • Server通过RPC交流
• Candidate: 新Leader的候选人

任期Term：任期有自增ID，termID最高的Leader有话语权。每个任期从一次选举结束，如果选出Leader，则在Leader挂掉时任期结束；如果没有选出Leader（spilt vote），则开启新的Term

选举过程

1. 修改自身状态Follower→Candidate
2. termID++
3. 发起对自己的投票
   • 收到大多数赞成→成为Leader
   • 收到一个有效Leader的消息→变为Follower
   • 没有一个candidate变成Leader→增加任期，重新发起下一轮选举

如何降低多个候选者选举失败的可能？——设置随机数，在[T,2T]中随机选择时间，T为选举超时时间，防止同时变为Candidate并发起投票

Log replication

每个Log entry由index,term,command组成，存在磁盘中以防止出错。最终保持一致

• 客户向Leader发送指令
• Leader将指令添加到自己的日志中
• Leader向Follower发送AppendEntries RPC
  • 如果followers慢不停retry直到成功（至少一次）
• 如果Leader收到了大多数ACK，则将日志标记为committed
  • Leader将命令发给自己的状态机，结果返回给用户
  • 将committed entires告知follower，follower将命令发给自己的状态机

解决日志不同步

考虑这样情况，当内容发给旧领导人，但是还没来得及给其它follower就挂了，此时肯定就是没提交（绝大多数没收到），这时候以最新领导人为准。

在AppendEntries时，先校验前面的内容，如果发现不同，则Follower的日志会被覆盖掉，以Leader的日志为准

但也导致即便有一条日志被大多数Follower接受，即commit成功后仍然有可能被覆盖掉

那么如何尽可能避免被覆盖掉的情况？
——选举时Follower检测Candidate的日志是否比自己新，选取当前log最新的Leader（当然还是先考虑term），如果比自己旧则拒绝投票
但是仍不能完全避免：

比如开始正常，S1S2突然被partition了，这时候选了S5做Leader，接收了几条后S5也亖了又回到S1领导，分发2后又去世了。那么再次选举肯定为S5当选（log最新），那么2的内容就被覆盖了。

Network

TCP/IP 协议

link layer：点到点传输
Network Layer ：把Link layer连接起来，不保证发包时候成功
End-to-end Layer：如果发现发包的时候这条路是断的，那么我们就让 Network Layer 再找一条路。

数据大小在64-1500之间是一个trade-off，保证利用率和负载。最小64用来冲突检测。

Application Layer：可以自己定义一套 application 的 protocol（HTML FTP SMTP…）;对于网页来说，它要考虑 data 的内容是什么，比如video/text

Transport Layer：当我们连到一台服务器的时候，大家通过 port 和 application 连接，所以在一台笔记本上，我们就可以同时发起 65535 个请求。因为一台机器只有 1 个 IP， 我们就可以使用 port 来做扩展。

Link layer

目标就是从一个点到物理邻居，直接连接。应用：蓝牙、局域网、DJI

同步传输需要精确时钟，仅在CPU等精密部件上使用，网络传输需要异步传输。

初步想法：Three-wire ready/acknowledge protocol

• A将数据存储在data line
• A改变ready line的值
• B看到ready line的值被改变，读取data line的值

传输速度：1/2△t(propagation time)为了提升传输速度，只能采取增加并行线缆的方法，但是实际效果不佳，且线与线之间有干扰，所以目前还是使用一根线串行传输。USB-通用串行总线

USB可以借助一个物理元件VCO实现数据无损传输，一根线解决数据传输。但问题是如果出现大量连续的1/0，VCO无法识别时钟，也就导致无法识别数据。因此我们需要调整数据传输编码。

曼彻斯特编码：最简单的想法就是0→1+0；1→0+1（根据标准不同，可以相反），保证每一次都有变化，问题就是浪费一半。还有其他不同的编码。

单根数据线如何做到并行：按人头分时复用（无法处理更多的用户）/数据包，一般采取数据包的形式。但问题是资源总数固定，比如说打电话连接建立后，不说话也占用。

如何识别数据包？
——识别包头和包尾
我们规定包头为7个1，数据内如果存在6个连续的1，则在6个1后面添加一个0

海明编码

基本想法：错一位会落入非法的值，然后被纠正
原理：海明距离——直观来说银行卡海明距离大，输错几位转不出去。而手机号小，输错一位打出去

考虑三位编码，可以构建成下图，4bit->7bit 自动纠一位

如果我们需要识别1位的错误，就可以让数据落在 (111,100,010,001)四个点上，这样即便错误1位也可以落在非法的点上；如果我们需要纠正一位的错误，就需要让数据落在(111,000)这样处于对角线的点上，这样可以纠正1位的错误，识别两位的错误。

海明编码：–e.g. 1101→1010101。纠1位检测2位，3位可能检测出。
检测：检测124位，看看哪些不一样，去表中找到对应的问题。

NetworkLayer

Attachment Point (AP)：当我们接到网络的时候，我 们要找到 AP，把设备通过 AP（WiFi、网口）接入网络。

网络可以分成两种：Best-effort network & Guaranteed-delivery network，前者不保证成功传输，后者相反。现实生活中后者用在高层网络中。

网络沟通需要一张路由表，Control-plane用于构建路由表，要求准确性，Data-plane通过路由表快速发包，要求性能。

Control Plane

显然我们不存在一张全局表，用于记录从一个节点到另一个节点的最快路径；所以我们在每个交换机上存储一张路由表，用于计算到另一个节点的最快路径

• HELLO protocol：得到自己的邻居
• advertisement：告诉别人“我”认识谁（link state/distance vector）
• 计算最短路径

Link-state 链路状态 

向所有人广播一个list，包括邻居和到达邻居的cost

最后所有设备都得到了这张图的信息，然后做Dijkstra

Distance-vector

告诉邻居“我”认识谁（包括如何到达这个节点）

然后使用Bellman-Ford，但是一轮不一定得到了最优，所以还需要把自己的值再发送出去。

link-state与distance-vector对比

	link-state	distance-vector
adv包含什么	到邻居的距离	到每个可到达节点的距离
谁收到adv	所有认识的节点	邻居
故障可靠性	高	低
性能瓶颈	传播节点过多	错误处理
优点	快速收敛	发送低开销，只需要发 2* connection 个 advertisement
缺点	flooding需要发 2 * node * connection 数量的 advertisement，成本高昂	收敛时间与最长路径成正比；Infinity问题

• Infinity问题
• 链路断开：假设某条链路（如 B 到 C）断开，B 无法直接到达 C，于是将到 C 的距离设为 ∞（理论上表示不可达）。
• 错误的更新：由于 A 在 t=10 的更新中告诉 B，它能通过 A 到达 C，B 误以为 A 能到达 C，而不是因为 B 原本认识 C。
• 循环更新：B 会以错误的距离值更新自己的路由表，A 之后可能又被误导，认为 B 能到 C，距离值会反复递增。

解决方法：不传递学来的信息回原路径：
A 不会把它通过 B 学到的 “到 C 的路由” 发回给 B。即在发送给 B 的 advertisement 中，会去掉与 B 有关的 C 的信息。
B 的行为：B 仍然会将 C 的距离更新为 ∞，并告诉 A 这条路由已经断开。

但是上面两种方法都只适合小规模网络

扩展路由

• Path-vector Routing
• Hierarchy of Routing路由等级
• Topological Addressing拓扑地址

Path-vector Routing

类似于 Distance-Vector，但提供了更多信息，主要用于避免路由循环并优化网络收敛时间。通过传递完整路径信息（Complete Path）来记录路由器到达目标的路径，从而克服了 Distance-Vector 协议中的一些问题，比如 Count-to-Infinity 和 路由循环。

对于如下路径

• G的4个邻居AHJK发来消息
• G形成自己的Path Vector，分配不同的端口。
• 邻居们根据发来的内容更新后，AHJK再次发来消息
• G形成path vector分配端口

避免 Count-to-Infinity 问题：由于每次传递的路径是完整路径，不会出现无穷大更新的问题。
更快的收敛：Path Vector 的路径信息更全面，避免了冗余传播，减少了网络的收敛时间。
如何避免环路？路由器拒绝任何包含自身的路径。
如何选择多条路径中的最优路径？根据路径的 总成本（Cost） 进行选择，例如跳数最少或延迟最低。
网络拓扑变化时怎么办？新链路：将其加入路径向量并重新计算。失效链路：移除邻居停止广告的路径。

Hierachical

我们的路由表只需要记录 4 个 region，比如找到R1，在交给R1的处理，找到R1.B

缺点：Address和location需要绑定。如今可以通过ip查到地址，有这方面原因

跨越Rgion路由需要BGP

Addressing

如何简洁地表示连续的IP地址？
——CIDR Notation：(18.0.0.0)→(18.0.0.255)都可以表示成(18.0.0.0)/24，/24代表前24位，注意是倒着看

Data Plane

交换机如何在几百个Cycle内完成一个数据包的转发？
——甚至不能访问内存

一次需要做的事情

• 查表，在转发表中查找数据包的目的地，全部进cache
  • 知道就找出口在哪就找，找不到就放弃
• 更新TTL，使用专门的硬件进行更新以提高速度
  • TTL （能被转发多少次timeToLive）：是数据包头部中的一个字段，用来防止数据包在网络中无限循环。每经过一个路由器，TTL 会减少 1。如果减少到 0，数据包将被丢弃。
• 发送到对应端口，传输链路

不要使用sleep，一直轮询

NAT

NAT（network address translation）是因为电脑太多了，网络太少了，所以要分为内网和外网。内网开头是 10.和 192.。内网ip无法被外部访问，内网访问外网需要经过Netgate，占用一个对外端口，并以一个统一的ip对外访问

比如访问baidu，做了一个translation，转换过去转换回来。需要根据实际的端口再转换为回来给内网用。

• 问题
• NAT Port 的数量是有限的。
• 这是典型的破坏了层级的设计。Ip 地址不够了，我们用到了上层 end-to-end layer 的 port 的概念。网络层修改了端口。用上层的概念解决了下层的问题，所以这并不是一个很漂亮的设计。而且必须要求上层必须是 port，如果我们用的不是 TCP/UDP 的 port 概念，那么 NAT 就不能用了。
  • 破坏端到端通信，增加延迟。不适合大量并发连接（端口耗尽问题）。
  • 本质就是ip少了，那么IPV6可以解决，恢复简洁。

以太网

以太网（Ethernet）是一种局域网（LAN）技术的统称，基于广播的通信方式。所有连接在共享的电缆或光纤链路上的设备都可以接收到彼此的传输信息。为管理网络中的通信，以太网采用了一种“发送前监听”（carrier sense）的规则，确保在发送数据之前，设备会检查链路是否空闲。如果两台设备同时开始发送数据，就会发生一种称为“碰撞”的错误。为了减少因碰撞导致的传输时间浪费，以太网还引入了“发送中监听”的规则，用以检测碰撞并及时采取措施。这个协议被称为载波监听多路访问及碰撞检测（Carrier Sense Multiple Access with Collision Detection，简称 CSMA/CD）。

类别：半双工（发收分开），全双工（连接后又可以接收又可以发），以太网的数据包格式如下

• Hub模式：所有设备通过集线器 (Hub) 连接，使用广播的方式发送数据包，数据会传送给网络中所有设备。非常不安全
• Switch 模式：交换机 (Switch) 根据MAC地址表将数据包定向发送给目标设备，减少广播。

以太网的发送-接收

在发送端，ETHERNET_SEND 只将调用传递到链路层。在接收端，检测包的目标是否为自己，如果是自己则进行处理，否则忽略

Layer Mapping

将以太网连接到Network Layer的转发网络

考虑下面的以太网架构（LMN…为ip地址；17/15/18为mac地址）

内网访问：L→N，N会监听到消息，发现数据包的mac地址是自己，然后接收到了消息

外网访问：L→E，由于E不在以太网内，包头中需要包括ip地址“E”和路由器K的mac地址“19”，然后路由器会从4号口将消息发送到其他路由器，为了防止对面的路由器也是以太网，还需要把mac地址从“19”改成E在自身内网中的mac地址。mac可能相同，但实际在同一以太网下概率比较小。

地址解析协议ARP

一个新加入网络的L如何知道其他人的地址？

内网：L知道M的IP地址，希望通过以太网访问，则会发送一个类型为ARP的消息，广播到以太网上的设备上去问，如果请求包中的目标 IP 地址 和自己的相同，就会将自己主机的 MAC 地址写入响应包返回主机

外网：L知道E的IP地址，希望通过以太网访问，路由器会接收到这个消息，告诉L将准备发给E的消息发送给自己，同时在外网上找寻E的位置（或者原本就知道E的位置）

问题：因为问mac地址是谁知道都可以回，那么hacker就可以回自己的，就可能被hacker中间利用。无法防御，所以部队上arp绑定死了，手动加入防止有人入侵。

End to End Layer

三种协议

• UDP(User Datagram Protocol)：仅仅只是把数据包发出去，没保障速度快
• TCP(Transmission Control Protocol)：保持顺序，不会丢包，不会有重复包；支持流式控制（控制网络流量）
• RTP(Real-time Transport Protocol)：主要用于音视频等流式数据

理想的端到端网络的要求：

• 保证at-least-once（至少收到一次）
• 保证at-most-once
• 保证数据正确
• 保证数据流的顺序
• 网络波动控制(Jitter control)（不出现大的波动）
• 授权管理及隐私性
• 保证端到端的性能（最难）

以上三种协议都无法全部满足7个需求

At-least-once

基本策略：发送包之后，如果一段时间后对方未发送ACK消息，就再发一次
“一段时间”的确定——RTT

RTT(Round Trip time)=之前发包的平均时延+冗余量

实现：

• 发包时包括nonce(id)
• sender保存一份包的数据
• 如果超时则重发nonce对应的包
• 直到receiver返回一个包括nonce的ACK
• 如果retry过多则放弃

确定RTT的三种方法：

• 首先绝不能用固定时间，过长过短都不好
• 使用Adaptive timer：每遇到一次超时，则将RTT变为1.5倍；当然还有一些改进的方法（经验）
• NAK(Negative Acknowledgment)：receiver在收到所有包之后告诉sender自己缺失了哪些包，需要receiver维护一个Timer

At-most-once

几种方法：

• 最基本的实现：receiver记下最近的nonce，如果sender重发，则不再处理
  ——但是无法界定什么时候删除nonce，可能删了还收到，变成一个墓碑
• 请求保证幂等性，容忍重新发包
• nonce自增，记下见到的最高nonce，忽略nonce低的请求。——如果乱序怎么办。同样可能会成为墓碑，但因为只有一个包不占用地方
• 每个端口只服务一次请求，如果端口10000收到了一个包，下一次使用10001，但是什么时候能复用端口？端口个数可能不够

Anyway，没有完美的方法

数据正确

基本想法：checksum校验，但是总有数据和校验同时出错的情况

发送顺序

sender告诉receiver一共有几个包，并且每个包涵盖索引

几种方法：

• 收到3号包后，只收4号包，抛弃更大的包
• 维护一个buffer，但是如果网络出问题，会使buffer占用极大的空间
• buffer满了以后，清空buffer，全部重传
• receiver发送NAK，告知sender缺少哪个包

波动控制

解决方法：视频缓冲区，通过时延确定需要多大的缓冲区

分别是99长时延，最低时延，平均延迟

授权管理及隐私性

解决：公钥及私钥，私钥不能泄露

端到端的性能

• 最基本的实现：发包→ACK→发包→ACK…收到后才返回
  • 这样一定顺序，正确性也最好
  • 问题是时延，通讯效率很低
• 改进：sender一直发包，receiver收到后发ACK回来
  • 可能发太快了，丢包
• 问题：sender一直发包会占用大量的带宽，所以可以发n个，停一会，再发n个

如何确定n——需要考虑带宽和receiver的处理能力

异常处理

为了获得最好的表现：window size的设置：window size ≥ round-trip time（往返时间）× bottleneck(瓶颈) data rate

如：sender速率1MBps，receiver速率500kBps，RTT=70ms，单个包大小5kB
则Sliding window size=500kB*70ms=35kB（一个窗口发7个包）

问题是网络状况会改变，如何解决？

TCP堵塞控制

谁来负责冲突控制

network layer：可以直接感知到堵塞；最终决定如何处理超额数据包
end to end layer：可以通过收到ACK判断，但是并不高效

为了防止拥堵，我们不能无限地发包，还需要给Sliding window size设定一个上界

为了防止拥堵：window size的设置：window size ≤ min(RTT × bottleneck data rate, Receiver buffer)，显然性能和防止拥堵是矛盾的。

堵塞控制

• 缓慢增加包的数量
• 如果没有发现丢包，则继续增加
• 如果发现丢包，则快速降低包的数量（保守的方式）

需要考虑的问题：
性能：即便降低包的数量，也不能过于低，需要尽可能占满瓶颈流量
公平性：共享瓶颈的发件人需要获得相等的吞吐量

AIMD(Additive Increase, Multiplicative Decrease)

每个RTT中:

• 网络状况好: cwnd = cwnd + 1
• 部分丢包： cwnd = cwnd / 2
• 全部丢包：从头开始

问题：初始值是1，初始增长过慢，解决方案是第一次增长按指数级，cwnd=2*cwnd，之后都是加法

这里是一个比较保守的做法，尽可能地不对网络产生压力；如果是数据中心等网络状况良好的方法，降低的幅度可以变小。

AIMD可以保证带宽分配公平性，原理如下图，通过不断修正，原理是斜率不同

TCP的缺点

• 路由器需要buffer，过大就会影响性能。排队时间会很长
• 在无线网中，遇到网络信号问题不应该减少发包数量，而应该增大（因为不是网络流量瓶颈）
• 在数据中心中表现不好，前面提过，不要每次折半
• 对于RTT较大的情况有“偏见”

DNS域名系统

如果没有域名，对于程序不会有任何影响，但是对于用户不友好。

一个域名可以具有多个IP地址，方便负载均衡、提高用户承载
一个IP地址可以有多个域名，只需要多个端口
域名与IP地址的绑定可以改变

通过域名找到IP

起初是放在一个txt文件中，但是很不方便

BIND系统

将域名分层。.com;.cn等根域名分别由不同的DNS服务器管辖，如se.sjtu.edu.cn，每个后缀层层下放，每人只管理自己和下一层（类似文件系统）

于是我们可以按下面的过程获得一个域名的ip地址

但是我们认为这样造成的网络请求过多，有两种改良方式

• 使用自己的DNS服务器/在本地存储结果，优先从指定的服务器/本地获取域名到IP的映射
• Recursion：由根节点获取全部域名，再返回给用户。服务器间网络带宽普遍高，能获得更好的性能
• Cache：Recursion对root的要求极高。所以实际上并不是非常的“等级分明”，下层DNS服务器会使用cache，存储一定量的其他“域名-ip”映射，有网络请求时会先访问下层DNS服务器，如果找不到再去root询问，需要设置一个合理的过期时间。（长减小负担，但导致更新不及时，短反之）

DNS的优缺点

优点：层级架构去中心化；域名全球可用；性能可扩展；管理可扩展；容错；速度快
缺点：受到当地政策影响www.baidu.com；根服务器负载过重；安全性 (恶意的DNS服务器) 

和文件系统对比

比较项	文件名 (File-name)	主机名 (Host-name)
作用	更加用户友好	更加用户友好
绑定目标	文件名 -> inode编号	主机名 -> IP地址
结构	文件名是分层结构	主机名是分层结构
绑定目标的结构	inode编号是平面结构	IP地址是平面结构
是否是对象的一部分	文件名不是文件的一部分（存储在目录中）	主机名不是网站的一部分（存储在名称服务器中）
名称与值的绑定关系	1-名称 -> 多值 (否)；多名称 -> 1-值 (是)	1-名称 -> 多值 (是)；多名称 -> 1-值 (是)

Naming

作用：检索（URL），共享（引用），节省空间（名称指代对象），隐藏（操作对象不用知道底层），支持访问控制（知道名称才可以），友好访问（域名比ip好访问），间接访问

命名方案：名称集合（所有合法的名称），值集合（名称对应的所有可能值），查找算法（用于将名称解析为值）
查找方式：表查找（电话簿），递归（Recursive ）查找（/usr/bin/rm），多重查找（没有绝对路径时，按预定义列表查找 e.g. $PATH）

要点：命名语法（比如c++不能用for命名），可对应的值，如何解析，是否是全局

一些FAQ:

• 每个名称是否都有值？（悬空名称，无绑定值）
• 名称是否可以有多个值？（多播地址有多个接收者）
• 每个值是否都有名称？（匿名值如临时文件）
• 值是否可以有多个名称？（同义词如软链接）
• 名称对应的值是否会随时间变化？（DNS记录ip会）

内容分发网络CDN

docker镜像、b站视频等内容，在分发时可能会造成很大的网络压力，那么我们能做些什么
——内容分发，将同样的内容在全球各地的服务器上建立多个副本，以达到最佳的访问性能。

用户通过多次DNS搜索，得到最近的服务器，如果服务器内没有该内容，服务器会从中心服务器获取，发给用户的同时，存储到自己的cache内.
开始可能问：最近的淘宝图片哪里来的。那一定不是中心服务器，而是最新的CDN服务器保存

P2P(Peer to Peer) Network

——No Central Server

BitTorrent比特洪流

特点：

• 分布式资源共享：用户从其他人那里下载文件的片段，而不是从单一的来源。
• 边下载边上传：用户在下载文件的同时，BitTorrent 会将已经下载的部分分享给其他用户。
• 持续分享（种子保持活跃）：文件下载完成后，BitTorrent 客户端会继续运行一段时间（成为“种子”），将文件分享给其他用户。

三个角色：

• tracker：记录每个文件的每部分在哪里
• seeder：有整个文件
• peer：有一部分文件

执行过程

• 文件发布者将文件的基础信息(.torrent文件)发布到一个网站上（tracker的url，文件名及大小，hash校验码）
  • 这一步是中心化的
• tracker组织一个peer的群，分别拥有文件的不同部分（有重复）
• Seeder将文件的种子发布出去（指向网站上的.torrent文件）
• 下载者先通过种子获取.torrent文件，再获取到tracker的url
• tracker返回一个peer的列表
• 下载者从peer处进行下载

BitTorrent的缺点：依赖tracker；规模很难扩大(tracker需要跟踪每个用户的加入、离开，来保证数据完整性)

为了解决问题，我们将tracker的数据存储在一个分布式哈希表上

DHT分布式哈希表

• 用于快速查找负责的peer
• 每个节点存储一部分哈希表
• 不严格保证数据的时效性

如何确定需要的key在哪个服务器上：

我们对key做一次哈希，再对服务器的ip地址做一次哈希，得到下表

将哈希值构建成一个环，每个服务器负责那些哈希值落在自己逆时针方向的key。当我们访问key的值，只需要计算一次哈希值，然后不断顺时针旋转，就能找到最终的服务器。

现在我们将O(n)的算法提升到O(log n)：每个服务器保存其顺时针方向的多个服务器地址，我们不需要一个一个找寻服务器，可以直接通过当前服务器保存的节点，跳过不属于哈希范围的服务器

Finger i points to successor of n+2ⁱ，这样每个存的节点也少，提高了效率

join类似于链表添加，询问后面自己要复杂的值。

如果服务器挂了怎么办：

• 一个key保存在其顺时针方向上的多个服务器，这样可以保证数据不会丢失
• 同时，每个节点同时也保存其后方几个节点（successor list），可以方便跳过损坏节点

如果哈希值分布不均匀：构建出hash值不同的虚拟节点，分配到不同服务器上，就均衡了。

总结

Distributed Computing

总计：训练一个大模型所需要的总算力大致是6 * #parameters * Batch size

如何提升算力：

• 单核设备算力提升：流水线、超标量（每个cycle多条，原理预测指令 一般4-8最多）、 超频
• 单核设备算力再提升：SIMD：一个指令执行多个浮点操作（有物理上界）
  • 新指令集架构（ISA）：SIMD处理：
  • 单指令、多数据（SIMD）一条指令（例如读取或加法）可以同时作用于多个数据。
  • 同一指令会被广播到多个算术逻辑单元（ALUs），并行执行。
  • 为什么不使用不同的指令？管理每个ALU独立的指令流的成本太高，会增加复杂性并降低效率。
  • 同时会占用很大缓存以及访存导致实际提升并没有预期快。
  • 为什么不塞几千个ALU（？）物理信号传递限制/工艺限制，同步也花很多时间。
  • SIMT：单指令多线程，是一种并行编程的抽象模型，不是具体的硬件实现，SIMD思想扩展。
    • 编译器会将这些代码转化为底层（条件）SIMD 操作
    • 开发者需要考虑硬件细节，才能充分利用硬件性能。
• 多核
  • 缓存一致性协议：
    • 目的：确保不同核心对缓存数据有一致的视图。如果核心1更新了缓存行L1，那么L1的值会及时对核心2可见。
    • 监听协议：每个缓存控制器会监听其他核心的所有内存读/写操作。
    • 目录协议：可能通过一个全局目录来实现（用于记录缓存的状态）。
  • 监听协议（Snoop-based protocols）监听开销，目录协议（Directory-based protocols）一致性开销，扩展开销。
  • 现代CPU：单个芯片上的核心数量有限（20-100个）。
  • 现代GPU：核心数量很多，但完全没有缓存一致性机制。
• 对于某些计算做专门的硬件

roofline model：用于确定性能瓶颈在计算/访存

随着硬件的专用性提高（从微处理器到DSPs，再到专用硬件），能效显著提升，但灵活性降低。一个trade-off

批处理

MapReduce

基本想法：先分工(map)，再合并(reduce)

需要解决的问题

• 节点间的数据传输方式（Map Rreduce之间传输）
• 如何协调各个节点的工作（任务分发依赖要考虑 先Map后Reduce）
• 错误处理（出错很容易，节点死了job也要继续完成，重新执行恢复）
• 对局部性进行优化（尽量不访问其他节点的数据，尽量让map和reduce在一台机器上）
• 将数据分区以开启并行（map容易reduce难并行）

两个函数

• Map(fuction, set of values)：将每个set分别作为function的输入，然后得出一个结果
• Reduce(fuction, set of results)：将所有result的结果通过function进行汇总

Map很容易并行，但是Reduce在我们目前的描述中不能并行。在处理一些问题时Reduce也是可以并行的（比如word count）。

有了MapReduce，做分布式计算只用考虑如何Map和Reduce，这两个函数就行。

具体实现：

• 如何做sharding：由于运行在GFS系统上，所以一个切片64MB
• 任务调度：master将任务分配给空闲的MapWorker
• 执行Map：读取sharding中的内容，得出结果（键值对），存储在内存中
• 结果存储到Intermediate File中（要分块，以便每个ReduceWorker能够快速找到）
• 对全部的结果进行排序，将上面分的块按ReduceWorker排在一起
• 由ReduceWorker进行合并并输出最终结果

截至目前我们解决了问题中的1、2、5，还有错误处理及局部性优化需要解决

错误处理：

• worker出错：master持续heartbeat，如果挂了就把任务重新分配给别人
  • 分配给失效 Worker 的 Map 或 Reduce 任务会被重置回初始状态，并重新分配给其他 Worker 进行执行（重新执行，re-execution）
  • 即使在一次任务中丢失了 1800 台机器中的 1600 台，任务仍然可以顺利完成。
• master出错：我们将master的状态使用checkpoint存储到GFS中（或任一个可靠的文件系统），如果出错就恢复，一般失败罕见

局部性优化：

GFS内部服务器按理说不该暴露给user，但是在这里GFS将chunk server及其中存储的shard暴露给master，然后master将对应shard的计算任务分配给对应的服务器，极大减少了通过网络请求获取数据的概率

其他优化：

冗余计算：减少出错 ，同时防止某些机器由于硬件问题，运行速度极慢。我们把一个任务分配给多个人，几个人搞竞赛，显然也浪费了硬件。

优点： 易扩展；错误处理；对于某些任务具有很好的性能表现

缺点：难以处理复杂任务，编程上难度大，不支持多个MapReduce容错

计算图-Computation Graph

所有的计算都可以表示成一张有向无环图

好处：无环图容易做错误处理；DAG可以很方便地找到并行任务

执行原理：当执行完一个任务，其子节点的入度-1，每次执行入度为0的点

机器学习

机器学习的训练过程也可以构建成计算图

x是输入特征，类型是32浮点，形状是一个维度的大小不固定，784图
W是变量表示模型的权重矩阵，784 是输入的特征数，10 是输出的类别数
y 是模型的输出，使用了 softmax 激活函数，将线性输出转化为概率分布，tf.matmul(x, W) 表示矩阵乘法

1. matmul（矩阵乘法）：计算 𝑦=𝑊⋅𝑥，即线性变换。
2. softmax（Softmax 激活）：对 𝑦 应用 Softmax，生成概率分布。
3. log（对数）：对 Softmax 的输出取对数，计算 log-probabilities。
4. mul（逐元素乘法）：将 Log-Softmax 输出与真实标签 𝑦_ 相乘（对应交叉熵的公式）。
5. mean（取平均值）：对 Batch 的所有样本的损失取平均值，得到最终的交叉熵损失。
6. mul：反向传播时，对 Batch 的损失取 1/batch_sizebatch_size1。
7. log-grad 和 softmax-grad：依次计算 Log 和 Softmax 的梯度。

计算图的应用好处：
（1）基于计算图可以轻松计算导数：因为每个操作（节点）都有对应的导数实现。利用链式法则将导数组合起来：通过计算图，操作节点的导数可以自动结合在一起，完成梯度计算。
（2）结合硬件加速器（TPU/GPU/NPU)，通过工具（如编译器）在复杂硬件上高效执行模型计算。
（3）节点融合将多个计算图节点融合成一个更大更复杂的节点操作。减少通信开销（内部GPU不同单元间和分布式机器之间通信开销）

随机梯度下降（训练模型）

一般的公式：

我们考虑并行，显然只要把求和拆开就行（这种方法叫数据并行，还有一种叫模型并行，我们后面介绍），于是我们可以将计算图做如下的转化，分别计算一部分最后求和。问题是如何把汇总做快

由于机器学习的特点，我们每做完一次上述任务后，需要将结果进行汇总并进行全局广播，而这实际上非常耗时，我们希望能尽量将汇总再广播的AllReduce操作并行执行

AllReduce

一般计算开销很小，需求：减少每条信息的数据量（优化数据大小，降低网络传输的数据量）， 减少瞬间流量（控制并发请求，避免服务器因过多消息而产生瓶颈）总参数量 N，处理器数量 P

Parameter Server

将所有结果发给Parameter server，计算后再广播。显然我们的两个需求都没有被满足

Sharded PS

每台服务器计算1/n的值，降低了PS的负担，但仍有极大的瞬间流量。
每台机器的总通信量N * (P – 1) / P，通信量按比例分摊到每个处理器上，很好
总通信轮数固定，效率很高。很好
高 fan-in（扇入）：意味着多个处理器同时向一个节点发送数据，容易带宽瓶颈和单点压力，尽量避免

De-centralized approach

按距离发送；第一个时间片发送给前一个，第二个时间片发送给前两个。降低了网络流量，但效率较低
每台机器的总通信量：N * (P – 1) data (Bad …)，扇入（fan-in）很好，总通信轮数：O(P * P)太高

Sharding Reduce

我们仍然将一个包拆成n个，对于第0个包，我们采取以下的发送方式，进一步减少的数据量
节点2必须向节点0发送消息，直到节点1完成通信，所有节点都必须保持与其他节点的网络连接（大规模成本高昂）

Ring Allreduce

在上面的方式中，每个节点都要与所有节点通信，有没有办法只与相邻节点连接？

现在每个人有了自己的梯度，还需要做n轮广播，使每个节点都拥有所有的梯度

我们发现梯度计算的顺序并不是严格的w₁+w₂+w₃+w₄，在GPU的浮点数实现中，加法不满足交换律（可能是精度丢失？），所以这种方法会导致一定的误差
2 * (P-1) * N / P: the same as partitioned，扇入（fan-in）O(1)，效率较高。总通信轮数：O(P)，相比参数服务器方法的 O(1) 仍然高得多。

总结

	Round	Peak node bandwidth 节点同时接收的数据量	Per-node  fan-in 节点同时接收的消息数
Parameter server (PS)	O(1)	O(N*P)	O(P)
sharded PS	O(1)	O(N)	O(P)
Decentralized Allreduce	O(P)	O(N)	O(1)
Ring allreduce	O(2*P)	O(N/P)	O(1)

一种更优的方法：Tree Based

我们先构造一棵树，每个节点在树中只出现一次，每个节点将子节点的消息汇总，再发给父节点，但是只有左边一棵树，网络负载不均衡，所以我们将树反转得到右边的树，这样除了0和31两个节点，其他节点都是两进两出，网络负载相对均衡

可以将Ring allreduce的O(2*P)降低到O(log p)，其他不变

模型并行

数据并行中我们把求和符号拆开，再模型并行中我们把求和式子拆开

具体而言，是因为模型太大了，我们不能做到在每台机器上都保存一个完整的模型以支持数据并行，所以需要对模型进行拆分，形成新的数据流图如下

模型并行还分为两类：pipeline并行和tensor并行

pipeline并行

我们按layer分割，将计算任务分配到不同的机器上

就会产生下面这种计算序列

显然上方有很大的空缺（Bubble）没有被利用，我们的解决方法是对Batch进行切割Micor-baching，每计算出一点梯度，就向下传递，达到下图的效果

我们要拆成多少份呢？Bubble size=p−1，其中 p 是设备的数量（#devices）

我们计算一下Bubble占所需时间的比例=(p-1)/m；m为batch被分成的份数

为了Bubble所占比例更小：我们需要减少机器数量，很难；增加Batch的大小（这样就可以划分出更多的份数），也很难，受硬件限制。

Tensor并行

tensor 并行是一种将神经网络中的张量（Tensor）在多个张量并行（Tensor Parallelism，TP）是一种模型并行技术，设备上拆分并旨在将深度学习模型的计算任务拆分到多个设备（如GPU）上并行并行处理执行

机器学习的过程就是计算一个Y=WX的分块矩阵乘法，我们可以对矩阵乘法进行分块，然后再进行汇总，这是Forward pass，还有Backward pass
前向传播（Forward Pass）：往管道里倒水（输入数据），看水流出来的结果（预测值）。
反向传播（Backward Pass）：根据目标结果和实际输出的差异，调整管道的弯曲程度（参数），让水流得更精准。

前向传播中的通信代价

• 张量并行（Tensor Parallelism）：
  • 每个分区需要通信的代价为：
    (B × Di × (P – 1)) / P(B × Di × (P – 1)) / P
  • 总的通信量为：
    𝑁×𝐵×𝐷𝑖N×B×Di
    （每个权重矩阵的前向传播计算和通信代价）
    由于太慢会用些比较快的网络()link?
• 流水线并行（Pipeline Parallelism）：
  • 前向传播中通信量为：
    𝐵×𝐷𝑖B×Di

张量并行的通信代价通常更高。
特别是在不考虑反向传播的情况下，张量并行已经有更高的通信成本。
反向传播中还需要 2倍的 Allreduce（全归约通信），进一步增加张量并行的通信负担。

	Pipeline parallelism	Tensor parallelism
定义	按层分割计算图	分割层内的参数
优点	减少网络沟通	对大模型支持更好
缺点	bubbles	网络沟通较多

一般会一起使用

Information Security

信息安全的三个目标

• 保密性Confidentiality：确保只有授权的人能看到文件内容，限制文件读取
• 正确性/完整性Integrity：确保文件内容不被篡改，限制文件写入
• 可用性Availability：保证服务正常运转，用户随时都能使用。

Threat Model威胁模型：攻击者会采取什么方式攻击，是一种假设，比如：

• 攻击者位于公司网络/防火墙之外
• 攻击者不知道合法用户的密码
• 攻击者不会弄清楚系统是如何工作的
• ……

显然，上面的威胁模型并不完整，甚至不切实际，但是我们仍需要将一个威胁模型作为我们进行安全系统设计的前提

Password

密码的设计目标

• 能够对用户进行身份验证
• 攻击者必须猜测
• 猜测成本是昂贵的

首先我们考虑偷库的问题
简单想法：在服务器上存储密码的哈希值
显然并不安全，可以用常见密码的哈希进行碰撞
于是我们想到了添加“盐”字符串的方法：我们给每个人分配一个随机的盐字符串，将密码与盐字符串进行哈希，再存储。虽然没有完全规避风险，但是可以使攻击者的进攻成本增加许多倍（因为要对每个人都进行一轮碰撞）
不存储密码明文，只存密码的哈希值。
加“盐”：为每个用户生成一个随机字符串，把它加到密码里再哈希。
优点：让攻击者无法使用通用哈希表，只能为每个用户单独破解。

密码保密技术

询问-响应

考虑监听的问题
我们在登录时需要向服务器发送密码，为了防止被监听，简单的想法就是在本地做哈希再上传。
但是哈希仍然可以被监听，我们就需要一种方式，能够使每次的哈希值不同。
我们可以先从服务器请求一个随机数，将密码和随机数一起做哈希，再发给服务器。
这样的问题就是服务器必须保存密码的明文

反向验证

非常不常用，比如让服务器加密一个随机数，用户检查解密结果，防止访问了假的服务器

将离线攻击转化成在线攻击

在注册时，服务器会要求用户上传一张图片，在每次登录时，服务器会要求用户先输入用户名，服务器将图片返回，用户确认图片正确后再输入密码。

那么如果我有一个假网站，我如果想骗到用户的密码，那么我就必须在用户输入用户名后访问真服务器，得到用户的图像，再展示在我的假网站上，以欺骗用输入密码。

这样的后果就是假服务器需要多次请求图片，真服务器可以通过访问次数来发现假服务器，及时止损。

特定密码

为每个软件生成一串密码

N次密码

首先我们需要知道自己登录的次数。在注册时，服务器会对密码+盐做n次哈希
在第一次登录时，我们对密码+盐做n-1次哈希，服务器做一次哈希，再将存储的哈希值替换成n-1次的
在第二次登录时，我们对密码+盐做n-2次哈希，服务器做一次哈希，再将存储的哈希值替换成n-2次的
……

这样的好处是，如果攻击者监听到了哈希值，他必须对哈希做逆向，成本极高

而用户只需要在使用n次后修改密码

时间哈希

实际上就是银行U盾的原理

服务器和用户都保存一个秘密的字符串K，校验时对K+时间做哈希，服务器会检测之前一段时间到现在的时间值是否有同样的哈希

授权与请求绑定

在执行一些操作（付款、转账）等要求用户再输入一次密码

FIDO-Fast IDentity Online

以FaceID登录为例。
用生物识别（如FaceID）本地生成私钥，服务器只存公钥。
登录时用私钥签名服务器的挑战码，服务器用公钥验证签名。

我们录入FaceID时，通过物理元件生成了一对保存在本地的私钥和发给服务器的公钥。
在使用FaceID登录时，手机请求服务器，发送一段“挑战码”，用公钥加密；用户需要使用FaceID才能访问储存私钥的元件，并用私钥对服务端的挑战码进行数字签名，然后将签名和对应的公钥ID（用于识别用户）发送回服务端。服务端使用存储的公钥验证签名的真实性。

Security Principles

• Least Privilege最小权限：在完成同样功能的情况下，尽可能减少给予的权限数量
• Least Trust最小信任：因为每个组件都有可能出错，所以我们尽量不去信任其他组件
• Users Make Mistakes：用户可能自己把密码泄露出去
• Cost of Security安全代价：过于提高安全性会导致性能及用户体验变差

ROP-return-oriented programming

什么是“返回导向的”编程
——recall：ICS1-AttackLab，我们通过栈溢出修改%rax的值，使得代码跳转到了我们编写的程序中。这种攻击被DEP(Data Execution Prevention)防御住，因为他标记了内存中的哪些代码是可执行的。于是我们通过“断章取义”，将原有的代码借助多次return拼接出我们想要执行的代码，然后进行攻击。

防御方式：

• 隐藏二进制文件，攻击者就无法获取到汇编代码
• ASLR地址随机化，每次执行都在不同的内存地址执行（但fork一样
• Canary金丝雀，放在return address前，如果Canary被覆盖掉，说明return address不安全。可以read stack一点点读出来。

CFI-Control-Flow Integrity

什么是“控制流正确性”
——ROP攻击破坏了代码执行的顺序，我们可以提前构建出执行流图来抵御ROP攻击

构造控制流图

我们首先找到程序里需要跳转的地方，构造出如下的图

添加一段硬编码的随机数data到lib，在跳转前检查跳转地址，如下图。上、下分别为修改前和修改后的汇编代码

问题：假设A可以调用C，B可以调用C、D；因为B对%ecx检查只能有一个值，所以C、D的ID是一个值，也就导致A可以调用D
解决方法：将代码复制，不要让B在同一个地方既能调用C也能调用D；多个ID

问题：A调用F，B也调用F，那么F的return会出现和上面一样的问题
解决：shadow stack，为返回值维护另一个栈，用于检查返回的准确性。

实际上CFI不能彻底防御针对于控制流图的攻击，但已经得到了很好的效果

Blind ROP（盲返回导向编程）

假设只知道服务器有栈溢出问题，不知道二进制文件，不知道内存地址空间

发送一个HTTP请求，得到的返回值三种情况：正常返回（无论是网页or404，反正是没崩）/连接断开/kale

假设我们通过栈溢出，覆盖到一部分return address时，我们可以通过n次尝试，得到return address的前几位（错的都崩了，没崩意味着是正确的），同样的攻击方法可以攻破金丝雀
为什么每次地址都一样——因为nginx的服务进程是从父进程fork出来的

如果我们需要进行攻击，就要得到二进制文件；仍然做尝试，我们通过仅修改return address的后两位（一般不会报错），同样可以得到三种情况（正常返回/连接断开/kale）

找到return：

• 我们覆盖两个地址，那么return后就会跳到第二个地址
• 假设我们先将第二个地址设置成断开连接的地址，运行，发现连接断开
• 再将第二个地址改成kale的地址，运行，发现kale，说明第一个地址执行了return

然后我们需要找到能够修改内存的代码，具体而言就是需要找到pop %rdi; return; 之类的代码，显然是很难的，我们从简单的开始。

我们现在需要调用write函数，那么我们需要修改rdi/rsi/rdx三个寄存器的值，外加调用+return

而x86汇编在函数末尾常有以下的代码段，因为这些寄存器是callee save寄存器，所以函数前会有大段push，函数后会有大段pop

我们可以通过连续修改8个return address，然后修改最后一个，看能否引发结果的变化，来判断是不是执行了以上6个pop

而上面这段代码可以通过断章取义执行pop rdi和pop rsi

我们再尝试修改rdx；因为rdx是caller save寄存器，就可以通过调用其他函数修改rdx，而这样的能修改rdx的函数包括系统函数strcmp，而这种函数会存储在PLT中

PLT表有两个特点：地址8对齐；其中全部是可执行的地址，不会导致崩溃

当我们找到PLT表，就可以通过修改rdi、rsi来找到strcmp，方法是通过下面这种方式测试结果

最后我们需要找到write，同样使用PLT表，检查是否能收到一些乱码。

数据流跟踪

我们最初的目标是保护数据，那么能不能通过跟踪数据流动，限制隐私数据发送？

原理：通过计算，禁止jmp到一个被染色（taint为true）（用户可控制）的地址，是动态控制的

原理就是在内存级别做一个taint表，禁止将taint为true的值发送出去。但是taint也是能通过控制流被洗掉的。

Secure Channel安全通道

如何保证设备与设备间的安全

• 两边共享一个密钥key（除非遍历key否则得不到内容）
  • 双方共享一个密钥（key），用它加密和解密消息。
  • 安全性：如果中间者不知道密钥，就无法解密内容，但密钥一旦泄露，消息就不安全了。
• mac：key和message一起加密得到token，token用于校验，防止被篡改（中间者可以拦截A到B的消息，并不断给B重发，可以反复让B执行同样的操作，比如解锁车门）
  • 用key和消息一起生成一个token，发送给接收方。
  • 接收方用同样的方法生成token，比对是否一致。
• 在消息中加入一个变化的seq，用于防止反复测试（避免了重发，但是两边的seq是一样的，中间者可以截取A给B的seq，拼接到自己的假消息上，冒充B给A发）
• Diffie-Hellman：两边交换公钥，然后分别用对方的公钥加密，用自己的私钥解密（中间者可以在密钥交换时拦截，然后一直在中间转发消息）
  • 双方交换公钥，各自用对方的公钥和自己的私钥计算一个“共享密钥”。
  • 中间者可以拦截并替换公钥，和双方分别建立不同的“共享密钥”，让自己变成中间代理。
• RSA公私钥加密：A从网络上的权威机构得到B的公钥（或者B给A发送公钥和权威机构发放的证书）
  • A通过权威机构获取B的公钥（或B提供公钥和机构签发的证书）。
  • A用B的公钥加密消息，只有B的私钥能解密。
  • 优点：公钥是公开的，不怕泄露，私钥在自己手中安全。

Data Privacy数据隐私

技术	核心问题	核心特点
OT（遗忘传输）	隐藏数据需求	数据选择过程不暴露
DP（差分隐私）	防止个人数据泄露	添加噪声或限制查询
Secret Sharing（秘密共享）	多人联合恢复数据	安全分发数据，但需要k个以上联合
HE（同态加密）	数据隐私与计算需求	密文直接计算，保护数据隐私
TEE（可信执行环境）	数据运行环境的安全	硬件隔离和内存加密，防止恶意程序攻击

OT-Oblivious Transfer

A有两个数据；B想要一个，但是B不想让A知道“我”想要哪个

A生成两对公私钥，分别对应一个数据；B生成一个随机数r，并通过想要的数据的公钥加密，发给A；A得到消息后用两个私钥解密得到k₀，k₁（其中有一个是r），然后将两个数据分别与k₀，k₁，做异或，全部发给B；B再和r做一次异或，就能得到自己要的数据

A不清楚B到底要哪一个数据。
B保证自己只拿到需要的数据，不泄露意图。

DP-Differencial Privacy差分隐私

B数据库中有各种数据，只支持多条数据一起返回；但是A想得到一个人的数据。显然A可以通过多次反复筛选得到想要是数据。所以B的处理方式是：返回值分段（返回一个近似值而非精确值，有损的）；设定询问预算（在数据库未更新前，B只能询问几次）这样即使数据被多次查询，仍然无法得到精确的个人信息。

Secret Sharing

假设n个人共享一个数据，分成n份，而只要有任意k个人就能恢复出数据

原理：S为加密数据，f(x) = S + a₁x + a₂x + … + a_k-1x^k-1，n个人拿不同的x，k个人就能解出全部a_i

优点：是一个信息理论上安全的协议

缺点：理想假设（至少 k 个部分永远不会串通） 通信开销

HE–Homomorphic Encryption同态加密

能否实现密文加减乘除得到的结果，也是原文加减乘除得到的结果对应的密文（用于云上运算）

SWHE(SomeWhat Homomorphic Encryption)部分同态加密：支持部分操作的同态加密
FHE(Full Homomorphic Encryption)全同态加密：所有运算都支持；做不到

数据在加密状态下可以计算，保护隐私。
缺点：全同态加密目前效率较低。做不到

TEE-Trusted Execution Environment可信执行环境

原理：内存加密，加载到cache中变成明文

TEE 可以访问所有 DRAM 和外围设备；REE 无法访问 TEE 的资源

缺点：必须信任硬件厂商