人言,权力越大,责任越大。本人身为一个800人qq群的管理,权利倒是没体会到,责任倒是一大堆,不断有人来问各种问题,大部分情况下其他人就回答了,不过也有人指明希望我回答,对此本人表示相当的无奈,好在年底并无什么急事,所以有时间还是会回答的。

昨天,有人就提出了这个问题,

某海量用户网站,用户拥有积分,积分可能会在使用过程中随时更新。现在要为该网站设计一种算法,在每次用户登录时显示其当前积分排名。用户最大规模为2亿;积分为非负整数,且小于100万.

本人之前也做过类似的东西,只是用户数远远达不到这个量级。自然解决思路也大不相同,在用户少的时候,我们通过一个redis sort set可以胜任。但是如果用户有2E肯定就不能这么做了。

要得到用户的排名,我们需要找出的是比这个用户分数高的人的数量。为此,我们建一系列的“桶”。分数在0-1000000,那么我们建1000个桶,每个桶表示1000分的范围,如0-999,999-1999……..,我们在获取排名排名的时候,我们先根据用户的userid找到用户的score,然后根据它这个score所在的区间找出属于哪个桶,然后我们找出比这个桶的区间大的所有桶的人数之和,再加上他所在本桶的排名。

下面,我们把整个过程捋一遍。

  • 首先是用户的信息的存储,这个过程mysql即可胜任,可以根据用户的id水平分表。然后根据userid缓存,缓存可以设置过期时间,因为并非所有用户都是活跃的,设置过期时间可以保证只缓存活跃用户。用户更新积分可以根据userid取出score,计算后再插入,此过程可以用redis的hash,也可以单独一个k-v,k为userid,v为score。
  • 接下来,我们生成一批"桶",数据结构为redis sort set,key为bucket:$n,$n为数字,bucket:$n表示的分数范围为1000*$n到1000*($n +1)-1。里面存的是userid和score。假如用户是3870分,那么$n = 3870/1000.得出的桶为bucket:3,我们需要统计所有$n>3的桶里人数之和,再加上他在本桶内的排名即为他的排名
  • 那么更新用户积分的时候,我们先看用户的新score和旧score跨桶没有,如果没有,只需要更新用户的分数,然后给bucketnum表里桶对应的人数+1即可,如果跨桶了,则需要从以前的桶里移出来,然后把userid查进新桶。对应的bucket的表里也需要对应的增减。整个过程可以先进队列,然后依次操作。
  • 上面的过程很显然有个弊端,那就是如果用户分数很低,那我们岂不是需要查找很多桶,分别找出他们的人数,再相加?为此我们还需要一个单独的list ,key为bucketnum,每节值为bucket:$n的$n*1000+(999-index)对应的总人数。如3000的桶里,存的依次是3999,3998......3000分数的人数,这样就可以避免实时查询每个桶的人数了,我们要找$n以前的桶,只需要lrange('bucketnum',0,(999-n)),然后把每个节点的值相加即可。


在上诉的开发中,我们采用的桶是sort set,对应的是userid,score,1000个桶,平均每个桶有20W的用户,实际开发中我们知道,分数的分布明显不是均匀的,这样会导致的结果是某个桶的人数过多,如果我们不需要获取排名人的详细信息,只需要获取排名即可,我们每个桶可以采取list结构,存的是对应这个段的人数,比如分数为bucket:3的index为3节点存的是分数为3003的总人数,要想获取积分为3003的分数所在的排名,我们需要算出$bucket:$n ,$n>3的桶的人数之和,以及3桶里,lrang('bucketbum',0,996)的结果之和

以上只为本人胡思乱想之作,未经实际验证,只是提供一种思维而已。