NoSQL海量用户积分排行算法琢磨【转载】

正文内容

  • 问题
  • 储存结构
  • 算法1:简单SQL查询
  • 到底法2:均匀分区设计
  • 算法3:树形分区设计
  • 算法4:积分排行数组

该文具体来源哪儿,不是杀确定,而我是当某某微信公众号及见到底~文中的情节相比较有启发性的~

问题


某海量用户网站,用户所有积分,积分可能会面以运过程被随时更新。现在如为该网站设计同样栽算法,在每一回用户登录时显得该眼前积分名次。用户太特别局面为2亿;积分为非负整数,且小于100万。

PS:据说这是迅雷的一道面课题,不过问题本身有着异常强之实,所以本文打算以真实面貌来设想,而无囿于为给试题的优异条件。

储存结构


第一,我们所以同样摆用户积分表user_score来保存用户之积分音讯。

表结构:

NoSQL 1

演示数据:

NoSQL 2

下的算法会基于这大旨的申结构来展开。

算法1:简单SQL查询


先是,很轻想到的缓解方案是,用同久简单的SQL语句询问有积分大于该用户积分的用户数量:

select 1 + count(t2.uid) as rankfrom user_score t1, user_score t2

where t1.uid = @uid and t2.score > t1.score

对此4号用户我们可以收获下边的结果:

NoSQL 3

算法特点

  • 亮点:简单,利用了SQL的功效,不需复杂的查询逻辑,也无引入额外的蕴藏结构,对小框框仍然性质要求未赛的使用不失为一种植好的解决方案。
  • 缺点:需要对user_score表举行全表扫描,还得考虑到查询的又即使有积分更新会对表造成锁定。在海量数据规模和赛起的用被,性能是无能为力经受之

到头来法2:均匀分区设计


以群拔取中缓存是釜底抽薪性能问题的重要途径,我们当然会想,是否可以把用户名次用Memcached缓存呢?不过又挂念发现,缓存似乎帮不达标啊忙,因为用户名次是一个全局性的总结性目的,而毫不用户之个体属性,其他用户的积分变化或者会晤这影响及按用户之排行。但忠实应用被的积分变化实在是有早晚规律,平常一个用户的积分不晤面蓦然暴增暴减,一般用户总是要以低分区混迹很丰盛一段时间才会师日渐升起可强分区,也就是说用户积分的分布是发生区段的,我们越来越注意到大分区用户积分的微小变化实在针对亚分段用户之行影响不死。于是,大家得以想到按积分区段举行总结的方,引入一摆分区积分表
score_range

表结构:

NoSQL 4

数量示例:

NoSQL 5

表示 [from_score, to_score)
区间有count个用户。若论每1000分叉来划分一个距离,则发出[0, 1000), [1000,
2000), …, [999000,
1000000),共1000个区间,未来对用户积分的更新要对应地换代score_range表的区间值。在分区积分表的拉扯下询问积分为s的用户排行,首先确定其所属区间,把高于s的积分区间的count值累加,再查询有拖欠用户以准区间内的排行,二者相加即可获取用户的行。

乍一收押,这么些方法一般通过区间聚合缩短了询问总括量,实则不然。最老的问题在安询问用户以以区间内的排名呢?假倘使于算法1遭之SQL中丰裕积分标准:

select 1 + count(t2.uid) as rankfrom user_score t1, user_score t2

where t1.uid = @uid and t2.score > t1.score and t2.score < @to_score

每当地道图景下,由于把t2.score的克限制于了1000盖内,如果对score字段建立目录,我们愿意之SQL语句以透过索引大大缩短扫描的user_score表的行数。可是真实意况并非如此,t2.score底界定在1000盖内并无意味着该距离内的用户数为是1000,因为这边出积分相同之气象有!二八定律告诉我们,前20%之低分区往往集中了80%底用户,这就是说对此大气低分区用户展开区间内名次查询的性质远不如对个别底强分区用户,所以当相似意况下这种分区法无碰面带实质性的性能提升

算法特点

  • 长:注意到了积分区间的是,并透过先行聚合消除查询的全表扫描。
  • 短:积分非均匀分布之特色令性能提高并无美。

算法3:树形分区设计


统统匀分区查询算法的挫败是由积分分布的非均匀性,那么大家自然就会想,能不可能按照次八定律,把score_range表设计呢未净匀区间也?比如,把低分区划密集一点,10分一个距离,然后逐渐变成100细分,1000私分,10000分

当然,这真是一栽格局,然而这种分法有必然的随意性,不便于把好,而且整个类其它积分分布会随着以如渐渐发生变化,最初的较好之分区法恐怕会合变得不适应将来底情景了。我们巴找到同样栽分区法,既可以适应积分非均匀性,又可适应系统积分分布之变动,这虽是树形分区

大家得将[0, 1,000,000)作为顶尖区间;再将一流区间分为三只2级区间[0,
500,000), [500,000, 1,000,000),然后拿二级区间二分吧4单3级区间[0,
250,000), [250,000, 500,000), [500,000, 750,000), [750,000,
1,000,000),依此类推,最后大家会见取得1,000,000单21级区间[0,1), [1,2) …
[999,999,
1,000,000)。这实际上是管区间社团成为了平等种平衡二叉树结构,根结点代表超级区间,每个非叶子结点有一定量单子结点,左子结点代表低分区间,右子结点代表大分区间。树形分区协会要在革新时保持一如既往栽不变量(Invariant):非叶子结点的count值总是顶其左右子结点的count值之和。

NoSQL 6

从此,每一次用户积分有转移所用改进的间隔数量与积分变化量有涉及,积分变化越来越小更新的区间层次越小。总体达成,每一趟所需要更新的距离数量是用户积分变量的log(n),也就是说要用户积分相同破变于百万级,更新区间的数额在二十夫级别。在这种培训形分区积分表的支援下询问积分为s的用户排行,实际上是一个每当间隔树上由上到下、由小及细一步步确定s所在地方的进程。

随,若积分为499,000,排行先河值为0。首先,它在左子树[0,
500,000)区间,此时底用户排行是这些右子树[500,000,
1,000,000)的用户数count值累加到拖欠用户名次上,接着,它置身[250,000,
500,000),所以未用累加count到排行变量,直接入下一级区间;再次,它属于4级区间的…;直到最终大家将用户积分精确定位在21级区间[499,000,
499,001),整个累加过程做到,得出排行!

虽然,该算法更新与询问都关乎到多单操作,但假如否距离的from_scoreto_score树立目录,这个操作都是基于键的询问以及换代,不会晤生出表扫描,因而效用又胜似。另外,本算法并无依赖让关周密据模型和SQL运算,能够随便地改造也NoSQL等任何存储方,而基于键的操作为蛮容易引入缓存机制进一步优化性能。进一步,我们得估算一下树形区间的数码大约为2,000,000,考虑每个结点的高低,整个结构就占几十M空间。所以,我们完全可以当内存建立区间树结构,并经user_score表在O(n)的日内起头化区间树,然后名次的查询与翻新操作都得以于内存举行。一般来讲,同样的算法,从数据库及外存算法的属性提升日常可以齐10^5以上;由此,本算法可以齐丰裕大之性。

算法特点

  • 瑜:结构稳定性,不深受积分分布影响;每便查询或更新的复杂度为积分最老价值的O(log(n))级别,且同用户规模无关,可以答应针对海量规模;不指让SQL,容易改造为NoSQL或内存数据结构。
  • 缺陷:算法相对更复杂。

到底法4:积分排行数组


算法3虽说性能比高,达到了积分变化之O(log(n))的复杂度,可是落实上相比复杂。其它,O(log(n))的复杂度只以n特别大之时候才显它的优势,而事实上使用中积分的变情形屡屡不谋面极其可怜,这时和O(n)的算法相比往往无明了的优势,甚至可能更慢。

设想到立时同样境况,仔细察看一下积分变化对名次的切实影响,可以窥见某用户之积分从s变为s+n,积分小于s或者抢先等于s+n的其他用户排行实际上并无谋面被震慑,唯有积分在[s,s+n)区间内之用户名次会下降1位。大家好用于一个大小也1,000,000底数组表示积分和名次的呼应关系,其中
rank[s]表示积分s所对应之排名。开始化时,rank数组可以由user_score表在O(n)的复杂度内总结而来。用户名次之询问与翻新基于这数组来进行。查询积分s所对应之行平昔归rank[s]即可,复杂度为O(1);当用户积分从s变为s+n,只待将rank[s]到
rank[s+n-1]立n个因素的价值扩充1即可,复杂度为O(n)。

算法特点

  • 瑜:积分排行数组比区间树还简明,易于落实;排行查询复杂度为O(1);名次更新复杂度O(n),在积分变化不雅的情景下颇神速。
  • 症结:当n可比好时,需要更新大量因素,功效不设算法3。

总结


地点介绍了用户积分名次之几乎种植算法,算法1简单容易了然与促成,适用于有些圈圈及低产出应用;算法3引入了重复扑朔迷离的树形分区协会,可是O(log(n))的复杂度性能优越,能够行使为海量规模及高起;算法4以简约的行往往组,易于落实,在积分变化不慌之景色下性能不逊色让算法3。本问题是一个开放性的问题,相信一定还有其他优良的算法和解决方案,欢迎钻探!

网站地图xml地图