h*****e 发帖数: 14 | 1 问一道多线程面试题: 设计一个类似于黑名单的服务。 每个用户每次请求一个服务都
会记录ID。每个用户只能在固定的时间内请求固定次数的服务, 比如说1分钟之内只能
请求10次。如果请求服务的次数大于10次,就会被加入黑名单而且在5分钟之内不会得
到任何服务。并且, 如果用户在这个5分钟之内仍然发送请求, 则重新计算这个5分钟。
还需要实现一个方法能随时返回在当前时间间隔内10个访问次数最多的用户,时间间隔
是10分钟。就是说每隔10分钟就把所有的访问次数重新记0。
没做过多线程的东西, 不知道用什么样的数据结构来实现共享, 并线保重性能。
请各位大神赐教啊! |
b**********5 发帖数: 7881 | 2 这种主要不是考你multithreading吧。。 你先按single thread做, 你做出来后, 在
看看哪里需要改的。。。
钟。
【在 h*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问一道多线程面试题: 设计一个类似于黑名单的服务。 每个用户每次请求一个服务都 : 会记录ID。每个用户只能在固定的时间内请求固定次数的服务, 比如说1分钟之内只能 : 请求10次。如果请求服务的次数大于10次,就会被加入黑名单而且在5分钟之内不会得 : 到任何服务。并且, 如果用户在这个5分钟之内仍然发送请求, 则重新计算这个5分钟。 : 还需要实现一个方法能随时返回在当前时间间隔内10个访问次数最多的用户,时间间隔 : 是10分钟。就是说每隔10分钟就把所有的访问次数重新记0。 : 没做过多线程的东西, 不知道用什么样的数据结构来实现共享, 并线保重性能。 : 请各位大神赐教啊!
|
d*****c 发帖数: 605 | 3 这明显是system design,跟数据结构没关系,很多台server用一个common persistent
就ok了啊,要考虑performance的话加一层cache,然后考虑怎么maintain cache |
t****t 发帖数: 387 | 4 抛砖引玉
第一个问题,假设有个thread pool来处理请求,假设每次用户请求包含id,
timestamp
在服务器端用一个数据结构来保存请求次数 map
class RequestHistory
{
int maxRequest = 10;
queue historyQueue;
bool isBlocked;
void HandlerRequest(datetime ts)
{
if(!isBlocked)
{
//check ts diff with oldest element ts
//4 possible cases, handle each case, should be easy
//queue size < 10, ts diff < 1min
//queue size < 10, ts diff > 1min
//queue size = 10, ts diff < 1min
//queue size = 10, ts diff > 1min
}
else
{
//assume queue size is 10 when it's in blocked state
//check ts diff with newest element ts
//2 possible cases
//ts diff < 5min
//ts diff > 5min
}
}
};
第二个问题,用一个thread来管理一个专门的数据结构,这个thread每10分钟运行一次
清空记录
数据结构可以很简单map RequestCountIn10Min,每当有请求进来就update
这个记录。还可以同时保存一个按次数排序的数据结构,这样可以随时得到排序
这个里面的locking,不需要Lock整个数据结构,可以per user id |
h*****e 发帖数: 14 | 5
嗯, 但线程还是比较简单。 主要就是不知道变成多线程之后怎么么处理共享的数据。
【在 b**********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这种主要不是考你multithreading吧。。 你先按single thread做, 你做出来后, 在 : 看看哪里需要改的。。。 : : 钟。
|
h*****e 发帖数: 14 | 6
persistent
对, 这题就是靠多线程的系统设计, 我倒是没想用多台server。
用cache的话, 怎么实现呢
【在 d*****c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这明显是system design,跟数据结构没关系,很多台server用一个common persistent : 就ok了啊,要考虑performance的话加一层cache,然后考虑怎么maintain cache
|
h*****e 发帖数: 14 | 7 这个应该可以实现题目中的两个功能。想知道一下如果在这种实现的基础上怎么确保性
能呢?
【在 t****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 抛砖引玉 : 第一个问题,假设有个thread pool来处理请求,假设每次用户请求包含id, : timestamp : 在服务器端用一个数据结构来保存请求次数 map : class RequestHistory : { : int maxRequest = 10; : queue historyQueue; : bool isBlocked; : void HandlerRequest(datetime ts)
|
t****t 发帖数: 387 | 8 这样的设计性能应该没有太大问题
lock by user id,所以大部分的时候thread都不会block
而且需要做的事情很少,可能只要很少的thread就可以
【在 h*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个应该可以实现题目中的两个功能。想知道一下如果在这种实现的基础上怎么确保性 : 能呢?
|
h*****e 发帖数: 14 | 9
知道方向了, 多谢了。
如果按照你建议的用一个data structure来记录访问次数, 比如说用map
。那么每个用户每次访问的时候都应该update这个map。假如说这个访问量很大的话,
有什么好的方法来保证性能吗? 还是说因为这个update只是一个简单的操作, 所以不
会影响性能呢?
【在 t****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这样的设计性能应该没有太大问题 : lock by user id,所以大部分的时候thread都不会block : 而且需要做的事情很少,可能只要很少的thread就可以
|
H*******g 发帖数: 6997 | |
t****t 发帖数: 387 | 11 所以我说lock by user id
有不同的用户发请求 不需要block这个数据结构
【在 h*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 知道方向了, 多谢了。 : 如果按照你建议的用一个data structure来记录访问次数, 比如说用map : 。那么每个用户每次访问的时候都应该update这个map。假如说这个访问量很大的话, : 有什么好的方法来保证性能吗? 还是说因为这个update只是一个简单的操作, 所以不 : 会影响性能呢?
|