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）。 |
