Distributed Systems Flashcards
What is a distributed system?
A collection of independent and dynamic components, including hardware, software components and web services which work together and appear to users as a single coherent system. They help us to share resources of components through communication.
What is middleware?
Software technology that enables distributed system components to work together and communicate as if they were virtually non-distributed. It hides DS developers from low-level networking details, and provides abstraction and infrastructure for constructing distributed applications.
What is a remote procedure call?
Where we adopt the traditional paradigm of splitting a system into procedures, and mask remote function calls as being local instead. This is usually implemented with message passing. The programmer executes a remote function without coding the network communication; uses C.
How does RPC work?
The caller sends arguments to the client-side stub, which marshals them, generates ID, starts timer, sends message to server-side stub, which unmarshals and feeds the arguments to the remote function.
Limitations of RPC
Synchronous request/reply interaction means that client may be clocked for a long time if server is overloaded, and slow clients may delay servers. Host information is required, which means location transparency cannot be facilitated. It’s also not object oriented.
Components of RPC
Server: defines the service interface using an interface definition language, which specifies names, parameters, and types for all client-callable procedures
Stub compiler: reads the IDL declarations and produces two stub functions, one server-side and the other client-side
Linking: server programmer implements the service’s functions and links with the server-side stubs, client programmer implements the client program and links it with client-side stubs
What is Object Oriented Middleware?
Remote objects are visible through remote interfaces, RMI masks remote objects as being local using proxy objects, skeleton object directs incoming calls from clients to the appropriate object. The object request broker identifies / discovers remote objects.
Remote Method Invocation
RMI originated from Java to allow object-to-object communication among Java objects for realizing a distributed system. RMI allows us to distribute our objects on various machines and invoke methods on the objects located on remote sites.
What is a registry
A registry is a running process on a host machine, which maintains names of remote objects and helps with looking up those objects. Servers can register their objects, clients can find server objects by name and obtain stubs for them.
What is message-oriented middleware?
Communication is done using messages, which are stored in message queues. Message servers decouple client and server.
Asynchronous interaction, meaning client and server are only loosely coupled compared to RMI and COBRA. Messages are queued and may be processed/filtered/transformed by the message server. The queues are also in persistent storage, and may be processed by intermediate message servers
Properties of OOM
Follows object-oriented programming model, synchronous request/reply interaction, location transparency (the ability to access objects without the knowledge of their location)
What are web services?
Web services provide a service interface enabling users to communicate with its servers through the internet. The service interface describes operations of web services. They use web-based protocols based on HTTP, designed to work over the public internet. This allows these protocols to traverse firewalls and work in a heterogeneous environment. They count as a middleware technology.
What is WSDL
Web Services Description Language: interface description for web services, also has details of communication method and URL
What is replication and what are the two different types?
Replication provides multiple copies of the same data or functionalities (services) in a distributed system. It improves system capabilities in terms of performance, availability and load distribution.
Computation (service) replication: multiple instances of the same functional process are executed, but may run on different hardware and be implemented by different algorithms.
Data replication: same piece of information is being stored on multiple devices.
How are incoming requests received when we have replication?
The front-end received the request, forwards it to replica servers
Rs accept a request and decide the ordering of a request relative to other requests
They process the request
They reach consensus on the effect of the requests
They reply to the front end, optionally processing the response beforehand
Fault-tolerant services
Provide a correct service despite up to N process failures
Each replica is assumed to behave according to the specification of the distributed system, when they have not crashed
When is a service based on replication correct?
If it keeps responding despite failures (failure transparency), and if clients can’t tell the difference between the service they obtain from an implementation with replicated data and one provided by a single correct replica manager.
How are incoming requests received when we have passive replication?
Request: a FE issues the request, containing a unique identifier, to the primary R
The primary processes each request atomically in the order in which they were received
It checks the unique ID, and resends the response if it has already done that request
The primary executes the request and stores the response
If the request is an update, the primary sends the updated state, the response, and the unique identifier to all the backups, which then send an acknowledgement
Response: the primary responds to the FE
Advantages of passive replication?
This type of system can survive up to n replica crashes, when the system comprises of n+1 replicas. It requires very little front-end functionality, only needing to lookup new primary replica when the current one is not available.
What is active replication?
Where the Rs are all state machines playing the same role, organised as a group. They all start in the same state and perform the same task in the same order so that their state remains identical (synchronisation).
How are incoming requests managed when we have active replication?
- Request: a FE attaches a unique ID and uses totally ordered reliable multicast to send requests to Rs. At worst, FE crashes but never sends requests in parallel.
- Coordination: the multicast delivers requests to all the Rs in the same order
- Every R executes the request, and the ID is put in the response
- No agreement is requird because they all execute the same operations in the same order
- The FEs collect responses from Rs. If the FE is only trying to tolerate crash failures, it just gives the client the first response
What is a Byzantine fault?
An arbitrary fault that occurs during the execution of an algorithm when multiple servers are involved to produce results based on the same client request. It’s when inconsistent results are obtained from the servers because of omission failures (crashes, failing to receive/send stuff) or commission failures (processing a request incorrectly, corrupting local state, sending an incorrect response).
How does active replication mask Byzantine failures?
The system can mask up to n Byzantine failures if the system incorporates at least 2n+1 replicas. This is because the front end waits until it has collected n+1 identical responses and then passes that response back to the client, ignoring the others.
Read-only requests and active replication
If there’s a read-only request, then the front end might only send it to one replica. We lose fault tolerance, but remain sequentially consistent and can easily mask replica failure by just passing the read-only request to another replica.
What are deadlocks?
When two transactions are both stuck waiting for each other to give up the lock on an item
Why is centralised deadlock detection a bad idea?
It depends on a single server, suffering from poor availability, lack of fault tolerance and no ability to scale. If the global graph is collected less frequently, deadlocks may take longer to be detected. There are also phantom deadlocks, which are detected but aren’t really deadlocks. The global deadlock detector requires time to receive local wait-for graphs for constructing the global one.
What is edge chasing?
Where each server involved attempts to find cycles in the wait-for graph by forwarding messages called probes. A probe message consists of transaction wait-for relationships representing a local path in the global wait-for graph.
What does it mean if operations are linearisable in distributed systems?
The interleaved sequence of operations meets the specification of a (single) correct copy of the objects.
The order of operations in the interleaving is consistent with the real times at which the operations occurred in the actual execution.
Modeling of consistency control
An object is coherent if the value returned by a read operation is always the value that the user expected
The consistency model defines rules for the apparent order and visibility of updates, and it is a continuum with trade-offs
What is strict consistency?
The strongest consistency model, where any read on a data item X returns a value corresponding to the result of the most recent write on X. This requires an absolute global time and practically can only be implemented within one single machine.
What is sequential consistency?
For any transaction, there is some interleaving of the series of operations that satisfies these criteria:
- The interleaved sequence of operations meets the specification of a (single) correct copy of the objects
- The order of operations in the interleaving is consistent with the program order in which each individual process executed them. For each process, the interleaving of operations has the same order for the process’ operations as in the process description.
MEETS SPEC, RIGHT ORDER
No reference to most recent time, absolute global time does not play a role
When is an execution of operations sequentially consistent?
It can be rearranged into a sequence that respects the order of each process, and each read operation returns the value of the last preceding write operation over the same variable.
If one process has R(x)b and R(x)a, and the other has R(x)a and R(x)b then it’s not sequentially consistent
Causal Consistency
If event B is caused or influenced by an earlier event A, causality requires that everyone first see A and then B
Concurrent: operations that are not causally related. If W(x)b comes before W(x)c and there is no intervening read operation, then we’re allowed to have:
R(x)c R(x)b
R(x)b R(X)c
Time redundancy for fault tolerance
Perform same operation multiple times
Detects temporary faults but not permanent ones, also impacts system performance
Component redundancy
Introduce two or more independent running components which provide the same functionalities
N-version programming implements multiple versions of the program
Information redundancy
Encode outputs with error detecting or correcting code (e.g. parity check, checksum)
Less hardware required than replicating module, supports fault detection
Added complexity, limited fault recovery
Backward and forward recovery
Backward recovery: move the system back to a failure-free state
Forward recovery: find a new state from which the system can continue operation
Checkpointing for backward recovery
Each DS component periodically saves its state, which contains sufficient information to restart component execution. Global checkpoints are when every component makes a local checkpoint. The most recent one is called the recovery line.
Types of Checkpointing
Uncoordinated checkpointing
Each process takes its checkpoints independently
Coordinated checkpointing
Process coordinate process checkpoints in order to save a system-wide (global) consistent state, avoids domino effect
Communication-induced checkpointing
Force each process to take checkpoints based on information piggybacked on the application messages it receives from other processes (add forced checkpoints -> recovery line)
Domino effect
Cascaded rollback which causes the system to roll back too far
Implementing forward recovery
Switch from a failed to a non-failed component executing the same task-code
Error compensation is continuously applied,e.g., Voting schemes (address Byzantine fault)
Simulate application response (e.g. in online gaming)
Measuring reliability and availability
Reliability: mean time between failures
Availability: percentage of time it’s ready to use
A = MTBF/(MTBF+MTTR)
MTTR = mean time to repair
Load balancing with JSQ
Joining the server with the shortest queue. This has a high implementation cost for large systems like datacenters.
Power-of-d algorithm
The algorithm chooses d out of N servers, and route the job to the least loaded one
Join-idle-queue algorithm
Servers can inform the front-end or loadbalancer when they have no jobs (become idle). Then loadbalancer can send an incoming job to one of these idle servers.
Estimating the load
Queue length of waiting tasks
CPU and CPU utilisation
Storage read/write bandwidth utilisation
Network bandwidth utilisation
Application dependent factors
This information is collected centrally
Layer 4 routing vs Layer 7 routing
4: Server selection is purely based on information from the IP header
7: Examine a request at the application level and select a server accordingly.
Types of load distribution algorithm
Static: decisions are hard-coded into algorithm, requires a priori knowledge of system
Dynamic: make decision during runtime based off system states
Adaptive: enhance dynamic approach by allowing a choice of decision algorithms and the frequency of collecting load information
Transfer and selection policies
Transfer policy: decides whether a server needs to transfer tasks
Selection policy: determines which tasks to transfer
Location and information policies
Location policy: Decides which receiving server for transferring a task
Information policy: decides which information to collect. Demand-driven: server collects state of other servers when it becomes sender/receiver, or periodic
Problems with sender-initiated algorithm
Can become unstable at high loads, hard to find receivers, increased polling activity may make the system more unstable
