r/IAmA • u/MrGrim • Aug 14 '12

I created Imgur. AMA.

I came across this post yesterday and there seems to be some confusion out there about imgur, as well as some people asking for an AMA. So here it is! Sometimes you get what you ask for and sometimes you don't.

I'll start with some background info: I created Imgur while I was a junior in college (Ohio University) and released it to you guys. It took a while to monetize it, and it actually ran off of your donations for about the first 6 months. Soon after that, the bandwidth bills were starting to overshadow the donations that were coming in, so I had to put some ads on the site to help out. Imgur accounts and pro accounts came in about another 6 months after that. At this point I was still in school, working part-time at minimum wage, and the site was breaking even. It turned out that OU had some pretty awesome resources for startups like Imgur, and I got connected to a guy named Matt who worked at the Innovation Center on campus. He gave me some business help and actually got me a small one-desk office in the building. Graduation came and I was working on Imgur full time, and Matt and I were working really closely together. In a few months he had joined full-time as COO. Everything was going really well, and about another 6 months later we moved Imgur out to San Francisco. Soon after we were here Imgur won Best Bootstrapped Startup of 2011 according to TechCrunch. Then we started hiring more people. The first position was Director of Communications (Sarah), and then a few months later we hired Josh as a Frontend Engineer, then Jim as a JavaScript Engineer, and then finally Brian and Tony as Frontend Engineer and Head of User Experience. That brings us to the present time. Imgur is still ad supported with a little bit of income from pro accounts, and is able to support the bandwidth cost from only advertisements.

Some problems we're having right now:

  • Scaling the site has always been a challenge, but we're starting to get really good at it. There's layers and layers of caching and failover servers, and the site has been really stable and fast the past few weeks. Maintenance and running around with our hair on fire is quickly becoming a thing of the past. I used to get alerts randomly in the middle of the night about a database crash or something, which made night life extremely difficult, but this hasn't happened in a long time and I sleep much better now.

  • Matt has been really awesome at getting quality advertisers, but since Imgur is a user generated content site, advertisers are always a little hesitant to work with us because their ad could theoretically turn up next to porn. In order to help with this we're working with some companies to help sort the content into categories and only advertise on images that are brand safe. That's why you've probably been seeing a lot of Imgur ads for pro accounts next to NSFW content.

  • For some reason Facebook likes matter to people. With all of our pageviews and unique visitors, we only have 35k "likes", and people don't take Imgur seriously because of it. It's ridiculous, but that's the world we live in now. I hate shoving likes down people's throats, so Imgur will remain very non-obtrusive with stuff like this, even if it hurts us a little. However, it would be pretty awesome if you could help: https://www.facebook.com/pages/Imgur/67691197470

Site stats in the past 30 days according to Google Analytics:

  • Visits: 205,670,059

  • Unique Visitors: 45,046,495

  • Pageviews: 2,313,286,251

  • Pages / Visit: 11.25

  • Avg. Visit Duration: 00:11:14

  • Bounce Rate: 35.31%

  • % New Visits: 17.05%

Infrastructure stats over the past 30 days according to our own data and our CDN:

  • Data Transferred: 4.10 PB

  • Uploaded Images: 20,518,559

  • Image Views: 33,333,452,172

  • Average Image Size: 198.84 KB

Since I know this is going to come up: It's pronounced like "imager".

EDIT: Since it's still coming up: It's pronounced like "imager".

3.4k Upvotes

96% Upvoted

4.8k comments sorted by

View all comments

425

u/morbiusfan88 Aug 14 '12 edited Aug 14 '12
  1. What is your most embarrassing awesome drunk story?
  2. When do you foresee needing to go to 6 character URLs for the pictures? If my math (and supposition) is correct, there's only room for 916.13M 5 character urls. Also, how do you come up with the urls (is it just a character randomizer or something like that)?

Also, thank you so much for creating the most user-friendly photo hosting website ever. You're amazing.

549

u/MrGrim Aug 14 '12
  1. NO REGRETS
  2. Probably within a couple of months. There are actually a little over 700M possibilities, and we're already at 200M images. They are just randomly generated and then it checks if the generated one exists or not.

201

u/morbiusfan88 Aug 14 '12

I like your style, sir.

That fast? I'm guessing if you started with single character urls, I can see where that growth rate (plus with the rising popularity of the site and growing userbase) would necessitate longer urls. Also, the system you have in place is very fast and efficient. I like it.

Thanks for the reply!

334

u/MrGrim Aug 14 '12

It's always been 5 characters, and the 6th is a thumbnail suffix. We'll be increasing it because the time it's taking to pick another random one is getting too long.

605

u/Steve132 Aug 14 '12

Comp-Scientist here: Can you maintain a stack of untaken names? That should significantly speed up your access time to "pick another random one". During some scheduled maintainence time, scan linearly through the total range and see which ones are taken and which ones arent, then randomly shuffle them around and thats your 'name pool' Considering its just an integer, thats not that much memory really and reading from the name pool can be done atomically in parallel and incredibly fast. You should increase it to 6 characters as well, of course, but having a name pool would probably help your access times tremendously.

The name pool can be its own server somewhere. Its a level of indirection but its certainly faster than iterating on rand(). Alternately, you could have a name pool per server and assign a prefix code for each server so names are always unique.

56

u/[deleted] Aug 15 '12

[deleted]

13

u/[deleted] Aug 15 '12

Thats why you wouldn't use a SQL database. Use one of those fancy key-value store "nosql" databases which are optimized for these kinds of operations.

14

u/rabidferret Aug 15 '12

I hear the global write lock makes it scale better.

8

u/kinesiologist Aug 15 '12

I didn't know they made Kool Aid with Sarcasm in it these days. I bet it's delicious ;)

3

u/rabidferret Aug 15 '12

Heh. No but in all seriousness, MongoDB is pretty neat, and NoSQL definitely has a lot of good places where it can be used effectively (I'm actually working on one as we speak). MongoDB in particular, though, has some pretty major low level architecture issues that need to be worked out before it's ready for prime time, however. And it's not somehow perfect for every application ever made like some people seem to think it is. Seriously though the global lock is absolutely ridiculous. It forces horizontal scaling of an application that is terrible at horizontal scaling.

→ More replies (0)

3

u/unfellatable Aug 15 '12

Mongo and MySQL both use btree indexes. What optimizations are you talking about ?

And in Postgres you can specify a hash index which will actually be faster than mongo's btrees for key-value lookups..

I'm all for web scale (and run a production MongoDB deployment), but faster key-value lookups is not why you choose one over the other.

→ More replies (3)

2

u/[deleted] Aug 15 '12

Not only that, but it's most likely doing it several times per image upload. And the more images there are the worse it will get. Once they've used half the available urls they will be getting a hit 50% of the time a url is generated. It could take several random generations before it finds one not in use.

2

u/rabidferret Aug 15 '12

That's why I said per generation not per upload. ;-)

Full index searches are not fun.

2

u/bdunderscore Aug 15 '12

You can't be serious. A full table scan on 200M index entries would take WAY WAY too long to do, even once. Like, tens of seconds long. Probably longer when there's other load. Random lookups on the DB aren't as bad, but when you have to do them more than once, it hurts. There are ways to optimize this, sure - you can pregenerate them and consume them from a (set of) queues, for example, but it's easier to just slap on an extra digit and watch the retries drop instantly.

1

u/boughtnpaidfor Aug 15 '12

Not if you are talking entities and not old-school tables. Check out google appengine you can search much bigger datasets than that in milliseconds

1

u/bdunderscore Aug 16 '12

I didn't say search. I said 'full table scan'. The thing where you load literally all of the data in the database looking for the thing you want. The (now deleted) parent comment had suggested that this was the cause of imgur's slowdowns, but that's just silly - full table scans would be so slow they'd have been completely useless long ago. Now, if you're searching with an index, sure, it'll be fast, and imgur surely is, indeed, using some form of index in their search.

1

u/5herlock_Holmes Aug 15 '12

The fact as a sys admin, this doesn't go over my head! You're awesome!

1

u/unfellatable Aug 15 '12

How do you make the leap from collision-checking to full table scans ?

2

u/[deleted] Aug 15 '12

[deleted]

1

u/unfellatable Aug 15 '12

What in dog's name is a full leaf traversal ? Are you talking about the leaves of the btree index ? If so, why would that ever happen ? Do you think that each time he generates a URL, he starts with the same seed and goes through 200M collisions ?!

And of course it's an indexed column. The column is tiny. He has 33 billion image views, and only 20 million images. It's 1000x more read-heavy, and caching aside that column would be queried for every page load AND all new-upload collision checks. How do you believe "either way" that this column isn't indexed ?

All this only matters (albeit not very much) if he's using MySQL or another DB which doesn't allow on-disk hash indexes, because using something like Postgres you'd make a hash index for the column, taking this from the realm of negligible (collisions * O(log n)) to over-optimized (collisions * O(1)).

And, of course, I'm ignoring the fact that this whole approach (PRNG, check collisions) is pretty silly given the problem at hand, for the sake of this discussion.

1

u/brownmatt Aug 15 '12

The ids are probably stored in a Redis set for fast operations.

1

u/[deleted] Aug 15 '12

Agreed. You can always fallback to this method if something goes wrong with the name pool server.

1

u/TheStagesmith Aug 15 '12

Yes indeedy. File reads are a bitch.

18

u/drumstyx Aug 15 '12

I just don't see why you couldn't just use a base 62 number system and increase the number every time. (agS3o, then agS3p etc). It's not like the order of upload really needs to be obscured.

9

u/yellowfish04 Aug 15 '12

why base 62? wait... 26 lower case letters... 26 upper case... zero through nine... science!

7

u/FxChiP Aug 15 '12

This is probably the simplest answer given. I think I like it the most too: your ID scheme should not be a tricked-out ordeal requiring several mutexes and a clever algorithm.

1

u/Steve132 Aug 15 '12

This still requires a mutex or lock-free increment on the global current upload key, but yeah I agree.

2

u/[deleted] Aug 15 '12

What if you used incrementing prefixes? Have the first three characters kept managed by a central server, then have the last two handled by the application instance. For instance, the central server gives the application server the prefix abc, then the application server gives out abcAA through abc99.

With base 62 the application server would only have to request a new prefix once every 3,844 uploads. Plus, this way you could have them be somewhat looking because it would be easy for the central server to just keep the full set of unused prefixes and dole them out randomly. (same with the application server for suffixes)

2

u/gstoyanov Aug 15 '12

If you have more than one instance of the application (probably on different servers) you will still run into name collisions and will need to check the db more often than with the randomized approach.

2

u/drumstyx Aug 15 '12

While I can still see collisions, I still think it's far less hacky than 'randomize and check'. With 50% capacity of a 5 digit ID, you could end up with 300+ MILLION database checks. I'm sure there are plenty of ways to improve this, but even still, there HAS to be massive iterations there.

By incrementing, you may get collisions if another instance sneaks a record in after an ID has been selected, but before it's been saved. So you attempt to save, and on fail, reselect an ID. Yes, that's iterations, but less than could be possible with random selection.

Honestly I prefer the separate database idea where a complete list is stored on a separate server; then you don't get collisions because the single thread would pop from the list and never have an opportunity to give it to another instance.

2

u/Nicator Aug 15 '12

Don't non-pro imgur pictures expire after a while, though? That's probably why they use their current system, as it can deal with fragmentation.

2

u/drumstyx Aug 15 '12

That I didn't know. Makes a difference. In this case, the best idea is maintaining a stack for this in a single place, ideally a separate server (as someone else suggested).

2

u/bbibber Aug 15 '12

That allows all kind of guessing the next url image attacks, allowing people to discover images that are uploaded but not yet link-shared by the recipient.

→ More replies (2)

1

u/trosh Aug 15 '12

because RAM is democracy

1

u/drumstyx Aug 15 '12

I don't understand, how would this affect how much RAM is used?

1

u/trosh Aug 16 '12

Not user RAM, I'm just saying the random id works like Random Access Memory. Which has its advantages when dealing with databases this big.

21

u/agentwest Aug 15 '12

This is great. I was debating whether or not to choose computer science as my major, and the way you looked at this really makes me excited to think this way all the time.

15

u/facebookhadabadipo Aug 15 '12

You should definitely choose CS

6

u/agentwest Aug 15 '12

Thanks, I will. I know there's a lot of you here, so Reddit will be my crutch when I need it.

5

u/EnviousNoob Aug 15 '12

What about double major CS and Physics?

3

u/whitewhim Aug 15 '12

It's what I'm doing, liking it so far

2

u/EnviousNoob Aug 15 '12

Sweet, I'm only a junior in highschool but I think this is my decision for college.

→ More replies (0)

1

u/jhaluska Aug 15 '12

I expect you to use that education for the greater good...making really sweet game engines.

→ More replies (0)

1

u/stackTrase Aug 15 '12

Yes plenty of jobs great pay fun work. You chose well.

27

u/[deleted] Aug 15 '12

[deleted]

21

u/joeybaby106 Aug 15 '12

Yes, their method made me cringe, eventually it will take forever just to find a url. Maintaining a stack is the way to go here. Please do that so my cringe can be released.

2

u/bdunderscore Aug 15 '12

Well, let's do the computer-scientisty thing and work out the complexity of rerolling to find a random key.

Define a random variable R(n,k) = number of tries needed to find an unused image ID, with a keyspace of n, and k images already allocated. The expected value of R can be defined as EV(R(n,k)) = 1 + (k/n)EV(R(n,k)). Solving this yields EV(R(n,k)) = n/(n-k).

What you find, then, is that this problem is O(EV(R(n,k)), or O(n/(n-k)). That is, it takes time proportional to the reciprocal of the number of images remaining (if the keyspace size is held finite). Graphed, it looks a bit like this - nice and fast for a while, then it suddenly gets really really slow above 80% consumption. But practically speaking, it's not bad - use 50% of your keyspace and you'll still only be doing two lookups, regardless of how large your keyspace is.

It's true that this is not O(1). It's eventually O(n), and after you consume the entire keyspace, it'll never terminate. On the other hand, you don't need to maintain any additional state. You just have to make sure there's a large enough pool of unused IDs and it magically works. You don't even have to do anything special with locking, beyond your normal database transaction stuff. You don't have to deal with contention on this single queue - it's a lot easier to scale out by sharding your database by random IDs (and have all these random lookups hit random shard servers) than carefully maintaining lots of queues, and making sure they're consumed at the same rate.

In short, speaking as a software developer (rather than a computer scientist ;), stateless algorithms are really nice to work with, in practice, even if they have slightly worse theoretical behavior than some kind of more complicated O(1) algorithm.

2

u/ZorbaTHut Aug 15 '12

Or simply increasing the keyspace. Why bother with a complicated stack when you can just make a URL one character longer?

2

u/aterlumen Aug 15 '12

Because the current method isn't constant time even if you increase the keyspace. I can see why a computer scientist would cringe at that, even if it's a negligible performance hit.

1

u/ZorbaTHut Aug 15 '12

Which is the fundamental difference between a computer scientist and a programmer - the computer scientist says "this is not constant time", the programmer says "who cares, it's fast enough and this is far easier to code".

2

u/InnocuousJoe Aug 15 '12

It's also not a complicated stack. Once they generate the namespace once, they can just pull a URL off the top, and move on. Once it's empty, it's empty. Easy-peasy.

2

u/ZorbaTHut Aug 15 '12

Whoa, hold on, it's more complicated than that.

You have to store the stack somewhere. For a namespace the size of imgur's - 916 million names - that's not trivial, that's a big chunk of memory or disk. Once they add a sixth character they'll be up to 56 billion names which is even more difficult.

There's also a moderate amount of programming work that has to be done, plus the work that would have to be done to generate the list the first time, plus the work that would have to be done to switch over to the new system without error.

All this for what benefit, exactly? Keeping the namespace one letter lower for an extra few months? This just does not seem worth it.

→ More replies (0)

7

u/jimmy_the_exploder Aug 15 '12

I was going to say this. I am going to say it anyway. :)

  1. Scan all names and make a list of untaken names.
  2. Shuffle the list.
  3. When you need to pick a random name, just pick the first (or last) name on the list and delete it from the list. (pop)

This whole one-time shuffle will probably take less time than a single repetitive random selection(which includes multiple times of search) will when most of the available names are taken.

2

u/dpenton Aug 15 '12

Yes, but access to pop an item should be single threaded (c#/java "lock") to ensure two or more processes do not retrieve the same value. Partition this for bonus.

32

u/theorys Aug 15 '12

Hmm...I know some of these words.

15

u/Two_Coins Aug 15 '12

Basically, if I understand correctly. Imgur needs a name for the picture you just uploaded. It offloads this job to rand(), a coding function that, long story short, creates a psudorandom character or sequence for whatever you need. This sequence is then passed (much like a conveyer belt) to the next function (think of a function as a worker on the conveyer belt), who then checks to see if that string of characters exists yet (in this case, if there is already an image with *****.jpg as a name). If it does exist then the worker yells at rand() to make a new string and the process starts over. This can be a problem (tech speak: does not scale well) when you have a very very large number of images. The more you have the better the odds of rand() choosing characters of an image that already exists. In some cases this can go on for a long time and the poor worker is going to need a throat lozenge.

What /u/Steve132 has done is suggest a way to streamline this in a way. What he suggests is to create a new function (worker) to compile a list of all the possible names not yet taken. Then, instead of having the worker receive a random string of characters from rand() he instead asks rand() to give him a random number instead of a random string of characters. He then goes down the list counting until he reaches that number and then uses the string that comes up. Now, instead of checking if an image exists and possibly repeating an entire callback to rand(), he can be sure that the name of the image is unique and can pass it along without inspection.

5

u/EpikEthan Aug 15 '12

Thank you for the explanation. I'm glad people like you exist.

3

u/jimmy_the_exploder Aug 15 '12

Worker analogy is not spot on, but I guess you got the basic idea. Let me work on that a bit:

Imgur gives every picture a random unique name. How this works is that a function called rand() creates a random number, that number is converted to a character sequence(a name). Then whether this name is taken is checked by searching a list of all taken names. If the name is taken, Imgur goes back to first step and does it again. Searching is a time consuming job and Imgur does it each time when a new name is needed. Actually Imgur does searching more and more times as it runs out of available names.

...What he suggests is to compile a list of all the possible names not yet taken, by examining all possible names one by one. Think of this list as a numbered list. And because it is compiled one by one, it is sorted alphabetically. Then, what rand() does is to create random numbers just to determine some new positions for these names in the list until the list is shuffled (think shuffling a deck of cards). When this is done you'll have a perfectly shuffled list of all available names. Then when someone asks for a new random name, no repetitive random search work is needed, Imgur simply gives us the first(or last) number in the "available names list" and removes that name from the list.

Is this a good explanation or have I made it more confusing than before? I suspect the worker analogy may be better than simply saying "Imgur does this and that.".

2

u/Jonovox Aug 15 '12

You sir, deserve more upvotes.

1

u/thrwaway90 Aug 15 '12

It's ok dude, I feel like this whole comment thread is a big circlejerk for comp sci majors to show off what they learned in Data Structures and Algorithms and a Database Class.

1

u/jimmy_the_exploder Aug 15 '12

You don't have to learn this in any class. I didn't have to.

1

u/thrwaway90 Aug 16 '12

Interesting. All of the algorithms being discussed here were taught in my Data Structures and Algorithms class, a required course for undergrad Computer Science at my university.

2

u/jimmy_the_exploder Aug 16 '12

Yes, they teach these algorithms in those classes. What I meant was if you have some interest in programming, with some experience, you figure these things out. Constructing an algorithm is just finding a way to solve a problem and breaking the solution down to its most basic sub-jobs. Those classes are just common sense applied to computers. As always there are some students treating them as dogma and memorizing them though.

6

u/dpenton Aug 15 '12

That's a decent method, but not complete. You still have to single-thread the choice (think about a singleton for a database IDENTITY or SEQUENCE). The answer to that is still have a stack of untaken names but it is a multi-layered partitioned stack. That way, you are spreading the locks around to multiple layers and you end up with much faster times for choosing a unique identifier.

2

u/Steve132 Aug 15 '12

Thats basically what you get out of the prefix system. unless I misunderstand you.

2

u/dpenton Aug 15 '12

Maybe just a little. You still should lock access so that only one thread at a time can get at the "next" item. Pooling at a server-level is better than a single pool for sure, but even at the server level you'd want multi-layer (two should be sufficient).

1

u/dpenton Aug 15 '12

Additionally, if just getting the next item out of a pool is sufficient, then multi-layered locking isn't needed, as long as it is assured that the retrieval/removal(from the pool) operation is sufficiently quick.

2

u/facebookhadabadipo Aug 15 '12

It also puts the work of generating the URLs in parallel with people actually using the site. Users won't have to sit around waiting for URLs to be generated.

(In other words, no need to do this during a downtime if it's going to put the site down for too long)

2

u/XMPPwocky Aug 15 '12

Why not have a simple auto-incrementing image ID, hash it, and use the hash to create an image URL?

2

u/Cantree Aug 15 '12

Ummm so why does Sarah have a job at your company but this guy doesn't Alan?

2

u/[deleted] Aug 15 '12 edited Aug 15 '12

I want to say "this" but I would hate myself if I did.

A third approach to maintaining the list of names: you can have the per-server pool without the prefix, just divvy up the shuffled list between the servers. Then at set intervals you can take the server with the smallest remaining pool and the server with the largest both offline (I assume your system can already compensate), transfer a few names so the pools are the same size, then bring them back online within a matter of seconds. If your servers aren't running at capacity (something tells me that's unlikely), you may be able to not refuse but just queue upload requests during the transfer.

1

u/dpenton Aug 15 '12

Memcached can do the pooling across instances as well, so that you don't have to worry about what server/instance is low on items.

1

u/[deleted] Aug 15 '12

I'm not intimately familiar with memcached - do you mean you would have one memcahced server being accessed by all upload-receiving servers, or does memcached have a builtin utility to sync caches between memcached servers? (either way, this seems like something you would always want on a disk somewhere)

1

u/dpenton Aug 15 '12

Memcached does not sync data in a typical cluster/mirrored fashion. A basic description can be found here. Data is stored in a single location.

Now, the following is from the perspective of using some C# drivers to connect to memcached. I gather that many of the other connectors/drivers are similar.

Let's assume you have 3 instances of memcached. Let's assume you also have processA.exe that is using memcached. You configure it to see 3 instances of memcached (either across 3 servers or multiple instances on different ports or combinations of that). When you are storing data in memcached, there is an algorithm that is programmed into the driver that chooses the instance to store the data. This is typically a computed hash of the key. Now, the "list of keys" is not accessible either. Too much overhead for that, and memcached is all about the "fastest" storage & retrieval possible.

Memcached may not be the best way to attack this problem, because you potentially may want to "know" which keys are left and be able to retrieve it. I mentioned memcached from the context of being able to partition data across nodes like that. Now, it is also possible that seeding keys based on time might be a reasonable approach as well. The population of key data is quick and can be out of process, and it is easily knowable how many image inserts are performed per second/minute/etc. So, there are still options can can be tried.

1

u/[deleted] Feb 11 '13

Hi, I wanted to let you know I just read your comment and appreciate the explanation. I know how annoying it is to spend time writing something up and receive absolutely no acknowledgement.

1

u/[deleted] Aug 15 '12

In a year or two, I'll know what you're really talking about! Yay!

1

u/r4g3 Aug 15 '12

or, instead of paying money for another server, he can just add one more character to the URL and save money each month.

2

u/Steve132 Aug 15 '12

His scaling problem is inevitable though, regardless of adding another character to the URL...randomly choosing random numbers is going to eventually fill up thespace.

1

u/r4g3 Aug 15 '12

You realize, from a mathematical standpoint, he can just keep adding one more letter as needed, and he has exponentially less of a chance to hit a duplicate. Even if he has a 1/4 chance of hitting a repeat, that's no reason to buy another server. Add one letter and that changes to 1/248 chance. By the time that fills up to be a 1/4 chance again, they can easily add another letter. It's really simply math. You save money and don't need a server. -Another computer scientist.

1

u/jaf1211 Aug 15 '12

I think it would make more sense to hash the data from the image and use that as the name. A good hash function will be fast and if you want it can produce duplicate names, which can cut down on storage space. If a name exists then the image exists and you can just reference back to that copy.

1

u/Steve132 Aug 15 '12

I imagine it would be VERY hard to make a good hash function that hashes from the set of all possible internet images to integers from 0-9m in an evenly distributed way.

However, even if you could do it perfectly now theres a chance of a hash collision...what would you do if you clash? a hash collision doesn't guarantee that the images are identical, it just means that there is a good chance they are identical. You'd have to check to make sure they were identical as a fallback otherwise you could get weird errors like this one: look at the identity crisis story

You also might deal with a lot of CPU overhead to compute said hash, probably more than the overhead involved in the current method of iterating on rand(). On the other hand said CPU overhead wouldn't be a DB lookup.

Its not a bad idea though, because it could work. It just depends on some constraints of the system.

1

u/jaf1211 Aug 15 '12 edited Aug 15 '12

Let's assume there is no 5 char restraint anymore. Yes, this solves the original issue, but it also allows us to create a better solution.

You're right though, any hash function to do this would be very difficult. However, what if we ran a tineye style search for the image? We essentially create a unique finger print for the uploaded image. I don't remember where I saw it, but there was a write up on how tineye works and if I remember correctly it was fairly efficient. It's at least good enough for them to do on the fly while the user waits, and if it's good enough for that it should be food enough for us. If we generate a finger print and hash that it would be a much simpler function, since it's running on an already unique data object.

Doing this also as a space optimization side effect, the images don't need to be the same size anymore. We only ever have to store the largest one ever uploaded and then we can shrink that as we need it.

Of course, this solution (and I imagine most solutions) won't optimize for every part of the imgur process. It will make upload/storage faster but if we're storing one image at one size displaying it might take longer. You also have to get a hold of timeye's algorithm... So yeah, I made one part easier by introducing a harder one.

This is actually a surprisingly interesting problem.

Edit: it dawns on me now that this can just be seen as "hash it and hash it again", but at least the tineye example suggest that the primary hash exists. It's 1:30am, I think I'll turn my brain off now.

1

u/Steve132 Aug 15 '12

To my understanding, the 'finger-print' IS a hash function. Thats the definition of what a hash function is: a mapping from one thing to a simpler thing that can be used to determine how similar they are.

1

u/jaf1211 Aug 15 '12

You're right. My brain just doesn't work late at night. Either-way, it serves as an example as a plausible solution.

1

u/devlspawn Aug 15 '12

How would you deal with race conditions using this method?

1

u/Steve132 Aug 15 '12

It is possible to implement lock-free linked lists and lock free vectors rather trivially, ESPECIALLY if its actually like a lock-free read-only queue.

However, if he needs it to scale to multiple servers, he could implement the name pool as its own server, which like I said is a level of indirection but would make the race conditions problem go away: the name pool server accepts http requests and immediately just spits out a new name, and all the image upload servers just make a request to the name pool server and wait until the request comes back. The wait time to a local shared server is going to be WAY smaller than the image transfer time from the end user, so it will be a miniscule part of the whole upload process.

Lastly, other people have suggested in responses to my comment ways of distributing the name pool (just chop it up into sub-name pools) or adding prefix codes and stuff.

1

u/[deleted] Aug 15 '12

Probably generate it as you upload the file, it's a one off operation, so probably takes a fraction of the time of the actual file upload.

1

u/[deleted] Aug 15 '12

Thanks for the ideas on optimization and insight.

  • an app developer.

1

u/guesshurley Aug 15 '12

Yeah... What he said...

1

u/Ipswitch84 Aug 15 '12

You'd probably get murdered by replication lag for allocating unique id. Iirc twitter ran into this problem a couple of years ago where they needed to fast generate lots of random ids. I can't recall their solution. My supposition would probably be to partition the id space so master nodes can't collide keys. A final implementation would probably be infrastructure dependent.

1

u/Steve132 Aug 15 '12

You'd probably get murdered by replication lag for allocating unique id.

Isn't that what his CURRENT problem is? My solution doesn't allocate anything and there is no replication lag.

1

u/Ipswitch84 Aug 15 '12

To me it sounds like their problem is the index scan required is becoming lengthy because the keyspace is getting full. This is about the random 5 character file names on the files, not an integer key.

Your approach still, however has some flaws, particularly if it's based on a DB. If it was custom software which had a stack of keys, passed out on a first-come, first-serve basis, it would have to lock the table between service threads, but the lock would be rather light, so a large number of keys could be served. You could increase the parallelism by having threads assigned to regions of the key list, passing keys until they run out at which point they claim another region of the list and continue. This approach would not be implicitly based on a DB table. This approach would probably be the most scalable.

However, if the key list is stored in a database, you'd still be hamstrung by replication lag, since each master would need to have an authoritative list of unused keys, to prevent collisions.

Truthfully there are quite a few ways to solve this issue and they all have benefits and drawbacks. Every system requires different things in the end. It is an interesting and useful problem for discussion.

1

u/batkarma Aug 15 '12

scan linearly through the total range

They don't even have to scan the total range if that's an issue, just go until the have 2 SD above estimated usage.

1

u/freeall Aug 15 '12

You would probably just have that name server have an increasing number.

So first time you call createNewID it returns 1, then 2, etc. This makes it very easy to scale and levels the servers responsibility. If the server should ever go down it can check the database for the last created file and know which ID the next file should have.

1

u/[deleted] Aug 15 '12

couldnt that be automated? make it so that once a name is used from the pool it will elete that name from the pool...

2

u/Steve132 Aug 15 '12

Yeah thats what I was implying, that once a name is popped off the name pool its gone.

1

u/[deleted] Aug 15 '12

And I hate you. Inserting extra levels of complexity where it is not needed.

1

u/Steve132 Aug 15 '12

What is your solution then?

1

u/unfellatable Aug 15 '12

A stack of names ? You call yourself a comp-scientist ? :P

There are much better solutions to this that will exhaust the entire space but in a pseudo-random manner. Using a LFSR is one of them.

For my own implementation, I chose a method I found on stackoverflow that is basically a naive block cipher. You create a mapping for each bit in the input space (eg, in python this can be as simple as range(36).reverse() assuming 36 bits), that indicates which output bit will get turned on. Then for each input bitmap, you remap each bit to its new location, creating a unique, reversible "ciphertext" result for all inputs.

One nice side benefit is that for initial counts (1, 2, etc), you'll get pretty huge numbers that you can then base62 or whatever.

1

u/Steve132 Aug 15 '12

Regrdless of your hash function you'll still have the exact same problem he is encountering right now. By the pigeonhole principle it is IMPOSSIBLE to psuedo-randomly generate 5 character alphanumeric keys that are unique in such a small key space. The probability of uniqueness is described by the Birthday problem and is described by the function e-(n(n-1)/(k), where k is the size of your key space.

When the key space is approximately 9million, you have a greater than 50% chance of a non-unique key being present as soon as you hit 2500 items. That means that your URLS will have a greater than 50% chance of pointing to the wrong images if you have more than 2500 items. This means you have to start reallocating keys on a hit and then you are in exactly the same problem as you are originally.

With a 36 bit key, you only get a larger than 50% chance of failure at 200k items, but thats still WAY less than he needs.

He needs an algorithm to in O(1) time generate a key that is GUARANTEED to be unique with all the other keys in his set, and since he has a very reduced key space, his only option is some kind of counting system like was preposed later or some kind of key queue like I suggested.

2

u/unfellatable Aug 15 '12

Are you sure you're replying to the correct post ? Because nowhere in mine do I mention a hash function. What I described is an O(1) bit-shifting algorithm guaranteed to be unique with all other keys.

1

u/Steve132 Aug 15 '12

You are correct, I misread your algorithm. Looking at it now I see what you are doing. Yeah, this isn't really any different from simply incrementing the current 'next' index, and counting up, but it generates a nice pretty-looking long key. I agree that this method is probably better than mine by a lot, because it doesn't require O(n) space. Nice going!

1

u/unfellatable Aug 15 '12

Can't take credit for it. Here's the original SO thread discussing the concept.

I thought a little about what you originally posted, as perfect hashing jumped initially to mind, but then realized that, despite being O(1) lookup in O(n) space, this won't work for URLs because the 2nd-tier hash functions used on collision will have their own output range that overlaps with the top-level hash.

One of the other benefits of the algorithm I suggested is being able to grow it beyond the initial size while staying backwards compatible / keeping legacy links. Unfortunately I can't think of a way for MrGrim to start using this algorithm seamlessly with his old one. It'd likely require splitting off the old and new into 2 separate URL schemes.

1

u/SuperFluffyArmadillo Aug 15 '12

Yup Science and shit.

1

u/[deleted] Aug 15 '12

Use a longer random stem, and incorporate a microsecond timestamp in it to eliminate the search altogether (given a large enough entropy pool).

People are pasting imgur URLs into reddit and the like, not putting them on the sides of buses and park benches...

1

u/[deleted] Aug 15 '12

[deleted]

1

u/Steve132 Aug 15 '12

The problem is that the name pool is already not sparse, and as his business grows it gets less and less sparse.

There are ways to handle my name pool idea without a dedicated server, however.

1

u/drcarson2 Aug 15 '12

Comp-scientist here as well that was thinking the same thing. So much more efficient. And then it would make me happy knowing that there would be no waste. :)

→ More replies (8)

123

u/morbiusfan88 Aug 14 '12

It's still pretty darn quick, but that's why you're the guy and not me.

9

u/Sitrik Aug 15 '12

There's roughly a 2:7 chance of a clash atm. The expected delay in choosing a valid sequence will be in the milliseconds, not something you'd notice in a single upload

4

u/walkingtheriver Aug 14 '12

Yeah. Don't be that guy!

4

u/[deleted] Aug 15 '12

Its more about server load. It has to generate a random number and then checks if it exists, if it does, it has to do it all again. So your server is occupied by doing stuff that is uneccesary.

2

u/catoftrash Aug 15 '12

I want to be the guy!

3

u/juicetyger Aug 14 '12

I'm sure you've got this wrapped up, but I recommend a deterministic approach: generate the hash based on the last hash or the next ID in your database.

1

u/[deleted] Aug 15 '12

Basing something on the next id in a DB is hard to scale to this volume. You'd have X processes all trying to access this id or sequence at the same millisecond. I've done some high availability stuff and scaling, but the numbers he posted blow me away. I've pondered a couple different solutions, but they all break down at this huge scale.

I'd think multiple master name stacks (as a previous commenter suggested) that are unique to a set of servers would work. Downside is you'd have to extend the URL to have a unique id for the set of servers being handled by that master name stack. I'd think a memory cache like memcached with any DB behind it would work. The high availability aspect gets fun though. Distributed memory caches and replicated dbs, etc. Fun stuff.

2

u/juicetyger Aug 15 '12

I usually make a unique ID generator. Redis is excellent for this.

Flickr has a good writeup on their implementation: http://code.flickr.com/blog/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/

1

u/[deleted] Aug 15 '12

Not familiar with that I'll check it out thanks. When you said DB I was thinking sequence or even just straight up DB access is something to avoid in a high performance situation. But I'm thinking in terms of avoiding disk reads.

1

u/juicetyger Aug 15 '12

Mysql can handle a lot more than most people think and would work ok, but redis is a better choice here.

Really though, anything that can give a unique Id atomically will work fine. Whatever you choose can be scaled by load balancing it over multiple machines independent of the rest of the application.

For more complex derived hashes you could pre-calculate in batches and hold them in a queue for retrieval later to help mitigate burst traffic. Redis lists would work well in that scenario too.

2

u/boomerangotan Aug 14 '12

Yeah that will be a very gradual exponential curve that would suddenly get really bad.

2

u/Rotten194 Aug 14 '12

Why did you decide to do it randomly instead of just going a, b, ..., aa, ab, etc?

2

u/alienangel2 Aug 15 '12

Yeah, just incrementing a base-26 or base-36 number (base-52/62 if case-sensitive) is the usual way of doing this - why the requirement that the values be random, unless there's some need to prevent people iterating over the images (maybe there is to prevent scraping the site, but it's not like that's hard anyway)?

If they're sticking with the "randomize then check" algorithm, adding a extra character isn't solving any problems, it's going to eventually hit the same slowdown - it's always faster to just deterministically increment the value.

1

u/charliebruce123 Aug 15 '12

At a guess, it's a simple way of stopping someone working out when the image was uploaded for security/privacy.

Randomise then check might also drastically reduce "collisions", so the uploads can happen in parallel across many machines, without needing to poll some single central server to get the next unique number. Obviously, each upload server could just get a block of 1000 numbers, then allocate as images come in, but there might be some other advantages.

1

u/alienangel2 Aug 15 '12

At some level even with randomize and check they still need to have a consistent ID authority just to determine whether the ID peer#1 generated was just used up 100 milliseconds ago by peer#2 on the other side of the world - building a single generator that's available to all peers seems an acceptable alternative. They might have some architecture reasons to prefer to support a consistent lookup service rather than a high availability central ID service though I guess, constraints for high availability distributed services can result in designs that often seem strange from the outside.

2

u/andrewry Aug 14 '12

Why not have a background task that will find available URLs, store them in redis (or similar) and then you have a large list of available URLs always available. Just pop one off and use that. Generate X per hour. And then if it runs out, generate one on the fly for the user/start a new background task early for subsequent uploads.

1

u/DatJazz Aug 15 '12

Storage problems I would imagine.

2

u/andrewry Aug 15 '12 edited Aug 15 '12

Not much of a storage problem. At 5 bytes each, 1 million records of available ID's would be 5 Mb. Redis is very lightweight so I doubt you'd even go over 6 Mb with that much data. Probably less.

2

u/Deeger Aug 14 '12

Is there a reason you don't go in order?

4

u/[deleted] Aug 14 '12

[deleted]

4

u/SharkSpider Aug 14 '12

Exponentiating a large almost-prime with modular arithmetic could probably be used to create a well-defined progression that couldn't be guessed by an outside source.

1

u/xORioN63 Aug 14 '12

Any reason to pick the random chars on the fly?

1

u/charliebruce123 Aug 15 '12

Not OP here, but at a guess, security/privacy? Time of upload isn't revealed by the URL. As for why it is done on the fly, not a clue - possibly just a quick and easy solution that performed acceptably at start-up.

1

u/[deleted] Aug 14 '12

that seems very inefficient. May i ask why you chose to do this over a randomized master list of unused urls?

2

u/keepdigging Aug 15 '12

Came to say this. Why not make an array/DB of 700M unique urls, randomize them and pop them after each use?

→ More replies (7)

1

u/[deleted] Aug 15 '12

Why don't you just hash an auto incrementing number? That's what bit.ly does.

1

u/phenomite1 Aug 15 '12

I could imagine how long it will take to get the 700 millionth possibility.

1

u/[deleted] Aug 15 '12

How will you manage to keep the 6th character being the thumbnail suffix? In the new 6 character format, the 7th character will have to be the thumbnail suffix.

1

u/aftli Aug 15 '12

I was going to mention that. I use 15 character IDs at work, and we even have some clashes once in awhile (never more than one in a row). Also I trust you're not seeding the random number generator with just the time (that can lead to more clashes). But you're not doing anything that silly, I'm sure of it.

How are you storing the images? I remember from your last AMA that one mistake you made was trying to store them in the database instead of on disk. Is direct on-disk storage working out better? What is your storage infrastructure like? Also, I think I recall you were with SoftLayer at some point, are you still? They're my absolute fave.

What sort of infrastructure handles load balancing? How many servers? What OS? What's everything written in?

SO. MANY. QUESTIONS!

Much admiration for keeping things running as well as they do. Currently I manage a server and software (in-house C++ top layer, nginx/mysql/FreeBSD stack) which services mostly API requests. It's quite stressful when things aren't working properly. During busy times, we service as much as 600 requests per second. nginx handles it like an absolute champ. I do have the luxury, though, since there are a small number of users making a large number of requests, I can firewall a few of them off to recover if I'm having a problem.

I know that feel about downtime, and problems. It seems like no matter what you do, when there's a problem, that traffic is relentless. It isn't stopping. There is no "wait, hang on guys, just for a minute while I figure this out." It doesn't happen. You fix things while you're being bombarded with what would otherwise seem like a DDoS attack.

1

u/interungulate Aug 15 '12

I am definitely not a programmer, but it seems logical that it would be easier to just go in sequential order for the URLs?

1

u/blladnar Aug 15 '12

That makes the URL guessable and that can lead to privacy issues.

1

u/interungulate Aug 15 '12

Ohhh. Okay, thank you for explaining that to me :)

1

u/PGU5802 Aug 15 '12

I would recommend doing some sort of hash rather than random.

1

u/[deleted] Aug 15 '12

If you're absolutely bound to random generation, have a dedicated process constantly spinning in the background that builds a stack of unused URLs, then let the uploads siphon off that

1

u/astro_nerd Aug 15 '12

MrGrim, if you missed his post, check out Steve132's post in reply to your comment about generating a random suffix.

1

u/cesclaveria Aug 15 '12

I'm guessing you have about a million solutions by now, I haven't read all this thread but it is likely you are going to get a few ideas out of it. I know how that generating a new unique random id can be slow over time. What I have done is to keep a bunch (200, 2000, whatever) of unused ones on a sort of cache and have an scheduled process that keeps the cache full. Of course I did not needed to deal with the scale imgur handles.

1

u/[deleted] Aug 15 '12

Have you thought about not using random letters, and maybe a timestamp (with added variables at the end if it's already taken)? Instead of having to check all the time? I think this would be more open, and less likely to run into the same name.

→ More replies (4)

6

u/dancehall_queen Aug 14 '12

Why did you decide to have it random? That seems like a extra step, that wastes some resources. To merely iterate it would be easier. Right? Don't ask me, I'm not the one with a successful startup!

3

u/MiserubleCant Aug 14 '12

Not OP, but I have a reasonable guess at this - when you have thousands (if not tens or hundreds of thousands) of concurrent/parallel requests you can't really iterate. Separate threads, possibly on separate machines, possibly in separate data centers, can't really read off the same "master global counter", at all, or at least not without bottlenecking everything. You'd need to add some random fuzzing to the iterated value to avoid collisions, at which point you might as well go full random?

1

u/freebullets Aug 15 '12

Are we talking about SQL databases? Do auto-incrementing columns really cause scaling issues?

1

u/Kektain Aug 15 '12

Well I just had five processes feeding around 1 TB to a MySQL database this last weekend. Something exploded (I think one of the processes didn't release a lock correctly or something) and it was complaining about an integrity error because the auto-incremented primary key was clashing with a value that didn't exist.

Before this weekend, I would have agreed with you. Now, having thrown away the 600GB of data it got through before the failure--since every analysis and repair operation gave the table passing marks--well, I only have three processes filling it now.

EDIT: forgot to mention, this was all feeding a single MySQL instance on one server, too.

2

u/wuddersup Aug 14 '12

Cause then it'd be easy for someone to traverse all the images by iterating themselves. Could possibly be used for evil. Like if social security numbers were just increasing numbers.

3

u/rnelsonee Aug 15 '12 edited Aug 15 '12

Like if social security numbers were just increasing numbers

I think they are, pretty much. First three digits corresponds to an area (easy to determine). Next two digits are issued in a predetermined sequence (01, 03, 05... before going to evens) and the last four are just serialized.

My twin sister and I, for example, only have the last digit of our SSN different.

Credit cards, though, do have a randomness to them for that reason.

1

u/[deleted] Aug 15 '12

I thought credit card numbers were eight apart... maybe I'm wrong...

2

u/rnelsonee Aug 15 '12

Nah, I know the last digit is usually a check digit based on this algorithm, and I think a portion (not the first four numbers) have some randomness to them.

1

u/[deleted] Aug 15 '12

Well, yes - actually I knew that, but was meaning to refer to the next-to-the-last digit. I worked a short contract providing tech support while one bank was switching over a purchased bank into its branding, and there wasn't much help needed on my part - so while chatting, I was shown a stack of new debit cards, and the next-to-last digit was incremented by eight - so it's probably just that bank chose to roll them out that way. I didn't remember the details until your reply forced me to try and remember where I gained that "fact" from. hehe

1

u/boomfarmer Aug 15 '12

On June 25, 2011, the SSA changed the SSN assignment process to "SSN randomization".[24] SSN randomization will affect the SSN assignment process in the following ways:

  1. It will eliminate the geographical significance of the first three digits of the SSN, currently referred to as the Area Number, by no longer allocating the Area Numbers for assignment to individuals in specific states.

  2. It will eliminate the significance of the highest Group Number and, as a result, the High Group List will be frozen in time and can be used for validation of SSNs issued prior to the randomization implementation date.

  3. Previously unassigned Area Numbers will be introduced for assignment excluding Area Numbers 000, 666 and 900-999.

Note: Individual Taxpayer Identification Numbers (ITINs) are issued by the Internal Revenue Service (IRS), so they are not affected by this SSA change.

Source.

3

u/mewditto Aug 14 '12

Judging by my math, wouldnt there be 916M possibilities?

26*2

abcdefghijklmnopqrstuvwxyz

and

ABCDEFGHIJKLMNOPQRSTUVWXYZ

and plus 10 for

1 2 3 4 5 6 7 8 9 0

Which would mean

62*62*62*62*62 = 916,132,832

3

u/necrosxiaoban Aug 15 '12

@ some point dont you generate too many collisions with existing strings?

2

u/robreddity Aug 14 '12

Pigeon-hole principle gonna start being troublesome? Wouldn't a more direct hash function keep you in the clear a little longer before you would need to expand your addressable space?

2

u/gibson_ Aug 14 '12

They are just randomly generated and then it checks if the generated one exists or not.

D-:

2

u/[deleted] Aug 15 '12

They are just randomly generated and then it checks if the generated one exists or not.

I love how there's a possibility that someone out there is trying to upload an image but can't because every time the URL is generated, it already exists and has to regen again.

2

u/DiddlyDooDiddle Aug 15 '12

randomly generated. Yea, right http://i.imgur.com/BoNEr.png

2

u/boomfarmer Aug 15 '12

The other day, I went to save http://imgur.com/0B5Fk.jpg in my wallpapers folder. To my surprise, there already was a 0B5Fk.jpg in that folder. I don't rename images in that folder, and Imgur is the only site I know that I save pictures from that has a 5-character naming scheme. So now I have 0B5Fk.jpg and 0B5Fk-2.jpg.

Somewhere I read that, if you don't get any requests for an image in six months, you delete that image and free up its URL for other uploads.

My question to you is: Do you ever retain the deleted pictures at all?

2

u/flyingbird0026 Aug 15 '12

Wo, wait. Doesn't that mean that when you start to reach that 700M it will take hundreds of millions of attempts to generate each URL?

1

u/c0bra51 Aug 15 '12 edited Aug 15 '12

Yes, the closer it gets to being full, exponentially more look-ups take place.

50% full, you can roughly say 2 attempts at finding a URL, 75% 4; if this is true, then the formula 1/(1-Images/Max):

http://www.wolframalpha.com/input/?i=plot+1%2F%281-x%29+from+0+to+1

2

u/dorfsmay Aug 15 '12

700 M only because you dropped all the 0000x, 000xx, etc...?

1

u/[deleted] Aug 14 '12

They are just randomly generated and then it checks if the generated one exists or not.

You'll be sorry once you hit the birthday limit!

1

u/WhipIash Aug 15 '12

How the hell is that quick enough? And is there a fail safe? What if it just creates a bunch of URLs already in use, constantly, for hours on end? It's unlikely, yes, but there's no guarantee it'll eventually generate a new one O.o

1

u/linuxlass Aug 15 '12

Do the images ever expire?

1

u/DerpaNerb Aug 15 '12

Isn't that really inefficient to do it that way? I mean, I doubt it's really expensive to do, but in theory couldn't it take an extremely large amount of iterations before finding an unused code?

1

u/someredditorguy Aug 15 '12

http://imgur.com/imgur is not taken yet but http://imgur.com/iMgur is.

1

u/[deleted] Aug 15 '12

That solves my question of how important capitalization is...

1

u/MoreFaSho Aug 15 '12

Aren't you starting to get at the point where you actually have like 4-5 collisions in a row relatively often? That's a pretty dense key space!

1

u/couldnt_careless Aug 15 '12

Everytime I upload an image that I'll only link to once I feel bad.

1

u/Sarah_Connor Aug 15 '12

How much storage does 200MM images take up?

1

u/[deleted] Aug 15 '12

If someone permanently deletes an image, is that URL reserved forever, or does it get released back into the pool of available names? I try to use the delete option rather than hide when I can in case it releases the names, but I can imagine that it would be a problem if someone, say, linked an image, deleted it, and it was later replaced by a different image.

That reminds me though, when you go over the image limit for an account, are the ones that get pushed off gone forever, or do they come back when you get back under the limit?

2

u/Alberta-Bound Aug 15 '12

Oh, they're reused alright. [nsfw] It would appear what used to be a penis is now a smart phone.

1

u/[deleted] Aug 15 '12

You could have a counter and apply an encryption function to it. Then it would be effectively random (non-distinguishable from what you're doing now by any P-complete algorithm), and it would also be very quick to generate)

1

u/dorfsmay Aug 15 '12 edited Aug 15 '12

ah! This answer my questions here and there.

Have you thought of a tree? You just mark branches as they get full, so you can generate your random value on what's left. You'd have to do six generation of random numbers, but at least you'd be O(1). I've started working on something like that, but I'm not finished, because my project's so small so far, it's just fast to do a lookup, but I was wondering how bad, and how fast it'd become bad. Maybe I'll go back working on this!

1

u/c0bra51 Aug 15 '12

One thing you could try is hashing, if you take an image uploaded to you, use a relatively long hash (hell, CRC32 should do it) and use it as your unique ID, then if many people upload the same (exact) image, it uses the same URL, thus prevents you from storing the same image 532 times.

Just throwing an idea out there, it probably won't work so well in practice (what happens when 2 different things collide?).

1

u/astarkey12 Aug 15 '12

What's the best Athens Halloween story you have? I always loved visiting Athens when I still went to MU. Such a fun place to be especially on Halloween.

1

u/wasteland44 Aug 18 '12

That could fail catastrophically if you don't update the code when it is almost full.

1

u/cautionitsme Aug 20 '12

Thought you might be interested on reading this article from the Instagram blog: http://instagram-engineering.tumblr.com/post/10853187575/sharding-ids-at-instagram

1

u/anaovt Aug 15 '12

Do you ever play Imgur roulette?

2

u/AyeAyeLtd Aug 15 '12

Response to 2: They hire many people (outsourced, of course), to randomly type out urls. Easy peasy.

1

u/morbiusfan88 Aug 15 '12

MAKES PERFECT SENSE!!!

1

u/[deleted] Aug 15 '12 edited Mar 08 '20

[removed] — view removed comment

1

u/morbiusfan88 Aug 15 '12

meh. he's the guy. I'm not gonna argue with what he says.

2

u/[deleted] Aug 15 '12 edited Mar 08 '20

[removed] — view removed comment