Hacker News Reader

Comment by jbert | Hacker News Reader

I don't understand how that scheme can work, since changing the number of shards changes the location of most users.

e.g. we have 4 shards, so user 5 is on shard1. If we go to 6 shards, user5 is now on shard5.

I guess it works with downtime to move the users, or another layer of indirection, where the newly created shards can "point back" to existing shards, but otherwise I don't see it.

My understanding of sharding is that it's best to have a global lookup table user->shard. That's not a huge amount of data, even for millions of users.

Anyone care to educate me as to how they get user%num_shards working in practice?

View on HN

You don't change the number of shards, you change the number of machines and re-balance the shards across them. Shard != machine.

    12 shards on 1 machine
    6 shards on 2 machines
    4 shards on 3 machines
    3 shards on 4 machines
    2 shards on 6 machines

And on and on...

Ah, OK. So you start with enough shards "for ever" and not change the number?

Edit: no wait. If you can split a shard across multiple machines, what's the benefit of having more than 1 shard? Why not have 1 shard split across 1000 machines?

The above table wasn't too clear, but my understanding is that a shard exists on only a single machine, but that a single machine could host multiple shards.

Correct, you don't split shards across machines. Each machine hosts x number of shards.

OK, but # of shards is fixed "for ever" under the modulus scheme? You pick it once, when you first shard and then you're looking at downtime to adjust it?

In order to split across multiple dbs, you're looking at creating say 100/1000 dbs in our initial split (when you've got maybe 2-3 machines). And that number then caps the number of machines you can scale to without adding another layer (sharding-shards) or having downtime?

Yes. In the simple modulo scheme, the number of shards is fixed. Unless you want to re-shard the entire thing. (AFAIK)

> You pick it once, when you first shard and then you're looking at downtime to adjust it?

Yes, but you say that like it's a bad thing, it's not. If you're ever forced to reshard, that means you grew beyond what you ever hoped... hurray, awesome, nice problem to have. The reality is however, 99% chance that'll never happen.

Like 1 in a 1000 people ever run into a scaling problem of this magnitude but if you read the blogs you'd come away thinking scaling issues that require sharding are common and everyone needs this stuff, but they aren't, and they don't.

Instead of using normal hashing you can use consistent hashing so you don't need to move that many users. Here's a post explaining it: http://www.spiteful.com/2008/03/17/programmers-toolbox-part-...

You make a large number of virtual shards. Each virtual shard is mapped to some machine. When you add a new machine, you move some shards to the new real machine.

Presumably consistent hashing is also helpful here.

I don't see how this scheme can scale simply for the reason that there's no built in balancer. What's to stop shardN from becoming overwhelmed when all the power users end up there, while shardN-1 has no activity?

Edge-Case YAGNI. Have lots of shards, put multiple shards on each machine, shuffle the shards around as necessary. Rinse. Repeat.

flickr deals with that problem by manually moving power users if necessary. They have a tool that lets them do that. See: http://highscalability.com/how-flickr-handles-moving-you-ano...

In practice it's going to be very rare that you'll overwhelm a single shard and adding an extra layer to point to where people actually are is quite simple and fast. You can use a simple cache key (read-through cache of course) that, if it exists means the user is on a specific shard, overriding the default algorithmic pick.

Hopefully they simplified things for the sake of brevity and they're using consistent hashing or some other predictable algorithm in practice.

Reply on news.ycombinator.com