Title: CS544 / 09-cassandra
Tags: cs544-cassandra

Q: What is the open source system most similar to Google's BigTable?
A: HBase

Q: How do HBase and Cassandra handle replication differently for N-times replicated data?
A: A row in HBase will belong to a single RegionServer, but that RegionServer will store that data in a N-times replicated HDFS file.
A row in Cassandra will belong to N different workers, each of which will store it in a single local file system (the local FS does not replicate it).
In other words: HBase replicates at the file system level, Cassandra replicates at the database level.

Q: HBase and BigTable are "versioned sparse tables" -- what does this mean?
A: There is not a fixed number of columns, and different rows can have different columns.  Looking up a cell is more like using a dictionary, something like table["row:column"].
Each cell may also have multiple versions, and if we want a specific one, we can use table["row:column:version"].
If we look at every possible combination of rows/columns in the table, many correspond to cells with no values -- in a normal database, these missing values would be represented as NULL and representing those NULLs would take a little storage/memory space.  In versioned sparse tables, no space is used to represent the missing values (hence "sparse").

Q: What happens to the regions an HBase RegionServer was responsible for if that server dies?
A: All of that dead server's files (which contain region data) should still be safely stored in HDFS, so other healthy RegionServers can be assigned to take over these regions.

Q: What is a Cassandra keyspace, and where is the data it contains stored?
A: A collection of tables.  Every keyspace has data spread across all workers in the cluster.

Q: Why might you want all data for a particular user to live in a single row in an HBase table?
A: A single row will belong to a single RegionServer, meaning requests for that users data will go to one server instead of many.

Q: At what granularity can a user specify the replication factor, in both HDFS and Cassandra?
A: HDFS: the user specifies replication per file
Cassandra: the user specifies replication per keyspace

Q: What is the primary key in a Cassandra table?
A: The combination of the partition key and cluster key.

Q: What about a row determines which Cassandra workers are responsible for that row?
A: The value in the partition key

Q: What determines the sort order of rows within a partition?
A: The values in the cluster key column(s)

Q: For what kinds of columns are the same values shared across many rows of data?
A: Two cases:
1. partition key
2. static column

Q: What are two systems that inspired the design of Cassandra?
A: Dynamo (from Amazon)
BigTable (from Google)
Both these published papers, but not source code.  Facebook designed Cassandra using the ideas in the papers, then open-sourced Cassandra.

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.  We wrap around (from biggest to smallest token) if necessary.

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.

Q: When multiple nodes in a system can be affected by the same fault, we say they are in the same _________
A: fault domain
these nodes are vulnerable to "correlated failure"

Q: What are some examples of "faults", and what does fault tolerance mean?
A: Few examples of faults: disk failure, network down, node dies, rack loses power, data center is destroyed.
Fault tolerance: the system can keep "working" even when certain faults occur.
Fault tolerance can take many forms, because different systems can handle different kinds of faults.  For example, HDFS can handle a DataNode failure, but it is not geographically distributed, so it couldn't handle loss of a whole data center.  Cassandra can be geographically distributed, so it could potentially.  Fault tolerance also varies based on what "working" mean -- for example, some systems might insure durability (your data is not lost), but not availability (so the system might be offline for a while).

Q: Given a token T for a row that is replicated N times, how do you "walk the ring" to find the N nodes necessary?
A: Start on T, and keep increasing it, recording every vnode you match or pass in a replica set.  Stop when the replica set contains N nodes.
Special cases:
1. if you get to the biggest possible token number, wrap around to the smallest
2. if you find a vnode that is in the same "failure domain" as another vnode already found, potentially skip it.  This depends on the policy, which is pluggable.  The simplest policy will just skip vnodes on the same physical node, but more complex policies might also skip nodes that are in the same rack or datacenter.

Q: What does "ack" stand for, and what does it mean in the context of writing data?
A: "ack" is short for "acknowledgement", and receiving an acknowledgement back from a system means our data is "committed" (in other words, "safe" even if certain bad things happen).
Different systems guarantee different levels of safety for committed data.  For example, for one system it might mean the data is in RAM on two workers.  On a system with a stronger guarantee, in contrast, it might mean the data is on disk on three workers.

Q: If you receive an ACK, what does it mean?  If you don't receive an ACK, what does it mean?
A: ACK: the data is definitely committed
No ACK: the data MAY or MAY NOT be committed (perhaps the write works fine, but an issue arose with sending the message back to report that)

Q: Cassandra has RF, W, and R options.  How are these used when reading and writing data?
A: Writing: a coordinator will attempt to write RF copies of the data.  It will report success (ack) if at least W nodes successfully write it.
Reading: a coordinator will attempt to read the data from R nodes.  1 of these will be a full data read, and (R-1) workers will just send back a checksum of the data.

Q: In terms of RF, W, and R: what should you do if you want a stronger durability guarantee when you get an ack?
A: Increase W (RF must be >= W, so RF might need to increase too).

Q: In terms of RF, W, and R: what should you do if you want better write availability?
A: Decrease W -- then our write can be considered successful even if fewer nodes are currently working.

Q: In terms of RF, W, and R: what should you do if you want better read availability?
A: Decrease R: then we can read the data even if fewer nodes are currently working.

Q: In terms of RF, W, and R: what should you do if you want to guarantee that reads will see the last written data?
A: Make sure W+R > RF.
This guarantees the write and read quorums will overlap.  For example, if you have 5 nodes, and two subsets, of size 2 and 4, those two subsets are mathematically guaranteed to have some overlap.

Q: What does eventually consistent mean?
A: It means different versions of the data on different workers can temporarily "diverge" -- this means that neither version 1 or version 2 of a row is strictly "newest".
Perhaps version 1 has the latest data in column A, but version 2 has the latest data in column B.  Eventually, though, the rows should sync up.

Q: In eventually consistent systems, sometimes you do a read, and you get conflicting versions of the data back.  Neither version can be considered strictly better.  What are some approaches to handling this?  What does Cassandra do?
A: Approach 1: Pass all the different versions back to the client doing the reads -- let the client sort it out.
Approach 2: Automatically merge all the versions to get a new version.
Cassandra automatically merges.  It keeps timestamps on every cell, and uses a LWW policy (last writer wins), meaning we compare the versions cell by cell, picking the data with the freshest timestamp in each case.