10月16日百度笔试系统设计题
有一个客户-服务系统，服务器对客户端发过来的请求进行处理。一般情况下，每个客户发送两次请求的间隔不小于1分钟，如果有客户端在1分钟内连续发送两次以上请求，则说明该客户端属于异常客户。现要求对异常客户进行识别，每个客户可有其ipv6地址进行标识其ID。由于客户比较多，单台服务器无法存储其ipv6的hash值。请设计一个系统，对异常客户进行识别。可使用多台机器，但尽量越少越好。

[解决办法]
这个题我感觉在考分布式部署，在一个服务器上面搭建一个apache的服务接受发送过来的请求，然后在转发，最后在其它的服务器上面处理apache发送过来的请求。
[解决办法]
你这是网络/分布式系统的问题，怎么能发到算法来啦？
算法很简单，就是每收到一个请求就对相应ip（v4或v6都一样）对原来的表进行遍历，如果已经存在就拉入黑名单。如果然后这个表每一分钟自动清空一次（清空期间属于互斥访问区，不允许访问）
但关键是如何让时间最短。要么让数据库同步，缺点是需要来回传递大量数据，但优点是带宽确定（因为数据库的大小你知道）。要么向其他机器都发一次请求，缺点是占用大量带宽，并且带宽是多少还不确定——取决于用户访问量。当然，在访问请求量很少时，这个方法就很好了。
[解决办法]
整理一下思路：
1、每个服务器上的程序设计思路：
有一张表作为访问记录。每来一个新的请求就查一次表，如果重复了就拉黑。同时自动清空那些上次访问距离现在超过一分钟的。
2、服务器之间设计思路有两种：
A.数据库同步。服务器之间的表不断进行交换。具体实现参考路由器的同步算法。优点是查询时间短，但需要大量资源花费在同步数据库上。
B.每来一次新请求，在本机查找一次之后，按ip顺序向其他服务器也做一次查询请求，等待所有查询结果。记得域名服务器里的迭代查询和递归查询么？就类似那个。如果有一个记录了它是黑名单用户，就禁止它。优点是不需要大量带宽同步数据库，缺点是无法保证正确性。因为有可能造成各种时间、数据不一致。

总结，实际是考了网络的问题。算法实现反而成为了基础。
[解决办法]
IPv6 是 128位长度。太长了，必须弄成hash什么的，为什么说单台服务器无法存储其ipv6的hash值呢？运算速度不够？存储不够？还是什么原因？
这个还要看访问的用户数的，你不会打算把所有的ipv6数据都保存吧，这个必须经过1分钟就要把数据删除的，不能过多的留数据，不过也消耗了CPU时间。
这个还是看什么公司具体需求吧，就这么说很难决定用什么方法什么服务器挖~~能做到一个方案全世界的公司都适用么？我是做不到~~~
[解决办法]
两级Hash表吧，比如ipv6地址第一个字节表明在哪台机器，剩下的5个字节作为第二级Hash。
[解决办法]
我的答案是使用DHT（分布式哈希表），然后依照KAD协议来做的
[解决办法]
这个适合用二叉树,不适合用哈希表.
[解决办法]
恭喜恭喜