分布式系统入门：探索Dynamo、BigTable和MapReduce背后的概念

需积分: 50 29 浏览量更新于2024-07-18 13 收藏 811KB PDF 举报

"分布式系统是现代信息技术中的一个重要概念，它涉及到多个独立的计算机节点通过网络进行协同工作，共同处理任务。分布式系统的设计旨在提供高可用性、可扩展性和容错性，以应对大规模数据处理和高并发访问的需求。本资源提供了一个关于分布式系统的概述，包括关键概念和最新技术的介绍，如亚马逊的Dynamo、谷歌的BigTable和MapReduce、阿帕奇的Hadoop等。作者旨在提供一个易于理解的入口，帮助读者掌握分布式系统的基础知识，并理解其核心理念，而不是深入到每一个细节。在分布式系统中，有两个主要的后果需要处理： 1. 信息传播速度：由于信息传输受到光速的限制，分布式系统必须考虑到延迟问题。这涉及到网络通信的优化，例如减少网络请求的次数，使用更有效的数据压缩和缓存策略，以及利用更高效的协议来提高通信效率。 2. 独立组件的独立故障：分布式系统由多个独立的节点组成，每个节点都有可能单独出现故障。因此，设计时必须考虑容错性，通过冗余和复制策略确保系统的高可用性。例如，副本一致性、故障检测和恢复机制是解决这一问题的关键技术。分布式系统的设计通常围绕以下几个核心概念： - 分布式一致性：确保在分布式环境中数据的一致性，即使在节点间存在延迟或故障的情况下。常见的模型有强一致性（如两阶段提交）和最终一致性（如Paxos和Raft算法）。 - 分布式计算：通过并行处理大量数据，如MapReduce模型，将大任务分解成小任务并行执行，然后汇总结果。 - 分布式存储：如BigTable和Hadoop的HDFS，提供高容量、高吞吐量的数据存储解决方案，支持大数据的读写操作。 - 负载均衡：有效地分配系统资源，确保所有节点的负载均衡，以避免部分节点过载。 - 容错机制：通过心跳检测、故障转移和自动恢复策略，确保系统在单个或多个组件失败时仍能继续运行。 - 分布式协调：例如Zookeeper这样的服务，用于管理配置信息、命名、提供分布式同步和组服务。了解这些基本概念后，你可以根据个人兴趣深入研究各个主题，例如分布式数据库的ACID属性、CAP定理、事件溯源、微服务架构等。随着互联网的发展，分布式系统技术持续演进，不断有新的框架和工具涌现，如Kubernetes用于容器编排，Elasticsearch用于分布式搜索，以及各种分布式消息队列系统。学习分布式系统不仅能够提升对大型系统的理解，也有助于开发出更稳定、高效的应用程序。"

Every concept originates through our equating what is unequal. No leaf ever wholly equals

another, and the concept "leaf" is formed through an arbitrary abstraction from these individual

differences, through forgetting the distinctions; and now it gives rise to the idea that in nature

there might be something besides the leaves which would be "leaf" - some kind of original form

after which all leaves have been woven, marked, copied, colored, curled, and painted, but by

unskilled hands, so that no copy turned out to be a correct, reliable, and faithful image of the

original form.

Abstractions, fundamentally, are fake. Every situation is unique, as is every node. But

abstractions make the world manageable: simpler problem statements - free of reality - are

much more analytically tractable and provided that we did not ignore anything essential, the

solutions are widely applicable.

Indeed, if the things that we kept around are essential, then the results we can derive will be

widely applicable. This is why impossibility results are so important: they take the simplest

possible formulation of a problem, and demonstrate that it is impossible to solve within some

set of constraints or assumptions.

All abstractions ignore something in favor of equating things that are in reality unique. The trick

is to get rid of everything that is not essential. How do you know what is essential? Well, you

probably won't know a priori.

Every time we exclude some aspect of a system from our specification of the system, we risk

introducing a source of error and/or a performance issue. That's why sometimes we need to go

in the other direction, and selectively introduce some aspects of real hardware and the real-

world problem back. It may be sufficient to reintroduce some specific hardware characteristics

(e.g. physical sequentiality) or other physical characteristics to get a system that performs well

enough.

With this in mind, what is the least amount of reality we can keep around while still working

with something that is still recognizable as a distributed system? A system model is a

specification of the characteristics we consider important; having specified one, we can then

take a look at some impossibility results and challenges.

A system model

A key property of distributed systems is distribution. More specifically, programs in a distributed

system:

run concurrently on independent nodes ...

are connected by a network that may introduce nondeterminism and message loss ...

and have no shared memory or shared clock.

There are many implications:

each node executes a program concurrently

12/72

knowledge is local: nodes have fast access only to their local state, and any information

about global state is potentially out of date

nodes can fail and recover from failure independently

messages can be delayed or lost (independent of node failure; it is not easy to

distinguish network failure and node failure)

and clocks are not synchronized across nodes (local timestamps do not correspond to

the global real time order, which cannot be easily observed)

A system model enumerates the many assumptions associated with a particular system

design.

System model

a set of assumptions about the environment and facilities on which a distributed system is

implemented

System models vary in their assumptions about the environment and facilities. These

assumptions include:

what capabilities the nodes have and how they may fail

how communication links operate and how they may fail and

properties of the overall system, such as assumptions about time and order

A robust system model is one that makes the weakest assumptions: any algorithm written for

such a system is very tolerant of different environments, since it makes very few and very weak

assumptions.

On the other hand, we can create a system model that is easy to reason about by making

strong assumptions. For example, assuming that nodes do not fail means that our algorithm

does not need to handle node failures. However, such a system model is unrealistic and hence

hard to apply into practice.

Let's look at the properties of nodes, links and time and order in more detail.

Nodes in our system model

Nodes serve as hosts for computation and storage. They have:

the ability to execute a program

the ability to store data into volatile memory (which can be lost upon failure) and into

stable state (which can be read after a failure)

a clock (which may or may not be assumed to be accurate)

Nodes execute deterministic algorithms: the local computation, the local state after the

computation, and the messages sent are determined uniquely by the message received and

local state when the message was received.

13/72

There are many possible failure models which describe the ways in which nodes can fail. In

practice, most systems assume a crash-recovery failure model: that is, nodes can only fail by

crashing, and can (possibly) recover after crashing at some later point.

Another alternative is to assume that nodes can fail by misbehaving in any arbitrary way. This

is known as Byzantine fault tolerance. Byzantine faults are rarely handled in real world

commercial systems, because algorithms resilient to arbitrary faults are more expensive to run

and more complex to implement. I will not discuss them here.

Communication links in our system model

Communication links connect individual nodes to each other, and allow messages to be sent in

either direction. Many books that discuss distributed algorithms assume that there are

individual links between each pair of nodes, that the links provide FIFO (first in, first out) order

for messages, that they can only deliver messages that were sent, and that sent messages can

be lost.

Some algorithms assume that the network is reliable: that messages are never lost and never

delayed indefinitely. This may be a reasonable assumption for some real-world settings, but in

general it is preferable to consider the network to be unreliable and subject to message loss

and delays.

A network partition occurs when the network fails while the nodes themselves remain

operational. When this occurs, messages may be lost or delayed until the network partition is

repaired. Partitioned nodes may be accessible by some clients, and so must be treated

differently from crashed nodes. The diagram below illustrates a node failure vs. a network

partition:

It is rare to make further assumptions about communication links. We could assume that links

only work in one direction, or we could introduce different communication costs (e.g. latency

due to physical distance) for different links. However, these are rarely concerns in commercial

environments except for long-distance links (WAN latency) and so I will not discuss them here;

a more detailed model of costs and topology allows for better optimization at the cost of

complexity.

Timing / ordering assumptions

14/72

One of the consequences of physical distribution is that each node experiences the world in a

unique manner. This is inescapable, because information can only travel at the speed of light.

If nodes are at different distances from each other, then any messages sent from one node to

the others will arrive at a different time and potentially in a different order at the other nodes.

Timing assumptions are a convenient shorthand for capturing assumptions about the extent to

which we take this reality into account. The two main alternatives are:

Synchronous system model

Processes execute in lock-step; there is a known upper bound on message transmission

delay; each process has an accurate clock

Asynchronous system model

No timing assumptions - e.g. processes execute at independent rates; there is no bound on

message transmission delay; useful clocks do not exist

The synchronous system model imposes many constraints on time and order. It essentially

assumes that the nodes have the same experience: that messages that are sent are always

received within a particular maximum transmission delay, and that processes execute in lock-

step. This is convenient, because it allows you as the system designer to make assumptions

about time and order, while the asynchronous system model doesn't.

Asynchronicity is a non-assumption: it just assumes that you can't rely on timing (or a "time

sensor").

It is easier to solve problems in the synchronous system model, because assumptions about

execution speeds, maximum message transmission delays and clock accuracy all help in

solving problems since you can make inferences based on those assumptions and rule out

inconvenient failure scenarios by assuming they never occur.

Of course, assuming the synchronous system model is not particularly realistic. Real-world

networks are subject to failures and there are no hard bounds on message delay. Real world

systems are at best partially synchronous: they may occasionally work correctly and provide

some upper bounds, but there will be times where messages are delayed indefinitely and

clocks are out of sync. I won't really discuss algorithms for synchronous systems here, but you

will probably run into them in many other introductory books because they are analytically

easier (but unrealistic).

The consensus problem

During the rest of this text, we'll vary the parameters of the system model. Next, we'll look at

how varying two system properties:

whether or not network partitions are included in the failure model, and

synchronous vs. asynchronous timing assumptions

influence the system design choices by discussing two impossibility results (FLP and CAP).

15/72

剩余71页未读，继续阅读

江南梅爷

粉丝: 7
资源: 10

分布式系统入门：探索Dynamo、BigTable和MapReduce背后的概念

Distributed Computing Pearls

后台密码破解器

DES前端加密，后端可解密

DistributedSystem

distributed system

distributed system material

Distributed System BuildingBlocks

RMI.rar_distributed system_operating system

s2_distributedsystem_

COMP512_DistributedSystem

最新资源