1

I have little app that i plan to run behind load balancer, with up to 5-8 instances.

Inside the app has service, that needs to generate unique number that has up to 10 digits ( so 1-10 digits) each time user triggers the process.

There will be approximately 10-50k invocations of this function per month.

In non-distributed environment i was using DB's sequence to generate another unique number. I can still use this as central generator of numbers, however it would introduce single point of failure + it would be slower since every instance of my app would be getting number from single sequence ( but speed is not really issue ).

I was researching ways of generating unique numbers in distributed environment and found out about Twitter snowflake.

enter image description here

Since it includes timestamp it is possible to order the numbers by time which is plus.

However this is 64 bit number so it would be up for 20 digit number - i need maximum 10 thus i need log2(9999999999) + 1 bits = 34. Right now i have plan to have maximum 8 instances = 4 bits,

If i approximate 50k calls (as upper bound ) per month, include 3 years support, thats 50k*12*3 thats 1800000 calls divided by 8 ( number of instances ) and thats 225000, that is represented by 18 bits.

So i am left with

|12bits|4bits|18 bits|

Even if i set custom epoch time, i really cant save much milliseconds in 12 bits, thus this technique is not really usable for 34 bit number.

If i omit the timestamp part, and give up on ability to sort by time i can use

|_____4 bits for encoding node _____ |30 bits to encode number| which would give me much more space for sequence, and some space to include more nodes ( and use more than 4 bits for encoding it ).

However, what if i would need ability to sort? Is there any technique i have not found? Or what is "standard" ( or one of the standard ways ) to do so ?

Thanks for help! All links/techniques and everything that will send me down the rabbit hole much appreciated. Also, whe does the twitter snowflake needs leading 0 ? Cant they just assume Unsigned number?

3
  • 1
    "There will be approximately 10-50k invocations of this function per month." So about one invocation per minute? You are massively, massively over-engineering this. Commented Jan 31 at 19:35
  • @PhilipKendall do you mean it in context of "one invocation per minute" is not that much ( which probably isnt ) or 50k invocation is way too much and not realistic. I am pretty new to distributed env and scaling so im not really sure :). I am also over engineering it since its my toy project where i have chance to tinker with distributed systems and learn.
    – Darlyn
    Commented Jan 31 at 19:46
  • Why is GUID not suitable for the task?
    – Basilevs
    Commented Feb 1 at 8:44

2 Answers 2

2

I think you are massively overcomplicating things. Considering the "one invocation per minute", would you need a load balancer at all?

But let's take for granted that you decide to do this, and that you want Snowflake ID style IDs.

  • 8 worker instances is 3 bits, not 4.
  • The sequence number only needs to be able to distinguish the maximum number of invocations per millisecond per worker, not all invocations per worker. Quick sanity check: you don't need more bits for this than Twitter does. Honestly, you could probably get away with just a couple of bits. Let's be generous and reserve 6 bits for this. That means you can get away with 64 calls per millisecond per worker, which means you can handle some very intense spikes in traffic, given that you expect 1 call per 8 minutes per worker on average.
  • 34 bits is very awkward, either pick 64 bits or 32 bits. If you were to use 64 bits, there's no reason not to just copy the Snowflake ID scheme, so let's go with 32 bits for now.

We end up with this:

|                          32 bits                          |
| 23 bits timestamp | 3 bits worker id | 6 bits sequence id |

If you want millisecond resolution for the timestamp, that would give this scheme a total lifetime of 2^23 ms... which is less than two and a half hours.

So that's a bust. At this point you can either just implement Twitter's Snowflake ID, or just go with a sequential number from your DB. I don't think this particular aspect of your application will be a bottleneck, especially with only 8 workers, and only 1 call per minute on average. Just use a 64-bit auto-increasing ID and not worry about it any more.

2

Good, I am glad to see you are approaching the engineering trade-offs in the right way.

Within 10 digits, you have plenty of headroom. Two thousand calls per day, a thousand days, that sounds like 2 million serial members. Not even close to billions. So we have room to allocate bits for other things, such as timestamp, or server identity.

Your approach that used a database to hand out unique serials was a good one. We can adapt it to work here.

First, hold an election to see which host will be leader. Simplest approach would be oldest man standing, where the winner has oldest timestamp of joining the service, and he gets to keep being leader as long as we see current heartbeat time stamps from him. An alternative would be to use zookeeper, or preferably the Raft algorithm for distributed consensus.

OK, we have a leader. Leader can produce timestamp serial numbers for his own consumption. Followers will request blocks of unique serials from the leader. It would be convenient to request perhaps 100 or 128 serials at a time. A follower will always have a partial block that it is working through for current requests, and should also have a spare block that has not yet been used, but can be pressed into service at any moment. When that happens, follower will immediately make a request to the leader for a fresh block of serials. The size of the block, and the number of calls per second, determine two things. They affect how much time a Raft distributed consensus decision can spend before it must complete successfully, and they also determine how closely the sort order will reflect true timestamp order.


If you're keen to blow a few bits on the individual host identities, probably best to make those the low-order bits. Then we have a "mostly" chronological sort order. It's certainly not a causal order, since the only thing really sorted about it is the order in which blocks of serial were handed out. If that happens in blocks of 128, then masking out seven bits reveals how those blocks were handed out. And we get a partial order if we interpret serials as (block_num, increment) tuples, with increments being less than 128.

BTW I assume that 50k monthly transactions are not arriving "one per minute", but may arrive in clumps, for example in a market-close or end-of-quarter burst. Put another way, I did not read "uniform Poisson arrivals" into the OP requirements.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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