Design a system to return an unique ID for each request. For most of requests, the ID value should increase as time goes, the system should handle 1000 requests per second at least. timestamps alone is not valid since there might be multiple requests with same timestamps.


第一种解法

We could use UUID. UUID may be generated from a combination of system time stamp, CPU / system unique ID, NIC MAC addresses, HBA WWNs etc.

Questions to ask:

  • What's the min length of the ID?
  • The requirement states the system should handle 1000 request/s at least.
  • What's the average request rate?
  • What's the max. burst rate the system must handle?
  • What's the max. latency (wait time) for a request?

Let's assume the following parameters:

  • What's the min length of the ID? <= 128 bits In that case I'll choose the standard 128 bit UUID format.
  • The requirement states the system should handle 1000 request/s at least.
  • What's the average request rate? 1000 < avg req. rate < 10,000
  • What's the max. burst rate the system must handle? < 1,000,000
  • What's the max. latency (wait time) for a request? 1 ms

It's a classical consumer-producer problem.
In this case we have many consumers of UUIDs and one producer.
All common server OS'es have API's to create UUIDs. For embedded/mobile systems one may have to build the functions. Let's assume the OS provides an API to generate UUIDs and the max. running time of the API is 1ms.

First, pre-allocate 2 Million UUIDs into an array / stack/ heap (depending on implementation) structure. 2 Million UUIDs ensures system can handle burst rate.


第二种解法

I think this question check if you could use thread synchronization.

  1. Create thread for each link.
  2. Create a variable for record ID, after there is thread read then do self-increasing. And set thread lock for it to avoid access conflict.

缺陷: In theory it will work if you are assuming it's all run in the same process space. However 1000 rps is 1ms per request. Thread synchronization will not keep up with such speeds (acquiring and releasing locks is expensive and usually takes longer than 1 ms). Since if you have to spawn multiple processes, the model you presented breaks.