WARNING:
JavaScript is turned OFF. None of the links on this concept map will
work until it is reactivated.
If you need help turning JavaScript On, click here.
This Concept Map, created with IHMC CmapTools, has information related to: ch15 repl goss, Gossip architecture Gossip update operations Update operations are processed in causal order A FE sends update operation u.op, u.prev, u.id to RM i A FE can send a request to several RMs, using same id When RM i receives an update request, it checks whether it is new, by looking for the id in its executed ops table and its log if it is new, the RM increments by 1 the ith element of its replica timestamp, assigns a unique vector timestamp ts to the update and stores the update in its log logRecord = <i, ts, u.op, u.prev, u.id> The timestamp ts is calculated from u.prev by replacing its ith element by the ith element of the replica timestamp. The RM returns ts to the FE,which merges it with its vector timestamp For stability u.prev ≤ valueTS That is, the valueTS reflects all updates seen by the FE. When stable, the RM applies the operation u.op to the value, updates valueTS and adds u.id to the executed operation table., Vector timestamp held by RM i consists of: ith element holds updates received from FEs by that RM jth element holds updates received by RM j and propagated to RM i Query operations contain q.prev they can be applied if q.prev ≤ valueTS (value timestamp) failing this, the RM can wait for gossip message or initiate them e.g. if valueTS = (2,5,5) and q.prev = (2,4,6) - RM 0 has missed an update from RM 2 Once the query can be applied, the RM returns valueTS (new) to the FE. The FE merges new with its vector timestamp ???? in a gossip system with 3 RMs a value of (2,4,5) at RM 0 means that the value there reflects the first 2 updates accepted from FEs at RM 0, the first 4 at RM 1 and the first 5 at RM 2., Gossip architecture ???? the gossip architecture is a framework for implementing highly available services data is replicated close to the location of clients RMs periodically exchange ‘gossip’ messages containing updates gossip service provides two types of operations queries - read only operations updates - modify (but do not read) the state FE sends queries and updates to any chosen RM one that is available and gives reasonable response times Two guarantees (even if RMs are temporarily unable to communicate each client gets a consistent service over time ( i.e. data reflects the updates seen by client, even if they use different RMs). Vector timestamps are used – with one entry per RM. relaxed consistency between replicas. All RMs eventually receive all updates. RMs use ordering guarantees to suit the needs of the application (generally causal ordering). Client may observe stale data., Gossip architecture Processing of query and update operations Vector timestamp held by RM i consists of: ith element holds updates received from FEs by that RM jth element holds updates received by RM j and propagated to RM i Query operations contain q.prev they can be applied if q.prev ≤ valueTS (value timestamp) failing this, the RM can wait for gossip message or initiate them e.g. if valueTS = (2,5,5) and q.prev = (2,4,6) - RM 0 has missed an update from RM 2 Once the query can be applied, the RM returns valueTS (new) to the FE. The FE merges new with its vector timestamp, Gossip architecture Gossip processing of queries and updates The five phases in performing a client request are: request FEs normally use the same RM and may be blocked on queries update operations return to the client as soon as the operation is passed to the FE update response - the RM replies as soon as it has seen the update coordination the RM waits to apply the request until the ordering constraints apply. this may involve receiving updates from other RMs in gossip messages execution - the RM executes the request query response - if the request is a query the RM now replies: agreement RMs update one another by exchanging gossip messages (lazily) e.g. when several updates have been collected or when an RM discovers it is missing an update, Update operations are processed in causal order A FE sends update operation u.op, u.prev, u.id to RM i A FE can send a request to several RMs, using same id When RM i receives an update request, it checks whether it is new, by looking for the id in its executed ops table and its log if it is new, the RM increments by 1 the ith element of its replica timestamp, assigns a unique vector timestamp ts to the update and stores the update in its log logRecord = <i, ts, u.op, u.prev, u.id> The timestamp ts is calculated from u.prev by replacing its ith element by the ith element of the replica timestamp. The RM returns ts to the FE,which merges it with its vector timestamp For stability u.prev ≤ valueTS That is, the valueTS reflects all updates seen by the FE. When stable, the RM applies the operation u.op to the value, updates valueTS and adds u.id to the executed operation table. Gossip messages an RM uses entries in its timestamp table to estimate which updates another RM has not yet received The timestamp table contains a vector timestamp for each other replica, collected from gossip messages gossip message, m contains log m.log and replica timestamp m.ts an RM receiving gossip message m has the following main tasks merge the arriving log with its own (omit those with ts ≤ replicaTS) apply in causal order updates that are new and have become stable remove redundant entries from the log and executed operation table when it is known that they have been applied by all RMs merge its replica timestamp with m.ts, so that it corresponds to the additions in the log, The five phases in performing a client request are: request FEs normally use the same RM and may be blocked on queries update operations return to the client as soon as the operation is passed to the FE update response - the RM replies as soon as it has seen the update coordination the RM waits to apply the request until the ordering constraints apply. this may involve receiving updates from other RMs in gossip messages execution - the RM executes the request query response - if the request is a query the RM now replies: agreement RMs update one another by exchanging gossip messages (lazily) e.g. when several updates have been collected or when an RM discovers it is missing an update ???? the gossip architecture is designed to provide a highly available service clients with access to a single RM can work when other RMs are inaccessible but it is not suitable for data such as bank accounts it is inappropriate for updating replicas in real time (e.g. a conference) scalability as the number of RMs grow, so does the number of gossip messages for R RMs, the number of messages per request (2 for the request and the rest for gossip) = 2 + (R-1)/G G is the number of updates per gossip message increase G and improve number of gossip messages, but make latency worse for applications where queries are more frequent than updates, use some read-only replicas, which are updated only by gossip messages