midterm review
Chap 1 Intro
what’s a distributed system
- definitions:
- a collection of independent computers that appears to users as a single coherent system
- a collection of autonomous computers linked by a computer network and supported by software that enables the collection to operate as an integrated facility
- crash you never heard of stops you from getting work done
- types:
what do we want from distributed system
resource sharing:
- Quality of Service, trade-offs
transparency: information hiding applied to distributed systems
- hiding different aspects of distribution from clients
- make the system more user friendly
- appears to users and applications as a single computer system
- users/apps should be able to access remote resources the same way they access local resources
- types:
- access: hide differences in data representation and how a resource is accessed
- location: hide where a resource is located
- migration: hide that a resource may move to another location
- relocation: hide that a resource may be moved to another location while in use
- replication: hide that a resource is replicated
- concurrency: hide that a resource may be shared by several competitive users
- failure: hide the failure and recovery of a resource
openness:
- offer services according to standard rules
- In other words, the interfaces to the system are clearly specified and freely available
- formalized in protocols, not proprietary
- definitions are language and machine independent interoperate
- separating policy from mechanism
scalability: able to grow to meet increasing demands
- 3 dimensions of scalability
- size: users/resources
- performance bottlneck: centralized server, data, algorithms
- geographically: topologically
- LAN: synchronous, fast ,reliable
- WAN: asynchronous, slow, unreliable
- administratively: independent organizations/domains
- vertical horizontal
- problems:
- trade-off: scalability, security
- scaling techniques
- caching: proximity, client decision
- replicate: consistency vs scalability
- asynchronous: hiding communication latency
- synchronous
- hierachies, domains, zones split
elements of distributed system
- networks
- hosts
- middleware
architecture styles
describe a particular way to configure a collection of components and connectors
layered
object-based: object + RPC/RMI
event/publish-subscribe:
- publish to event bus => event bus delivers
- asynchronous communciation, decouples senders&receivers
shared data-space:
- publish to shared persistent data space => data space delivers
client/server model:
- user-interface level: GUI
- processing level: core functionality
- data level: interacts with database or file system
- two-tiered:
- thin-client: GUI
- fat-client: user interface + processing + some data
- three-tiered:
- application server acting as a client
- client => middleware => resource management server
various configurations of distributed systems
example distributed systems
Chap 2,3 Communications Foudamentals
packets
- segment = original data + transport layer header
- packet = segment + network layer header
- fram = packet + data link layer header
protocols
- connection-oriented: setup of communication first
- connectionless: no setup of communication
- application-specific vs application-independent
blocking/unblocking communication calls
- blocking: process/thread execution is suspended until transmission finishes
- unblocking: execution continues without waiting for the finish of the transmission
layering
- do I need other intermediators to relay the message?
layered protocols
application layering
communication between processes
middleware and application protocols
- application layer protocols
- between application and transport: middleware
- program and network layer
layered network models
OSI 7-layer model Open System Interconnection
- application: support application-specific needs
- presentation: process information format and deliver(serialize and encrypt)
- session: manage communication sessions among applications
- transport: end-to-end communication for applications
- network: route data packets among senders/receivers
- data link: send, detect and correct data frames(units of bits)
- physical: transfer bits over physical interfaces(fiber optics)
TCP/IP 4-layer
- application: SMTP,HTTP,FTP,Telnet
- transport: UCP,TCP
- network: IP
- link: most network hardware Ethernet/fiber/satellite
Ethernet: local area network
Inter-network Protocols IP
- define datagram as the basic data unit
- define the internet address schema
- routes datagrams to destinations
- divides and assembles datagrams
addressing and routing
- TCP
- Transmission Control Protocol
- data sent via streams of bytes
- UDP
- User Datagram Protocol
- data sent in messages
- communication ports and sockets
multicast : more than one recipient
client/server communication protocols
processing multiple requests
- iterative processing:
receive => process => return result => wait for new - concurrent processing:
receive => ask another to process => wait for new
process => return result - using replicated processes
- using multiple threads
- using message brokers/space repository
communication types
- transient: messages are kept in the communication temporarily only if both the sender and the receiver are live
- persistent: messages are kept in the communciation system until they are delivered to the receiver
- synchronous:
- the sender waits until it knows the messages have been delivered to the receiver
- blocking send/receive
- asynchronous:
- the process continues as soon as sending messages have been copied to the local buffer
- non-blocking send
- callback mechanisms
stateful/stateless server
- keep clients’ state information
Chap 4,5,6,9 Commuications Programming
ports
sockets
- how does an application use the transport layer communciation to send/receive messages? Transport-level socket programming via socket interface
- socket interface: socket APIs
- what is a socket: a communication end point to/from which an application can send/receive data through the underlying network
- message-oriented transient communication at transport level
- client: connect, send, receive
- server: bind, listen/accept, recieve, process, send
binding
- attach a local address to a socket
datagram sockets
UDP User Datagram Protocol
locating resources on the network
network programming: sockets
socket programming with TCP
models for application communications
- RPC, remote procedure call
- asynchronous RPC:
- synchronize at request submission
- synchronize at request delivery
- synchronous RPC:
- synchronize after processed by server
- asynchronous RPC:
- message-oriented communication
- transient socket
- persistent message-queuing
- time uncoupling
- stream-oriented communication
- multicast communication
remote objects and RMI
- distributed/remote objects
- RMI, Remote Method Invocation
web services
- architecture
- REST
- resources are identified and accessed through URIs
- resources are data and functionality
- a web service manages a set of resources
- a client and a service exchange representation of resources via standardized interface and protocols
- cloud computing/ cloud resources: file, storage, compute machine, middleware
stream data programming
- data stream: a sequence of data units
reading bytes from a file and sending bytes via a TCP socket - can be used for:
- continuous media: video
- discrete media: stock market events/twitter events
- timing issues transmission modes
- asynchronous: no contraints of delay(when the transmission completes)
- synchronous: maximum end-to-end delay defined for each data unit
- iochronous: maximum and minimum delay defined
group communication
use multicast messages
- IP multicast
- application-level multicast
- application processes are organized into an overlay network, in mesh or tree
atomic multicast: messages are received either by every memeber or by none of them
reliable multicast: messages are delivered to all members in the best effort, but not guaranteed
gossip based communication
- why? It can spread messages fast and reliably.
- periodically transmit to b random targets
- other nodes do same after receiving multicast
Chap 10 Naming
definitions:
- entity: any kind of object in distributed system:
process, file, printer, host, communication endpoint - naming services:
- usefulness:
- identification
- providing detailed description
- foundations for communication, security, auditing
- usefulness:
- name space:
- contains all valid names recognized and managed by a service
- naming domain:
- name space with a single administrative authority which manages names for the name space
- name resolution:
- a process to look up information/attributes from a name
- mounting:
- a directory node in a remote server can be mounted into a local node
- name: set of bits/characters used to refer to an entity/a collective of entities, in a context
- identifier: a name that uniquely identifies an entity
- address: the name of an access point, the location of an entity
design principles:
- flat naming:
- identifiers have no structured description, just a set of bits
m-bits in distributed hash table
- identifiers have no structured description, just a set of bits
- structured naming:
- hard links: multiple absolute paths names referring to the same node
- symbolic links: leaf node storing an absolute path name
- attribute based naming:
naming services:
- DNS
- distributed naming service
- global layer: com, org, us, edu
- administrational layer: yale.cs.linda
- managerial layer: robot.txt
- iterative/recursive name resolution
- client’s name resolver => name server =>client’s name resolver
- iterative name resolution at resolver side
- iterative name resolution at server side
- recursive name resolution
- administrative zones
- caching servers
- scalabiltiy
- response time
- fault tolerance
- scalabiltiy
- Directory Service(LDAP,RDF)
- LDAP implementation, flow
attributed-based naming
- a tuple(attribute,value) can be used to describe a property
- directory service
- hierachical implementation: LDAP
- decentralized implementations
name and name services
naming space and implementation
flat naming and simple resolutions
structured naming
DNS
Virtualization
definitions
hypervisor
- type 1:
- right on top of computer hardware
- all guest operating systems are a layer above the hypervisor
- type 2: VMware workstation
- run over a host OS
- the second layer over the hardware
- the guest OSs run a layer over the hypervisor(the third layer)
virtual machine
- virtual machine layer, VMM, hypervisor: software that runs in a layer between a hypervisor/host OS and one of more VMs
full vs platform virtualization
- full virtualization native VM
- complete simulation of underlying hardware, all instructions
- hardware architectural support provided to allow virtualziation
- platform virtualization hosted VM
- limited simulation of underlying hardware
- full virtualization native VM
native vs hosted VM
performance/efficiency analysis
- virtual networking
- bridging: guest OS is given direct access to the host’s NIC independent of the host OS
- NAT: guest OS is given a virtual NIC
network traffic => virtual NIC => host OS => physical NIC - Host Only: virtual NIC has no direct route to physical NIC
- virtual IO
- emulation: scalable, low performance
- direct IO: unscalable, high performance
- SRIOV
- solution to 50 VMs but 5 I/O devices
- allow PCIe device to present itself as multiple virtual interfaces
- best performance
- limitation: VF configuration depends on PF configuration, thus can not configure
- trade off
case study
- XEN architecture
- domain 0 for control and I/O
- Amazon AWS/Google
virtual machine
virtual machine architecture
virtual I/O and networking
Chap 13, Peer to Peer System
history Napster
- servers store table: filename, peer pointer(ip address, port number)
- peers store their own files
- all communications use TCP
- problem:
- centralized server: congestion
- centralized server: single point of failure
- security: plaintext messages
distributed hash table
- to insert, lookup and delete objects with keys
- key, object(file)
Chord
- finger table: ft[m] [0,m-1]
- ft[i] = first peer with id >= (n+pow(2,i)) mod pow(2,m)
- file is stored at first peer with id >= file_key mod pow(2,m)
- efficiency analysis: O(log(n)) for insertion and lookup given correct finger table entries
- lookup algorithm, finger table
- local search
- query largest successor/finger table entry <= k
- if none exist, query next successor
- new nodes joining
- stablization algorithm: O(n^2) rounds for strict stablization
- rate of churn per hour: define r(successor and predecessor)
Failure Detection
two different system models
- synchronous distributed system
- asynchronous distributed system
- no bounds on process execution
- no bounds on message transmission delay
- the Internet
failure model
- process omission failure
- crash-stop
- crash-recovery
type of failure detection
- process failure
- arbitrary failure
- arbitrary process failure
- arbitrary channel failure
- communication failure
- send omission
- channel omission
- receive omission
- completeness and accuracy
- completness: no misses
- accuracy: no mistakes
Every detected failure corresponds to a crashed process.
- synchronous and asynchronous model
- measuring accuracy(metrics)
- speed: detection time
- accuracy:
- mistake recurrence time
- mistake duration time
- number of false failure detections per time
- number of undetected failures per time
process failure
pj fails
- ping-ack
pi Ping=> pj, pj Ack=> pi - heartbeat
pj Heartbeat=> pi - satifies completness and accuracy in synchronous systems
- satifies completness and probabilistic accuracy in asynchronous systems
implement heartbeat in a distributed system environment
- want all to know the failure
- combine failure detection with a dissemination protocol
- central, ring, all-to-all
- heartbeat combined reliable multicast protocol