COMP90015 Distributed Systems
Distributed System Models
Aaron of Computing and Information Systems © The University of Melbourne
2022 Semester II
Copyright By PowCoder代写 加微信 powcoder
(School of Computing and InformaCtiOonMSPy9s0te0m15s ©DistTrihbeutUednivSeyrsstietymosf Melbourne)
2022 Semester II 1/53
1 Modelling Overview
2 Functional Models
Processes and Machines Common architectural patterns Network characteristics Distributed system topology System state and overheads
3 Non-functional Models Temporal Model
Failure Model
Security Model
(School of Computing and InformaCtiOonMSPy9s0te0m15s ©DistTrihbeutUednivSeyrsstietymosf Melbourne)
2022 Semester II 2/53
Modelling Overview
Functional and non-functional models
In this section we will develop a model of a distributed system, from first principles.
• Developing the model means specifying a notation for representing a real-world distributed system and its environment as an ideal (read mathematical) object or concept.
• Functional models are concerned with how the distributed system implements functionality, the tangible aspects of the distributed system. In this section our Functional models will be time-independent – that is they describe aspects of the system that are constant over the system’s lifetime.
• Non-functional models are concerned with aspects which are intangible such as time, reliability and security. When we model time then we can revise our Functional models to provide time-dependent Functional models.
In this section we will demonstrate how the models can be used to make some basic statements of a distributed system’s properties and behaviour.
(School of Computing and InformaCtiOonMSPy9s0te0m15s ©DistTrihbeutUednivSeyrsstietymosf Melbourne) 2022 Semester II 3/53
Functional Models Processes and Machines
Processes and machines
The Architectural Model is, in a broad sense, concerned with the components or entities of the system, the roles that they take, the relationships between them, and how they are expected to interact with each other. In this subject we are satisfied by the components being considered simply as processes, and to describe the physical hardware/OS, i.e. the platform or platforms that the processes execute on:
• Architectural elements – components of the system that interact with one another
• Architectural patterns – the way components are mapped to the underlying system
• Associated middleware solutions – existing solutions to common problems
(School of Computing and InformaCtiOonMSPy9s0te0m15s ©DistTrihbeutUednivSeyrsstietymosf Melbourne) 2022 Semester II 4/53
Functional Models Processes and Machines
Process Roles
Each process has a high-level purpose or role that it takes in the distributed system. Here are some common examples of process roles:
• User Interface Process – a process that allows users to interact with the distributed system, either graphical or command line based. It usually acts as a client to other processes in the distributed system.
• Data Cache – a process that caches information, typically in memory, for fast access by other processes.
• Communication Relay – a process that other processes can connect to in order to undertake indirect communication with other processes.
• Job Manager – a process that can start, stop and monitor other distributed system processes.
• Index or Registry Server – a process that provides the location, e.g. the network address, of resources in the distributed system.
• Database Server – a process that provides a database service. A database server process allows other processes acting as database clients to connect to it and obtain database services.
• Authentication Server – a process that authenticates users, e.g. by passwords or other security mechanisms. Other processes in the distributed system may require users to authenticate with the Authentication Server prior to providing service.
(School of Computing and InformaCtiOonMSPy9s0te0m15s ©DistTrihbeutUednivSeyrsstietymosf Melbourne) 2022 Semester II 5/53
Functional Models Processes and Machines
Middleware
In most cases the roles described earlier can be undertaken by a group of processes, that we sometimes refer to as a sub-system e.g.:
• Reliable Key-Value Storage – a fault tolerant general purpose storage system
• Cluster Resource Management – helps to manage resources on a cluster of machines
• Enterprise User Management – helps to manage users in a large organization
• High Performance Messaging – provides optimized communication mechanisms
They are usually referred to as middleware. As part of our distributed system architecture we may choose to use various kinds of middleware as sub-systems that solve common problems for us in a distributed way. We should understand the architecture of the sub-system and what impacts it has on our distributed system architecture as a whole. Our models help us do this.
(School of Computing and InformaCtiOonMSPy9s0te0m15s ©DistTrihbeutUednivSeyrsstietymosf Melbourne) 2022 Semester II 6/53
Functional Models Processes and Machines
Machine Roles
Similarly to processes, machines tends to have well defined roles in the distributed system, and here are some examples:
• Dekstop/PC – runs client processes, has a fixed location at home or at work, user may or may not be at the machine, has no power limitations, has reasonably good resource capacity, usually connected to the network via Ethernet, may be switched on for long periods of time, may or may not have a public IP address
• Mobile Device – runs client processes, is mobile – may connect via all kinds of public networks, tends to be with the user 24/7, has power limitation, usually limited resource capacity, only connected via wireless WiFi or cellular, may be on 24/7, usually wont have a public IP address
• Front End Server – runs server processes that allow clients to connect to it, located in a machine room at a fixed location, is only remotely connected to, has no power limitations, has significant resource capacity, connected via high speed Ethernet, on 24/7, has a public IP address
• Back End Server – runs distributed processes to support front end servers, located in a machine room at a fixed location, is not reachable from the public Internet, has no power limitations, has significant compute and storage capacity, connected via high speed Ethernet, on 24/7, has a private address
• Virtual Machine/Server – runs on cloud infrastructure, provides capabilities similar to Front/Back End Servers.
(School of Computing and InformaCtiOonMSPy9s0te0m15s ©DistTrihbeutUednivSeyrsstietymosf Melbourne) 2022 Semester II 7/53
Functional Models Processes and Machines Interfaces and IPC mechanisms
• Distributed processes can not directly access each others internal variables or procedures. Passing parameters needs to be reconsidered, in particular, call by reference is not supported as address spaces are not the same between distributed processes. This leads to the notion of an interface. The set of functions that can be invoked by external processes is specified by one or more interface definitions.
• Programmers are only concerned with the abstraction offered by the interface, they are not aware of the implementation details.
• Programmers also need not know the programming language or underlying platform used to implement the service.
• So long as the interface does not change (or that changes are backwards compatible), the service implementation can change transparently.
• Choices of IPC mechanism include:
• Direct IPC are the underlying primitives – relatively low-level (perhaps the lowest level) of
support for communication between processes in a distributed system, e.g. shared
memory, sockets, multicast communication
• Remote invocation – based on a two-way exchange between communicating entities in a
distributed system and resulting in the calling of a remote operation, procedure or
method, e.g. request-reply protocols, remote procedure calls, remote method invocation
• Indirect communication:
• space uncoupling – senders do not need to know who they are sending to
• time uncoupling – senders and receivers do not need to exist at the same time
• for example: group communication, publish-subscribe systems, message queues, tuple spaces,
distributed shared memory
(School of Computing and InformaCtiOonMSPy9s0te0m15s ©DistTrihbeutUednivSeyrsstietymosf Melbourne) 2022 Semester II 8/53
Functional Models Processes and Machines
Placement of processes onto machines in the distributed system is a fairly central aspect of the distributed system architecture and design problem. E.g.:
• mapping services to multiple servers – a single service may not make use of a single process and multiple processes may be distributed across multiple machines
• caching – storing data at places that are typically closer to the client or whereby subsequent accesses to the same data will take less time
• mobile code – transferring the code to the location that is most efficient, e.g. running a complex query on the same machine that stores the data, rather than pulling all data to the machine that initiated the query
• mobile agents – code and data together, e.g. used to install and maintain software on a users computer, the agent continues to check for updates in the background
(School of Computing and InformaCtiOonMSPy9s0te0m15s ©DistTrihbeutUednivSeyrsstietymosf Melbourne) 2022 Semester II 9/53
Functional Models Processes and Machines Modelling processes, machines and process placement
We can start modelling a distributed system by consider the collection of processes, or let us say n processes in order to model it.
Similarly we can consider the collection of machines that these processes will be distributed over, let us say m machines in this case.
Each process runs on a machine. If we wanted to model this we could define a mapping or placement from processes to machines. Let’s say if
i ∈ N = {1,2,…,n} is a process, referred to as process i, then let Pi = j be the machine j ∈ M = {1,2,…,m} that process i is placed on.
We could simplify the model by assuming that there are as many machines as there are processes, m = n. Some distributed systems can be modelled this way, e.g. peer-to-peer file sharing systems tend to have a peer running on each user’s computer. There are no other processes or machines involved.
(School of Computing and InformaCtiOonMSPy9s0te0m15s ©DistTrihbeutUednivSeyrsstietymosf Melbourne) 2022 Semester II 10/53
Functional Models Processes and Machines Process resource requirements and machine capacity I
Lets continue to expand the model. Let Lj be the number of processes that are placed on machine j:
Lj ={i | Pi =j}
Load can be interpreted as a simple or first order measure of the resource capacity requirements of a machine – every process requires resources; cpu, memory, network, storage.
We can model each processes’ resource requirements if we wish and we can also model each machine’s capacity. A more detailed model becomes harder to understand but it allows us to make more precise statements about the distributed system. Let’s see where we can get to in this direction.
We could simply say that each machine has an integral capacity of K ≥ 1, meaning that no more than K processes can be placed on any single
(School of Computing and InformaCtiOonMSPy9s0te0m15s ©DistTrihbeutUednivSeyrsstietymosf Melbourne) 2022 Semester II 11/53
Functional Models Processes and Machines Process resource requirements and machine capacity II
machine. Our machines are said to be homogeneous with respect to capacity. Or we could allow our machines to be heterogeneous and model the capacity as Cj ∈ Z>0, .i.e. Cj > 0 is an integer. The case when
Cj = K for all j is the (special) homogeneous case of the heterogeneous model.
If we like we could have used the positive real numbers R>0 for our model instead of the positive integers Z>0. Doing so may be somewhat more realistic – a given machine’s capacity may well be e.g. 5.5 meaning that when executing 5 processes the machine still has spare capacity but not enough to support 6 processes. In engineering analysis and optimization we may want to use real numbers, but for the analysis and optimization of distributed algorithms and when analysing a distributed system’s architectural properties we may prefer integers.
We could model each of the machine’s primary resource capacities – cpu, memory, network and storage – with more detail. If this is desired we
(School of Computing and InformaCtiOonMSPy9s0te0m15s ©DistTrihbeutUednivSeyrsstietymosf Melbourne) 2022 Semester II 12/53
Functional Models Processes and Machines Process resource requirements and machine capacity III
could write Cj,resource to represent the capacity of a specific resource on machine j, e.g. Cj,cpu could be the number of cpus on machine j. Or more succinctly Cj,r could refer to the capacity of resource r ∈ R, which is some set of resources that we are interested in. We generally do not need to model machine resources beyond a simple first order measure, but we can if we wish.
When modelling the network resource we tend to talk in terms of available upload (data going out of the machine) and download (data coming into the machine) bitrates. The network is an important resource to model because all of our IPC will make use of it. There are other considerations as well with respect to network modelling since it is impacted by the computer network that our machine is connected to, and as well the other machine in the communication. We will specifically revisit our model of the network later.
(School of Computing and InformaCtiOonMSPy9s0te0m15s ©DistTrihbeutUednivSeyrsstietymosf Melbourne) 2022 Semester II 13/53
Functional Models Processes and Machines Process resource requirements and machine capacity IV
On the other hand we have process requirements. It is implicit in the model that each process requires to be placed on a machine. However continuing our definition of resources we could let Pi,r be the amount of resource r that process i requires. This could be considered the maximum amount of that resource that the process will consume when running. With these basic definitions in place we can consider the total resource requirements for resource r on a given machine j:
Lj,r = Pi,r i | Pi =j
(School of Computing and InformaCtiOonMSPy9s0te0m15s ©DistTrihbeutUednivSeyrsstietymosf Melbourne) 2022 Semester II 14/53
Functional Models Processes and Machines Analysis: load balancing and placement problems I
We can now formulate a number of interesting statements and problems with respect to process placement on machines and resource consumption. E.g. we might want to assert that no machine is allowed to execute more processes than it has capacity for:
Lj,r ≤ Cj,r for all r ∈ R
In other words we might assert that the placement of processes should never exceed the resource capacity of any machine. We might indeed formulate the problem of finding a placement of processes that achieves some objective (subject to the capacity restriction above), e.g. minimizing the maximum consumption of resource r over all machines,
arg min max {Lj,r } , {P1 ,P2 ,…,Pn } j
(School of Computing and InformaCtiOonMSPy9s0te0m15s ©DistTrihbeutUednivSeyrsstietymosf Melbourne) 2022 Semester II 15/53
Functional Models Processes and Machines Analysis: load balancing and placement problems II
minimizing the average percentage resource consumption over all machines,
argmin max 1 Lj,r, {P1 ,P2 ,…,Pn } j |{R}| r Cj ,r
or finding a placement that minimizes the number of machines that are required (bin packing problem) to satisfy the total process requirements:
arg min m, {P1 ,P2 ,…,Pn }
where in this case m = max{Pi } and again, the placement is subject to the capacity restriction given earlier. The bin packing problem is strongly NP complete.
(School of Computing and InformaCtiOonMSPy9s0te0m15s ©DistTrihbeutUednivSeyrsstietymosf Melbourne) 2022 Semester II 16/53
Functional Models Processes and Machines Connections between processes
Interprocess communication is an essential aspect of the Architectural Model. We can expand our model to include the notion of IPC by defining communication as a directed edge between two processes i , i ′ ∈ N , which we can write as the tuple (i,i′), and then define the set of all connections:
(i,i′) ∈ En if process i can initiate communication with process i′
To be specific, we can say that if (i,i′) ∈ En then process i can initiate communication with process i′ (i.e. using TCP or UDP) at least once in the lifetime of the distributed system (the model is currently not specifying exactly when or even if it does, just that it could take place). If for two processes a, b ∈ N those processes can never directly communicate in the lifetime of the distributed system then (a, b) ∈/ En and also (b, a) ∈/ En. Sometimes we use undirected edges, written {i,i′} when its not important to consider which process initiates the communication, or when either process could initiate the communication. With this model, {i,i′} ∈ En is equivalent to (i,i′),(i′,i) ∈ En.
(School of Computing and InformaCtiOonMSPy9s0te0m15s ©DistTrihbeutUednivSeyrsstietymosf Melbourne) 2022 Semester II 17/53
Functional Models Common architectural patterns Example process connection patterns
The connection “pattern” or architecture that arises between processes is an essential aspect to model and understand in a distributed system – we are usually especially interested to understand such patterns as the number of processes in the system grows larger, or to the extreme as n → ∞.
(School of Computing and InformaCtiOonMSPy9s0te0m15s ©DistTrihbeutUednivSeyrsstietymosf Melbourne) 2022 Semester II 18/53
Functional Models Common architectural patterns
Centralized Pattern
Client processes communicate with a Server process. Clients never directly communicate with each other. This pattern is the dominant design pattern for distributed systems:
• It is relatively easy to implement.
• All data is kept at the server.
• If the server fails or is attacked, the distributed system fails – single point of
• Since clients never directly communicate, they are not exposed to each over
the network – privacy/security.
• If some clients fail or are attacked, it does not have an impact on other clients.
• A single server may not be able to support a large number of clients –
scalability bottleneck.
• Depending on the geographic/network location of the server to the clients,
different clients may see different performance characteristics – latency may vary among clients.
client server
(School of Computing and InformaCtiOonMSPy9s0te0m15s ©DistTrihbeutUednivSeyrsstietymosf Melbourne) 2022 Semester II 19/53
Decentralized Pattern
Functional Models Common architectural patterns
The decentralized pattern became popular with the rise of peer-to-peer file sharing systems.
• Every peer process can directly communicate with every other peer process.
• Harder to implement than a centralized pattern – processes need to be both clients and servers.
• Data is distributed evenly over the peers.
• The failure of any peer is no worse than the failure of any other peer – the
distributed system is very robust to process failure.
• Since peers are exposed to each other over the network their IP address becomes public – privacy/security.
• Resource capacity increases for the system as a whole for each new peer included in the system – scalability.
(School of Computing and InformaCtiOonMSPy9s
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com