b*********n 发帖数: 1258 | 1 Design an algorithm to give unique id for each request, the id should be a
64 bit number. The algorithm should be scalable.
How to make each id unique?
我感觉应该用hash.
If the total memory can not hold all the numbers, we have to save it to Disk
, to get better performance, we don't save it each time an ID is created,but
saved as a block. How to make the id unique even if the machine crash some
ids doesn't write to the memory.
特别是这个问题,没有太好的思路.
还有就是网上看见相似的题目.
Given constant incoming requests, each ass | a*****e 发帖数: 51 | 2 (1) Why use hashing? Just using a global count, say id. When id is almost
overflow, reset it to 0. Something like id=id%0xFFFFFFFFFFFFFFFE.
(2) Use two global count, say blockID and tempID. id=blockID*BLOCK_SIZE+
tempID. When crash happens, retrieved the last blockID that is saved in disk
, id=(blockID+2)*BLOCK_SIZE+tempID.
(3) Estimate the time for one block (or several block, in order to improve
accuracy), #of unique requests=k*BLOCK_SIZE*T/t, where k is the number of
block in the first estima
【在 b*********n 的大作中提到】 : Design an algorithm to give unique id for each request, the id should be a : 64 bit number. The algorithm should be scalable. : How to make each id unique? : 我感觉应该用hash. : If the total memory can not hold all the numbers, we have to save it to Disk : , to get better performance, we don't save it each time an ID is created,but : saved as a block. How to make the id unique even if the machine crash some : ids doesn't write to the memory. : 特别是这个问题,没有太好的思路. : 还有就是网上看见相似的题目.
|
|