[HN Gopher] Crush: Controlled, Scalable, Decentralized Placement...
___________________________________________________________________
Crush: Controlled, Scalable, Decentralized Placement of Replicated
Data [pdf]
Author : todsacerdoti
Score : 36 points
Date : 2021-01-04 01:37 UTC (21 hours ago)
(HTM) web link (ceph.com)
(TXT) w3m dump (ceph.com)
| jchanimal wrote:
| How is this related to Kademlia?
| https://en.wikipedia.org/wiki/Kademlia
|
| Seems seems to solve a similar problem?
| [deleted]
| teraflop wrote:
| 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).
| notacoward wrote:
| 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.
| siliconc0w wrote:
| The difficultly with CRUSH is the cost of random writes and
| behavior at capacity. With Ceph you really need to treat 70% as
| 100% or risk full OSDs
| 1_person wrote:
| 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.
| notacoward wrote:
| > for a very long time
|
| 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.
| chromatin wrote:
| Classic paper, but should have [2006] in the HN title
| notacoward wrote:
| 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.
| klysm wrote:
| From what I know about the space, the algorithm is pretty much
| still best in class
___________________________________________________________________
(page generated 2021-01-04 23:03 UTC)