0%

COEN317_midterm

midterm review

Chap 1 Intro

what’s a distributed system

  • definitions:
    1. a collection of independent computers that appears to users as a single coherent system
    2. a collection of autonomous computers linked by a computer network and supported by software that enables the collection to operate as an integrated facility
    3. crash you never heard of stops you from getting work done
  • types:

what do we want from distributed system

  • resource sharing:

    1. Quality of Service, trade-offs
  • transparency: information hiding applied to distributed systems

    1. hiding different aspects of distribution from clients
    2. make the system more user friendly
    3. appears to users and applications as a single computer system
    4. users/apps should be able to access remote resources the same way they access local resources
    • types:
      1. access: hide differences in data representation and how a resource is accessed
      2. location: hide where a resource is located
      3. migration: hide that a resource may move to another location
      4. relocation: hide that a resource may be moved to another location while in use
      5. replication: hide that a resource is replicated
      6. concurrency: hide that a resource may be shared by several competitive users
      7. 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

    1. 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
    1. vertical horizontal
    2. problems:
    • trade-off: scalability, security
    1. 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:
      1. synchronize at request submission
      2. synchronize at request delivery
    • synchronous RPC:
      1. synchronize after processed by server
  • 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
    1. resources are identified and accessed through URIs
    2. resources are data and functionality
    3. a web service manages a set of resources
    4. 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:
    1. continuous media: video
    2. discrete media: stock market events/twitter events
  • timing issues transmission modes
    1. asynchronous: no contraints of delay(when the transmission completes)
    2. synchronous: maximum end-to-end delay defined for each data unit
    3. iochronous: maximum and minimum delay defined

group communication

  • use multicast messages

    1. IP multicast
    2. 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
  • 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
  • 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
  • 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

    1. type 1:
    • right on top of computer hardware
    • all guest operating systems are a layer above the hypervisor
    1. 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

    1. full virtualization native VM
      • complete simulation of underlying hardware, all instructions
      • hardware architectural support provided to allow virtualziation
    2. platform virtualization hosted VM
      • limited simulation of underlying hardware
  • 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:
    1. centralized server: congestion
    2. centralized server: single point of failure
    3. 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:
      1. mistake recurrence time
      2. mistake duration time
      3. number of false failure detections per time
      4. 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