http://www.raychase.net/1453
有一个SNS应用，用户在使用的过程中积累积分，例如登陆+3点，个人空间每次浏览+1点，结交每个朋友+5点等等。同时，很重要的一点是，用户需要看到自己的积分累计有多少，能够根据积分划分用户等级，在自己的空间展示积分。
在用户量比较大的情况下（例如超过三千万），这是一个比较典型的读写都很频繁的问题，而且写入的次数可能和读取的次数差别不大（大多数SNS应用中，读次数远超写次数的场景居多，例如用户的状态信息，更新一次以后有成千上万的访问）。
这实际是一个简单，但是典型的功能。试想，给文章投票（例如“顶”一下），给微博统计访问次数，给媒体打分……这些都是非常类似的功能。对于这样问题的思考和设计，考虑到典型性和推广性，是很有价值的。
需要准确的数据？
在常规情况下，我们可以自问自答这样几个关于产品设计约束的问题。例如：
- 用户需要看到准确的积分吗？
- 如果是别的用户的操作引发了用户积分的增加，允许一定的延时；如果是用户自己的操作，必须实时看到积分变化。例如：有用户关注了我，无论我是否马上知道，理论上我应当立即获得4点的积分，但是这个操作如果不实时反映到用户的积分展示上，对我影响不大；但是如果我发起结交了一位朋友，我希望马上看到我的积分增加了5点。
- 在我积分少的时候，我希望看到积分的实时变化；如果积分超过了一定数量（例如10000分），积分的变化实时性变得反而没那么重要。
- 用户需要看到准确的积分排名吗？
- 我是这个应用的粉丝，我的排名在1000名以内，积分排名非常重要，实时性要求高，当我的积分超过我的竞争对手的时候，我希望看到我的排名立即获得上升；
- 我的排名在千里之外，把我排在第9876543名还是8765432名其实对我来说并不重要，兴许，你只需要告诉我我排在十万名之外就行了，我不需要那么高的实时性。
- 用户需要知道自己的准确平均分（这种分数是另一种类型，重要的是平均分而不是总分，例如用户可以给彼此打分，再如淘宝网站销售记录里的平均得分等等）吗？
- 这个问题也类似，在用户被打分次数比较小的时候，任何一次给用户的打分都会影响到平均分；
- 但是在用户被评了几万次几十万次的时候，几十、几百个用户打分都不会对展示的平均分有一丝影响，这时候实时性就没有那么高的要求了。
这些问题，都是需要在产品设计阶段考虑清楚的。当然，从技术实现的角度来说，对于这种大用户量的积分功能的设计，实时性要求越低，越容易实现。我们可以把用户分为多个级别，如果只有那些top用户的排名才显得很重要，那么可以区分对待，例如对于100名以内的用户排名需要实时计算，那么实际可以实时计算200名以内的用户排名（其中的后100名用户视作缓冲，可能会和前100名用户排名发生交换）。
数据结构设计
这里谈论数据结构的设计主要是考虑到在如此高的读写频率下，我们需要在内存里面存放一部分或全部的用户积分信息，以减少对数据库或者文件存储系统的压力。
map
最常见的一种数据结构就是使用一个LRU的map，需要获知积分数据的时候，先根据用户的id去这个map里寻找积分数据。排名的问题要麻烦一些，如果非实时要求，可以定期、单独计算排名，例如每天凌晨1点算一次排名。对于那些top用户，他们的排名信息也和积分数据一样，使用一个LRU的map缓存在内存里面。在数据量不是非常大的情况下，所有的积分、排名信息都可以存储在内存中。
这个map如果对并发性能要求高，可以自己设计读写算法，也可以寻找开源实现。对于JDK中的ConcurrentHashMap，我曾经测试过，它的写入速度要略好于没有加同步保护的HashMap，但是读取速度大大低于没有同步保护的HashMap（大约只有一半）。
数组
使用数组也是适合的，特别是在用户id分布规律的时候（例如从1到999999），只需要一个大小为1000000的数组，由于访问是随机访问，非常快。在设计排名的时候，数组有一个妙用：用户积分的变化往往不大，例如从1024分变到1026分，但是如果要考虑排名实时性，就不得不把整个用户的排名重新计算一遍，这显得杀鸡用牛刀。如果把数组设计以存储排名信息，但是数组的下标不是表示用户id，而是表示积分：
例如上图，左侧是数组下标，右侧的中括号里表示的是排名，右侧逗号分隔的数表示的是相应的用户id。现在id为50的用户积分1024点，因为某个操作而增加了两点，变成了1026点，他的排名只需要计算上述三个蓝色表示的数组元素所存储的排名就够了，也就是说，积分少量的变化不需要进行整个数组排名的重计算。
树
树是一种有趣的办法，它的好处在于通过节点的分裂和合并，使得其的结构和节点内元素数量总是处在一个合理的位置：
每一个非叶子节点（实线）都分裂出若干个节点，直到叶子节点（虚线）为止。每个叶子节点关联若干个用户id，例如上图中，积分为100077的用户包括了403、7886和36651三位用户。有很多构建和调整这棵树的策略，例如：
- 同层节点是有序的，当用户的积分改变时，该用户id在树中的位置就会发生变化。
- 同时，每一个非叶子节点也记录了该节点下递归包含的所有用户id数量p，对于每个非叶子节点x有一个包含所有用户数量的上限f(n)，以及下限g(n)，其中n为该节点的深度：
- 当数量超过f(n)的时候，该节点x会分裂出一个新的子节点来；
- 当数量小于g(n)的时候，该节点会和兄弟节点合并。
- 可以通过树的节点调整和转换，让树的深度和节点的最大子节点树保持在一个合理的范围内。
我们当然也可以参照一些经典的关于树的数据结构的方案来思考，但总的来说，实现略有复杂，但是这种设计方法有较好的适应性，对于不同的积分-用户分布的情况，同一深度的节点所对应的积分区间各不相同，但总是让每个节点下的用户节点的数量保持在一个可接受的范围内。
如果要获知用户所在的排名，就需要遍历树的节点：找到该用户所在节点所有左侧的兄弟节点和所有递归父节点的所有左侧兄弟节点下所有的用户数量（下图中红色叶子节点存储了需要统计的用户id，蓝色节点所包含的所有用户id数量应当被统计进去）：
数据库的选择和设计
数据库（甚至使用某种文件系统）是必不可少的，以持久化积分或排名的数据。通常情况下，这张表的读取和写入频率都很高，考虑一些常见的优化方式：
- 用户积分的表是一张大表，因为许多数据库都是按块读取数据的，尽可能减少每一行的大小可以提高数据库表访问的性能，所以，一定要把这张表独立出来（例如，userId是主键，也关联到用户表的外键，还有一个字段是mark），不能给用户表添加一个mark字段了事；
- 数据库sharding，把这张表的userId做散列，分布到不同的服务器上，以减轻服务器压力；
- 上面说的是水平切分，也可以考虑垂直切分，我们可以考虑把单独的用户积分表放到单独的服务器上；
- 把统计和映像功能独立到其他的服务器上去，尽可能让这些异步的辅助功能不影响主功能的运行；
- 如果要选用NoSQL的数据库，根据CAP原理，可用性肯定不能牺牲，分区容忍性也显得相对比较重要，只能牺牲一致性了，比如Dynamo、Cassandra等等。
稍微多说一下关于功能独立的问题，把统计和映像功能独立到其它的服务器上去：
snapshot的作用仅仅是给当前数据做镜像，在很多情况下，用户的积分变更记录我们需要获知，但是也许不需要获取每次的变更，只需要定期取得这样一个镜像（包括数据库的状态）就可以了；而statistics是进行数据统计挖掘的服务器，数据尽可能从snapshot中获取，以免对主数据库造成影响。
批量和异步
批量和异步都是牺牲实时性和一致性来换取性能的做法。对于用户的评分，不需要每次都实时写入数据库，完全可以积攒到一定的程度批量写入，而且，数据库关心的应当是写入请求提供的增量数据，如“用户xxx评分增加15点”，而不是“应将总点数66553写入数据库”：
如上例，多台server中，每台机器都会触发事件将用户的积分信息批量写入数据库，一旦满足：
- 时间超过t而未写入数据库；
- 或内存中待写入的用户数量超过100000
- 或容器重启。
在读取环节，选用适当的缓存框架（特别是分布式和多层的缓存框架），可以帮助提高读取性能。需要注意的是缓存数据的过期条件，尤其是在集群环境中。有这样一个常见的场景，用户一个登陆操作增加了自己的积分，也许对于其他用户来说也许实时性并不重要，但是你肯定希望用户自己能立刻发现自己的积分上涨了。这时，积分的增加至少要在当前用户会话所在的服务器机器上体现出来，其他集群机器则可以延迟一些。
