2006. I never worked on Ceph myself, but I did work with a lot of Ceph folks. As far as I can tell, this particular idea was the little seed from which the rest of Ceph as we know it eventually grew, and the thing that most distinguishes it from other similar efforts.
Only very loosely. They are both techniques for managing data in distributed systems, and they both involve hashing identifiers, but that's pretty much where the similarities stop.
Kademlia is a protocol for locating individual key-value pairs in a big, loosely-connected network of independent nodes. The assumption is that you have very little control over which nodes are interested in storing what data, or how they're connected, or whether some of them are malicious. The idea is to make it so that if the information you're looking for is somewhere in the network, you have a high probability of being able to track it down using a reasonably small number of hops -- but there are few hard guarantees.
CRUSH, on the other hand, is a system for controlling the placement of data objects. The idea is that rather than defining a way to ask other nodes for the location of the data you want, you simply consult a policy that deterministically maps the object's name to its storage location. Since all of the nodes are part of the same cluster, they all agree to obey the policy. The policy format -- the "CRUSH mapping" -- is designed to be reasonably flexible (allowing things like placing specific numbers of replicas in different datacenters), fast to evaluate, and efficient in terms of how much data needs to be moved when the policy changes (e.g. when the cluster is expanded and new nodes are added to the list).
Great answer. Thank you. I considered trying to answer myself, but (a) I was too lazy and (b) it wouldn't have been as good as your answer anyway. To make amends, here are two additional points about the relationship between the two.
(1) One of the statements in the CRUSH paper introduction is flat-out false. Specifically, it says that "RUSH [a predecessor] remains the only existing set of algorithms in the literature that utilizes a mapping function in place of explicit metadata" etc. By 2006, other approaches - including Kademlia, but more commonly circular consistent hashing - were extremely well known. Just as Ceph itself grew from this paper, so did the tendency to make exaggerated claims on its behalf (e.g. "it's a filesystem" years before that was actually true).
(2) One of the key problems with any "deterministic placement" approach like CRUSH, which relies on clients later duplicating the process by which data had been placed, is what to do when the map changes. Section 3.3 addresses this in terms of how much data has to move, but that process is hardly instantaneous. What to do in the interim? And how does the new map get propagated? These issues are not addressed in the paper, which is fine given its mathematical focus, but anyone who hopes to build an actual system based on an algorithm like this needs to think through the answers, and those answers have a large effect on how well the system really works.
> One of the statements in the CRUSH paper introduction is flat-out false. Specifically, it says that "RUSH [a predecessor] remains the only existing set of algorithms in the literature that utilizes a mapping function in place of explicit metadata" etc.
Looking at the rest of the sentence: " ... that utilizes a mapping function in place of explicit metadata and supports the efficient addition and removal of weighted devices.", I feel like calling the statement is "flat-out false" is incorrect.
Those other well known methods also support efficient addition and removal. Supporting weighted devices is a tweak that should be obvious to any competent engineer, which I know because I've done it myself in a similar system. The paper might reasonably claim their way is better, but to represent it as a qualitative change granting never-before-seen capabilities is to misrepresent the state of the art at the time. The only comparison where that works is to Lustre's "MDS controls all" approach, which most people working in the field at the time (but apparently not the buffoons working on HDFS) already knew was bad.
This has not been the case with configurations optimized for high utilization or random writes for a very long time.
The auto-balancing behavior of recent versions approaches something that you can raise the max full parameters on with no additional tuning.
In the past it's been possible to utilize a relatively large number of placement groups (for which the performance penalty insinuated in the documentation seems to be greatly exaggerated, and the complications resulting from using too few greatly understated) to approach and exceed 95% utilization even with heterogeneous OSDs. It is also possible to achieve very high utilization via manual tuning of host and osd weights.
If you care about random write performance and are not using Optane or NVRAM journals, then you are doing it wrong.
12 comments
[ 0.22 ms ] story [ 31.3 ms ] threadSeems seems to solve a similar problem?
Kademlia is a protocol for locating individual key-value pairs in a big, loosely-connected network of independent nodes. The assumption is that you have very little control over which nodes are interested in storing what data, or how they're connected, or whether some of them are malicious. The idea is to make it so that if the information you're looking for is somewhere in the network, you have a high probability of being able to track it down using a reasonably small number of hops -- but there are few hard guarantees.
CRUSH, on the other hand, is a system for controlling the placement of data objects. The idea is that rather than defining a way to ask other nodes for the location of the data you want, you simply consult a policy that deterministically maps the object's name to its storage location. Since all of the nodes are part of the same cluster, they all agree to obey the policy. The policy format -- the "CRUSH mapping" -- is designed to be reasonably flexible (allowing things like placing specific numbers of replicas in different datacenters), fast to evaluate, and efficient in terms of how much data needs to be moved when the policy changes (e.g. when the cluster is expanded and new nodes are added to the list).
(1) One of the statements in the CRUSH paper introduction is flat-out false. Specifically, it says that "RUSH [a predecessor] remains the only existing set of algorithms in the literature that utilizes a mapping function in place of explicit metadata" etc. By 2006, other approaches - including Kademlia, but more commonly circular consistent hashing - were extremely well known. Just as Ceph itself grew from this paper, so did the tendency to make exaggerated claims on its behalf (e.g. "it's a filesystem" years before that was actually true).
(2) One of the key problems with any "deterministic placement" approach like CRUSH, which relies on clients later duplicating the process by which data had been placed, is what to do when the map changes. Section 3.3 addresses this in terms of how much data has to move, but that process is hardly instantaneous. What to do in the interim? And how does the new map get propagated? These issues are not addressed in the paper, which is fine given its mathematical focus, but anyone who hopes to build an actual system based on an algorithm like this needs to think through the answers, and those answers have a large effect on how well the system really works.
Looking at the rest of the sentence: " ... that utilizes a mapping function in place of explicit metadata and supports the efficient addition and removal of weighted devices.", I feel like calling the statement is "flat-out false" is incorrect.
The auto-balancing behavior of recent versions approaches something that you can raise the max full parameters on with no additional tuning.
In the past it's been possible to utilize a relatively large number of placement groups (for which the performance penalty insinuated in the documentation seems to be greatly exaggerated, and the complications resulting from using too few greatly understated) to approach and exceed 95% utilization even with heterogeneous OSDs. It is also possible to achieve very high utilization via manual tuning of host and osd weights.
If you care about random write performance and are not using Optane or NVRAM journals, then you are doing it wrong.
Can you quantify that? "Very long time" for someone very close to the project and its release cycles might seem like "very short time" to anyone else.