一站到底
采用SpringBoot构建项目，主要通过分布式缓存、队列、限流保证系统高可用，Netty、缓存、反向代理保证高并发。
双人对战答题、公司对战抢答。
▐ 如何设计排行榜
- 个人总得分和总排名实时更新；
- 个人排行榜按分数、时间、次数、正确率展示；
- 日榜、过去N日榜滚动更新；
- 性能优化过程
第一条需求很简单，使用了Redis的Zset实现不过这里总得分采用了基于分数、时间、次数和正确率的混合加权。考虑到数据的持久化，以及关系数据库和缓存的一致性导致的设计的复杂性，使用了谷歌开源的JamsRanking。
优点是可以直接使用现成的setScores和getRanking接口封装了Redis和Mysql和消息队列的完成事务和一致性的使用细节。缺点是并发比较低使用Jmeter进行压测，单机只有20左右的TPS。
后来看了下源码，主要是它针对每一次设置都进行了分布式事务处理，并且会返回事务提交或回滚的结果。了解了底层实现以后就去谷歌的开源社区去查阅了相关的解决方案，当时官方对这个问题并没有通过配置能直接解决问题的快捷方式，不过推荐了使用者自身如果对响应时间不高的场景下可以采用批量合并事务的方式进行优化。基于这个思路，我们把写操作进行了封装并放入了队列，然后在消费者端批量取得数据后进行事务的批量处理，压测环境下整体性能达到了500TPS。已经基本满足了线上更新的需求，但是当时压测的过程中，队列偶尔的吞吐量会大范围波动，经常会持续数十秒，然后业务一次性处理完再响应，导致局部响应时间大幅度增长。
后来也是在官网上查询，了解到谷歌开源组件使用的队列服务底层是使用BigTable作为持久层，但是当BigTable分片过大时，会触发再分片的过程，再分片的过程中，是不会进行任务分发的，所以就会导致先前的问题。针对这个问题，谷歌官方的建议是提前配置队列的数量、负载策略和最大容量等信息，保证所有队列不同时触发再分片。
进行两次优化后，压测环境已经基本可以满足预期了，在实际生产环境的部署中，发现对于事务更新失败时，JamsRanking会对失败的事务进行切分和重试，整个过程对于研发人员是透明的，不利于线上问题排查，所以我们当时特地写了一个watchdog的工具，监控事务回滚达到十次以上的事务，查明原因后通过后台管理系统进行相应补偿，保证最终一致性。
最终结果：
- 高效快速：能在数百毫秒内找到玩家排名以及进行更新
- 强一致性以及持久化、排名准确
- 可以扩展到任意数量的玩家
- 吞吐量有限制，只能支持约每秒 500次更新。
针对这个缺点谷歌官方也是给出了使用分片树和近似排名的解决方案，当然复杂的方案有更高的运维成本，所以我们优化工作也就到此为止。
- 方案优化过程
方案1：每日一个滚动榜，当日汇聚（费时间）
首先记录每天的排行榜和一个滚动榜，加分时同时写入这两个榜单，每日零点后跑工具将前几天数据累加写入当日滚动榜，该方案缺点是时间复杂度高，7天榜还好，只需要读过去6天数据，如果是100天榜，该方案需要读过去99天榜，显然不可接受。
方案2：全局N个滚动榜同时写（费空间）
要做到每日零点后榜单实时生效，而不需要等待离线作业的完成，一种方案是预写未来的榜单。可以写当天的滚动榜的同时，写往后N-1天的滚动榜一起写入该方案不仅能脱离离线作业做到实时更新，且可以省略每天的日榜。但缺点也不难看出，对于7天滚动榜，每次写操作需要更新7个榜单，但是对于百日榜，空间消耗无法接受，1000万榜单大约消耗1G内存。
方案3：实时更新，常数次写操作
有不有办法做到既能实时更新，写榜数量也不随N的增加而增加呢？
仍然是记录每天的排行榜和一个滚动榜，加分操作也还是同时操作当日榜和全局榜，但每日零点的离线作业改为从全局榜中减去之前过期的数据，从而实现先滚动更新。此方案每次只需读取一个日榜做减法，时间复杂度为O(1)；但是无法做到实时更新。这个方案的优点是在十二点前提前准备好差分榜，到了十二点直接加上当天数据就是滚动榜内容 ，这样就在常数次写操作的前提下，实现了滚动榜的实时更新。
▐ 如何解决重复答题
- 利用setnx防止重复答题
分布式锁是控制分布式系统之间同步访问共享资源的一种方式。利用Redis的单线程特性对共享资源进行串行化处理。
// 获取锁推荐使用set的方式String result = jedis.set(lockKey, requestId, "NX", "EX", expireTime)
// 推荐使用redis+lua脚本String lua = "if redis.call('get',KEYS[1]) == ARGV[1] then return redis.call('del',KEYS[1]) else return 0 end";Object result = jedis.eval(lua, Collections.singletonList(lockKey)
▐ 一个题目被多个人抢答
利用redis来实现乐观锁（抢答），好处是答错的人不影响状态，第一个秒杀答对的人才能得分。
- 利用redis的watch功能，监控这个 Corp:Activ:Qust: 的状态值；
- 获取Corp:Activ:Qust: 的值，创建redis事务，给这个key的值-1；
- 执行这个事务，如果key的值被修改过则回滚，key不变；
▐ 如何管理昵称重复
使用布隆过滤器：
它实际上是一个很长的二进制矢量数组和 K 个哈希函数。当一个昵称加入布隆过滤器中的时候，会进行如下操作：
- 使用 K 个哈希函数对元素值进行 K 次计算，得到 K 个哈希值。
- 根据得到的哈希值，在位数组中把对应下标的值置为 1。Na
用户新增昵称时需要首先计算K个哈希值，如果K个哈希值有一个不为0则通过，否则不通过，不通过时通过加随机字符串再次检验，检测通过后返回给前端，帮助用户自动填写。
布隆过滤器的好处是它可以用来判断一个元素是否在一个集合中。它的优势是只需要占用很小的内存空间以及有着高效的查询效率。对于布隆过滤器而言，它的本质是一个位数组：位数组就是数组的每个元素都只占用 1 bit ，并且每个元素只能是 0 或者 1。
BloomFilter 的优势是，全内存操作，性能很高。另外空间效率非常高，要达到 1% 的误判率，平均单条记录占用 1.2 字节即可。而且，平均单条记录每增加 0.6 字节，还可让误判率继续变为之前的 1/10，即平均单条记录占用 1.8 字节，误判率可以达到 1/1000；平均单条记录占用 2.4 字节，误判率可以到 1/10000，以此类推。这里的误判率是指，BloomFilter 判断某个 key 存在，但它实际不存在的概率，因为它存的是 key 的 Hash 值，而非 key 的值，所以有概率存在这样的 key，它们内容不同，但多次 Hash 后的 Hash 值都相同。对于 BloomFilter 判断不存在的 key ，则是 100% 不存在的，反证法，如果这个 key 存在，那它每次 Hash 后对应的 Hash 值位置肯定是 1，而不会是 0。
▐ 如何管理出题定时任务
压测环境中服务器通过Netty的主从Reactor多路复用NIO事件模型，单机可以轻松应对十万长连接，但是每个业务中，由于每个用户登录系统后需要按照指定顺序答题，例如一共要答十道，那么服务器针对这一个用户就会产生十个定时任务，所以对于系统来说，定时器的数量就是百万级别的。
通过压测结果发现：JDK自带的Timer，在大概三万并发时性能就急剧下降了。也是此时根据业务场景的需要，将定时任务改成了Netty自带的HashedWheelTimer时间轮方案，通过压测单机在50万级别下依然能够平滑的执行。
也是这个强烈的反差，使我在强烈的好奇心促使下，阅读源码了解到常规的JDK 的Timer 和 DelayedQueue 等工具类，可实现简单的定时任务，单底层用的是堆数据结构，存取复杂度都是 O(NlogN)，无法支撑海量定时任务。Netty经典的时间轮方案，正是通过将任务存取及取消操作时间复杂度降为 O(1)，而广泛应用在定时任务量大、性能要求高的场景中。
基于Netty的Websocket底层，服务器端维护一个高效批量管理定时任务的调度模型。时间轮一般会实现成一个环形数组结构，类似一个时钟，分为很多槽，一个槽代表一个时间间隔，每个槽使用双向链表存储定时任务。指针周期性地跳动，跳动到一个槽位，就执行该槽位的定时任务。
单层时间轮的容量和精度都是有限的，对于精度要求特别高、时间跨度特别大或是海量定时任务需要调度的场景，可以考虑使用多级时间轮以及持久化存储与时间轮结合的方案。时间轮的定时任务处理逻辑如下：
- 将缓存在 timeouts 队列中的定时任务转移到时间轮中对应的槽中
- 根据当前指针定位对应槽，处理该槽位的双向链表中的定时任务，从链表头部开始迭代：
- 属于当前时钟周期则取出运行
- 不属于则将其剩余的时钟周期数减一
- 检测时间轮的状态。如果时间轮处于运行状态，则循环执行上述步骤，不断执行定时任务。
