【分布式计算：原理、算法和系统】第一章引言

1.1 定义

何谓分布式系统：A distributed system is a collection of independent entities that cooperate to solve a problem that cannot be individually solved.

分布式系统是由一组相互独立的实体构成的集合 这些实体相互协作可解决任 何单独的实体所不能解决的问题

分布式系统的特点：A distributed system can be characterized as a collection of mostly autonomous processors 自治的处理器 communicating over a communication network and having the following features.

• No common physical clock-没有共同的物理时钟: inherent asynchrony amongst the processors 存在异步问题

• No shared memory-没有共享内存

• Geographical separation-地理分散

• Autonomy and heterogeneity-自治与异构的：The processors are "loosely coupled"松散耦合的

1.2 与计算机系统部件的关系

典型的分布式系统如下：

P：处理器 M：存储器组

The distributed software is termed as middleware.中间件

An execution is also sometimes termed a computation or a run.

The distributed system uses a **layered architecture ** to break down the complexity of system design 分层的架构

Distributed software：provide transparency of heterogeneity at the platform level.异构透明性

CORBA：common object request broker architecture

RPC：remote procedure call

RPC机制在概念上类似于本地的过程调用，区别在于过程代码可能存在于远端机器上，RPC软件通过网络发送一个消息来调用远端的过程。而后，调用者等待响应，从调用它的程序的角度看，获得响应后，这样的一个过程调用才算完成

1.3 动机

The motivation for using a distributed system is some or all of the following requirements:

1️⃣ Inherently distributed computations.

2️⃣ Resource sharing.

3️⃣ Access to geographically remote data and resources.

Advances in the design of resource-constrained mobile devices as well as in the wireless technology with which these devices communicate have given further impetus to the importance of distributed protocols and middleware.

4️⃣ Enhanced reliability.Reliability entails several aspects:

1. availability：资源应当在所有的时间内都可以访问
2. integrity：面对多个处理器同时进行访问时，资源的值或者状态应当是正确 的符合应用所期望的语义
3. fault-tolerance：即有能力在系统故障的时候恢复工作

5️⃣ Increased performance/cost ratio

6️⃣ Scalability. 由于处理器通常通过广域网络连接，所以增加更多的处理器不会直接在通信网络中造成瓶颈

7️⃣ Modularity and incremental expandability.异构的处理器只要运行相同的中间件算法就可以很 容易加入到系统中而不会影响性能

1.4 与并行多处理器/多计算机系统的关系

1.4.1 并行系统的特征

并行系统大体上分为以下三类：

1️⃣ Multiprocessor system. 多处理器系统直接访问共享内存(下图a)

UMA：uniform memory access

All the processors usually run the same operating system, and both the hardware and software are very tightly coupled 紧耦合.

The processors are usually of the same type, and are housed within the same box/container with a shared memory

2️⃣ Multicomputer parallel system. The multiple processors do not have direct access to shared memory.（上图b）

The processors are in close physical proximity and are usually very tightly coupled (homogenous hardware and software), and connected by an interconnection network.

NUMA: non-uniform memory access. The latency to access various shared memory locations from the different processors varies.

3️⃣ Array processors.阵列处理器

physically co-located, are very tightly coupled, and have a common system clock (but may not share memory and communicate by passing data using messages).

The primary and most efficacious use of parallel systems is for obtaining a higher throughput by dividing the computational workload among the processors.

1.4.2 Flynn的分类法

Flynn identified four processing modes, based on whether the processors execute the same or different instruction streams at the same time, and whether or not the processors processed the same (identical) data at the same time. 基于处理器是否同时执行相同或者不同的指令流，以及处理器是否同时处理相同的数据，区分出了四种处理模式：

1️⃣ Single instruction stream, single data stream (SISD)——单指令流、单数据流

• Conventional processing in the von Neumann paradigm with a single CPU, and a single memory unit connected by a system bus.

2️⃣ Single instruction stream, multiple data stream (SIMD)——单指令流、单数据流

• Multiple homogenous processors which execute in lock-step on different data items.
• Operations on large arrays and matrices.
• Illiac-IV, MPP, CM2, and MasPar MP-1 were SIMD machines.
• The MMX units in Intel processors and DSP chips such as the Sharc

LOCKSTEP技术使用相同的、冗余的硬件组件在同一时间内处理相同的指令。

LOCKSTEP技术可以保持多个CPU、内存精确的同步，在正确的相同时钟周期内执行相同的指令

3️⃣ Multiple instruction stream, single data stream (MISD)——多指令流、单数据流

• The execution of different operations in parallel on the same data.
• Visualization——可视化

4️⃣ Multiple instruction stream, multiple data stream (MIMD)——多指令流、多数据流

• The various processors execute different code on different data.
• There is no common clock among the system processors.
• Sun Ultra servers, multicomputer PCs, and IBM SP machines.
• The most general and allow much flexibility in partitioning code and data to be processed among the processors.

1.4.3 耦合、并行、并发与粒度

1、Coupling-耦合

🔥 定义：The degree of coupling among a set of modules, whether hardware or software, is measured in terms of the interdependency and binding and/or homogeneity among the modules

SIMD and MISD architectures generally tend to be tightly coupled because of the common clocking of the shared instruction stream or the shared data stream.

通过耦合程度，我们可以将MIMD架构进行划分：

1️⃣ Tightly coupled multiprocessors (with UMA shared memory)

2️⃣ Tightly coupled multiprocessors (with NUMA shared memory or that communicate by message passing)

3️⃣ Loosely coupled multicomputers (without shared memory) physically colocated

4️⃣ Loosely coupled multicomputers (without shared memory and without common clock) that are physically remote

2、Parallelism or speedup of a program on a specific system

Parallelism：并行性

speedup：It is expressed as the ratio of the time $T(1)$ with a single processor, to the time $T(n)$ with n processors.
$$S_p=\frac{T(1)}{T(n)}$$

3、Parallelism within a parallel/distributed program

This is an aggregate measure of the percentage of time that all the processors are executing CPU instructions productively 有效执行CPU, as opposed to waiting for communication (either via shared memory or message-passing) operations to complete.

4、Concurrency of a program

Concurrency：并发性

The parallelism/concurrency in a parallel/distributed program can be measured by the ratio of the number of local (non-communication and non-shared memory access) operations to the total number of operations, including the communication or shared memory access operations.

并行性和并发性是既相似又有区别的两个概念，并行性是指两个或多个事件在同一时刻发生；而并发性是指两个或多个事件在同一时间间隔内发生。在多道程序环境下，并发性是指在一段时间内宏观上有多个程序在同时运行，但在单处理机系统中每一时刻却仅能有一道程序执行，故微观上这些程序只能是分时地交替执行。

并发适用于分布式系统、并行适用于并行系统。

5、Granularity of a program

Granularity：粒度

定义：The ratio of the amount of computation to the amount of communication within the parallel/distributed program is termed as granularity.
$$granularity=\frac{amoun{t}_{comp}}{amoun{t}_{commu}}$$
Coarse-grained (fine-grained): more (fewer) productive CPU instruction executions, compared to the number of times the processors communicate either via shared memory or messagepassing and wait to get synchronized with the other processors.如果是粗粒度（细粒度）并行性，则相较于处理器通过共享内存或者消息传递进行通信以及等待与其他处理器同步所花费时间而言，会有相对来说更多（更少）有用的指令执行

Programs with fine-grained parallelism are best suited for tightly coupled systems.

松耦合：粗粒度；紧耦合：细粒度

对多处理器/多计算机系统进行分类

1️⃣ network operating system：The operating system running on loosely coupled processors (i.e., heterogenous and/or geographically distant processors), which are themselves running loosely coupled software (i.e., software that is heterogenous)

2️⃣ distributed operating system：The operating system running on loosely coupled processors, which are running tightly coupled software (i.e., the middleware software on the processors is homogenous).

3️⃣ multiprocessor operating system: The operating system running on tightly coupled processors, which are themselves running tightly coupled software

1.5 消息传递系统与共享内存系统的对比

Shared memory systems are those in which there is a (common) shared address space throughout the system.

Semaphores and monitors.

The abstraction called shared memoryis sometimes provided to simulate a shared address space. For a distributed system, this abstraction is called distributed shared memory.

1.5.1 Emulating message-passing on a shared memory system (MP → SM)

The shared address space can be partitioned into disjoint parts, one part being assigned to each processor.

“Send” and “receive” operations can be implemented by writing to and reading from the destination/sender processor’s address space, respectively.

A $P_i-P_j$ message-passing can be emulated by a write by $P_i$ to the mailbox and then a read by $P_j$ from the mailbox.

The write and read operations need to be controlled using synchronization primitives to inform the receiver/sender after the data has been sent/received.

1.5.2 Emulating shared memory on a message-passing system (SM → MP)

Using “send” and “receive” operations for “write” and “read” operations.

Each shared location can be modeled as a separate process; “write” to a shared location is emulated by sending an update message to the corresponding owner process; a “read” to a shared location is emulated by sending a query message to the owner process. 写入一个共享位置可以通过给相应位置的进程发送更新消息来仿真，读出 一个共享位置可以通过对相应位置的进程发送一个查询消息来仿真

The latencies involved in read and write operations may be high even when using shared memory emulation.网络延迟很高

As message-passing systems are more common and more suited for wide-area distributed systems, we will consider message-passing systems more extensively than we consider shared memory systems.

1.6 分布式通信的原语

primitive：原语

计算机进程的控制通常由原语完成。所谓原语，一般是指由若干条指令组成的程序段，用来实现某个特定功能，在执行过程中不可被中断。在操作系统中，某些被进程调用的操作，如队列操作、对信号量的操作、检查启动外设操作等，一旦开始执行，就不能被中断，否则就会出现操作错误，造成系统混乱。所以，这些操作都要用原语来实现。原语是操作系统核心（不是由进程，而是由一组程序模块组成）的一个组成部分，并且常驻内存，通常在管态下执行。原语一旦开始执行，就要连续执行完，不允许中断。

1.6.1 阻塞/非阻塞，同步/异步原语

消息发送和消息接收通信原语可以分别以$Send()$和$Recivie()$标识。一个$Send()$原语具有至少两个参数——目标以及用户空间的缓冲区，缓冲区中包含了需要发送的数据。类似地，一个$Recivie()$原语也至少包含两个参数——发送数据的源 （可能被忽略）以及一个用户的缓冲区用来存放接收到的数据 。

当$Send()$原语被调用的时候有两种方式可以发送数据缓冲方式和非缓冲方式。对于$Recivie()$原语来说缓冲方式通常是需要的，这是由于在调用这个原语的时候，数据可能已经到达，需要在内核中有一个存储位置

下面是有关于阻塞/非阻塞以及同步/异步原语的一些定义：

1️⃣ Synchronous primitives

A Send or a Receive primitive is synchronousif both the Send() and Receive() handshake with each other.

2️⃣ Asynchronous primitives

A Send primitive is said to be asynchronous if control returns back to the invoking process 调用进程 after the data item to be sent has been copied out of the user-specified buffer.

3️⃣ Blocking primitives

A primitive is blocking if control returns to the invoking process after the processing for the primitive (whether in synchronous or asynchronous mode) completes.

4️⃣ Non-blocking primitives

A primitive is non-blocking if control returns back to the invoking process immediately after invocation, even though the operation has not completed.

同步异步是针对调用者来说的，调用者发起一个请求后，一直等待被调用者的反馈就是同步，不必等待去做别的事就是异步。

阻塞非阻塞是针对被调用者来说的，被调用者收到一个请求后，做完请求任务后才给出反馈就是阻塞，收到请求直接给出反馈再去做任务就是非阻塞。

A synchronous Send is easier to use from a programmer’s perspective because the handshake between the Send and the Receive makes the communication appear instantaneous, thereby simplifying the program logic.

The non-blocking asynchronous Send (see Figure 1.8(d)) is useful when a large data item is being sent because it allows the process to perform other instructions in parallel with the completion of the Send.

The non-blocking Receive (see Figure 1.8(b)) is useful when a large data item is being received.

Blocking primitives are easier to use.

1.6.2 处理器同步

Processor synchrony indicates that all the processors execute in lock-step with their clocks synchronized.

As this synchrony is not attainable in a distributed system, what is more generally indicated is that for a large granularity of code, usually termed as a step, the processors are synchronized.

1.7 同步与异步执行

1.7.1 Asynchronous Execution

1️⃣ There is no processor synchrony and there is no bound on the drift rate of processor clocks.

所谓时钟漂移：抖动的另一种形式，工程上给出这样的解释：当抖动频率小于10Hz的时候把这样的抖动叫做漂移。抖动即在时钟信号短时间内的波动。

2️⃣ Message delays (transmission + propagation times) are finite but unbounded.

3️⃣ There is no upper bound on the time taken by a process to execute a step.

1.7.2 Synchronous Execution

1️⃣ Processors are synchronized and the clock drift rate between any two processors is bounded.

2️⃣ Message delivery (transmission + delivery) times are such that they occur in one logical step or round.

3️⃣ There is a known upper bound on the time taken by a process to execute a step.

The fewer the steps or “synchronizations” of the processors, the lower the delays and costs

Virtually synchronous execution：processors are allowed to have an asynchronous execution for a period of time and then they synchronize.

1.8 设计主题与挑战

1.8.1 从系统角度看分布式系统的挑战

下面几个功能必须要在设计和构建一个分布式系统的时候考虑到：

1. Communication
2. Process
3. Naming
4. Synchronization
5. Data storage and access
6. Consistency and replication
7. Fault tolerance
8. Security
9. API and transparency
10. Scalability and modularity

1.8.2 分布式计算中的算法挑战

Reliable and fault-tolerant distributed systems

1. Consensus algorithms

2. Replication and replica management

3. Voting and quorum systems

4. Distributed databases and distributed commit

5. Self-stabilizing systems

   A self-stabilizing algorithm is any algorithm that is guaranteed to eventually take the system to a good state even if a bad state were to arise due to some error.

6. Checkpointing and recovery algorithms

7. Failure detectors

   Failure detectors represent a class of algorithms that probabilistically suspect another process as having failed (such as after timing out after non-receipt of a message for some time), and then converge on a determination of the up/down status of the suspected process.

参考资料

[1] Ajay D. Kshemkalyani, & Mukesh Singhal (2008). Distributed Computing: Principles, Algorithms, and Systems