How does cassandra find the node that contains the data?

Question

I've read quite a few articles and a lot of question/answers on SO about Cassandra but I still can't figure out how Cassandra decides which node(s) to go to when it's reading the data.

First, some assumptions about an imaginary cluster:

1. Replication Strategy = simple
2. Using Random Partitioner
3. Cluster of 10 nodes
4. Replication Factor of 5

Here's my understanding of how writes work based on various Datastax articles and other blog posts I've read:

• Client sends the data to a random node
• The "random" node is decided based on the MD5 hash of the primary key.

• Data is written to the commit_log and memtable and then propagated 4 times (with RF = 5).

• The 4 next nodes in the ring are then selected and data is persisted in them.

So far, so good.

Now the question is, when the client sends a read request (say with CL = 3) to the cluster, how does Cassandra know which nodes (5 out of 10 as the worst case scenario) it needs to contact to get this data? Surely it's not going to all 10 nodes as that would be inefficient.

Am I correct in assuming that Cassandra will again, do an MD5 hash of the primary key (of the request) and choose the node according to that and then walks the ring?

Also, how does the network topology case work? if I have multiple data centers, how does Cassandra know which nodes in each DC/Rack contain the data? From what I understand, only the first node is obvious (since the hash of the primary key has resulted in that node explicitly).

Sorry if the question is not very clear and please add a comment if you need more details about my question.

Many thanks,

Bonsai

Answer 1

Client sends the data to a random node

It might seem that way, but there is actually a non-random way that your driver picks a node to talk to. This node is called a "coordinator node" and is typically chosen based-on having the least (closest) "network distance." Client requests can really be sent to any node, and at first they will be sent to the nodes which your driver knows about. But once it connects and understands the topology of your cluster, it may change to a "closer" coordinator.

The nodes in your cluster exchange topology information with each other using the Gossip Protocol. The gossiper runs every second, and ensures that all nodes are kept current with data from whichever Snitch you have configured. The snitch keeps track of which data centers and racks each node belongs to.

In this way, the coordinator node also has data about which nodes are responsible for each token range. You can see this information by running a nodetool ring from the command line. Although if you are using vnodes, that will be trickier to ascertain, as data on all 256 (default) virtual nodes will quickly flash by on the screen.

So let's say that I have a table that I'm using to keep track of ship crew members by their first name, and let's assume that I want to look-up Malcolm Reynolds. Running this query:

SELECT token(firstname),firstname, id, lastname 
FROM usersbyfirstname  WHERE firstname='Mal';

...returns this row:

 token(firstname)     | firstname | id | lastname
----------------------+-----------+----+-----------
  4016264465811926804 |       Mal |  2 |  Reynolds

By running a nodetool ring I can see which node is responsible for this token:

192.168.1.22  rack1       Up     Normal  348.31 KB   3976595151390728557                         
192.168.1.22  rack1       Up     Normal  348.31 KB   4142666302960897745                         

Or even easier, I can use nodetool getendpoints to see this data:

$ nodetool getendpoints stackoverflow usersbyfirstname Mal
Picked up JAVA_TOOL_OPTIONS: -javaagent:/usr/share/java/jayatanaag.jar 
192.168.1.22

For more information, check out some of the items linked above, or try running nodetool gossipinfo.

Varicose

Does this mean each Cassandra node keeps a list of all token-range-to-node mappings? Just to clarify, if I have 10,000 nodes and each has 256 tokens, then each node needs to remember 10,000*256 different assignments? Where is this information stored? – Gang

@JaySullivan yes, check out the system.peers table. – Varicose

Answer 2

Cassandra uses consistent hashing to map each partition key to a token value. Each node owns ranges of token values as its primary range, so that every possible hash value will map to one node. Extra replicas are then kept in a systematic way (such as the next node in the ring) and stored in the nodes as their secondary range.

Every node in the cluster knows the topology of the entire cluster, such as which nodes are in which data center, where they are in the ring, and which token ranges each nodes owns. The nodes get and maintain this information using the gossip protocol.

When a read request comes in, the node contacted becomes the coordinator for the read. It will calculate which nodes have replicas for the requested partition, and then pick the required number of nodes to meet the consistency level. It will then send requests to those nodes and wait for their responses and merge the results based on the column timestamps before sending the result back to the client.

Nonu

Answer 3

Cassandra will locate any data based on a partition key that is mapped to a token value by the partitioner. Tokens are part of a finite token ring value range where each part of the ring is owned by a node in the cluster. The node owning the range of a certain token is said to be the primary for that token. Replicas will be selected by the data replication strategy. Basically this works by going clockwise in the token ring, starting from the primary, and stopping depending on the number of required replicas.

What's important to realize is that each node in the cluster is able to identify the nodes responsible for a certain key based on the logic described above. Whenever a value is written to the cluster, the node accepting the request (the coordinator node) will know right away the nodes that need to execute the write.

In case of multiple data-centers, all keys will be mapped across all DCs to the exact same token determined by the partitioner. Cassandra will try to write to each DC and each DC's replicas.

Pericynthion