Skip to content

Replace range sharding with consistent hash sharding #364

Open

Description

@coffeemug

Pros:

  1. Distribution query code goes away
  2. CLI split/merge commands go away
  3. Shard suggestor code goes away (the user just consistently types a number of shards in every UI)
  4. The shards are automagically perfectly balanced without any work
  5. The unsharding/region code is a lot simpler (no RxR space nonsense)

Cons:

  1. OrderBy is potentially worse (but not by much -- we just merge sort bits from every shard -- considering that secondary indexes require access to every shard, this isn't a biggie)
  2. It's a bit of work

Activity

  1. coffeemug commented on Feb 19, 2013

    @coffeemug
    ContributorAuthor

    @al3xandru mentioned that we also have to think about custom sharding functions for people. We had a long conversation about it, but I'm too tired to transcribe it here, so there :)

  2. jdoliner commented on Feb 19, 2013

    @jdoliner
    Contributor

    Another big advantage of this is that the semilattice metadata and the directory metadata both get a lot smaller.

  3. coffeemug commented on Feb 19, 2013

    @coffeemug
    ContributorAuthor

    Which means... drum rolls scalability problems go away (for a while) with no actual scalability benchmarking work!!!

  4. coffeemug commented on Feb 19, 2013

    @coffeemug
    ContributorAuthor

    After thinking about this some more, everything about this sounds wonderful. We should fire the idiot product manager who delayed the project by probably six months by insisting on range shards in the first place (ducks)

  5. underrun commented on Oct 10, 2013

    @underrun

    any update on this? can it happen sooner rather than later?

  6. coffeemug commented on Oct 10, 2013

    @coffeemug
    ContributorAuthor

    This is almost certainly going to happen post an LTS release. However, this shouldn't affect you as it's a purely internal change. Out of curiosity, could you say why this feature is important to you?

  7. underrun commented on Oct 15, 2013

    @underrun

    Datasets with unevenly distributed keys require manual intervention to maintain balance.

    If I am creating a table for a dataset with keys that I know will have an uneven distribution up front I need to use the cli to set split points before inserting data. possibly this would be less of concern if sharding after data is inserted or rebalancing tables had less of an impact on performance than it seems to.

    it also seems like if i don't have any clue what the split points should be it is difficult for me to create an empty sharded table, and there is no way at all to do so using the web interface.

    obviously there are work arounds, but this is tedious stuff to have to care about.

  8. srh commented on Oct 17, 2013

    @srh
    Contributor

    It's plausible that the new cache changes will have a hard time with the existing stats block (because it expects all write transactions to be drained when flushing, and we don't want that) in such a way that finer-grained out-of-date in memory but up-to-date on disk subtree key counts are kept and updated instead (using the LBA, the way repli_timestamp_t is used). This would eliminate some of the balance estimate problems we have, but it wouldn't help with keeping shard balance up-to-date, if keys are inserted in some order.

  9. nergdron commented on Dec 12, 2013

    @nergdron

    I agree that hash-based sharding should be considered a primary feature, rather than an "internal" change. Can't think of another major datastore which doesn't have automatic shard placement and balancing, and the lack of such here is going to be a major stumbling block for an LTS release with many workloads.

  10. timmaxw commented on Apr 28, 2014

    @timmaxw
    Member

    If I recall correctly, the main reason for range-based sharding was to make range gets efficient. For example, suppose that the user wants every document whose primary key starts with http://www.google.com/, and there are only a few such documents. Then the query gets sent to a single shard (or two shards in the rare case where the shard boundary starts with http://www.google.com/). But if we used consistent hashing, then the query would hit every shard. Is this a problem?

  11. nergdron commented on Apr 28, 2014

    @nergdron

    While I can't speak for the RethinkDB internals, this isn't typically a problem with the other distributed solutions we use, because the request happens in parallel on all the shards, and each shard ends up returning fewer rows.

  12. underrun commented on Apr 28, 2014

    @underrun

    hitting multiple shards could be an improvement - depending on how its implemented. if each shard can respond directly to the client then you can increase the aggregate bandwidth of a system. if clients must go through only one shard then you could see an impact.

    but really, you are implementing a nosql solution here - the major advantages come from the independence of each document. sacrificing anything for the sake of improving performance on a relational query is questionable.

  13. coffeemug commented on Apr 28, 2014

    @coffeemug
    ContributorAuthor

    But if we used consistent hashing, then the query would hit every shard. Is this a problem?

    I think this isn't a problem. RethinkDB isn't meant for thousands of shards (and if we ever get there, enough other things will have to change that hash sharding will be the least of our concerns). If you're using a reasonable number of shards (say, under 32), we'll hit all the shards in parallel and then use a merge sort to get the results to the user, which is quite efficient. I think it's a very good compromise for our target goals.

  14. timmaxw commented on May 15, 2014

    @timmaxw
    Member

    This interacts in a slightly awkward way with the incremental backfilling idea discussed in #1944 and #2002. In particular, if the ordering on the keys in the B-tree is not the same as the ordering used to construct shards, then incremental backfills are much less elegant. If they're different orderings, then a backfill is equivalent to creating a full-width but "empty" shard, then gradually "filling" it; we still have a "RxR" space. But if they're the same ordering, then a backfill is equivalent to creating a zero-width shard and then gradually moving the boundary until it's as big as you want it. You can also do neat things like create a zero-width shard and then gradually expand it to the desired size

    There are a couple of things to consider here:

    • Switching the B-trees to use consistent hashing would make range-get performance terrible. So that's probably the wrong way to go, unless there's some additional advantage that I haven't considered.
    • A major advantage of incremental backfilling is that you can get rid of the pending operations queue. If a write applies to a key you've already backfilled, apply it directly; if it applies to a key you haven't backfilled yet, don't worry, because you'll get the write as part of the backfilled value. So you only need a short queue to hold writes that apply to keys that are in the process of backfilling. This means that backfilling requires constant additional memory, instead of an arbitrarily large disk_backed_queue_t. But to make this work, we need to be able to "shard" writes lexicographically; i.e. we need to be able to say, "give me the part of this write that applies to keys in thus-and-such lexicographical range". Again, this means we're keeping the "RxR space nonsense".
    • One of the original motivations for incremental backfilling (discussed in Stuck with "primary_when_safe" #2002) is to make it easier to recover from a failed backfill. Consistent hashing doesn't break this, but it does make it more complicated; it would probably mean pushing the "RxR space nonsense" all the way up to the administrative code (although not necessarily exposing it to the user).
    • One of the big issues advantages of consistent hashing over lexicographical order is that it makes rebalancing shards unnecessary. Incremental backfilling makes rebalancing way easier, because you can gradually move shard boundaries, in real time, for cost proportional to the distance the boundary is moved. But this only works if the ordering on the B-tree is the same as the ordering used to construct shards.
    • The above scheme is bad if the client is inserting keys in lexicographical order. A naive implementation will pass the keys from shard to shard repeatedly, so the cost of keeping the shards rebalanced will be several times the cost of actually inserting the data. Consistent hashing doesn't have that problem. So incremental backfilling doesn't completely fix the rebalancing issues.
  15. timmaxw commented on Jul 3, 2014

    @timmaxw
    Member

    Incidentally, both MongoDB and Cassandra offer support for both hash-based and lexicographical sharding. Relevant Cassandra docs.

  16. modified the milestones: , subsequent on Sep 29, 2014
  17. nviennot commented on Nov 9, 2014

    @nviennot
    Contributor

    Note that users using a primary key that increases with time (like bson ids, as opposed to uuids) will suffer with range sharing since all new writes will always go to the same shard.
    Consistent hashing would be helpful when dealing with non uniform primary key distributions.

  18. thelinuxlich commented on Mar 3, 2016

    @thelinuxlich
  19. dgllghr commented on Jul 14, 2016

    @dgllghr

    I don't want to butt in to an internal conversation, but you might want to know that we take advantage of the fact that IDs are ordered using array IDs. With array IDs, we can use between to filter on the first ID and do a range on the second, and it's very fast. If you switch to hash sharding, it might still be helpful in use cases like ours to keep the IDs ordered on each node so that these queries like that can be just as efficient. Or you could even consider having the classic hash key, range key combination across 2 fields.

  20. danielmewes commented on Jul 14, 2016

    @danielmewes
    Member

    @dgllghr Keeping the keys ordered within a given shard/node even when using a hash-based criteria to determine which shard data goes into sounds reasonable. Thanks for the feedback.

  21. jedwards1211 commented on Sep 6, 2016

    @jedwards1211

    I hope you haven't reached the conclusion that hashed sharding is always better than ranged sharding?

    Sharding is my biggest remaining concern about switching to RethinkDB from MongoDB. Mongo lets users pick whether they want ranged or hashed sharding, and you have a lot of freedom in picking your shard key. From everything I've read, database applications are too varied for there to be a one-size-fits-all sharding solution. Why not provide both ranged and hashed sharding in RethinkDB? If you moved to only hashed sharding I'd completely lose the ability to control read locality.

    MongoDB docs state clearly that monotonically increasing keys are not a good use case for range-based sharding. Conversely, they explain how while hashed sharding automatically provides good write balancing, it can really hamper query performance for some kinds of data.

    Here are my other concerns:

    • The hard limit of 64 shards means the DB will never be able to scale beyond a certain size
    • RethinkDB doesn't automatically split and rebalance chunks like MongoDB does
    • I assume the sharding is just controlled by the primary key? The docs are not very explicit about this.
  22. danielmewes commented on Sep 7, 2016

    @danielmewes
    Member

    @jedwards1211 It's not entirely clear how much performance benefit range-sharding can have over hash-sharding in RethinkDB. For queries involving secondary indexes, we already have to hit all shards for example, so this won't change. The two cases I can see where range sharding is sometimes more efficient are queries of the form:

    1. r.table(...).between(a, b) (using the primary index)
    2. r.table(...).orderBy({index: "id"}) (again using primary index)

    Apart from that, range sharding I think makes our backfilling and resharding code simpler and more efficient.

    Hash-sharding in RethinkDB won't happen for a while. I'm not sure if we will do a full switch then, or offer both strategies (I think we'll probably be able to offer both strategies).

    • The hard limit of 64 shards means the DB will never be able to scale beyond a certain size

    Note that you can still make use of more servers if you split the data into multiple tables (also, if you want to have e.g. 3x replication, note that you can utilize up to 192 servers for a single table). But it can certainly put a limit on the scalability of some operations.

    • RethinkDB doesn't automatically split and rebalance chunks like MongoDB does

    Yeah, you currently have to run rebalance manually and it will cause brief table downtimes while it's transitioning.

    • I assume the sharding is just controlled by the primary key? The docs are not very explicit about this.

    That is correct, we currently only offer primary-key based sharding.

  23. jedwards1211 commented on Sep 7, 2016

    @jedwards1211

    So here is a more concrete example of something I am working on. I'm working on a data historian with a bunch of tenants and channels. So in MongoDB I could use the range shard key:

    {tenantId: 1, channelId: 1, pageTimestamp: 1}

    and then for example if I query

    {
      tenantId: ..., 
      channelId: {$in: ['channel1', 'channel2', ...]},
      pageTimestamp: {$gte: 14800000, $lte: 20800000}
    }
    

    it will only contact shards that contain one or more documents matching the query (unless I misunderstand something) instead of having to do an expensive scatter/gather query.

    Another important note is that MongoDB can guarantee the uniqueness of the tenantId, channelId, pageTimestamp combination even if the collection is sharded, because each combination is only mapped to a single chunk and guaranteeing uniqueness within each chunk is easy. So I would think there's nothing that would inherently prevent RethinkDB from likewise providing ranged sharding with compound keys?

    Otherwise, I have no idea how to do this optimally in RethinkDB sharding. Do you have any ideas?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions