Saturday, January 2, 2016

Update Propagation in Distributed System

Update Propagation

  • A comparison between push-based and pull-based protocols in the case of multiple client, single server system


Epidemic Protocols

  • Update propagation for systems that only need eventual consistency
  • Randomized approaches based on the theory of epidemics
    • Infective, susceptible and removed servers
  • Anti-entropy propagation model
    • A server P picks another server Q at random, and exchanges updates
    • Three approaches
      • P only pushes updates to Q
      • P only pulls new updates from Q
      • P and Q send updates to each other
    • If many infective servers, pull-based approach is better
    • If only one infective server, eitehr approach will eventually propagate all updates
    • Rumor spreading (Gossiping) will speed up propagation
      • If server P has been updated, it randomly contacts Q and tries to push the update to Q, if Q was already updated by another server, with some probability (1/k), P loses interest in spreading the update any further

The Gossip System

  • Guarantees
    • Each client obtains a consistent service over time
      • i.e., replica managers only provide a client with data that reflect the updates the client has observed so far
    • Relaxed consistency between replicas
      • Primarily causal consistency, but support also provided for sequential consistency
      • Choice up to the application designer
  • Procedure
    • Request
      • Front Ends sends a query or update request to a replica manager that is reachable
    • Update Response
      • RM replies as soon as it receives updates
    • Coordination
      • RM does not process the request until it can meet the required ordering constraints
        • This may involve receiving updates from other replica managers in gossip messages
    • Execution
    • Query Response
      • If the request is a query, the RM replies at this point
    • Agreement
      • The replica managers update each other by exchanging gossip messages, which contains the most recent updates they have received
      • This is one in lazy fashion
  • Query and update operations in a gossip service

  • Front ends propagate their timestamps whenever clients communicate directly

  • A gossip replica manager, showing its main state components





Bayou: Eventual Consistency

  • If no updates take place for a long time, all replicas will gradually become consistent
  • Domain specific conflict detection and resolution
    • Appropriate for applications like shared calendars

Motivation for eventual consistency

  • Sequential consistency requires that at every point, every replica has a value that could be the result of the global-agreed sequential application of writes
  • This does not require that all replicas agree at all times, just that they always take on the same sequence of value
  • Writes
    • When they arrive, are applied in the same order at all replicas
    • Easily done with timestamps

Conflict Resolution

  • Dealing with inconsistency
    • Every Bayou update contains a dependency check and a merger procedure in addition to the operation's specification
  • Replication not transparent to application
    • Only the application knows how to resolve conflicts
  • Split of responsibility
    • Replication system
      • Propagate updates
    • Application
      • resolve conflicts
    • Optimistic application of writes require that writes be "undoable"

Rolling Back Updates

  • Keep log of updates
  • Order by timestamp
  • When  a new update comes in, place it in the correct order and repapply log of updates
  • Need to establish when you can truncate the log
  • Requires old updates to be "committed", new ones tentative
  • Committed order can be achieved by designing a replica manager as the primary replica manager



No comments:

Post a Comment