logo
Redian新闻
>未名空间
>Programming - 葵花宝典
>
古德巴大牛，请看这个设计题
avatar
古德巴大牛，请看这个设计题# Programming - 葵花宝典
s*3
1 楼
本人2011年4月多开始的OPT,住在一个州,上班在另一个州,平时social security, Med
Care, state, federal都交了...
现在准备退税的时候一查原来social security 和 Med Care是不用给的,坑爹啊...
请问这个情况下federal和state的还能退么？
然后我到12年2月多点就是满五年,填表的时候应该是属于不满五年的nonresidents吧？
还有,我朋友说中国和美国有那个Tax treaty,但是只能退两年,2009,2010年,每年1000
刀,但是得证明你当时是学生什么的.
求大侠一一指教
avatar
f*a
2 楼
不能喝却喜欢喝，更不喜欢喝酒后微醺触动心灵的感觉。。。
感觉不好，尤其不想心动。。。
但是还是想喝，又没有合适的人一起喝，怎么破。。。？
avatar
p*p
3 楼
到底是啥? 就是左青龙,右白虎,老牛在腰间?
avatar
f*3
4 楼
设计一个系统，每次请求返回一个唯一的id，要求对大部分的请求做到后面请求的id要
比前面的大，要平均每秒能处理10000个请求，而且请求来自全球。还要求id尽量连续
，想过用时间做id，被毛子否了。
avatar
l*o
5 楼
真灵 即真灵之气。古人谓此存在于广袤的宇宙之中，是具有原始生命机能，能化生万
物的精微物质，为万物之本源。《素问·天元纪大论》：“太虚廖廓，肇基化元……布
气真灵，揔统神元。” .
avatar
g*g
6 楼
用时间是不行的，会冲突。我能想到的是time based UUID。源码这里有。但是连续就
比较够呛。
https://svn.apache.org/repos/asf/cassandra/trunk/src/java/org/apache/
cassandra/utils/UUIDGen.java

【在 f**********3 的大作中提到】
: 设计一个系统，每次请求返回一个唯一的id，要求对大部分的请求做到后面请求的id要
: 比前面的大，要平均每秒能处理10000个请求，而且请求来自全球。还要求id尽量连续
: ，想过用时间做id，被毛子否了。
avatar
l*d
7 楼
目前出现的最牛B的级别了，基本是，凡人灌水看来是没有止境了。
avatar
f*3
8 楼
这是狗家一毛子出的，说不需要严格连续，但是要尽量，我提了4种方案都被否了...
是不是被黑了

【在 g*****g 的大作中提到】
: 用时间是不行的，会冲突。我能想到的是time based UUID。源码这里有。但是连续就
: 比较够呛。
: https://svn.apache.org/repos/asf/cassandra/trunk/src/java/org/apache/
: cassandra/utils/UUIDGen.java
avatar
l*d
9 楼
怎么哪个版都能看到你的影踪啊。

【在 p*******p 的大作中提到】
: 到底是啥? 就是左青龙,右白虎,老牛在腰间?
avatar
g*g
10 楼
如果不用写盘，在内存里放个AtomicLong，或许能顶住1万次/s。但数据库ID一般是不
会这么做的。

【在 f**********3 的大作中提到】
: 这是狗家一毛子出的，说不需要严格连续，但是要尽量，我提了4种方案都被否了...
: 是不是被黑了
avatar
f*3
11 楼
我也觉得这个问题没有意义。毛子还说10000次/s只是平均值，有可能峰值很大，也可
能有时基本没有请求。全球同步，毛子不是想spanner吧，这update一次全球同步一次
，光网络时间都不值这么多了。

【在 g*****g 的大作中提到】
: 如果不用写盘，在内存里放个AtomicLong，或许能顶住1万次/s。但数据库ID一般是不
: 会这么做的。
avatar
g*g
12 楼
这种情况，通常都是用time based uuid，就是一个时间+ IP address + synchronized
counter on host. 不同机器无需同步可以保证唯一。老毛子多半是故意刁难。

【在 f**********3 的大作中提到】
: 我也觉得这个问题没有意义。毛子还说10000次/s只是平均值，有可能峰值很大，也可
: 能有时基本没有请求。全球同步，毛子不是想spanner吧，这update一次全球同步一次
: ，光网络时间都不值这么多了。
avatar
f*3
13 楼
好吧，算我倒霉。不过还是感谢这个uuid的方法，学习了。

synchronized

【在 g*****g 的大作中提到】
: 这种情况，通常都是用time based uuid，就是一个时间+ IP address + synchronized
: counter on host. 不同机器无需同步可以保证唯一。老毛子多半是故意刁难。
avatar
g*g
14 楼
我说错了，应该是mac address。

【在 f**********3 的大作中提到】
: 好吧，算我倒霉。不过还是感谢这个uuid的方法，学习了。
:
: synchronized
avatar
z*e
15 楼
uuid一般怎么做？
我一般是用毫秒数加上机器编号，然后syncrhonized生成方法做
不过因为cpu无法精确到毫秒，所以还是要存上一个生成的数字
然后比较，如果相同的话，+1

synchronized

【在 g*****g 的大作中提到】
: 这种情况，通常都是用time based uuid，就是一个时间+ IP address + synchronized
: counter on host. 不同机器无需同步可以保证唯一。老毛子多半是故意刁难。
avatar
g*g
16 楼
Time+ mac address +
synchronized counter on host.
上面的Link有实现。

【在 z****e 的大作中提到】
: uuid一般怎么做？
: 我一般是用毫秒数加上机器编号，然后syncrhonized生成方法做
: 不过因为cpu无法精确到毫秒，所以还是要存上一个生成的数字
: 然后比较，如果相同的话，+1
:
: synchronized
avatar
f*3
17 楼
其实当时想了个类似的，加上每个机器的"offset"，但是毛子说还要连续就吐血了...
魏老师的nb单机是不是能做到？ 但是毛子会说不scalable

【在 g*****g 的大作中提到】
: 我说错了，应该是mac address。
avatar
g*g
18 楼
得，你说UUID，老毛子最多不满意。你说魏老师的单机很牛逼，无限scalable，
老毛子多半把你轰出去了。

【在 f**********3 的大作中提到】
: 其实当时想了个类似的，加上每个机器的"offset"，但是毛子说还要连续就吐血了...
: 魏老师的nb单机是不是能做到？ 但是毛子会说不scalable
avatar
c*t
19 楼
可以是每台 id server 每次从 block server 那里要一个 block of IDs 。用完或者
级秒钟以后再从 block server 那里要。
这样的话，该 id server 里拿到的 id 应该是连续的。因为每隔几秒（根据 load
等来决定）或者 id block 用完，所以总的来说 id 是朝大方向走。

【在 g*****g 的大作中提到】
: 如果不用写盘，在内存里放个AtomicLong，或许能顶住1万次/s。但数据库ID一般是不
: 会这么做的。
avatar
b*s
20 楼
估计基本就是几个考点吧，一个是并发能力和同步,就是你一个要有减少同步的锁的开
支和减少每次计算负荷的概念，一个是看你有没有对容量的考虑，我估计基本需要设计
大数类型，否则你的这个ID如果是个int什么的没多久就overflow了，而且要讲出为什
么设计那么长度的数，这个考察你对用户容量的估计，第三个是看你能不能找到或者炮
制一个ever increasing的量，要简单，不需要大量计算，考虑到每秒要10000个请求，
你用时间tick肯定是不行的，这个每秒才1000个增量，需要做额外的计算，不需要计算
的你至少采样率要到你服务数量的2倍甚至更高，奈奎斯特频率嘛
我的直观感觉是可以用cpu clock tick,加到每次服务初始化的一个量，这个量可以是
上次的最后一个id值。
然后一个线程负责拿clock tick，这个线程polling次数不要超过3万/秒，但也别低于2
万/秒，看看有没有机器指令集支持这个好了。可以绑在一个核上
然后就是服务线程，其实和取时间的线程，还是个老掉牙的rw lock，算一下服务线程
的数量，满足服务请求能力就行，反过来可以推算系统硬件需求
然后考虑这个系统比如要运行5年，反过来可以推算你的id的字长是多少

【在 f**********3 的大作中提到】
: 设计一个系统，每次请求返回一个唯一的id，要求对大部分的请求做到后面请求的id要
: 比前面的大，要平均每秒能处理10000个请求，而且请求来自全球。还要求id尽量连续
: ，想过用时间做id，被毛子否了。
avatar
z*e
21 楼
那就找单个node专门出id咯

【在 f**********3 的大作中提到】
: 其实当时想了个类似的，加上每个机器的"offset"，但是毛子说还要连续就吐血了...
: 魏老师的nb单机是不是能做到？ 但是毛子会说不scalable
avatar
b*s
22 楼
use time stamp counter of CPU
avatar
b*s
23 楼
这个设计有一部分是有问题的，我再想想

于2

【在 b*******s 的大作中提到】
: 估计基本就是几个考点吧，一个是并发能力和同步,就是你一个要有减少同步的锁的开
: 支和减少每次计算负荷的概念，一个是看你有没有对容量的考虑，我估计基本需要设计
: 大数类型，否则你的这个ID如果是个int什么的没多久就overflow了，而且要讲出为什
: 么设计那么长度的数，这个考察你对用户容量的估计，第三个是看你能不能找到或者炮
: 制一个ever increasing的量，要简单，不需要大量计算，考虑到每秒要10000个请求，
: 你用时间tick肯定是不行的，这个每秒才1000个增量，需要做额外的计算，不需要计算
: 的你至少采样率要到你服务数量的2倍甚至更高，奈奎斯特频率嘛
: 我的直观感觉是可以用cpu clock tick,加到每次服务初始化的一个量，这个量可以是
: 上次的最后一个id值。
: 然后一个线程负责拿clock tick，这个线程polling次数不要超过3万/秒，但也别低于2
avatar
b*s
24 楼
嗯，锁策略改一下就行了，这下polling线程的负荷也下来了
avatar
b*s
25 楼
context switching的开销需要做点实验，先预估理论值，然后调整
avatar
P*l
26 楼
101个机器连续给号。100个机器先向头要个号,然后自己产生0到99,结果是头×100+自
己。
其它机器向这100个机器要号。如何?

【在 f**********3 的大作中提到】
: 设计一个系统，每次请求返回一个唯一的id，要求对大部分的请求做到后面请求的id要
: 比前面的大，要平均每秒能处理10000个请求，而且请求来自全球。还要求id尽量连续
: ，想过用时间做id，被毛子否了。
avatar
z*e
27 楼
魏老师的nb单机是不是能做到？
这个太有喜感了

【在 f**********3 的大作中提到】
: 其实当时想了个类似的，加上每个机器的"offset"，但是毛子说还要连续就吐血了...
: 魏老师的nb单机是不是能做到？ 但是毛子会说不scalable
avatar
b*s
28 楼
我这个也是不能扩展的方案，可扩展方案迟一点我也弄一个。google里面还是c++和
python党的天下，他们的思考习惯和魏老师估计比较接近
avatar
l*s
29 楼
不是有微秒级别的系统时钟吗？

【在 z****e 的大作中提到】
: uuid一般怎么做？
: 我一般是用毫秒数加上机器编号，然后syncrhonized生成方法做
: 不过因为cpu无法精确到毫秒，所以还是要存上一个生成的数字
: 然后比较，如果相同的话，+1
:
: synchronized
avatar
l*s
30 楼
cpu clock tick 这个主意好！

于2

【在 b*******s 的大作中提到】
: 估计基本就是几个考点吧，一个是并发能力和同步,就是你一个要有减少同步的锁的开
: 支和减少每次计算负荷的概念，一个是看你有没有对容量的考虑，我估计基本需要设计
: 大数类型，否则你的这个ID如果是个int什么的没多久就overflow了，而且要讲出为什
: 么设计那么长度的数，这个考察你对用户容量的估计，第三个是看你能不能找到或者炮
: 制一个ever increasing的量，要简单，不需要大量计算，考虑到每秒要10000个请求，
: 你用时间tick肯定是不行的，这个每秒才1000个增量，需要做额外的计算，不需要计算
: 的你至少采样率要到你服务数量的2倍甚至更高，奈奎斯特频率嘛
: 我的直观感觉是可以用cpu clock tick,加到每次服务初始化的一个量，这个量可以是
: 上次的最后一个id值。
: 然后一个线程负责拿clock tick，这个线程polling次数不要超过3万/秒，但也别低于2
avatar
l*s
31 楼
cpu clock tick 这个主意好！

于2

【在 b*******s 的大作中提到】
: 估计基本就是几个考点吧，一个是并发能力和同步,就是你一个要有减少同步的锁的开
: 支和减少每次计算负荷的概念，一个是看你有没有对容量的考虑，我估计基本需要设计
: 大数类型，否则你的这个ID如果是个int什么的没多久就overflow了，而且要讲出为什
: 么设计那么长度的数，这个考察你对用户容量的估计，第三个是看你能不能找到或者炮
: 制一个ever increasing的量，要简单，不需要大量计算，考虑到每秒要10000个请求，
: 你用时间tick肯定是不行的，这个每秒才1000个增量，需要做额外的计算，不需要计算
: 的你至少采样率要到你服务数量的2倍甚至更高，奈奎斯特频率嘛
: 我的直观感觉是可以用cpu clock tick,加到每次服务初始化的一个量，这个量可以是
: 上次的最后一个id值。
: 然后一个线程负责拿clock tick，这个线程polling次数不要超过3万/秒，但也别低于2
avatar
N*n
32 楼
我来出个主意吧。你没有提到并行处理，所以假设单流程处理
ID分两段。
第一段 是一个 int number. 这个 INT number 从时间零点开始每秒+1。
第二段 counter m bit(m>14,可以用16bit) 1024x16=16384 之间的数字。每来一个新
请求，则+1.新的一秒开始，则清零重新开始
如果要多流程，彼此不通讯，
假设是 Master-worker arch-tech. 则每个worker node get a unique identifier.
for 16 workers, 0-15
If u want to identify the source of request, u could add x bit,
which is from the 1st x bit of IP. x could be 8. This part can be optimized
, based on IP来源的频率分析.
比如 你统计发现 40% request coming from 199.126.* 30%request
from 17.* 30% from all other IP.
在一个简单的 2bit 系统，可以给所有 199.126。* 请求
一个 特殊的ID: 00； 17.* ： 01, all others IPs： 10, bit 11 is reserved
in case one of the 3 有超常溢出 etc.. 依次类推，也可以把它变成4bit系统
*****
当然这样分了以后 上面的第二段counter 可以可以相应加少 bit到大约8bit.
time_int,worker_bits(4),IP_bits(4),counter_bits(8)
如果嫌这样麻烦也可以直接
time_int,IP(8bit),counter(8bit)
只要IP分布不是特别偏，可以没问题。
***************
补：如果用上coconut的 block server 的概念应该能更保险。。

【在 f**********3 的大作中提到】
: 设计一个系统，每次请求返回一个唯一的id，要求对大部分的请求做到后面请求的id要
: 比前面的大，要平均每秒能处理10000个请求，而且请求来自全球。还要求id尽量连续
: ，想过用时间做id，被毛子否了。
avatar
d*e
33 楼
经典老题用个counter 哦 over

【在 f**********3 的大作中提到】
: 设计一个系统，每次请求返回一个唯一的id，要求对大部分的请求做到后面请求的id要
: 比前面的大，要平均每秒能处理10000个请求，而且请求来自全球。还要求id尽量连续
: ，想过用时间做id，被毛子否了。
avatar
d*e
34 楼
当然

【在 z****e 的大作中提到】
: 魏老师的nb单机是不是能做到？
: 这个太有喜感了
avatar
x*d
35 楼
would you consider zookeeper? you know, you can generate sequential with
zookeeper. it is not continuous, but distributed. it is said a little bit
slow, but don't know how slow.
for interview, I would slap this on the table, with UUID, if they don't like
, then try implement it raw, but I doubt I can do better than ZK during the
interview, you know short period of time, pressure.
backup your ZK solution with teacherWei's single machine design, 10k/s is
piece of cake. LOL.
avatar
f*4
36 楼
学习了～

optimized

【在 N*n 的大作中提到】
: 我来出个主意吧。你没有提到并行处理，所以假设单流程处理
: ID分两段。
: 第一段 是一个 int number. 这个 INT number 从时间零点开始每秒+1。
: 第二段 counter m bit(m>14,可以用16bit) 1024x16=16384 之间的数字。每来一个新
: 请求，则+1.新的一秒开始，则清零重新开始
: 如果要多流程，彼此不通讯，
: 假设是 Master-worker arch-tech. 则每个worker node get a unique identifier.
: for 16 workers, 0-15
: If u want to identify the source of request, u could add x bit,
: which is from the 1st x bit of IP. x could be 8. This part can be optimized
avatar
N*n
37 楼
互相学习。。:)

【在 f****4 的大作中提到】
: 学习了～
:
: optimized
avatar
c*o
38 楼
Mongodb的object ID不就是这样么?
avatar
P*l
39 楼
如果一台机器给其他机器产生id, 直接+１不就行了吗？
你这种方式也不能保证两台机器独立产生id.
还有，这道题非常实际． 那个id越有顺序越好．比如保证id(i)为数据库往往id相邻的逻辑上／物理上也相邻．

optimized

【在 N*n 的大作中提到】
: 我来出个主意吧。你没有提到并行处理，所以假设单流程处理
: ID分两段。
: 第一段 是一个 int number. 这个 INT number 从时间零点开始每秒+1。
: 第二段 counter m bit(m>14,可以用16bit) 1024x16=16384 之间的数字。每来一个新
: 请求，则+1.新的一秒开始，则清零重新开始
: 如果要多流程，彼此不通讯，
: 假设是 Master-worker arch-tech. 则每个worker node get a unique identifier.
: for 16 workers, 0-15
: If u want to identify the source of request, u could add x bit,
: which is from the 1st x bit of IP. x could be 8. This part can be optimized
avatar
g*g
40 楼
实际中time uuid 够用了。而且可以 client产生。也相邻，id 连续在 DB 里意义不大。

【在 P********l 的大作中提到】
: 如果一台机器给其他机器产生id, 直接+１不就行了吗？
: 你这种方式也不能保证两台机器独立产生id.
: 还有，这道题非常实际． 那个id越有顺序越好．比如保证id(i): 为数据库往往id相邻的逻辑上／物理上也相邻．
:
: optimized
avatar
P*l
41 楼
这要看那个数据库了．

大。

【在 g*****g 的大作中提到】
: 实际中time uuid 够用了。而且可以 client产生。也相邻，id 连续在 DB 里意义不大。
avatar
m*l
42 楼
这个是对的

【在 P********l 的大作中提到】
: 这要看那个数据库了．
:
: 大。
avatar
N*n
43 楼

从出题的角度，明显不是这个意思。。 如果这样是全连续的。
多机下，每个worker node/机器 有自己的ID 段。独立产生 ID。

【在 P********l 的大作中提到】
: 如果一台机器给其他机器产生id, 直接+１不就行了吗？
: 你这种方式也不能保证两台机器独立产生id.
: 还有，这道题非常实际． 那个id越有顺序越好．比如保证id(i): 为数据库往往id相邻的逻辑上／物理上也相邻．
:
: optimized
avatar
P*l
44 楼
那个uuid就是产生这个ID段的．它利用了mac地址（基本）唯一这个特点．
IP不行，因为有private ip address space.

【在 N*n 的大作中提到】
:
: 从出题的角度，明显不是这个意思。。 如果这样是全连续的。
: 多机下，每个worker node/机器 有自己的ID 段。独立产生 ID。
avatar
g*g
45 楼
我想起来了，我们给 rdbms分 id 的做法是前头应用服务器集群去数据库某个sequence
表里
做个加法取一段。接下来一直加一到这段用完为止。结点坏了，会跳过一些 id, 但不
会重复，这个貌似满足他的要求。
avatar
N*n
46 楼
NAT 我当然知道。。所以有后面的IP request 频率分析。。
private IP, 我想你说的10.*, 192.168.* 。。在2bit system, 他们都是在
其它之列。。
如果是 8比特。。就是直接用IP四个数的头一个，那 private IP, 不用的那个刚好
可以做备用。。
MAC 唯一不错，但是用上MAC,全球request..你怎么保证 ID连续？

【在 P********l 的大作中提到】
: 那个uuid就是产生这个ID段的．它利用了mac地址（基本）唯一这个特点．
: IP不行，因为有private ip address space.
avatar
P*l
47 楼
他要10000次／s, 还全球的．

sequence

【在 g*****g 的大作中提到】
: 我想起来了，我们给 rdbms分 id 的做法是前头应用服务器集群去数据库某个sequence
: 表里
: 做个加法取一段。接下来一直加一到这段用完为止。结点坏了，会跳过一些 id, 但不
: 会重复，这个貌似满足他的要求。
avatar
N*n
48 楼
你是在G家工作，还是面试题啊？

【在 f**********3 的大作中提到】
: 这是狗家一毛子出的，说不需要严格连续，但是要尽量，我提了4种方案都被否了...
: 是不是被黑了
avatar
g*g
49 楼
这个没问题， 是个集群。10个，100个机器都行。

【在 P********l 的大作中提到】
: 他要10000次／s, 还全球的．
:
: sequence
avatar
f*3
50 楼
当然是面试题

【在 N*n 的大作中提到】
: 你是在G家工作，还是面试题啊？
avatar
p*2
51 楼
这个用AKKA就可以轻松搞定了吧？
avatar
f*3
52 楼
请问二爷这个的原理是什么，我的思路如果不用时间或者uuid的话，毛子说全球，就是
服务器要分布在全球，然后看某个id用过没，就要全球同步，可能就是有些近似算法，
允许一定程度的顺序错乱，但是大大减少同步的次数。在现有的id pool用完之前，下
一次同步已经完成，这样用户就感觉不到wait time。等我下了飞机把我最后提出的思
路详细写写，毛子还是不满意，还要随时增加减少服务器都可以。我提了个方案应该能
做到。对我一只写过单服务器的new grad，至于吗？

【在 p*****2 的大作中提到】
: 这个用AKKA就可以轻松搞定了吧？
avatar
g*g
53 楼
我说的是用一个集群，这个集群也可以全世界分布。一个中心数据库。这个集群的每个
结点每次
到数据库上读当前好，比如100万，然后加上区段长度，10万，写回110万。这样那个结
点就预留了100万-110万，下个结点来拿就是110万-120万，不会跟其他结点冲突。每次
被request的时候，给出当前ID，计数加1即可。

【在 f**********3 的大作中提到】
: 请问二爷这个的原理是什么，我的思路如果不用时间或者uuid的话，毛子说全球，就是
: 服务器要分布在全球，然后看某个id用过没，就要全球同步，可能就是有些近似算法，
: 允许一定程度的顺序错乱，但是大大减少同步的次数。在现有的id pool用完之前，下
: 一次同步已经完成，这样用户就感觉不到wait time。等我下了飞机把我最后提出的思
: 路详细写写，毛子还是不满意，还要随时增加减少服务器都可以。我提了个方案应该能
: 做到。对我一只写过单服务器的new grad，至于吗？
avatar
N*n
54 楼
这就是 coconut说的那个吧
确实不错，而且加node/服务器 也没问题

【在 g*****g 的大作中提到】
: 我说的是用一个集群，这个集群也可以全世界分布。一个中心数据库。这个集群的每个
: 结点每次
: 到数据库上读当前好，比如100万，然后加上区段长度，10万，写回110万。这样那个结
: 点就预留了100万-110万，下个结点来拿就是110万-120万，不会跟其他结点冲突。每次
: 被request的时候，给出当前ID，计数加1即可。
avatar
P*l
55 楼
那个中心数据库就是将来的bottleneck.

【在 g*****g 的大作中提到】
: 我说的是用一个集群，这个集群也可以全世界分布。一个中心数据库。这个集群的每个
: 结点每次
: 到数据库上读当前好，比如100万，然后加上区段长度，10万，写回110万。这样那个结
: 点就预留了100万-110万，下个结点来拿就是110万-120万，不会跟其他结点冲突。每次
: 被request的时候，给出当前ID，计数加1即可。
avatar
g*g
56 楼
这个应该不会。比如我说10个server，区段是10万，一秒1万的话，
100秒才需要写这个数据库10次，每个server来数据库写一次。平均10秒一次，完全没
压力。
多几个数量级都还很轻松。

【在 P********l 的大作中提到】
: 那个中心数据库就是将来的bottleneck.
avatar
N*n
57 楼
这个设计如果说有缺点就是不一定保证后面的request 比前面的数大。如果每个站的
request不一样。。

【在 g*****g 的大作中提到】
: 这个应该不会。比如我说10个server，区段是10万，一秒1万的话，
: 100秒才需要写这个数据库10次，每个server来数据库写一次。平均10秒一次，完全没
: 压力。
: 多几个数量级都还很轻松。
avatar
P*l
58 楼
我也想问类似的问题．那个reqest的粒度（一次要几个id)没有控制．如果有哪个应用
不合作，一个一个地要，就有问题了．

【在 N*n 的大作中提到】
: 这个设计如果说有缺点就是不一定保证后面的request 比前面的数大。如果每个站的
: request不一样。。
avatar
x*d
59 楼
用zookeeper也是一段一段要。其实就是把zookeeper当成你说的block server。但不知
道为什么会慢。如果zookeeper会慢，我想自己做的东西也会慢。

【在 c*****t 的大作中提到】
: 可以是每台 id server 每次从 block server 那里要一个 block of IDs 。用完或者
: 级秒钟以后再从 block server 那里要。
: 这样的话，该 id server 里拿到的 id 应该是连续的。因为每隔几秒（根据 load
: 等来决定）或者 id block 用完，所以总的来说 id 是朝大方向走。
avatar
g*g
60 楼
zookeeper要比数据库里，一个row的锁慢得多。

【在 x****d 的大作中提到】
: 用zookeeper也是一段一段要。其实就是把zookeeper当成你说的block server。但不知
: 道为什么会慢。如果zookeeper会慢，我想自己做的东西也会慢。
avatar
x*d
61 楼
cassandra 和其他nosql 的auto increment怎么解决的？cassandra好象有个counter的
东西，那个是干啥的？
avatar
g*g
62 楼
Cassandra一般用UUID，ID即使连续，也不是存一块的，没有意义。Cassandra有个
distributed counter，挺复杂，你可以看看。
http://www.datastax.com/wp-content/uploads/2011/07/cassandra_sf

【在 x****d 的大作中提到】
: cassandra 和其他nosql 的auto increment怎么解决的？cassandra好象有个counter的
: 东西，那个是干啥的？
avatar
p*2
63 楼

AKKA就是大型分布式计算系统。是一个树形结构。最上边的节点掌控全局，也就是掌控
所有的ID。下边一层想发ID，都要向上边去要。下边可以每个地区一个supervisor, 根
据各个地区的request的量再往下分，一直到可以handle为止。因为是树，所以层次很
浅就可以handle很大的量.

【在 f**********3 的大作中提到】
: 请问二爷这个的原理是什么，我的思路如果不用时间或者uuid的话，毛子说全球，就是
: 服务器要分布在全球，然后看某个id用过没，就要全球同步，可能就是有些近似算法，
: 允许一定程度的顺序错乱，但是大大减少同步的次数。在现有的id pool用完之前，下
: 一次同步已经完成，这样用户就感觉不到wait time。等我下了飞机把我最后提出的思
: 路详细写写，毛子还是不满意，还要随时增加减少服务器都可以。我提了个方案应该能
: 做到。对我一只写过单服务器的new grad，至于吗？
avatar
x*d
64 楼
为啥呢？我没深入研究，但表面看不应该呀。
听说是慢，但应该不会慢过10000/s平均吧。而且实施时候并不是每个都从zk生成，而
是一段一段取，用魏老师的nb单机单机去取出来在分配出去，9million/s没问题呀。
lol

【在 g*****g 的大作中提到】
: zookeeper要比数据库里，一个row的锁慢得多。
avatar
g*g
65 楼
我没说ZK不行，我纯粹说比DB慢而已。distributed lock肯定比DB single row lock慢
呀。
另外，就是当年最高ID得找个地方存着，你不能丢了。

【在 x****d 的大作中提到】
: 为啥呢？我没深入研究，但表面看不应该呀。
: 听说是慢，但应该不会慢过10000/s平均吧。而且实施时候并不是每个都从zk生成，而
: 是一段一段取，用魏老师的nb单机单机去取出来在分配出去，9million/s没问题呀。
: lol
avatar
P*l
66 楼
我印象里google app engine里id改过一次．以前产生的id是分散的，后来改成的连续
的了．（没狗到．）

【在 g*****g 的大作中提到】
: Cassandra一般用UUID，ID即使连续，也不是存一块的，没有意义。Cassandra有个
: distributed counter，挺复杂，你可以看看。
: http://www.datastax.com/wp-content/uploads/2011/07/cassandra_sf
avatar
k*g
67 楼

应该就是spanner。他是纯考你的见识。

【在 f**********3 的大作中提到】
: 我也觉得这个问题没有意义。毛子还说10000次/s只是平均值，有可能峰值很大，也可
: 能有时基本没有请求。全球同步，毛子不是想spanner吧，这update一次全球同步一次
: ，光网络时间都不值这么多了。
avatar
P*l
68 楼
zkss. spanner有id的特殊处理？

【在 k**********g 的大作中提到】
:
: 应该就是spanner。他是纯考你的见识。
avatar
b*s
69 楼
It makes heavy use of hardware-assisted time synchronization using GPS
clocks and atomic clocks to ensure global consistency.
用你们的那些方法，要保持一致overhead是不低的，还是要找个自然的硬件的方法

【在 P********l 的大作中提到】
: zkss. spanner有id的特殊处理？
avatar
b*s
70 楼
机器编号你很难控制，mac和ip都是可以修改的
cpu可以精确到cycles

【在 z****e 的大作中提到】
: uuid一般怎么做？
: 我一般是用毫秒数加上机器编号，然后syncrhonized生成方法做
: 不过因为cpu无法精确到毫秒，所以还是要存上一个生成的数字
: 然后比较，如果相同的话，+1
:
: synchronized
avatar
b*s
71 楼
这个设计完全没考虑id servers产生重复的id

【在 c*****t 的大作中提到】
: 可以是每台 id server 每次从 block server 那里要一个 block of IDs 。用完或者
: 级秒钟以后再从 block server 那里要。
: 这样的话，该 id server 里拿到的 id 应该是连续的。因为每隔几秒（根据 load
: 等来决定）或者 id block 用完，所以总的来说 id 是朝大方向走。
avatar
b*s
72 楼
这是瓶颈

【在 z****e 的大作中提到】
: 那就找单个node专门出id咯
avatar
b*s
73 楼
你如何保证100个机器不产生冲突的号？解决冲突的代价很大的，别小看，你也无法控
制客户要到的号码是递增的

自

【在 P********l 的大作中提到】
: 101个机器连续给号。100个机器先向头要个号,然后自己产生0到99,结果是头×100+自
: 己。
: 其它机器向这100个机器要号。如何?
avatar
p*2
74 楼

我那个分层的有什么问题吗？

【在 b*******s 的大作中提到】
: 这是瓶颈
avatar
b*s
75 楼
ip放进id里面我觉得是个坏主意，不能保证递增

optimized

【在 N*n 的大作中提到】
: 我来出个主意吧。你没有提到并行处理，所以假设单流程处理
: ID分两段。
: 第一段 是一个 int number. 这个 INT number 从时间零点开始每秒+1。
: 第二段 counter m bit(m>14,可以用16bit) 1024x16=16384 之间的数字。每来一个新
: 请求，则+1.新的一秒开始，则清零重新开始
: 如果要多流程，彼此不通讯，
: 假设是 Master-worker arch-tech. 则每个worker node get a unique identifier.
: for 16 workers, 0-15
: If u want to identify the source of request, u could add x bit,
: which is from the 1st x bit of IP. x could be 8. This part can be optimized
avatar
b*s
76 楼
用客户方信息来保证唯一性是不可靠的，而且是额外增加负荷的

【在 P********l 的大作中提到】
: 那个uuid就是产生这个ID段的．它利用了mac地址（基本）唯一这个特点．
: IP不行，因为有private ip address space.
avatar
b*s
77 楼
赞，这个是到点子上了

【在 k**********g 的大作中提到】
:
: 应该就是spanner。他是纯考你的见识。
avatar
b*s
78 楼
效率低下

【在 p*****2 的大作中提到】
:
: 我那个分层的有什么问题吗？
avatar
b*s
79 楼
我那个方案是用cpu cycles，而google实际上用的是专门的原子钟和gps时钟，gps时钟
是全球同步的，10ns的误差，对于题目里给的够用了，原子钟估计是给分布在各地的服
务器矫正用的
avatar
d*e
80 楼
用上计算机了， 简单说几句。
第一，这题我面过，counter必过无疑。
第二，毛子讲更加清楚。10000这个数不是白给你的。
这里主要靠你知识面，看到10千，有经验的就知道考c10k问题了。
那么前端上任何 c10k server,基本上就是async的了。单机搞定。
后面要么自己写个简单函数/类, counter＋＋搞定。
要么上redis incr，我估计你说出用比如node.js, tornando+redis后面就不用多问了。
follow up可能要问你上百万 requests怎么办。这时你再发挥吧。
这么简单的问题上集群的都是扯淡。

【在 f**********3 的大作中提到】
: 设计一个系统，每次请求返回一个唯一的id，要求对大部分的请求做到后面请求的id要
: 比前面的大，要平均每秒能处理10000个请求，而且请求来自全球。还要求id尽量连续
: ，想过用时间做id，被毛子否了。
avatar
b*s
81 楼
用数据库来做这个，又是锤子党了，非常糟糕的想法，人家用这个服务就是给数据库提
供服务的，你们倒好，先来个数据库
avatar
b*s
82 楼
counter是最直观的想法

了。

【在 d******e 的大作中提到】
: 用上计算机了， 简单说几句。
: 第一，这题我面过，counter必过无疑。
: 第二，毛子讲更加清楚。10000这个数不是白给你的。
: 这里主要靠你知识面，看到10千，有经验的就知道考c10k问题了。
: 那么前端上任何 c10k server,基本上就是async的了。单机搞定。
: 后面要么自己写个简单函数/类, counter＋＋搞定。
: 要么上redis incr，我估计你说出用比如node.js, tornando+redis后面就不用多问了。
: follow up可能要问你上百万 requests怎么办。这时你再发挥吧。
: 这么简单的问题上集群的都是扯淡。
avatar
g*g
83 楼
你这个说得不对。实践当中，这么弄UUID的，一般都是连接DB的应用服务器，他们的IP
/Mac address不会相同。

【在 b*******s 的大作中提到】
: 用客户方信息来保证唯一性是不可靠的，而且是额外增加负荷的
avatar
g*g
84 楼
数据库是保证不重复，最简单最有效的方法。性能也很高。

【在 b*******s 的大作中提到】
: 用数据库来做这个，又是锤子党了，非常糟糕的想法，人家用这个服务就是给数据库提
: 供服务的，你们倒好，先来个数据库
avatar
b*s
85 楼
这个性能很“高”，大概是数据库意义上的，和实际授时系统等比，差很多个数量级呢

【在 g*****g 的大作中提到】
: 数据库是保证不重复，最简单最有效的方法。性能也很高。
avatar
b*s
86 楼
ip/mac顶多做到unique，你放在id里，破坏递增性的

IP

【在 g*****g 的大作中提到】
: 你这个说得不对。实践当中，这么弄UUID的，一般都是连接DB的应用服务器，他们的IP
: /Mac address不会相同。
avatar
g*g
87 楼
我说的只是UUID，那个scheme可以保证Unique，UUID没有讲究递增的。
递增的是我说的，数据库里大家都来预取一段，用完再取。

【在 b*******s 的大作中提到】
: ip/mac顶多做到unique，你放在id里，破坏递增性的
:
: IP
avatar
p*2
88 楼

为什么会低下？每次要id都是batch的，异步的。

【在 b*******s 的大作中提到】
: 效率低下
avatar
b*s
89 楼
单机的问题是，递增性是按照请求到达的顺序来的，而不是请求发起的顺序，这样由于
网络路由不同，我们坐在一起，可能你先提交请求，但是拿到的id我比你小。
不过其实也很容易解决，在request里面加时间戳就是了，服务器端处理就用LUT，表对
gps clocks的采样多一点，比如比需求高一个数量级，问题就不大了

了。

【在 d******e 的大作中提到】
: 用上计算机了， 简单说几句。
: 第一，这题我面过，counter必过无疑。
: 第二，毛子讲更加清楚。10000这个数不是白给你的。
: 这里主要靠你知识面，看到10千，有经验的就知道考c10k问题了。
: 那么前端上任何 c10k server,基本上就是async的了。单机搞定。
: 后面要么自己写个简单函数/类, counter＋＋搞定。
: 要么上redis incr，我估计你说出用比如node.js, tornando+redis后面就不用多问了。
: follow up可能要问你上百万 requests怎么办。这时你再发挥吧。
: 这么简单的问题上集群的都是扯淡。
avatar
b*s
90 楼
看和谁比，你数据库再快，快不过barebone的系统，而且这个系统没太多数据要存，上
数据库太笨重，你要在面试里提，估计回去会成为他们的午餐笑话，g那批人就是造轮
子的思维方式，里面c++出身的是主流

【在 p*****2 的大作中提到】
:
: 为什么会低下？每次要id都是batch的，异步的。
avatar
b*s
91 楼
时间戳的精度不够，这个如何解决我再想一下

【在 b*******s 的大作中提到】
: 单机的问题是，递增性是按照请求到达的顺序来的，而不是请求发起的顺序，这样由于
: 网络路由不同，我们坐在一起，可能你先提交请求，但是拿到的id我比你小。
: 不过其实也很容易解决，在request里面加时间戳就是了，服务器端处理就用LUT，表对
: gps clocks的采样多一点，比如比需求高一个数量级，问题就不大了
:
: 了。
avatar
b*s
92 楼
更恶劣的情况是，我同一台机器先后的请求，拿到反序的id

【在 b*******s 的大作中提到】
: 单机的问题是，递增性是按照请求到达的顺序来的，而不是请求发起的顺序，这样由于
: 网络路由不同，我们坐在一起，可能你先提交请求，但是拿到的id我比你小。
: 不过其实也很容易解决，在request里面加时间戳就是了，服务器端处理就用LUT，表对
: gps clocks的采样多一点，比如比需求高一个数量级，问题就不大了
:
: 了。
avatar
P*l
93 楼
谁说严格递增的？
不冲突太简单了．

【在 b*******s 的大作中提到】
: 你如何保证100个机器不产生冲突的号？解决冲突的代价很大的，别小看，你也无法控
: 制客户要到的号码是递增的
:
: 自
avatar
b*s
94 楼
拿时间戳可以这样做，在全球各地部署高精度的时间服务器，这些服务器利用gps
clock同步，由于近，合理部署可以消除网络路由时延带来的问题。
avatar
p*2
95 楼

我哪里上数据库了？

【在 b*******s 的大作中提到】
: 看和谁比，你数据库再快，快不过barebone的系统，而且这个系统没太多数据要存，上
: 数据库太笨重，你要在面试里提，估计回去会成为他们的午餐笑话，g那批人就是造轮
: 子的思维方式，里面c++出身的是主流
avatar
b*s
96 楼
题设里没有说严格递增？

【在 P********l 的大作中提到】
: 谁说严格递增的？
: 不冲突太简单了．
avatar
P*l
97 楼
你愿意相信就相信呗．good luck.

【在 b*******s 的大作中提到】
: 赞，这个是到点子上了
avatar
b*s
98 楼
好吧，看混了

【在 p*****2 的大作中提到】
:
: 我哪里上数据库了？
avatar
b*s
99 楼
你就说说你那100台是如何避免重复和错序的吧

【在 P********l 的大作中提到】
: 谁说严格递增的？
: 不冲突太简单了．
avatar
g*g
100 楼
错序太难，高并发也没有说不错序的。避免重复就是批量取呀。

【在 b*******s 的大作中提到】
: 你就说说你那100台是如何避免重复和错序的吧
avatar
z*e
101 楼
要保证跟硬件独立

【在 l*********s 的大作中提到】
: 不是有微秒级别的系统时钟吗？
avatar
N*n
102 楼
看了他后面补充的我才发现他是server遍布全球，（我理解成request 来自全球）
按他那个说法，直接可以把 Ip 部分去掉了

【在 b*******s 的大作中提到】
: ip放进id里面我觉得是个坏主意，不能保证递增
:
: optimized
avatar
P*l
103 楼
面试总不能不看不看题吧

【在 b*******s 的大作中提到】
: 题设里没有说严格递增？
avatar
b*s
104 楼
就算大部分递增 我也看不到你的设计里哪部分是保证这个的

【在 P********l 的大作中提到】
: 面试总不能不看不看题吧
avatar
N*n
105 楼
这个看来是有经验的。。顶一下再学习。

了。

【在 d******e 的大作中提到】
: 用上计算机了， 简单说几句。
: 第一，这题我面过，counter必过无疑。
: 第二，毛子讲更加清楚。10000这个数不是白给你的。
: 这里主要靠你知识面，看到10千，有经验的就知道考c10k问题了。
: 那么前端上任何 c10k server,基本上就是async的了。单机搞定。
: 后面要么自己写个简单函数/类, counter＋＋搞定。
: 要么上redis incr，我估计你说出用比如node.js, tornando+redis后面就不用多问了。
: follow up可能要问你上百万 requests怎么办。这时你再发挥吧。
: 这么简单的问题上集群的都是扯淡。
avatar
P*l
106 楼
自己先琢磨一下？

【在 b*******s 的大作中提到】
: 就算大部分递增 我也看不到你的设计里哪部分是保证这个的
avatar
p*2
107 楼

刚看到这个。看来还是得上node呀。

【在 N*n 的大作中提到】
: 这个看来是有经验的。。顶一下再学习。
:
: 了。
avatar
z*e
108 楼
哦，原来是铁道部website同类问题
那关键就是异步处理咯

了。

【在 d******e 的大作中提到】
: 用上计算机了， 简单说几句。
: 第一，这题我面过，counter必过无疑。
: 第二，毛子讲更加清楚。10000这个数不是白给你的。
: 这里主要靠你知识面，看到10千，有经验的就知道考c10k问题了。
: 那么前端上任何 c10k server,基本上就是async的了。单机搞定。
: 后面要么自己写个简单函数/类, counter＋＋搞定。
: 要么上redis incr，我估计你说出用比如node.js, tornando+redis后面就不用多问了。
: follow up可能要问你上百万 requests怎么办。这时你再发挥吧。
: 这么简单的问题上集群的都是扯淡。
avatar
b*s
109 楼
他的方法是最简单靠谱的

【在 N*n 的大作中提到】
: 这个看来是有经验的。。顶一下再学习。
:
: 了。
avatar
p*2
110 楼

redis能支持每秒10万吗？

【在 z****e 的大作中提到】
: 哦，原来是铁道部website同类问题
: 那关键就是异步处理咯
:
: 了。
avatar
z*e
111 楼
如果只做id generation的话，应该可以吧
这个要做压力测试

【在 p*****2 的大作中提到】
:
: redis能支持每秒10万吗？
avatar
p*2
112 楼

redis是单线程的。估计撑死了这么多。在往上估计就不行了。

【在 z****e 的大作中提到】
: 如果只做id generation的话，应该可以吧
: 这个要做压力测试
avatar
b*s
113 楼
直接说吧

【在 P********l 的大作中提到】
: 自己先琢磨一下？
avatar
p*2
114 楼

single point failure还靠谱？

【在 b*******s 的大作中提到】
: 他的方法是最简单靠谱的
avatar
z*e
115 楼
所以大多数产品做得跟屎一样
我天天给三大cloud提供服务
我可以负责任滴说一句
aws比gae,computing engine这些，强一万倍
stevey基本上说出了全部事实
google的cloud比m$还烂一个档次

【在 b*******s 的大作中提到】
: 看和谁比，你数据库再快，快不过barebone的系统，而且这个系统没太多数据要存，上
: 数据库太笨重，你要在面试里提，估计回去会成为他们的午餐笑话，g那批人就是造轮
: 子的思维方式，里面c++出身的是主流
avatar
z*e
116 楼
他这种单node做id generation的方式
一般也就是单线程搞定了
多线程和多node并发其实最后问题是一样的

【在 p*****2 的大作中提到】
:
: single point failure还靠谱？
avatar
p*2
117 楼

node request多了要上cluster的。

【在 z****e 的大作中提到】
: 他这种单node做id generation的方式
: 一般也就是单线程搞定了
: 多线程和多node并发其实最后问题是一样的
avatar
z*e
118 楼
但是我看他的解法
id还是从那一个node上出

【在 p*****2 的大作中提到】
:
: node request多了要上cluster的。
avatar
b*s
119 楼
他被问到过，过了
够说明问题了，我觉得他的方案只要解决我说的请求由于网络问题倒序就行了

【在 p*****2 的大作中提到】
:
: node request多了要上cluster的。
avatar
p*2
120 楼

100K的量不小了，而且量可能更大。我觉得一个node够呛。另外就一个node挂了怎么办
？

【在 z****e 的大作中提到】
: 但是我看他的解法
: id还是从那一个node上出
avatar
p*2
121 楼

那我跟你说我被问到过，也过了，你怎么说？

【在 b*******s 的大作中提到】
: 他被问到过，过了
: 够说明问题了，我觉得他的方案只要解决我说的请求由于网络问题倒序就行了
avatar
z*e
122 楼
所以这里是trade off

【在 p*****2 的大作中提到】
:
: 那我跟你说我被问到过，也过了，你怎么说？
avatar
b*s
123 楼
那恭喜你了

【在 p*****2 的大作中提到】
:
: 那我跟你说我被问到过，也过了，你怎么说？
avatar
p*2
124 楼

刚做了个试验10万个incr操作，redis要用到1.5秒， 所以撑不住那个量。

【在 z****e 的大作中提到】
: 所以这里是trade off
avatar
z*e
125 楼
所以只能是一个纯粹的c10k问题
不是c100k问题

【在 p*****2 的大作中提到】
:
: 刚做了个试验10万个incr操作，redis要用到1.5秒， 所以撑不住那个量。
avatar
p*2
126 楼

靠。我以为是100k呢。10k的话确实没问题。

【在 z****e 的大作中提到】
: 所以只能是一个纯粹的c10k问题
: 不是c100k问题
avatar
b*s
127 楼
赞

【在 p*****2 的大作中提到】
:
: 靠。我以为是100k呢。10k的话确实没问题。
avatar
p*2
128 楼
还是不对，单机方案如何解释
要求对大部分的请求做到后面请求的id要
比前面的大
avatar
z*e
129 楼
incre不行还是什么原因？

【在 p*****2 的大作中提到】
: 还是不对，单机方案如何解释
: 要求对大部分的请求做到后面请求的id要
: 比前面的大
avatar
b*s
130 楼
他的方案是counting，这个其实还有个隐患是大数问题，不过用64 bits够了
刚才算了下可以按每秒1万，挺个几千万年

【在 p*****2 的大作中提到】
: 还是不对，单机方案如何解释
: 要求对大部分的请求做到后面请求的id要
: 比前面的大
avatar
b*s
131 楼
服务用node不错

【在 p*****2 的大作中提到】
: 还是不对，单机方案如何解释
: 要求对大部分的请求做到后面请求的id要
: 比前面的大
avatar
p*2
132 楼

不是不行。是这样可以绝对的按顺序排列了。貌似跟面试官想考察的不是一个东西。不
然面试官为什么说那话。

【在 z****e 的大作中提到】
: incre不行还是什么原因？
avatar
z*e
133 楼
你是说绝对按照顺序排列和题目中大部分按照顺序排列有些不符？
这里貌似可以有优化的空间
比如让所有active nodes跑id generator node注册一下
然后id generator node扫描监控所有node上的id pool
低于一定程度，就塞一批过去，这样不能保证绝对顺序
但是大概有那么点意思

【在 p*****2 的大作中提到】
:
: 不是不行。是这样可以绝对的按顺序排列了。貌似跟面试官想考察的不是一个东西。不
: 然面试官为什么说那话。
avatar
p*2
134 楼

我就是这个意思。如果单机的话就可以保证绝对顺序了。
我感觉id generator node不应该主动塞。应该是被动的。

【在 z****e 的大作中提到】
: 你是说绝对按照顺序排列和题目中大部分按照顺序排列有些不符？
: 这里貌似可以有优化的空间
: 比如让所有active nodes跑id generator node注册一下
: 然后id generator node扫描监控所有node上的id pool
: 低于一定程度，就塞一批过去，这样不能保证绝对顺序
: 但是大概有那么点意思
avatar
z*e
135 楼
那就pool一批id
然后放在list里面
每一次request过来，先看当前id是否被锁
如果被锁，则跳到下一个去拿id，以此类推
然后拿id的时候，锁住当前的坑位
酱紫，不能保证绝对，但是一般而言，还是先到先得
检查lock的话，java代码可以看这个
http://stackoverflow.com/questions/1779795/how-do-determine-if-

【在 p*****2 的大作中提到】
:
: 我就是这个意思。如果单机的话就可以保证绝对顺序了。
: 我感觉id generator node不应该主动塞。应该是被动的。
avatar
p*2
136 楼

redis数大了应该就变浮点了，
node里的integer应该也是bigint

【在 b*******s 的大作中提到】
: 他的方案是counting，这个其实还有个隐患是大数问题，不过用64 bits够了
: 刚才算了下可以按每秒1万，挺个几千万年
avatar
b*s
137 楼
bigint就够了
浮点当id不是很常规

【在 p*****2 的大作中提到】
:
: redis数大了应该就变浮点了，
: node里的integer应该也是bigint
avatar
b*i
138 楼
你这里说请求来自全球，很后面又说服务器遍布全球。条件能不能确定一下？
如果请求每秒10000个，真的一个服务器就行了，就是能够保证round robin的机制。比
如AKKA。

【在 f**********3 的大作中提到】
: 设计一个系统，每次请求返回一个唯一的id，要求对大部分的请求做到后面请求的id要
: 比前面的大，要平均每秒能处理10000个请求，而且请求来自全球。还要求id尽量连续
: ，想过用时间做id，被毛子否了。
avatar
l*s
139 楼
这个不好，等于优先级要受客户机器时钟影响了。

【在 b*******s 的大作中提到】
: 单机的问题是，递增性是按照请求到达的顺序来的，而不是请求发起的顺序，这样由于
: 网络路由不同，我们坐在一起，可能你先提交请求，但是拿到的id我比你小。
: 不过其实也很容易解决，在request里面加时间戳就是了，服务器端处理就用LUT，表对
: gps clocks的采样多一点，比如比需求高一个数量级，问题就不大了
:
: 了。
avatar
b*s
140 楼
我在另一个帖子里补充过了

【在 l*********s 的大作中提到】
: 这个不好，等于优先级要受客户机器时钟影响了。
avatar
b*i
141 楼
产生几百万个incr有什么难度？

【在 p*****2 的大作中提到】
:
: redis数大了应该就变浮点了，
: node里的integer应该也是bigint
avatar
z*e
142 楼
时间消耗达不到要求
二爷力图在一秒内生成100k个ids

【在 b***i 的大作中提到】
: 产生几百万个incr有什么难度？
avatar
L*r
143 楼
这样行么：搞个message queue,后台有server不断产生新的id往里扔，前台所有server
从MQ里拿，MQ确保每个id只会被一台server acquire（应该很简单）。失败了就再申请
一次。要是怕一直申请不到，就搞个weight啥的，失败次数越多weight越高，下次拿到
的可能性越大。
这个就是比较简单了。MQ肯定是现成的，大约几十行code就能搞定。

【在 f**********3 的大作中提到】
: 设计一个系统，每次请求返回一个唯一的id，要求对大部分的请求做到后面请求的id要
: 比前面的大，要平均每秒能处理10000个请求，而且请求来自全球。还要求id尽量连续
: ，想过用时间做id，被毛子否了。
avatar
b*i
144 楼
不就是一个id吗？1秒50万个轻而易举啊？
但是要这样，分开id的产生和检查。id可以浪费，但是用一个唯一的不可重入的函数来
返回id。然后取得id的线程要查询以前这个ip/mac地址是否获得过id。不懂这个级别的
面试题怎么会成为问题。

【在 z****e 的大作中提到】
: 时间消耗达不到要求
: 二爷力图在一秒内生成100k个ids
avatar
w*w
145 楼
假定最多用256个server,64位的id:
前48位放从2010年1月1日开始的毫秒数，再8位毫秒内的计数，最后8位server的id,不
可以么？

【在 f**********3 的大作中提到】
: 设计一个系统，每次请求返回一个唯一的id，要求对大部分的请求做到后面请求的id要
: 比前面的大，要平均每秒能处理10000个请求，而且请求来自全球。还要求id尽量连续
: ，想过用时间做id，被毛子否了。
avatar
z*e
146 楼
没怎么倒腾过redis，不知道二爷那个数据是怎么做的
就假设二爷那个测试是正确的吧，不过这种单机的node
瓶颈是很明显的
不过很有趣的是，有些人看我说的马上反应过来这个有瓶颈
老魏说了半天居然在附和，生成一个id处理比搞火车票
那是要简单一万倍都不只了，如果这个有瓶颈
那火车票的瓶颈岂不是更明显？

【在 b***i 的大作中提到】
: 不就是一个id吗？1秒50万个轻而易举啊？
: 但是要这样，分开id的产生和检查。id可以浪费，但是用一个唯一的不可重入的函数来
: 返回id。然后取得id的线程要查询以前这个ip/mac地址是否获得过id。不懂这个级别的
: 面试题怎么会成为问题。
avatar
b*i
147 楼
我也没用redis,就是系统依靠一个单机实现id的生成。然后把id, ip, mac发送给多个
服务器，这些服务器根据ip,mac等来分库。我估摸着查找一个ip/mac是否用过这个存储
的信息量非常大，所以得用数据库了，分库是可以轻松提高并行度的。
不过我的目标是每秒百万的查询。当然web也是多个服务器，只不过这个id的生成是一
个单机上的“瓶颈”，这样才能保证唯一。

【在 z****e 的大作中提到】
: 没怎么倒腾过redis，不知道二爷那个数据是怎么做的
: 就假设二爷那个测试是正确的吧，不过这种单机的node
: 瓶颈是很明显的
: 不过很有趣的是，有些人看我说的马上反应过来这个有瓶颈
: 老魏说了半天居然在附和，生成一个id处理比搞火车票
: 那是要简单一万倍都不只了，如果这个有瓶颈
: 那火车票的瓶颈岂不是更明显？
相关阅读
windows batch file请问const myClass &src 和myClass const &src有什么区别？大牛 in Perl and SED?what's the system call for get file num of a dir?用什么写Http Client 比较好?which is faster, table look up or bitwise operator?The C++ questions I've been askedHelp: how to use Eclipse as C++ IDE in Linux? (转载)需要更好的论坛搜索吗？how to use stack(s) to realize a quequevisual studio 2005安装问题关于Makefile的一个问题problemHelp with a simple c-shell script.[合集] some interview questions i met and remembered人无食不活，码无库不通[合集] matlab 函数求救c++问题，请高人指点迷津，c++ faq lite的一个例子请教： 用stable_sort 在VC++下通过但在g++下通不过[合集] C里面return 1代表失败，return 0代表成功，对么？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。