Title: 544
Tags: lec28

Q: What is a weakness of HDFS's approach to partitioning?
A: You need a data structure somewhere that maps logical blocks to physical locations on DataNodes.  If there are many blocks in the system, the structure is large -- in the case of HDFS, it is stored in memory in the NameNode, which is expensive.

Q: What is elasticity?
A: It means you can efficiently scale up/down (for example, adding or removing workers in a cluster).  Being efficient means we can't move the majority of the data over the network each time we gain/lose a worker.

Q: What are the strengths and weaknesses of hash partitioning?
A: Strength: it's highly scalable because anybody can figure out where data goes with a little math: hash(key)%partition_count -- no need to ask a centralized boss.
Weakness: it's not elastic.  hash(key)%partition_count rarely equals hash(key)%(partition_count+1).  This means that if you add a worker, most data in the cluster will need to be shuffled over the network to a different worker.

Q: What are a couple famous systems that use consistent hashing to partition data across workers?
A: Dynamo and Cassandra

Q: In consistent hashing, how are tokens managed for (a) workers and (b) rows?
A: Workers: the system can choose tokens for workers (aka nodes) however it wants.  Some options: randomly, or trying to space tokens evenly.  Given the flexibility in the decision, whatever is decided needs to be remembered -- that is, stored in some data structure.  For Cassandra, that data structure is called the token map.  If there are only a few thousand workers in the cluster (a lot, actually), the token map won't take that much space in RAM.
Rows: we want to handle MANY rows (billions, trillions, ...) in the system, so it's not reasonable to store a map of tokens for every row in a table.  Instead, we take a hash of the row's key.  For Cassandra, the key used is the "partition key".  This means that all rows in the same partition will have the same token.

Q: Why does Cassandra have tokens for vnodes (virtual nodes) instead of just for nodes (the workers in the cluster)?
A: 1. when we add a worker to the cluster, it's better if the new worker can take some work away from a few other nodes.  If we only reassign some work from just one old node, it will take longer to hand off the data, and the cluster will not be as balanced in the end.
2. some workers might have more CPU/RAM/etc.  We can give these stronger nodes more vnodes, which will result in them receiving more work.

Q: Given a Cassandra row's token, how do we select a vnode to be responsible for that token?  Assume single replication.
A: If a vnode has exactly the same token as the row, then that vnode owns the row.  Having an exact match like this is rare.
Otherwise, we move to the right in the token ring, finding the first vnode token that is bigger than the row's token.

Q: What is the "wrapping range" in Cassandra, and how do we handle it?  Assume single replication.
A: This is the range of tokens that are bigger than any vnode token.
Having a row with a token in this range is a special case since we usually "walk the ring" to the right to find a vnode for a row.  We handle this corner case by assigning the row to the vnode with the smallest token in the cluster.

Q: What is "heterogeneity" in a cluster?
A: It means the workers are running on different hardware -- some machines might be more powerful than others (more CPU, RAM, etc.).

Q: Where is the token map stored in Cassandra?
A: We don't have a centralized boss, so every worker in the cluster stores a copy of the token map.

Q: How do we update the token map in Cassandra?  For example, we might need to insert some new vnodes to the token map if a new worker joins the cluster.
A: We can't plan to update all the workers at once (remember, they all have a copy of the token map).  At any given time, there are probably some machines offline (for example, rebooting) if we have a large cluster.
Instead, we update a few workers in the cluster.  All the workers engage in a "gossip" protocol.  Once every second (or N seconds), a worker chooses a peer, and they exchange gossip about any new information their copies of the token map.
As with gossip or epidemics, the information will quickly spread to all the nodes that are alive.  If a node was down or rebooting, it will get the information soon after it comes back online and starts gossiping with its peers.

Q: If a client wants to interact with a Cassandra cluster, how does it start?
A: The client can connect to any worker, which will serve as a coordinator.  Every worker has a copy of the token map, so the coordinator will know what node (or nodes) need to be involved for operations on a given partiton of rows.