m***6
发帖数: 7 | 1 A家二轮电面。三哥出了个设计题目。
有很多client向server要一个数字。server要保证回复的数字每次都是unique的。但无
需random。
由于client的请求太多。要用cluster（N台机器处理）。 我给了一个简单方案。每台
机器有个counter。回复了一个
client请求之后 count++ 。第一台机器负责[0,2^64/N] 第二台机器负责(2^64/N,2^65
/N]。。。。
用hash(user request)%N的办法把request assign 给相应的机器。
然后三哥说如何使系统scalable。比如增加几台机器到cluster中怎么办。 要提示 三
哥居然开始说 cant say。后来提示
不要早早就divide data 之类。
然后我就开始瞎掰了。因为不懂。
这三哥好像对A不大满意似得。最后环节我走流程的问了问他在A有没有什么
interesting project.他居然顿了顿说A能有啥
interesting。 电话里还在打哈欠。 哎 。。。。。
求牛人指点。不希望自己一直糊涂着。 |
f*****e
发帖数: 2992 | 2 dynamic assignment, the server receiving more frequent request is assigned l
arger range.
65
【在 m***6 的大作中提到】
: A家二轮电面。三哥出了个设计题目。
: 有很多client向server要一个数字。server要保证回复的数字每次都是unique的。但无
: 需random。
: 由于client的请求太多。要用cluster（N台机器处理）。 我给了一个简单方案。每台
: 机器有个counter。回复了一个
: client请求之后 count++ 。第一台机器负责[0,2^64/N] 第二台机器负责(2^64/N,2^65
: /N]。。。。
: 用hash(user request)%N的办法把request assign 给相应的机器。
: 然后三哥说如何使系统scalable。比如增加几台机器到cluster中怎么办。 要提示 三
: 哥居然开始说 cant say。后来提示
|
m***6
发帖数: 7 | 3 如果dynamic assignment 一台机器。其余N-1机器会被影响吧？ 我提到过这个办法。
三哥意思说这个他不喜欢。
l
【在 f*****e 的大作中提到】
: dynamic assignment, the server receiving more frequent request is assigned l
: arger range.
:
: 65
|
m***6
发帖数: 7 | 4 我其实面试时是在往 consistent hashing上扯的。 奈何三哥一直说 you don't solve
the question
自己也不是很懂。。。 |
w*******s
发帖数: 96 | 5 用生成uuid的方法？
int_128 getUUid()
{
static int_64 i = getLastInitialValue();
return ++i | getMac() << 64;
} |
f*******4
发帖数: 64 | 6 看不太懂，能解惑注释下么？
wiki了下UUID，
In this context the word unique should be taken to mean "practically unique"
rather than "guaranteed unique".
【在 w*******s 的大作中提到】
: 用生成uuid的方法？
: int_128 getUUid()
: {
: static int_64 i = getLastInitialValue();
: return ++i | getMac() << 64;
: }
|
m*****k
发帖数: 731 | |
p*****2
发帖数: 21240 | |
h*****a
发帖数: 1718 | 9 每个server有自己的id，同时用自己的计数器。比如64bit的id，你预期最多1000台
server，那就预留10bit给server id，然后剩下54bit是counter 部分。
这是一个分布式系统的常见问题，data sharding也都要用到类似的方法。
你的方案中把sharding提前固定了，这样data的分布和服务器的数量绑定在一起，是非
常不灵活的。所以面试官不满意是很正常的。
65
【在 m***6 的大作中提到】
: A家二轮电面。三哥出了个设计题目。
: 有很多client向server要一个数字。server要保证回复的数字每次都是unique的。但无
: 需random。
: 由于client的请求太多。要用cluster（N台机器处理）。 我给了一个简单方案。每台
: 机器有个counter。回复了一个
: client请求之后 count++ 。第一台机器负责[0,2^64/N] 第二台机器负责(2^64/N,2^65
: /N]。。。。
: 用hash(user request)%N的办法把request assign 给相应的机器。
: 然后三哥说如何使系统scalable。比如增加几台机器到cluster中怎么办。 要提示 三
: 哥居然开始说 cant say。后来提示
|
c********p
发帖数: 1969 | |
|
|
r**********o
发帖数: 50 | 11 兄弟：
10bit给server id的话， 在server达到1000台之前，就是说地址空间是
unconsistent的咯？ 并且某些地址空间是分配不到的？
【在 h*****a 的大作中提到】
: 每个server有自己的id，同时用自己的计数器。比如64bit的id，你预期最多1000台
: server，那就预留10bit给server id，然后剩下54bit是counter 部分。
: 这是一个分布式系统的常见问题，data sharding也都要用到类似的方法。
: 你的方案中把sharding提前固定了，这样data的分布和服务器的数量绑定在一起，是非
: 常不灵活的。所以面试官不满意是很正常的。
:
: 65
|
h*****a
发帖数: 1718 | 12 没错，有问题么
【在 r**********o 的大作中提到】
: 兄弟：
: 10bit给server id的话， 在server达到1000台之前，就是说地址空间是
: unconsistent的咯？ 并且某些地址空间是分配不到的？
|
m***6
发帖数: 7 | 13 这解释靠谱。
多谢！
【在 h*****a 的大作中提到】
: 每个server有自己的id，同时用自己的计数器。比如64bit的id，你预期最多1000台
: server，那就预留10bit给server id，然后剩下54bit是counter 部分。
: 这是一个分布式系统的常见问题，data sharding也都要用到类似的方法。
: 你的方案中把sharding提前固定了，这样data的分布和服务器的数量绑定在一起，是非
: 常不灵活的。所以面试官不满意是很正常的。
:
: 65
|
g*****g
发帖数: 34805 | 14 常见数据库做ID的方法就两种。一种是依靠RDBMS，一次取一段，比如每个结点到数据
库一次取10000个，数据库用transaction保证不冲突。
另一种就是type 1 UUID，就是mac+timestamp+synchronized counter on host。因为
cluster通常在在同一个子网上，mac肯定不会冲突。 |
m***6
发帖数: 7 | 15 这个总结很靠谱。
多谢！
【在 g*****g 的大作中提到】
: 常见数据库做ID的方法就两种。一种是依靠RDBMS，一次取一段，比如每个结点到数据
: 库一次取10000个，数据库用transaction保证不冲突。
: 另一种就是type 1 UUID，就是mac+timestamp+synchronized counter on host。因为
: cluster通常在在同一个子网上，mac肯定不会冲突。
|
p*****2
发帖数: 21240 | 16
因为
cluster通常在在同一个子网上，mac肯定不会冲突。
为什么这么说？
【在 g*****g 的大作中提到】
: 常见数据库做ID的方法就两种。一种是依靠RDBMS，一次取一段，比如每个结点到数据
: 库一次取10000个，数据库用transaction保证不冲突。
: 另一种就是type 1 UUID，就是mac+timestamp+synchronized counter on host。因为
: cluster通常在在同一个子网上，mac肯定不会冲突。
|
x*****0
发帖数: 452 | |
x*****0
发帖数: 452 | |
a*********3
发帖数: 15 | 19 第二种方法返回的值是不是还有很小的概率是一样的?
【在 g*****g 的大作中提到】
: 常见数据库做ID的方法就两种。一种是依靠RDBMS，一次取一段，比如每个结点到数据
: 库一次取10000个，数据库用transaction保证不冲突。
: 另一种就是type 1 UUID，就是mac+timestamp+synchronized counter on host。因为
: cluster通常在在同一个子网上，mac肯定不会冲突。
|
S*A
发帖数: 7142 | 20 用 hash 那个不能严格保证返回的 ID 是不冲突的。
我觉得用区间分配的办法是比较靠谱的。建立一个总服务器，一次分大段区间出去。
然后其他的服务器向总服务器要请求，可以根据以往处理的速度来要大概几十秒钟
能分出去那么多的区间。总服务器划分这个区间給这个服务器，可以调整分出去的
ID 多少。
这样总服务器只需要面相自己内部的服务器，如果集群大了，加大分出去的区间大小
就可以调整收到的请求的速率。做得更好可以精确调整分出去得区间大小，最终达到
分出去得 ID 是近似递增的。 |
a*********3
发帖数: 15 | 21 可不可以在client, server之间加一个Middleware? 由Middleware集中处理ID, 我
distributed system的project就是这样做的... |
