You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by "Kenneth Brotman (JIRA)" <ji...@apache.org> on 2018/03/01 12:57:00 UTC

[jira] [Comment Edited] (CASSANDRA-14267) The Dynamo web page on the Apache Cassandra site is missing content

    [ https://issues.apache.org/jira/browse/CASSANDRA-14267?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16381947#comment-16381947 ] 

Kenneth Brotman edited comment on CASSANDRA-14267 at 3/1/18 12:56 PM:
----------------------------------------------------------------------

From the Dynamo paper itself: [https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf]

 4.8 Membership and Failure Detection 4.8.1 Ring Membership In Amazon’s environment node outages (due to failures and maintenance tasks) are often transient but may last for extended intervals.  A node outage rarely signifies a permanent departure and therefore should not result in rebalancing of the partition assignment or repair of the unreachable replicas.  Similarly, manual error could result in the unintentional startup of new Dynamo nodes.   For these reasons, it was deemed appropriate to use an explicit mechanism to initiate the addition and removal of nodes from a Dynamo ring. An administrator uses a command line tool or a browser to connect to a Dynamo node and issue a membership change to join a node to a ring or remove a node from a ring.  The node that serves the request writes the membership change and its time of issue to persistent store. The membership changes form a history because nodes can be removed and added back multiple times. A gossip-based protocol propagates membership changes and maintains an eventually consistent view of membership. Each node contacts a peer chosen at random every second and the two nodes efficiently reconcile their persisted membership change histories.   When a node starts for the first time, it chooses its set of tokens (virtual nodes in the consistent hash space) and maps nodes to their respective token sets. The mapping is persisted on disk and 
202 212
initially contains only the local node and token set.  The mappings stored at different Dynamo nodes are reconciled during the same communication exchange that reconciles the membership change histories. Therefore, partitioning and placement information also propagates via the gossip-based protocol and each storage node is aware of the token ranges handled by its peers. This allows each node to forward a key’s read/write operations to the right set of nodes directly.  4.8.2 External Discovery The mechanism described above could temporarily result in a logically partitioned Dynamo ring.  For example, the administrator could contact node A to join A to the ring, then contact node B to join B to the ring. In this scenario, nodes A and B would each consider itself a member of the ring, yet neither would be immediately aware of the other.  To prevent logical partitions, some Dynamo nodes play the role of seeds.  Seeds are nodes that are discovered via an external mechanism and are known to all nodes.  Because all nodes eventually reconcile their membership with a seed, logical partitions are highly unlikely.  Seeds can be obtained either from static configuration or from a configuration service. Typically seeds are fully functional nodes in the Dynamo ring. 4.8.3 Failure Detection Failure detection in Dynamo is used to avoid attempts to communicate with unreachable peers during get() and put() operations and when transferring partitions and hinted replicas.  For the purpose of avoiding failed attempts at communication, a purely local notion of failure detection is entirely sufficient: node A may consider node B failed if node B does not respond to node A’s messages (even if B is responsive to node C's messages).  In the presence of a steady rate of client requests generating internode communication in the Dynamo ring, a node A quickly discovers that a node B is unresponsive when B fails to respond to a message; Node A then uses alternate nodes to service requests that map to B's partitions; A periodically retries B to check for the latter's recovery.  In the absence of client requests to drive traffic between two nodes, neither node really needs to know whether the other is reachable and responsive. Decentralized failure detection protocols use a simple gossip-style protocol that enable each node in the system to learn about the arrival (or departure) of other nodes. For detailed information on decentralized failure detectors and the parameters affecting their accuracy, the interested reader is referred to [8]. Early designs of Dynamo used a decentralized failure detector to maintain a globally consistent view of failure state.  Later it was determined that the explicit node join and leave methods obviates the need for a global view of failure state. This is because nodes are notified of permanent node additions and removals by the explicit node join and leave methods and temporary node failures are detected by the individual nodes when they fail to communicate with others (while forwarding requests).  4.9 Adding/Removing Storage Nodes When a new node (say X) is added into the system, it gets assigned a number of tokens that are randomly scattered on the ring. For every key range that is assigned to node X, there may be a number of nodes (less than or equal to N) that are currently in charge of handling keys that fall within its token range. Due to the allocation of key ranges to X, some existing nodes no longer have to some of their keys and these nodes transfer those keys to X. Let 
us consider a simple bootstrapping scenario where node X is added to the ring shown in Figure 2 between A and B. When X is added to the system, it is in charge of storing keys in the ranges (F, G], (G, A] and (A, X]. As a consequence, nodes B, C and D no longer have to store the keys in these respective ranges. Therefore, nodes B, C, and D will offer to and upon confirmation from X transfer the appropriate set of keys.  When a node is removed from the system, the reallocation of keys happens in a reverse process.   Operational experience has shown that this approach distributes the load of key distribution uniformly across the storage nodes, which is important to meet the latency requirements and to ensure fast bootstrapping. Finally, by adding a confirmation round between the source and the destination, it is made sure that the destination node does not receive any duplicate transfers for a given key range.  5


was (Author: kenbrotman):
From the Dynamo paper itself: [https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf]

 

> The Dynamo web page on the Apache Cassandra site is missing content
> -------------------------------------------------------------------
>
>                 Key: CASSANDRA-14267
>                 URL: https://issues.apache.org/jira/browse/CASSANDRA-14267
>             Project: Cassandra
>          Issue Type: Improvement
>          Components: Documentation and Website
>            Reporter: Kenneth Brotman
>            Priority: Major
>
> Content for the following topics is needed for [http://cassandra.apache.org/doc/latest/architecture/dynamo.html]
> Gossip
> Failure Detection
> Token Ring/Ranges
>  
> Please post content.  Myself or someone else will take it from there.
>  



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@cassandra.apache.org
For additional commands, e-mail: commits-help@cassandra.apache.org