h*****e
发帖数: 14 | 1 问一道多线程面试题： 设计一个类似于黑名单的服务。 每个用户每次请求一个服务都
会记录ID。每个用户只能在固定的时间内请求固定次数的服务， 比如说1分钟之内只能
请求10次。如果请求服务的次数大于10次，就会被加入黑名单而且在5分钟之内不会得
到任何服务。并且， 如果用户在这个5分钟之内仍然发送请求， 则重新计算这个5分钟。
还需要实现一个方法能随时返回在当前时间间隔内10个访问次数最多的用户，时间间隔
是10分钟。就是说每隔10分钟就把所有的访问次数重新记0。
没做过多线程的东西， 不知道用什么样的数据结构来实现共享， 并线保重性能。
请各位大神赐教啊！ |
b**********5
发帖数: 7881 | 2 这种主要不是考你multithreading吧。。 你先按single thread做， 你做出来后， 在
看看哪里需要改的。。。
钟。
【在 h*****e 的大作中提到】
: 问一道多线程面试题： 设计一个类似于黑名单的服务。 每个用户每次请求一个服务都
: 会记录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 的大作中提到】
: 这种主要不是考你multithreading吧。。 你先按single thread做， 你做出来后， 在
: 看看哪里需要改的。。。
:
: 钟。
|
h*****e
发帖数: 14 | 6
persistent
对， 这题就是靠多线程的系统设计， 我倒是没想用多台server。
用cache的话， 怎么实现呢
【在 d*****c 的大作中提到】
: 这明显是system design，跟数据结构没关系，很多台server用一个common persistent
: 就ok了啊，要考虑performance的话加一层cache，然后考虑怎么maintain cache
|
h*****e
发帖数: 14 | 7 这个应该可以实现题目中的两个功能。想知道一下如果在这种实现的基础上怎么确保性
能呢？
【在 t****t 的大作中提到】
: 抛砖引玉
: 第一个问题，假设有个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 的大作中提到】
: 这个应该可以实现题目中的两个功能。想知道一下如果在这种实现的基础上怎么确保性
: 能呢？
|
h*****e
发帖数: 14 | 9
知道方向了， 多谢了。
如果按照你建议的用一个data structure来记录访问次数， 比如说用map
。那么每个用户每次访问的时候都应该update这个map。假如说这个访问量很大的话，
有什么好的方法来保证性能吗？ 还是说因为这个update只是一个简单的操作， 所以不
会影响性能呢？
【在 t****t 的大作中提到】
: 这样的设计性能应该没有太大问题
: lock by user id，所以大部分的时候thread都不会block
: 而且需要做的事情很少，可能只要很少的thread就可以
|
H*******g
发帖数: 6997 | |
t****t
发帖数: 387 | 11 所以我说lock by user id
有不同的用户发请求 不需要block这个数据结构
【在 h*****e 的大作中提到】
:
: 知道方向了， 多谢了。
: 如果按照你建议的用一个data structure来记录访问次数， 比如说用map
: 。那么每个用户每次访问的时候都应该update这个map。假如说这个访问量很大的话，
: 有什么好的方法来保证性能吗？ 还是说因为这个update只是一个简单的操作， 所以不
: 会影响性能呢？
|
