R*******G 发帖数: 21 | 1 今天通知fail了。。
给大家分享个题目看看, 献丑了。
如果有更好的做法大家集思广益。
可能还是不够强大吧。
上来问phd项目,然后一直搞不懂我phd研究的意义。一直保持微笑拍马屁应对。
问完坏笑一个,问tcp reno和tcp vegas,我答对了。
然后系统设计题:单个机器上面很多table,然后thread pool容量有限,然后外部一个
很大的queue有很多update要处理。如何effecient的处理请求。size (queue) >> size
(table)>> size (thread poll)
我说两个方案:
一个把对table的updates hash 到 size of(thread poll),这样thread只处理自己
一部分table,不会有contention。但是hash的时候要根据table 的traffic hash,否
则一些thread会starve很长时间。
还有一个就是每个table自己有个local queue,当多个threads访问一个table的时候,
它们等待,超时以后把要写的updates放在那个table的queue上,下一个要写的thread
先pick up这个local queue的东西写,然后再写自己的。
其他所有轮engineer都聊的比较开心,做题没有遇到任何问题。
这阿三交流过程一路feedback非常negative,他回复一直是confused或者搞不懂或者
how。。。,
每次我才开始解释我的想法,还没说就完被打断,然后就开始质疑 confused how。 |
x****u 发帖数: 81 | 2 lz你能说说size (queue) >> size(table)>> size (thread poll)的时候,什么会影
响效率吗?
你的两个方案,为什么能解决问题? |
e*******7 发帖数: 347 | |
x*******1 发帖数: 28835 | 4 可以向HR反应。 如果4个都给positive feedback。 就一个nagetive, 应该有问题。 |
t*****9 发帖数: 569 | 5 你看楼主叙述的过程,问题不在题答得怎样
【在 x****u 的大作中提到】 : lz你能说说size (queue) >> size(table)>> size (thread poll)的时候,什么会影 : 响效率吗? : 你的两个方案,为什么能解决问题?
|
x****u 发帖数: 81 | 6
我之所以这么问,就是觉得lz的方案根本不在点上,看不出逻辑,想问问lz怎么想的。
【在 t*****9 的大作中提到】 : 你看楼主叙述的过程,问题不在题答得怎样
|
n*********d 发帖数: 1603 | |
R*******G 发帖数: 21 | 8 第一个就是简单解决contention
第二个是实现了近似non blocking
因为这个系统如果每个thread都在忙,然后写入又很慢的话,大queue就相当于block了
;而几个thread去处理同一个table就有contention了。
放在这里就是看大家有没有更好的办法?如果有更好的解法,一起学习。
这个印度人上来就比较负面,但是我想如果能直接提一个完美的方案也许机会大一点。
phd很浅显易懂,说的是个应用:多媒体网络传输啥的。所以他还confuse就感觉态度确
实比较负面,不过个人不想纠结这个了,希望国人多努力,级别上去了能多出来面试
candidate就行了。 |
l***0 发帖数: 784 | 9 锁和资源共享是必须考虑到的
优化就要针对优先级,最优的请求要能override其他请求
其他请求应该可以休眠
大批量请求最好使用流水线
大数据请求要有断点续传
有点离散,因为提
没看懂
【在 R*******G 的大作中提到】 : 第一个就是简单解决contention : 第二个是实现了近似non blocking : 因为这个系统如果每个thread都在忙,然后写入又很慢的话,大queue就相当于block了 : ;而几个thread去处理同一个table就有contention了。 : 放在这里就是看大家有没有更好的办法?如果有更好的解法,一起学习。 : 这个印度人上来就比较负面,但是我想如果能直接提一个完美的方案也许机会大一点。 : phd很浅显易懂,说的是个应用:多媒体网络传输啥的。所以他还confuse就感觉态度确 : 实比较负面,不过个人不想纠结这个了,希望国人多努力,级别上去了能多出来面试 : candidate就行了。
|
R*******G 发帖数: 21 | 10 感谢回复。
题目其实就是说这是个k个table的数据库node,n个updates都是对里面表的update。
讨论过程细节简化了。比如,优先级的方案说了2个,他说根本不能考虑优先级,运算
太复杂。所有请求一样重要,但是每个请求执行时间可长可短。
我说把对同一个表的请求写入之前处理一下,比如对一个shopping cart table的加减
物品-也许结合起来看cancle out一些请求,也说不能运算,太复杂。
所以最终就简化到我第一个帖子写的方案了。
关于流水线,能多说两句吗?
【在 l***0 的大作中提到】 : 锁和资源共享是必须考虑到的 : 优化就要针对优先级,最优的请求要能override其他请求 : 其他请求应该可以休眠 : 大批量请求最好使用流水线 : 大数据请求要有断点续传 : 有点离散,因为提 : 没看懂
|
|
|
g*****g 发帖数: 34805 | 11 不清楚要问啥,但数据库设计这里常见的优化就几种。client端批量处理以减少
connection cost。server端batch rewrite和根据不同需求可以考虑锁的粒度(row或
者table) |
l***0 发帖数: 784 | 12 还有根据业务分区
【在 g*****g 的大作中提到】 : 不清楚要问啥,但数据库设计这里常见的优化就几种。client端批量处理以减少 : connection cost。server端batch rewrite和根据不同需求可以考虑锁的粒度(row或 : 者table)
|
R*******G 发帖数: 21 | 13 我也不清楚他要啥
锁粒度说了 他说不行必须锁表
batch rewrite 说了,他说这个不考虑
还是多谢回复
【在 g*****g 的大作中提到】 : 不清楚要问啥,但数据库设计这里常见的优化就几种。client端批量处理以减少 : connection cost。server端batch rewrite和根据不同需求可以考虑锁的粒度(row或 : 者table)
|
R*******G 发帖数: 21 | 14 我说根据update的业务或者优先级 在server分到两个(多个)分别的thread pool来处
理,各个pool分到的thread数目根据load来分配,是这个意思不?
另外说了这是一个server,不考虑分到多个机器。
【在 l***0 的大作中提到】 : 还有根据业务分区
|
l***0 发帖数: 784 | 15 感觉烙印出了个很深入的实际题,而且没给你讲清楚
【在 R*******G 的大作中提到】 : 我也不清楚他要啥 : 锁粒度说了 他说不行必须锁表 : batch rewrite 说了,他说这个不考虑 : 还是多谢回复
|
x*****n 发帖数: 195 | 16 好奇怪。我做过类似的项目,kafka pipeline,目标node/db的partition和cache/
batch处理可是非常关键的设计,倒是lock的使用(我们用了zookeeper)是属于实现上
的细节。
【在 R*******G 的大作中提到】 : 我也不清楚他要啥 : 锁粒度说了 他说不行必须锁表 : batch rewrite 说了,他说这个不考虑 : 还是多谢回复
|
i*******t 发帖数: 79 | 17 没看懂你第二个方法。
如果第一个方法解决了contention,那自然就没了blocking,但是没看出你是具体怎么
按照traffic hash的?
如果事先把Q按照线程个数n分配好n个q,那某个线程做完了自己的q怎么办?如果动态
分配,那分配的时候相当于锁了整个Q,线程可能会等待。
有两个地方需要考虑contention,lz考虑了table,但是q也要考虑。
我的想法,每个pool里的线程有自己的q,一个线程T把update从整个Q转移到每个小q,
使得每个q中只有一种不同的table,同时维护一个的map。当某个线程
做完了自己的q,通知T填上自己的q(用新的table。T一直block在一个新的table的
update上)并更新map。
这样table的contention完全没有,Q的contention只是在某两个线程同时完成了自己的
q的时候才有,概率比较低。也可以当q小到一定程度就通知T,但是就更复杂了。
size
【在 R*******G 的大作中提到】 : 今天通知fail了。。 : 给大家分享个题目看看, 献丑了。 : 如果有更好的做法大家集思广益。 : 可能还是不够强大吧。 : 上来问phd项目,然后一直搞不懂我phd研究的意义。一直保持微笑拍马屁应对。 : 问完坏笑一个,问tcp reno和tcp vegas,我答对了。 : 然后系统设计题:单个机器上面很多table,然后thread pool容量有限,然后外部一个 : 很大的queue有很多update要处理。如何effecient的处理请求。size (queue) >> size : (table)>> size (thread poll) : 我说两个方案:
|
z***y 发帖数: 73 | 18 没太看懂题目。
1.size(queen) >> size(table) >> size(thread pool)
2.不考虑锁表
3.不考虑batch write
这种情况下效率不高的原因是什么?
我的猜想是:
1.线程采用异步更新;
2.设置流控,保证发给数据库的请求数不超过他的承载能力;
3.保证entry更新是串行(table+row唯一标识一个entry)。 |