Sharding and IDs at Instagram • Hacker News Board

Re: Sharding and IDs at Instagram

#11

Post by mikeyk » Fri, Sep 30, 2011, 10:26 PM UTC

jconley wrote: post #5

I've used the "snowflake" like approach in the past with great success. It's really not all that complicated. The reliance on time in the Instagram approach is a bit scary. A few ms off here and there could really hurt this scheme. How do you handle seamlessly transitioning these across machines when your shards move?

Thanks for the comment! We don't need the IDs to be exactly sortable, only roughly sortable within a second or so. As long as the clock doesn't move backwards on any given machine (we use ntpd in its gradual-adjustment mode), the IDs are unique.

The way we move shards is to use PostgreSQL's built-in streaming replication to create an exact, in-sync copy of a set of tablespaces, then 'fail over' to a new machine and start reading/writing to a subset of those tablespaces (this is similar to how Facebook describes their shard-moving process).

Re: Sharding and IDs at Instagram

#12

Post by mikeyk » Fri, Sep 30, 2011, 10:28 PM UTC

zeeg wrote: post #9

mikeyk wrote: post #8

Earlier quoted context omitted.

Right now, it's a lookup dict in our Django app--which involves brief downtime just to update the shard map when moving the data (more on this in another post). We hash on user ID (in most cases) and then look the shard # in the dict, then look up the shard # in a logical-to-physical dict. By the way we use & love Sentry!

Ah so you don't actually have 1000 (or whatever) schemas set up right off the bat? Or I might be misunderstanding, and you're saying that you're just mapping which physical server has the schemas

We set-up the schemas ahead of time, and then each lookup is (with, say, 1000 schemas):

  user_id % 1000 -> schema ID
  schema ID -> database ID

then select FROM schemaID.tablename etc on that particular database.

Re: Sharding and IDs at Instagram

#13

Post by jconley » Fri, Sep 30, 2011, 10:30 PM UTC

stevefink wrote: post #10

jconley wrote: post #5

I've used the "snowflake" like approach in the past with great success. It's really not all that complicated. The reliance on time in the Instagram approach is a bit scary. A few ms off here and there could really hurt this scheme. How do you handle seamlessly transitioning these across machines when your shards move?

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?

Re: Sharding and IDs at Instagram

#14

Post by mikeyk » Fri, Sep 30, 2011, 10:31 PM UTC

artilheiro wrote: post #6

I like it. Question, did you consider using composite keys of shard_id and id to make up a single primary key? If so what were the pros/cons you found with that approach? btw, tambem sou brasileiro vivendo em san francisco ( https://twitter.com/#!/artilheiro )

We considered the composite key, but we often have to store keys in other systems like Redis, where having a single 64-bit integer makes it more portable and stored compactly (Redis, for example, has an optimization when storing integer values vs string values in its lists). Valeu pelo comentário!

Re: Sharding and IDs at Instagram

#15

Post by mikeyk » Fri, Sep 30, 2011, 10:32 PM UTC

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?

Yep--definitely something to watch out for. At worst, though, you'd have a duplicate key when trying to insert, and can re-try without the risk of having a duplicate ID floating around your system.

Re: Sharding and IDs at Instagram

#16

Post by fleitz » Fri, Sep 30, 2011, 11:22 PM UTC

How to do sharding:

1. Define your keyspace in bits.

2. Shard your keyspace in CIDR notation

3. Resharding always splits a keyspace in half

  eg. 0.0.0.0/0 becomes 0.0.0.0/1 and 128.0.0.0/1

4. Store your shard keyspace in DNS with SRV/TXT records

5. Assign IDs randomly

This gives a couple interesting properties, for replication odds are very high that your corresponding server has a shard of similar size and if not its generally only split over two servers. Servers also only need to speak directly to their one or two replicas in the other data center. The other really nice property if you're using spindle disks is that you can copy the entire HD and just delete the half of the keyspace not used after the split.

It's all written up here if you want to dig into with a full description of all the pieces: http://bit.ly/FredPatent

Re: Sharding and IDs at Instagram

#17

Post by mark242 » Fri, Sep 30, 2011, 11:26 PM UTC

Holy god. The post mentions "We evaluated a few different NoSQL solutions, but (...)".

I couldn't even imagine having to _think_ about this sort of thing; CouchDB makes this an absolute no-brainer. I mean, the act of creating a document assigns it a UUID in the database _by_ _default_.

Or, do you want to fetch a UUID before assigning it to any data? localhost:5984/_uuids Want to fetch 10? localhost:5984/_uuids?count=10 Want to fetch a million? localhost:5984/_uuids?count=1000000

Instagram seems like the absolutely perfect candidate for CouchDB -- unstructured data, speed, HTTP querying, big data, attachments...

Re: Sharding and IDs at Instagram

#18

Post by mitchellh » Fri, Sep 30, 2011, 11:27 PM UTC

Cool technology, good explanation. Legitimate questions below.

What you're describing (uploading photos + storing metadata) sounds like something which Facebook has tech talked at length about at multiple venues. Their solution was to use distributed FS for images (such as HDFS, though FB uses their internal "Haystack") and then use HBase for the metadata. To be honest, your solution while it works now, looks like a weak home-grown HBase, but leveraging PL/PGSQL for unique IDs. Why not go the snowflake+hbase route? While it may add Ops complexity, it is a fairly battle-proven stack, and JVM ops is pretty well documented.

Or, if you insist on using an RDBMS for metadata, why not just throw money (and not that much) at the problem and buy an SSD for your DB? Increase your iops from 100 or 200 up to 30,000 or 40,000 with a cheap drive, and call it a day. Surely this would be less expensive than the engineering effort that went into (and will continue to go into) this project. This has the added benefit of having no impact on Ops complexity and should scale to quite a staggering number of QPS.

Thanks!

Re: Sharding and IDs at Instagram

#19

Post by fratrik » Fri, Sep 30, 2011, 11:28 PM UTC

Interesting article. It seems like a pretty good solution the problem, especially when judged on the ease of maintenance.

One thing that bothered me was, "Let’s walk through an example: let’s say it’s September 9th, 2011, at 5:00pm and our ‘epoch’ begins on January 1st, 2011. There have been 1387263000 milliseconds since the beginning of our epoch..."

The number of seconds between 5pm one day and midnight another obviously doesn't end in 3, so I looked into it. It looks like that number is taken from the epoch that is used later in the SQL which starts on Aug 24th.

Re: Sharding and IDs at Instagram

#20

Post by jbyers » Fri, Sep 30, 2011, 11:33 PM UTC

mark242 wrote: post #17

Holy god. The post mentions "We evaluated a few different NoSQL solutions, but (...)". I couldn't even imagine having to _think_ about this sort of thing; CouchDB makes this an absolute no-brainer. I mean, the act of creating a document assigns it a UUID in the database _by_ _default_. Or, do you want to fetch a UUID before assigning it to any data? localhost:5984/_uuids Want to fetch 10? localhost:5984/_uuids?count=…

Requirement number one was that IDs be sortable by time. CouchDB UUIDs are random.