Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Say for example I was running a popular image host and all my images have an ID which they can be accessed by. If I wanted this ID to be sequential and not random what would be the best way to make sure two images uploaded at the same time don't get assigned the same ID by different processes/servers.

The best way I can think of is having different processes reserve a block for example one might reserve 1-1000 and the next one could reserve 1001-2000 so the IDs would never clash.

What is the best solution to this problem and how is it usually solved. It seems like most sites use a random ID. Is there a reason for this?

share|improve this question
    
Where did you get the idea that most sites use a random ID? Don't let URL string identifiers fool you, they exist for different reasons. – Alternatex Mar 1 at 9:29
4  
What is the benefit of sequential (kind of) IDs? – 5gon12eder Mar 1 at 9:46
    
@5gon12eder Only thing I can think of is its easier to run over them with a script which may or may not be important. – Qwertie Mar 1 at 10:00
    
@5gon12eder They can be grabbed more easily / associated with a range of frames in timeline editors and playback. – dval Mar 1 at 14:19
up vote 7 down vote accepted

The solution you described is called Hi/Lo and is one of the ways to solve this.

Reason why some sites still use random numbers are few :

With Hi/Lo, you still need some central authority to keep the track of the blocks. This might be problematic, because the stability requirements are huge for such system.

Related to above, with random numbers being used, the systems generating them don't have to rely on specific system, making them more portable.

Second reason is that it is not critical error if two items have same ID. It most probably result in error being shown to user if two same IDs are generated. But if the random space is big enough, sun will run out of fuel long before you get good enough chance to generate two same numbers. This chance goes even lower with some GUID generations guaranteeing uniqueness on single system. So generating same number twice would be an issue only in some extreme cases.

share|improve this answer

If you really need sequential ids, you can run a central service that hands out ids on request. Assuming you are happy to have holes in your sequence, this can be a very simple, very fast service, running on udp sockets and allocating blocks of ids in order to reduce storage bandwidth. The primary downside of this is that if the service fails you will lose the ability to create new objects, so some kind of fast failover will be necessary, which will increase complexity.

I do however question like @5gon12eder what benefit you'd gain from doing this.

share|improve this answer

The problem of coordination is that the coordinator has huge availability/consistency/latency requirements.

So, let's examine 4 simple solutions:

  • A single sequence generator
  • The Hi/Lo solution, with a single Hi generator
  • The Hi/Lo solution, where Hi is the node ID (immutable)
  • The random solution, where a random ID is generated

In the first two solutions, you have a single generator, and it will need to be available and consistent. In the first solution it will also need to reply quickly, whereas in the second if you provision in advance, it need not be as fast.

In the third solution, the single generator need be consistent, but it is only needed when creating a new node/process/thread, and its performance has no impact.

In the fourth solution, there is no single generator.


Note that you can revert the Hi/Lo by partitioning by Lo. For example, a simple scheme is:

  • Generate Hi as a monotonic timestamp of sufficient accuracy (monotonic means that if the timestamp has not advanced yet, you still bump by +1 to generate a new one)
  • Generate Lo from solution (3), preferably, or (2)

This way, you can mostly globally sort IDs generated by different entities in a global timeline.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.