需求:
一个千万级数据量的服务,不停的插入和删除记录,每条记录需要知道自己的排名,比如SNS中的抢车位,如何让每个uid能够知道自己在所有人中的车总价排名?
致命伤(cache无用论)
有1000万个用户,试想排名第500万的用户突然发飙了,把他的车全卖了,那么他之后的500万个用户的排名都提高了,也就是cache全部瞬间失效了。。。pity,此时加再多的cache只能是浮云
解决方法:
1,划分子空间,比如k心网,不提供全部用户的排名,只提供用户在其好友中的车总价的排名(其实这样更有意义,不过这是产品层面),这样即时一个用户车价变化,影响的也只是其好友的cache,别人不做影响
2,牺牲实时性,算不过来就离线算呗,这个太容易想到了,比如k心网车总价的排名是每12个小时更新一次的
BT的需求:
假如,只是假如,我们就需要uid在所有用户中的实时准确排名怎么办??(产品不想牺牲实时性的UE),这时解决问题只能靠更好的算法模型
扩展的红黑树:
这 个结构在一般数据结构书不提,在CLRS是以扩展话题为讨论的,在TAOCP中是以课后题出现,但在CLRS的视频中可是重点介绍,讲了一节课呢,所以推 荐看这个视频11.Dynamic.Statistics。拷贝书上的介绍nonsense,所以只是简单的介绍一下:扩展红黑树ERBT中,每个节点不 仅有color,link,key信息,还包括了一个很重要的信息=>该节点所有子节点的数目(包括其自身在内),这样每个节点的排名可以在找到它 的那一霎那得到,因为(初始rank(root)=0):
rank(lnode)=rank(pnode)
rank(rnode)=children_count(lnode)+1
而作为补偿,同样需要在更改操作时,维护子节点的数目
查找和维护的时间复杂度都是log(n)
解决方案:
还 是车总价的排名显示问题,我们在内存中维护这样一颗ERBT,key就是车的总价位,当有用户的车总价发生变化时,我们就删除这个节点并插入一个新节点。 当需要显示用户的车总价排名时,先从uid得到车总价的数值(比如从mysql中),然后拿这个数值到ERBT中做查找,当找到这个值的时候,排名自然得 到。
对于千万级数据,log(n)基本在20-30,而使mc的话,每秒请求可以到2万这个级别,我们 假设hash的拉链平均长度为3,也就是使用ERBT的速度理论上是直接hash的1/10,也就是能够支撑2000r/s的请求,这样的能力对于一般的 SNS应用也是够了。当然如果要求更高性能还需要做更多的优化。
故障恢复:
首先这个服务就支持分布式,因为每台机器可以独立的跑ERBT,另外即时down机了,恢复也很容易,只要从mysql中导入数据一遍则自动生成,我们也可以把ERBT定时按照hash的形式dump出一份,以备意外时访问。