由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 求牛人 解答 一个Amazon 设计问题
相关主题
FB设计题求教。老年马工赶快去 fb
再来继续比较,芒果和redis各什么时候用比较好?dropbox一道题
问个snapchat的设计题讨论一下12306的架构?
问个L家 设计题Google Intern Host Match 求Match 求不淹死在Pool里
[zynga面经] backend software engineer请问最热的nosql是哪个?
[提供内推] Senior DBA (SFO市区, mysql, cassandra, redis, h (转载)G家店面design题目
系统设计题怎么准备问一道FB design
我的System Design总结脸家设计题,设计游戏排名系统
相关话题的讨论汇总
话题: 机器话题: server话题: 三哥话题: client话题: unique
进入JobHunting版参与讨论
1 (共1页)
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
8
Redis
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
10
mark
相关主题
[提供内推] Senior DBA (SFO市区, mysql, cassandra, redis, h (转载)老年马工赶快去 fb
系统设计题怎么准备dropbox一道题
我的System Design总结讨论一下12306的架构?
进入JobHunting版参与讨论
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
17
m
x*****0
发帖数: 452
18
m
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就是这样做的...
1 (共1页)
进入JobHunting版参与讨论
相关主题
脸家设计题,设计游戏排名系统[zynga面经] backend software engineer
内推苹果itunes部门[提供内推] Senior DBA (SFO市区, mysql, cassandra, redis, h (转载)
弱弱的苹果家面经系统设计题怎么准备
L家的一道设计题我的System Design总结
FB设计题求教。老年马工赶快去 fb
再来继续比较,芒果和redis各什么时候用比较好?dropbox一道题
问个snapchat的设计题讨论一下12306的架构?
问个L家 设计题Google Intern Host Match 求Match 求不淹死在Pool里
相关话题的讨论汇总
话题: 机器话题: server话题: 三哥话题: client话题: unique