本文转载自http://www.cnblogs.com/nankezhishi/archive/2009/09/12/1565274.html
作者：南柯之石
很多网游中都有排行榜，这里就专门讨论一下这个排行榜背后的数据库设计。一
开始我觉得这是一个基本的数据库设计问题。只需要有一个实体，没有实体间的关系，没有复杂的逻辑。网络上也搜索不到太多关于这类设计的问题，好像根本不值
得为其写个文章。但是在公司专门做了一个月的排行榜数据库设计。才发现问题根本没有看上去那么简单。甚至一篇文章都难以讲明白。不知自己误入歧途了，还是
这个问题的确就是很复杂的。所以写个文章讲给大家，或许能有人一语道破。
一开始听到要设计一个排行榜，觉得很简单，一个外键加一个分数列，排名不保存在数据库中，每次查询都实时计算。不就得了？
接下来，就来讨论一下这种方案的可行性。先来描述一下经过最简化的基本要求：
1. 参与排行的设计用户量为1000万左右。
2. 并不要求实时，一小时更新一次。（我一开始的想法很天真，实时不是更好？所以才试了这个实时的排行榜）
3. 排行榜的结果要正确。（最废话的一条，其实很关键，直接导致实时方案作废。）
生产环境，数据库服务器：
CPU：双路4核，至强。
内存：32G。
开发、测试的环境：（以下运行时间数据基于此环境）
CPU：赛扬D 2.66G
内存：1G。
建表：
Create Table RealTimeCLB
(
UserId INT NOT NULL PRIMARY KEY,
Rating INT NOT NULL
)
放数据：一定要用Tran。
BEGIN TRAN
DECLARE @I as int
SET @I = 0
INSERTDATA:
INSERT RealTimeCLB VALUES(@I, RAND()*10000000)
SET @I = @I + 1
IF @I < 5000000
GOTO INSERTDATA
COMMIT TRAN
插入500万数据就用了16分钟，心里有点怵了。实时计算排名会不会慢呢？不管了，试试再说，反正真正的服务器很强大的说。注意Rating值是用随机数生成的。
为Rating列加索引：
CREATE INDEX IX_RealTimeCLB_Rating ON RealTimeCLB (Rating);
加索引又用了30秒。
查询：
SELECT TOP 100 *, RANK() OVER (ORDER BY Rating DESC) AS [rank] FROM RealTimeCLB
用时0秒。很快啊。会不会影响并发的数据更新呢？
UPDATE RealTimeCLB SET Rating = Rating + RAND() * 1000 where UserId = 2
运行没有影响。
这里要解释一个问题。如果查询时，有更新操作，那查询出来的不就是脏的了吗？这个是可以接受了。更新晚于查询，再正常不过了。所以这个不是个问题。
但是如果世界就这么和谐了，也就不用研究一个月了。本文只是这一个月的第一天而已。
因为查询的方式多种多样。上面只查了前100名，很快。但是如果随便一个想查一下自己的名次呢？这也是必须要实现的基本功能。
查询指定用户的名次：
SELECT *, RANK() OVER (ORDER BY Rating DESC) AS [rank]
FROM RealTimeCLB WHERE UserId = 1
如果你看到这里没有大叫，就说明你没有仔细看，或者至少对SQL不熟悉。因为上面的语句永远返回1。无论查谁，都是第1。
正确的SQL有很多写法，下面是其中一种：
SELECT * from
(SELECT *, RANK() OVER (ORDER BY Rating DESC) AS [rank] FROM RealTimeCLB) AS d
WHERE d.UserId = 1
很不幸，这条语句用了4.5秒。如果用1000万用户的数据量，岂不是要10秒？如果你不知道为什么查询自己很慢，就找本书看看索引是如何运作的吧。这里我就不解释了。
也许我的SQL比较低效（你有快的吗？要实时计算。）。但是QQ和MSN之类用户已经有2亿了，如果那天也要做个迅雷样的排行榜。实时？那还了得？数据库服务器天天别干别的了，光排个名就排不过来了。
把Rank做为一列放进表里，查询不就快了？那更新不就慢了？更新一个人的分数，就要给一群人重新计算排名。你SQL写得好，在500万数据量上，也要5秒运行时间。
所以结论就是，排行榜，在大用户量和当前硬件环境下，是不可能实时的。
如果有人说，我们数据量很小，就10万用户，那总可以了吧？一次查询也就0.05秒，还可以了。听上去是可以了。SQL Server 2005提供的Rank函数，让按列计算排名快了很多。但是还是不行！因为上面的方法，无法保证最基本的一个需求，正确性！
可以不管查询出来的数据是旧的，但是一定要正确啊。但是上面的方案，不能保证查询结果的正确性！
而下面的解释，才是本文的重点部分。
回到查询语句
SELECT * from
(SELECT *, RANK() OVER (ORDER BY Rating DESC) AS [rank] FROM RealTimeCLB) AS d
WHERE d.UserId = 1
UserId是外键，而且用来查询的UserId一定存在，但是就是这个语句会出问题，有看出什么问题吗？
问题就在于，这个语句返回的行数不确定！逻辑上，一个User一个Rank，但是这个语句，可能会返回两个或两个以上的结果行，甚至可能没有返回（即使UserId存在）。
出现的必要条件：
1. 在这个查询语句正确运行时，同时有数据更新。
2. 表上的Rating列建有索引。
表上有索引，就可能有这个问题，经过测试，如果把表上的索引删除，这个语句一定有一个返回行。
大家应该已经猜到问题的所在。在有索引的表上更新索引列，索引树为了保持平衡，就要同时改变索引数据的位置。如果同时有基于此索引的查询，就有可能因为索引节点在索引树上跳来跳去而遗漏或是重复读取一些节点。从而导致上面的问题。
解决方案1：查询时加表锁。既保证了正确性，又保证了时效性。但是查询的时候，就不能更新数据了。放弃。
解决方案2：不加索引。先把索引删除。
DROP INDEX IX_RealTimeCLB_Rating ON RealTimeCLB
那么在500万数据量下的查询速度如何呢？
SELECT TOP 100 *, RANK() OVER (ORDER BY Rating DESC) AS [rank] FROM RealTimeCLB
要21秒。100万数据要4秒。基本上成正比。其实时间就是花在了排序上。所以运行时间基本上只和排序算法的效率相关。因为没有了索引，所以查询一个用户的时间也和这个差不多。如果你说你们只有几千用户量，还可以试下这个方法。
解决方案3：还是别实时了~~~~~，详见下回分解。
posted @ 2009-09-12 14:17
南柯之石 阅读(2215)
评论(83) 编辑 收藏 
发表评论
固执的用一个思路解决所有问题。
TOP 100和自己是第几名根本就不是一个问题。
#2楼[
楼主]2009-09-12 14:38 |
@Ivony...
我本来想给大家解释一下为什么查自己是第几名很慢。不过一想这种基础问题应该都知道。就没有理解。
你有兴致你来吧。我是没有自信，把这个问题用三言两句跟一个不知道索引如何发挥作用的人讲明白的。
你有什么高招能让查询自己是第几名也用0秒？
同楼上
top 100 在索引上查询 和数据量基本无关
自己名次的话必须全索引扫描才能得到 随数据量线性增长
#5楼[
楼主]2009-09-12 14:45 |
我是说你的思考方式有问题，可以仔细的体会一下固执这个词。
老实说，实时排行不可行是很武断的结论。
一个问题，根据外界条件的不同，解决方案也应该随之不同。如果就像你在文章一开始提到的场景，网游或者别的什么的积分排行。为什么不能更深入的思考问题？在这种场景中，用户排名的变动幅度会大么？如果不大，怎样有效的利用前一次的查询结果？
还有RANK最终的查询计划到底是怎样的？有没有优化的空间？能不能不用RANK？没有RANK怎么办？
继续，当然也会遇到数值变化区间小，排名变化幅度大的场景，在这种场景又有什么办法？
#7楼[
楼主]2009-09-12 14:48 |
@progame
多谢。看得好细心啊。
我就没有解释为什么慢，都来解释一下。
我是觉得懂的人，不用解释；不懂的人，你用两句话解释一下，他还是不懂。所以我才没有解释。
以后文章还是给懂的热心人再解释清好了。
省得自己还得解释为什么不解释清——！
#8楼[
楼主]2009-09-12 15:05 |
@Ivony...
没有深入研究，我也不会贸然下这个结论的。
在公司一开始做项目的时候，公司的Principle就说榜行榜没有实时的。我不信，所以才自己试试为什么不行。试过才知道，用户量大的时候就是不行。
至于你说的问题。
1. 用户排名变化大不大不一定，但是这个不能做为基本假设。如果一个游戏如此设计：两人比赛一次，胜者把负者一半的分数拿来。好。如果最后一名和第一名比赛赢了。你说排名变化大不大？
2. 利用前一次的结果的办法当然也有想过。但是你想到吗？我没有想到。如果不和数据库，自己用C++写个程序维护一个排名。一个人的排名变了，也许不用全部重新排一次，但是在数据库的框架内，我没有想到好的办法。
3. T-SQL Querying介绍的做Rank有四种方法。Rank函数作为SQL SERVER 2005的新功能。是专门用来做排名的，也是四种方法中最快的。如果你没有了解过，可以看看那本书。
你提的问题很好，但是你“武断”地认为我一个月来，我和我的同事们从来没有考虑过这个问题，是不是也武断了些呢？
文章开头我就说了。这潭水很深，几篇文章都介绍不完的东西。就算我能一下把我考虑到的东西全写出来，只怕读者都没有信心看完。
如果你知道什么好的解决方案，希望你不吝赐教。
说别人“固执”的时候，最好也同时提出一个不“固执”的方案来。不然是没有说服力的。
不懂SQL
Server
2005提供的Rank函数，但这个问题应该挺容易解决的，Server端自己写一个缓存，每次更新数据库之前先更新下缓存就行了，照样实时。10M用户
的ID加上Rating，也不过几十M的空间，无非更新时更新一下缓存需要一定的计算。设计一个特殊的数据结构，就可以将这个计算量控制在很小的程度，因
为每当Rating变化时，只会影响到Rating相近的几个用户的排名，比较一下这些Rating相近的用户的位置就行了。
你还是不能体会固执这个词。
比如说第一点，为什么不能做这个基本假设？你是在解决问题还是在设计RANK函数？你是不是需要去面对所有的情况。那么在这些所有的情况中，的确存在不能逾越的障碍。但不足以武断的说实时排名就不可行了。
我
们来看第二点，至少你得承认，这是在你的局限里（数据库框架内）才有可能使得这个问题无解，如果跳出这个局限（就像你说的C++之类）这个问题又是不是还
会存在呢？或者你至少应该说“为什么用SQL Server 2005
RANK函数在这种情况下实时排名不可行”或者“为什么在我的场景下实时排名不可行”。如果你认为我在咬文嚼字那就忽略吧，但就我的观点里，用词严谨的程
序员才可能思路严谨。
最后，我想问你的是，为什么不能假设需求的范畴，却能假设客户一定接受你们使用SQL Server 2005呢？这些在你看来理所当然的事情就是我所说的固执。在我看来，正是这种执念让你看不到事情的真相。
顺便问一句，就像上面指出来的，干脆直接做一个排名字段而不是采用实时运算的方案，你们这一个月又有多少时间认真考虑过？
如果继续固执下去，恐怕就是再研究上一年也还是这样。
#12楼[
楼主]2009-09-12 15:21 |
@xiaotie
你的建议很好。这个方法的确可以解决问题。
但是为什么我们没有用呢？因为在实现的项目中，排行榜要比你想像得复杂多。
比如我做的这个游戏中的排行榜。
有3类游戏模式。每类游戏模式有7种排行。每种排行有Overall，Daily，Weekly三个时间度量。这样就会有63个榜。（如果还要有Monthly就是84个榜。）
每个榜计算排名的时候，要参考7个数据参数（以尽量防止排名相同）。
这样，实际的数据量会是这个示例中的450倍。而且上面只是榜行榜的基本信息，榜行还有排名趋势等要显示。缓存，怕是32G内存的服务器上也不敢啊。
^_^
抽完了之后问题的根本还是几个基本的问题，无非三种情况，评分范围大，排名变化小；评分范围小，排名变化大；评分范围和排名变化都很大。
根据不同的情况，有不同的优化策略，无论把问题描述的多么复杂，不影响其抽象模型。
帮LZ设计一下。
一个64位的array A，每个元素的前32位存储rating，后32位存储用户id。A的容量需要比数据库表的现有用户量大一些，假设是现有数据库容量的120%，则A的前20%的元素置空，留给新id。A已经排好序。
另一个64位的array B，前32位存储用户id，后32位存储rating，也是排序排好了的。同样B的容量也是120%。后20%为空。
这样一来就可以了，不会给系统添加几千万对象，对GC造成压力。
新添加一个id，加到A的第一个数据之前的那个空位，然后，往B的尾部加进去，再对B进行排序。千万级数组在内存中排序比较轻松。考虑到新添加id不频繁。就先这样处理。
更新某Id的rating时，先从B中查找到前32位是该id的项，根据该项的后Id以及A中的空元素数量可以找到A中的该项，进行修改，然后和上下几个进行比较，进行局部排序。操作非常快。
查询某Id的rating，直接对A进行查询就可以了。
基本上上面的操作，除了新增ID稍稍可能花的了几ms，其它的计算量都非常小，可以忽略不计。
成本：加入有10M用户，需要多40*1.2=48MB内存。对GC来说，新增几个对象而已，不会造成压力。
几分钟写出来的，可能不完善 。。。。。。
数据库在持久化的情况下做实时排名压力非常大，排名字段不能做索引，分数不能做索引，除非你把用户分割成多个小表，实时排名汇总，结合实际应用情况，实时才有可能
#16楼[
楼主]2009-09-12 15:39 |
@Ivony...
我很想问一下，你看过文章的标题前半部分没？
我讨论的就是数据库上的排行榜设计。所以没有你说的“如果跳出这个局限”。
我还想问一下，你有没有看过文章标题的后半部分？
本文讨论的就是实时的排行不可行。所以没有你问的“干脆直接做一个排名字段而不是采用实时运算的方案”
我不期待你看到文章的结尾说，“详见下回分解”“不实时的”方案。
也不期待你看到文章中间说的，结论中“在大用户量，在当前硬件环境下”这样的字眼。
更不期待你看到文章中说，我在这里讲的，只是我这一个月里一天之中想到的。
但是我希望你在明白别人在说什么之前，别看见什么喷什么！
程序员就是这样，总是希望别人写个文章也想像也个程序一样。少个If语句就说不成文了。这不是严谨，是迂腐。
以你这样的心态，什么文章，什么结论，都足以让你喷得死去活来。
其实你心态也很好，觉得自己看个帖子想到的，就比别人一个月想到的多。佩服。佩服。
#17楼[
楼主]2009-09-12 15:41 |
@Ivony...
对，不影响模型，但是影响内存占用。谢谢。
解决方案二根本就不可行
把索引删除，就算你能承受100w-4秒的速度，但是如果真的是100w的用户，那每分钟有没有60次的排行榜查看？
然后你没了索引，是不是每次都需要去扫描全表？
扫描全表你到底是nolock还是带共享锁？
不带锁查询会不会就不是实时查询？
带锁是不是会阻塞或被要更新分数的语句？
如果你真的应用到实际情况中去，你就必须要应付我提到的这些问题
解决方案一没看太多，大意是不是加索引？
加索引每次分数的更新都要变化树，一棵100w的树也是不小了，而且这种索引的更新经常是加一分两分，大多是在索引页里面挪动，挪来挪去就造成大量碎片，还有大量的等待时间，加锁因唯一便宜了实时查询排行，但是实时更新分数方面却要付出很多代价
#19楼[
楼主]2009-09-12 15:53 |
@Keep Walking
一看回复，就知道你是也做过的。握握手。
不知你说的不能给Rating加索引是基于什么原因？
听语气好像是性能上的原因？
莫非数据库除了RANK和索引就没别的招了？或者说xiaotie的方案就只能在内存？
往上翻，xiaotie的方案思想上就是在更新时同步更新排名而不是实时计算排名的措施。这个非要到数据库之外去么？！
借用你的话，懂的人，不用解释；不懂的人，你用两句话解释一下，他还是不懂。所以我也懒得解释了。
既然您认为您的科研团队投入了很大的成本，所以就足以得出结论的话。
@南柯之石
先
不考虑复杂的数据结构了，还是上面的数据结构。如果每个榜计算参考7个数据参数，则计算完了作为Rating的实值，内存中只保留Rating，不保留其
它参数。这样就算一个榜是50M，84个榜，4.2G。每个榜的Array B合并成1个Array，这样大概一个榜算40M，84个榜，3.3G。
计算趋势不需要实时吧，就放数据库了。
如果需要的榜更多，可以把两个Array放到文件中，用定长记录存放，就可以Scale了。
这种问题，用数据库解决肯定是最慢的方案了。当然，如果不需要实时，还是用数据库方便。
#22楼[
楼主]2009-09-12 16:01 |
@xiaotie
说实话，细节没有看太明白。不过大意了解了。
不过有几个问题和建议。
问题：
1. 这个缓存程序放在什么地方？放在数据库服务器？Web服务器？
2. AB两个Array都没有保存Rank信息，直接用下标当Rank？
建议：
基于你的设计。
查询时间的复杂度是O(N),
更新复杂度是O(N) + M*LOG(M)，M是局部排序数据量。理论上比较小。
但是数据库：
查询时间复杂度是LOG(N)。更新比较慢。
你的方式瓶颈应该在于查找指定ID在Array中的位置。如果用HashTable会不会更好？
PS：你好像还没有看到我关于真实数据量的回复。
#23楼[
楼主]2009-09-12 16:08 |
哎，你想让我怎么样，你才愿意先看看我的文章呢？死活不愿意看我的文章的内容，还非愿意出来喷人。
他的方案，在文章中已经讨论过了。
如果在你的概念里，实时排行的定义就是：
实时的，从大量随机数据里，使用某个规则，计算出任意一条数据的排行。
结论是：不可行。
我想这种命题并不需要您们的科研团队去研究吧。
抱歉我们所理解的都是利用各种方法，满足客户的实时要求。
你的文章很好看，因为结论都摆出来了么：
所以结论就是，排行榜，在大用户量和当前硬件环境下，是不可能实时的。
#26楼[
楼主]2009-09-12 16:11 |
@xiaotie
排名实时，趋势当然要实时了。不然显示出来的排名和趋势岂不是不匹配了？至于其它参与排名的参数。如果不是和Rating一起缓存，又如何保证数据的同步性呢？
@南柯之石
查询时间的复杂度是OLOG(N)。没用hashtable是考虑内存占用，还有不给系统一堆零碎的对象去干扰GC。10M数据，log(n)很小的。
他所说的趋势实时是指你06:30:45查与前一天的排名变化趋势取的参考数据是前一天的午夜00:00:00的数据还是06:30:45的数据。
否则有实时的排名怎么趋势有什么问题？
@南柯之石
其它参数放数据库里面，这里只是把数据库不擅长计算的地方提出来放内存中。趋势如果觉得需要实时也可以放出来，内存再加一点。数据库就那点API，你没法干扰和控制。而这种记录定长，自己用Array和定长文件来处理，程序又不复杂，性能可以做到极致。
#30楼[
楼主]2009-09-12 16:19 |
可能我Out了，我就是这个意思。
因为积分的规则是不确定，不能保证积分没有大的变化。
这个也没有让我们团队研究过。一开始我就被告知，实行榜行是不可行的。研究它到底有多么的不可行是我的个人行为。
文章中基本要求已经说了，客户的要求是一小时更新一次。我说实时不是更好？
从这里你看不出来什么是我说的实时？
可以想象一下如果在分数上做索引，那么这个表最经常更新的是不是分数？索引原则第一条就是不能经常更新
其实如果你们公司有专门的dba，数据量超大，可以考虑使用olap方案，方案不是太实时，但是性能可以得以保证
那我就告诉你吧，如果要实时的从一大堆无序数据里面根据某条规则得到某条数据的排行，必然要进行排序，排序的时间复杂度在近几年内不可能有飞跃的发展，也就是说这是不可行的。
你说的加索引不也就是把排序提前到更新时么？这与别的解决方案并没有本质上的不同。
不过，你也可以理直气壮的去找那个告知你实时排行榜是不可行的人喷，只要你愿意。
#34楼[
楼主]2009-09-12 16:25 |
@Ivony...
没错，结论就是这个。
不知道你见过哪个网游的榜行榜是实时的？
不是他们不想做，是做不出来。
再纠正一次，是做得出来的，如果不固执的坚持一些东西的话。。。。
不做实时是没有必要的缘故。
@Ivony...
感觉还是Server端缓存实时排名，然后数据库隔一段时间记录一下快照，进行比较，这样比较好。
#37楼[
楼主]2009-09-12 16:31 |
@Keep Walking
哦。这个原则，的确是知道，但是根据测试结果来看，不加索引，查询要20秒，加了之后只要0.几秒。
而更新的时候似乎并不慢。
从结果上来看，似乎加索引合理些吧。
个人觉得，没有什么放之四海皆准的原则。只有测试测试再测试。
其实我上面已经给了我的一个初步想法了，根据需求分情况优化，例如排名基分范围大0-10000000000，大于排名数据总量的N倍，每个数据排名范围变化较小的话，显然就用你的方案就是合适的，无论具体是存在哪边，这个思路走下去就应该做的出。
但是如果反过来，排名基分范围小，如0-100（考试分数），小于排名数据总量（全市中小学生），这样排名的变化范围就会变得很大（你多一分就加很多名），或许就有别的思路来解决问题。
#39楼[
楼主]2009-09-12 16:35 |
@Ivony...
喷他什么？
喷他说“榜行可以实时！就是一次查询要5秒钟而已！”
然后回家找工作？
所以没有什么好喷的。你可能站得高，看得远，把我的一个白痴结论想复杂了。其实大家都一个意思……
#40楼[
楼主]2009-09-12 16:37 |
@Ivony...
没有必要实时？
你玩个游戏难道不想随时看到自己当前时间的排名？
看现在个个都是一天一排的，习惯了吧？
#42楼[
楼主]2009-09-12 16:41 |
@南柯之石
A,B
两个Array都放了Rating数据，id和rating都是int32，两个Array是int64的Array，只不过一个是id在前rating
在后，一个是rating在前，id在后。主要是考虑两种查询，一个是根据id查询，一个是根据rating取排行榜。至于放哪里，不清楚部署啊。根据前
面的估算，除了占几G内存外，对系统的影响不大。看实际情况tradeoff吧。
@Ivony...
都是局部化的。你说的那样的话，可能用带index的list(linkedlist)比较好。
@Ivony...
其实基分小最好搞了，每个基分搞个桶。。。。。。
如果你的更新分数的并发量不大，可以建索引，不然如果你真的应用到实际环境下去，那是灾难性的。
不单单是索引更新，还有这个索引在bufferpool里面都会不长驻留而导致经常性的物理读，物理读和逻辑读，那可是天远地远
你可以自己尝试模拟并发试试，我现在的mysql环境下稍微控制不好，就是超时，全阻塞着表
#49楼[
楼主]2009-09-12 17:05 |
#50楼[
楼主]2009-09-12 17:06 |
@Keep Walking
好。我再测试测试。
谢谢你的提醒啊。
另外有没有什么用来测试数据库并发的软件？推荐一下？
@Ivony...
其实排序问题的关键是掌握问题的约束情况而不是傻乎乎的用那些经典排序。经典排序是对最常用的情况的排序，它不考虑问题的约束条件，因为它必须通用。数据库的索引设计也是通用的。针对特定的问题，设计专用的方案，肯定比通用的性能要高的多。
在
离散事件仿真中，仿真事件的调度算法也就是排序问题：假定有1M个事件待调度，要在这1M个事件中找到时间最先的事件。经典的方案是Heap排序，用了很
多年，后来，人们根据事件的时间这一约束情况，提出了Calendar排序，根据时间散列，插入事件和取出最早事件的复杂都都是O(1)了。俺的一个项
目，对实时性要求很高。通用的Calendar排序因为要考虑到通用性，它可以适用全部的情况。但为了保证通用性，它的散列桶的宽度（根据时间区间散列
的）是要动态调整的，这一点对实时性有很大影响。因为项目的专用性，俺就把桶的宽度调整为0.0001s（因为俺的实时性要求是0.1ms），结果系统的
实时性就从0.01s提高了2个数量级到0.1ms。
因此，对一个解决方案的定制会得到高的多的性能。比如数据库它的设计是为通用设计的，而我们每个项目的方案都是专用的。通用用于专用，必然带来非常大的损失。
自己写缓存其实和数据库做的是同样的事情，问题是，数据库的设计必须考虑通用性，而自己写不用考虑通用性，就可以有很大的弹性很大的设计空间。代价就是，用数据库写的话，想修改排名方法比较好修改，自己写专用的排名的话，要改方案就比较麻烦了。
而这个方案中，要实现实时查询，就必须实时计算及更新积分和排名。因此，问题就在于实时更新积分和排名的代价问题。看看积分排名的约束条件：
（1）排名是有局部性的，一次积分的更新，只会影响部分排名。最好测量一下这个局部性，如果这个局部性很强，或者大部分情况下这个局部性很强，那就很好搞了。
（2）
排名的敏感性。对排名靠前的，排名是很敏感的，而对排名靠后，排名是不敏感的。也就是说，排名靠前的，排名必须准确，排名靠后的，排名不必须准确。一个排
名前100的，排名必须绝对正确。而一个排名是500万的，存在正负10甚至正负100，正负1000的误差是可以允许的。
另外，（1）和（2）是相关的。当排名在后面时，排名不敏感，排名的局部性不强，一次输赢可能排名上升下降几十万。当排名在前面时，排名敏感，但积分的局部性很强，一次输赢，就影响几百个ID的排名。
因
此，对于排名靠前的，就进行局部重拍。对于排名靠后的，可以采用影子更新策略。即，当积分变化较大时，只更改积分和排名，而不进行实际意义上的重拍。也就
是说，假如一个人的积分是12万，他的排名是358万。这一把，他赢了，积分是12万零800。查找积分是12万零八百人的排名是320万，就用这个排名
作为他的影子排名，而不进行局部重拍，此时，系统会出现两个排名同时是320万的。在这种情况下，人们是不会关心排名的个位数十位数的，允许有一定的误
差。对于排名重复情况，比如，如果一个房间里出现了两个排名一样的人。这种情况是极其罕见的，为了绝对的消除它，在客户端可以进行消重处理，增加或减少某
位的排名就行了。大家排名都是几十万几百万的，无所谓个位数的排名。
计算影子排名时可以应用查找法，向前或先后查找和积分相同或相似的人的排名，作为影子排名。当然，这还是有一定的代价。代价更少的方法是插值法，向前向后找几个数据，插值算一下就行了。
当实时排名数据从服务器端传递到客户端这个时间延迟，就会导致排名后面的那些人的排名顺序出现变化。因此，对排名在后的人，排名注定存在本质的测量的不确定性。所以，进行影子排名乃至插值估计都是可行的。
隔一段时间，再进行实际意义上的重排来纠正误差。
这里面可能会涉及到复杂的设计问题。原理上应该如上。
这样一来，就可以把更新局部化了，基本上O(1)了。当然，前面的ArrayB不是O(1)的。而如果换成Hashtable，也是O(1)，不过代价较大。
如果是我，一定不会死磕数据库方案。
1.不保存什么排名；
2.也不保存排名和分数的关系。
这样，实时的排名就解决了。这就是以空间换时间。
应用程序启动的时候，创建一个“排名器”。加载所有用户的分数，在内存中建立分数与名次间的索引。在每次更新用户分数的时候，通知排名器。任何时候如果需要用户的名次，由排名器提供。注意一点：应用程序与排名器间的通信需做并发控制。
当然，如果你一定要死磕数据库方案也勉强可以，如果是SQL Server 2008你可以用SQL CLR。虽然SQL Server 2005也支持SQL CLR，但是不支持在SQL CLR中做并发控制。
一般游戏好像有排名英雄榜
所以最前面的比如说100或1000名必须要准确并且实时
这个问题不难 更新分数的时候顺便也更新这个英雄榜
如果最多显示前100个 可以维护前110名的列表
而其它的用户就无所谓了 定期重算 比如说一小时或一天
其实大家都可以接受
如果大家很关心自己的排名
那就每次分数变化时去估个排名变化数去更新
当然如果说一定要找技术的解决方案就另说了
但很多时候纯技术并不是解决需求的最好方案
#55楼[
楼主]2009-09-12 18:35 |
@progame
谢谢你，这个的确是个很合理的方案。
所有问题都应该从需求上解决问题而不是从技术上。
我们的需求也很宽松，连英雄榜都不需要实时。所以完全用数据库也比较好实现。
本文只是一个技术探索，告诉对这个领域还不熟悉的人，现在做实时大用户量排行很难。同时给出一些数据，好用来说服一些不太了解情况的客户……^_^
很久没看见过这么精彩的辩论了..
园子里就需要这样的气氛
#57楼[
楼主]2009-09-12 18:50 |
@双鱼座
呵呵，不错。
实际的方案就是写了一个第三方程序，专门做排序工作。
这个可能会在下一篇拿出来给大家SHOW一下。
我觉得这个问题可以这么去做：
因为数据量很大的时候，每次查询都去重新计算排名显然不合适，因为可以在误差允许的最小范围时间段内重新计算每个用户每种排行的排名，然后缓存起来，需要的时候再读取缓存中的数据即可。
数据结构：
UserId（用户id）、RankId（排行榜id）、UserRank（用户排名）
（1）如果对速度要求高的话，直接将缓存结果保存在内存中；
（2）如果对速度要求稍低，将缓存结果放到数据库表中，并对3个字段都建立索引。
讨论的中心一点： 更新和索引之间的关系。
楼主提出的想法是： 用Rank排序，并且在指定字断有索引时，查出来
的数据是不准确的， 锁以弃用索引，情愿西生点时间，
我的看法是： 排行榜很难做到实时， 如果不是很需要，也没有必要
做成实时， 大约一个小时排一次就好。 缓存的思路个人不太看好，
不过XiaoTie的思路很给人启发。
楼主提的这个话提很有讨论性
#61楼[
楼主]2009-09-12 22:29 |
@Wuya
谢谢你的方案，前面也有人提到用缓存的方案。
但是没有详细描述缓存的实现方式。
基于你的描述和我个人的理解。缓存可以有两种。
一种是用数据库影子表。这个和XiaoTie的提法有些想像。定时把真实的排行数据做个快照。然后用户查询排行就从这个快照表里查。这个快照表就是一种只读缓存。
缺点是：
1. 排序工作还是由数据库来做。给数据库带来不小的CPU负担。
2. 工作量很难实现分布式运算。
另一种是在Web服务器上，由JSP也好，PHP好也，ASP.NET也好实现的内存数据缓存。
缺点是：
1. 数据同步占用网络带宽。
2. 内存占用大，实现方式略为复杂。
#62楼[
楼主]2009-09-12 22:33 |
@不若相忘于江湖
其实我的想法就是排行榜很难做成实时的。^_^
#63楼[
楼主]2009-09-12 23:07 |
@xiaotie
一直没有回复你的，因为要仔细考虑下。
你的方法很有启发性，从程序设计的角度，的确可以用排行榜本身的特殊性使得排行榜的运算简化很多并高效。
你的方法才引发了我更多关于软件开发的思考。不针对你的解决方案，只是表达一下自己的看法。
局域性和敏感度都是很好数学模型，但是模型的建立、分析、实现和应用到实际产品中都是有成本的。一个产品是否使用一个方案不仅仅要考虑它的效果还要考虑它的成本。
比快速排序快的排序算法很多。但是只有快速排列被做为了各种程序设计语言的标准排序方式。因为它是最实惠的。简单的实现就可以换来很高的效率。
我们都承认数据有局部性，但是我也应该看到人也是有局部性的。你觉得500万名之后的人不会在意自己的排名的个数。但是你有没有考虑过，对于一个身在500万名的人，他会把自己名次和谁比？不还是和自己附近的人比吗？
这时，每一个名次区间都是平等的。没有敏感不敏感之分。
影子排名是个很好的解决方案，在启发式算法中很有用，但是如果想得到确解，这个方案还不够完美。
select count(0) from [user] where rank > user.rank
MyRank = count + 1
@南柯之石
这个问题我前面也讨论过，就是测量的不确定性。一个测量，在数据库那边得出结果，传递给客户端，客户端看时的结果是传递过来的结果。客户端在t2时看到的结果是t1时的结果，而在t2-t1这段时间里，系统又发生了变化，所以他看到的结果不是t2时的真实结果。
这就是排名在后面的人排名的一个本质的不确定性，没法消除的不确定性。这个不确定性的存在使得排名后面的人的准确性变得毫无意义——因为它的排名随时都在变化，每一秒都在变化，但这个变化的幅度又不大——因此，允许存在误差。
也就是说，假定排名在500万排名的人他的排名以一种随机噪音的方式在飘动，假定这个噪音在正负X之间。因此，只要保证排名的准确性在正负X之间就行了。这种情况下，你在波动范围内随便说一个数说不定比计算的结果还准确。
@南柯之石
每
一个区间的人肯定是不相等的。假设A积分是在500万-510万之间，如果A是和同在500万-510万之间的人B比，因为这后面人的排名波动性大，下一
次，B不知道跑到哪里去了，A找得到找不到还是一个问题。如果A记住了B的名字，只需要将B的排名显示出来时和A进行消除就行了。因为系统排名每一秒都在
变化，所以不需要准确到个位都不差。
对于排在前面的那些排名由于稳定性很强，随时间变化不明显，就要准确了。
上面方案还没考虑到的一个问题就是游戏用户一般是只有少数人在线，多数人不在线。如果把这个先验知识考虑进去的话，估计还可以得到更好的方案。
通用性和专用性是个权衡，一般来说，专用方案比通用方案有数量级的提升（俺的体会），而专用方案在很多领域里都是know-how，外人不知，也没兴趣知道，或者无法知道——比如你这个系统里局部性到底怎么样——俺无法知道，只有测量才知道。
至于实时还是定时更新，更是工程上的TradeOff了。这里只是讨论技术可行性——我的估计是，千万用户的实时排行是可行的——至于有没人做是另外一码事，这地球上太多事情没人去做了。
为什么别人做实时排行榜就没那么多困难？
因为楼主不虚心 自己以为一点皮毛研究就叫深入了
随便提个简单的思路 就是把常变化和不常变化的分组
把整个表划分为活跃和不活跃两个部分
生成活跃用户在不活跃森林中的分布。
活跃的公式 和计算需要的冗余数据是在最初设计的时候就要收集的
不活跃的数据不以行计算 而以不活跃block计算
比如 用户提升了1级 从100000 越过了一个10000的非活跃用户block 到达90000排名
对，我就是这个意思。每一种特定的场景，都会有最优的解决方案。就像LZ的例子，在需求上必然存在特定的逻辑。但他只打算使用现有的RANK和索引来解决问题，这就是我所说的固执。在这种执念下，只可能得出不可行的结论。
查询自己的排名
直接查询比自己分数高的人数,再加上1
这样的速度会不会比楼主的方法快点？
#71楼[
楼主]2009-09-13 18:45 |
@传说中的天堂落日
没错，在有索引的条件下，平均要快1倍。因为不需要计算整个排名。
但是其实还是一个数据级的。还是不能满足大数据量时的性能要求的。
你这个跟使用排名函数分页，取第N页数据是一摸一样
大数据量肯定不行
#73楼[
楼主]2009-09-13 23:07 |
@Microshaoft
我就是在证明肯定不行。
不过好像大家对自己都很有信心的样子。
那么大数据量，应该如何快速地取到第N页呢？
更进一步，如何快速取到包含特定行的页呢？
呵呵，灌下水，楼主莫怪，能不能试试分布式？把用户拆分到10个服务器中，先记下某个家伙在哪台服务器里，然后查出他的得分，然后其他9台服务器并行处理再汇总结果，10台不行就100台:)
declare @n int ,@userid int
set @userid=12
select @n=COUNT(*)+1 from RealTimeCLB where Rating>(select Rating from RealTimeCLB where userid=@userid)
select @n
楼主：
请参见 的排行榜
共15个排行榜，实时的，可翻页，速度。。。。你自己体验，虽然线上只有6w数据。但是，在百万级用户的测试环境下跑过。速度和你现在看到的6w的一致。
甚至，还能与昨天的排名做比较。
数据库是死的，人是活的，凡事不存在定论。
刚看到你刚才放的话，你可以在看看，可以直接定位到用户自己的排名
#78楼[
楼主]2009-09-15 22:28 |
@FP0991
如果真是这样，那是太牛了。那就是复杂度为O(1)的方案了。
不过，我文章中讨论的是1000万级以上的用户量的排行榜，结论是大用户量，实时排行是不可行的。
这个网站的用户量即使有10万。实时排行也是可以的。
你说测试过100万，不知道你是如何测试的。因为如果有100万人，那么假设PCU有1万。以一场比赛一分钟计算，服务器每秒要处理200次的比赛结果，进行比分的更新，同时可能有每秒100次的查询。你的测试，对这些都准确模拟了吗？
我不知道是不是我的网络问题，这个6万人排行榜，点下一页要1.5秒出结果。我觉得是不可接受的。
呵呵,你访问慢是因为页面在构造 Flash，Flash 需要加载部分资源。但这已经发生在浏览器获得数据之后了。
你可以用 HttpWatch 去抓包，我2M ADSL 电信线路，响应速度在 0.18秒
顺便说一下，实现上效率几乎与用户数量无关。
大量并发请求导致响应速度变慢，那是必然存在的问题。
目前单台服务器极限每秒只能处理100场不到一点的战斗，其中包含比分更新和排行榜调整的操作。
但系统是分布式的，前端WEB服务器可以按需要增加。排行榜之类信息的运算虽然运算量相对很小，但也自然不会放在WEB服务器上，有独立服务器处理。与WEB服务器之间采用WCF传递数据。
咱的服务器可不是超级运算中心哦，呵呵！
没有细看
不过lz如果做过数据挖掘，就知道怎么生成中间数据，就是数据的数据。
之后再datamining去排名
应该说接近实时的绝对可行。如果lz坚持要在4000w数据里面去做排序，那么没有办法。
但是做了数据挖掘，建了数据表，估计延迟也就1、2分钟，如果服务器吞吐量够，延迟降低到几秒绝对没问题。这个算是实时了吧。
然后搜索top10的时候只是在一些中间表里面找，不找原始数据，那么速度快很多。
兄弟 可否留下QQ号 在线请教下? 我现在在做一个排行 正遇到查询问题 想请教下 一般排行的做法是怎么做的 查前多少名好查 查某个人的排名怎么去查 我用的是MYSQL
排名没想过，不过楼主的SQL上我个人觉得有些地方写的并不是太好。自己测试了一下，也不知道对不对，发出来大家看看，批评批评。
05 | id INT IDENTITY(1,1) PRIMARY KEY NOT NULL, |
16 | INSERT test VALUES(RAND()*10000000) |
26 | SELECT TOP 100 RANK() OVER(ORDER BY rating DESC),* FROM test |
30 | SELECT TOP 100 * FROM test ORDER BY rating DESC |
36 | (SELECT *, RANK() OVER (ORDER BY Rating DESC) AS [rank] FROM test) AS d |
43 | SELECT id FROM test WHERE rating>(SELECT rating FROM test WHERE id=1) |
阅读(3324) | 评论(2) | 转发(0) |
