Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Sharding and IDs at Instagram

instagram-engineering.tumblr.com

Post reply on HN
Print view View original

31–40 of 53 posts

Re: Sharding and IDs at Instagram

#31

Post by mikeyk »

kenjackson wrote: post #26

I'm sure I missed something, but this doesn't guarantee unique keys across the database does it? What if you have two tables with the same autoincrement value being updated at the same millisecond by two users with the same UserID%NumShards? Or is there some relationship between physical and logical shards that makes this impossible?

Hey Ken, (author here)

There's a 1:1 mapping between the user's hash modulo the number of shards, and the table they're writing to. So, if we had 1000 logical shards, we have 1000 schema/tablespaces, with the same tables in each. And the database's own 'nextval()' feature makes sure never have the same ID twice. Hope that clarified things.

Re: Sharding and IDs at Instagram

#32

Post by kenjackson »

mikeyk wrote: post #31
kenjackson wrote: post #26

I'm sure I missed something, but this doesn't guarantee unique keys across the database does it? What if you have two tables with the same autoincrement value being updated at the same millisecond by two users with the same UserID%NumShards? Or is there some relationship between physical and logical shards that makes this impossible?

Hey Ken, (author here) There's a 1:1 mapping between the user's hash modulo the number of shards, and the table they're writing to. So, if we had 1000 logical shards, we have 1000 schema/tablespaces, with the same tables in each. And the database's own 'nextval()' feature makes sure never have the same ID twice. Hope that clarified things.

Yep, that clarifies it. Thanks. And thanks for write-up. This is the type of stuff I love to see posted on HN.

Re: Sharding and IDs at Instagram

#33

Post by ww520 »

I think it's a mistake to tie the shard id into the object id. Shard id should be derived from the object id dynamically based on the placement of the object among the shards. If the shards grow or shrink or object migrated, a different shard id is generated, but the object id doesn't have to change.

Edit: I like how constructive criticism got downvoted. Thanks for discouraging technical discussion.

Re: Sharding and IDs at Instagram

#35

Post by underwater »

ww520 wrote: post #33

I think it's a mistake to tie the shard id into the object id. Shard id should be derived from the object id dynamically based on the placement of the object among the shards. If the shards grow or shrink or object migrated, a different shard id is generated, but the object id doesn't have to change. Edit: I like how constructive criticism got downvoted. Thanks for discouraging technical discussion.

If you do that then you need to keep a mapping of object IDs to shards. You can't store it on the application servers because of race conditions and memory constraints, so each object lookup will require two network trips.

They've defined 2^13 virtual shards, which is fine-grained enough that they can move entire shards between physical servers to eliminate hot spots.

Re: Sharding and IDs at Instagram

#36

Post by andrewf »

jconley wrote: post #13
stevefink wrote: post #10

Earlier quoted context omitted.

Not really. Like MongoDB, the first four bytes of an ObjectId are a timestamp. That the timestamp is synced with other instances isn't paramount because the actual value of the timestamp does not matter. What does matter is that the timestamp is new and increasing every second. This is to retain sorting capabilities. With the 13 bits that represent the logical shard ID from this article, Instagram will guarantee uniq…

"What does matter is that the timestamp is new and increasing every second." Right. I'm just sayin' that you have to be careful when you move data with a caveat like that. Moving the shard keyspace (the 13 bits) to a new machine that started generating ID's even one second behind (the first 4 bytes) would be troublesome, no?

The lower rotating 10 bits should give them a reasonable safety margin. If they're creating less than 128 entries in a particular shard per second (right now they're doing that across their entire datastore), their clocks would need to be out by 8 seconds to cause a problem.

They should definitely be monitoring their clocks though :)

Re: Sharding and IDs at Instagram

#37

Post by mikeyk »

santosh79 wrote: post #34

Did you evaluate using something like Redis for this? It's got an atomic increment command that guarantee's unique ID's and the performance is stupid fast.

We love Redis at Instagram (it powers a lot of our systems...more write-ups on these soon), and considered it for our ID generation, but it would have introduced a single point of failure, unless we split the load between several Redis instances, at which point it would be hard to make the IDs time-sortable. Also, most of our Redis systems are durable within a minute (we write to disk on a slave every minute), but if we were to lose the master and slave simultaneously (imagine an EC2 network issue or such), then it would be hard to know what the last known 'good' ID was--not an insurmountable problem, but one more moving part to worry about. That said, using Redis with something like the upcoming Redis Cluster could be a good choice, though.

Re: Sharding and IDs at Instagram

#38

Post by ww520 »

underwater wrote: post #35
ww520 wrote: post #33

I think it's a mistake to tie the shard id into the object id. Shard id should be derived from the object id dynamically based on the placement of the object among the shards. If the shards grow or shrink or object migrated, a different shard id is generated, but the object id doesn't have to change. Edit: I like how constructive criticism got downvoted. Thanks for discouraging technical discussion.

If you do that then you need to keep a mapping of object IDs to shards. You can't store it on the application servers because of race conditions and memory constraints, so each object lookup will require two network trips. They've defined 2^13 virtual shards, which is fine-grained enough that they can move entire shards between physical servers to eliminate hot spots.

Shard id is usually algorithmically derived rather than looking up from mapping table, which introduces unnecessary complexity. Look up Consistent Hashing for details, which deals with virtual shards, shard addition/removal, object migration in a consistent and simple manner.

Re: Sharding and IDs at Instagram

#39

Post by bandushrew »

underwater wrote: post #35
ww520 wrote: post #33

I think it's a mistake to tie the shard id into the object id. Shard id should be derived from the object id dynamically based on the placement of the object among the shards. If the shards grow or shrink or object migrated, a different shard id is generated, but the object id doesn't have to change. Edit: I like how constructive criticism got downvoted. Thanks for discouraging technical discussion.

If you do that then you need to keep a mapping of object IDs to shards. You can't store it on the application servers because of race conditions and memory constraints, so each object lookup will require two network trips. They've defined 2^13 virtual shards, which is fine-grained enough that they can move entire shards between physical servers to eliminate hot spots.

I hear what you are saying, but what they have done is derived the their IDs based partially on their current choice of architecture. If, for any reason, they would like to change their architecture later, suddenly they have a real problem.

That feels flaky to me. Its a nice techy solution, and the write up was interesting, but there are definitely a few weak points in their implementation. Their computers have to be absolutely in sync for time, their ID space is entirely guessable once you know the algorithm and they have effectively hard coded their current architecture into their software.

Re: Sharding and IDs at Instagram

#40

Post by speleding »

mikeyk wrote: post #31
kenjackson wrote: post #26

I'm sure I missed something, but this doesn't guarantee unique keys across the database does it? What if you have two tables with the same autoincrement value being updated at the same millisecond by two users with the same UserID%NumShards? Or is there some relationship between physical and logical shards that makes this impossible?

Hey Ken, (author here) There's a 1:1 mapping between the user's hash modulo the number of shards, and the table they're writing to. So, if we had 1000 logical shards, we have 1000 schema/tablespaces, with the same tables in each. And the database's own 'nextval()' feature makes sure never have the same ID twice. Hope that clarified things.

I understand 1000 logical shards is probably a good number to use with PostgreSQL. I'm currently looking at doing something like this myself but I was thinking that it would be so much more elegant if each user could live in his own shard.

Does anybody know of a database product / solution that will handle hundred thousands of shards? I don't have a need for joins across shards, each user account only uses it's own data. And data and access within a shard would be very small, a SQLlite instance for every user would be a theoretical solution. The idea would be to have one (in memory) table to connect the app to the correct shard for the user and then get "perfect" horizontal scaling. Is anybody doing this?

Post reply on HN