用户积分功能的设计

标签: Architecture 异步 数据库 用户 积分 | 发表时间:2013-06-15 22:58 | 作者:四火
出处:http://www.raychase.net

文章系本人原创,转载请保持完整性并注明出自 《四火的唠叨》

用户积分功能的设计 有一个SNS应用,用户在使用的过程中积累积分,例如登陆+3点,个人空间每次浏览+1点,结交每个朋友+5点等等。同时,很重要的一点是,用户需要看到自己的积分累计有多少,能够根据积分划分用户等级,在自己的空间展示积分。

在用户量比较大的情况下(例如超过三千万),这是一个比较典型的读写都很频繁的问题,而且写入的次数可能和读取的次数差别不大(大多数SNS应用中,读次数远超写次数的场景居多,例如用户的状态信息,更新一次以后有成千上万的访问)。

这实际是一个简单,但是典型的功能。试想,给文章投票(例如“顶”一下),给微博统计访问次数,给媒体打分……这些都是非常类似的功能。对于这样问题的思考和设计,考虑到典型性和推广性,是很有价值的。

需要准确的数据?

在常规情况下,我们可以自问自答这样几个关于产品设计约束的问题。例如:

  1. 用户需要看到准确的积分吗?
    1. 如果是别的用户的操作引发了用户积分的增加,允许一定的延时;如果是用户自己的操作,必须实时看到积分变化。例如:有用户关注了我,无论我是否马上知道,理论上我应当立即获得4点的积分,但是这个操作如果不实时反映到用户的积分展示上,对我影响不大;但是如果我发起结交了一位朋友,我希望马上看到我的积分增加了5点。
    2. 在我积分少的时候,我希望看到积分的实时变化;如果积分超过了一定数量(例如10000分),积分的变化实时性变得反而没那么重要。
  2. 用户需要看到准确的积分排名吗?
    1. 我是这个应用的粉丝,我的排名在1000名以内,积分排名非常重要,实时性要求高,当我的积分超过我的竞争对手的时候,我希望看到我的排名立即获得上升;
    2. 我的排名在千里之外,把我排在第9876543名还是8765432名其实对我来说并不重要,兴许,你只需要告诉我我排在十万名之外就行了,我不需要那么高的实时性。
  3. 用户需要知道自己的准确平均分(这种分数是另一种类型,重要的是平均分而不是总分,例如用户可以给彼此打分,再如淘宝网站销售记录里的平均得分等等)吗?
    1. 这个问题也类似,在用户被打分次数比较小的时候,任何一次给用户的打分都会影响到平均分;
    2. 但是在用户被评了几万次几十万次的时候,几十、几百个用户打分都不会对展示的平均分有一丝影响,这时候实时性就没有那么高的要求了。

这些问题,都是需要在产品设计阶段考虑清楚的。当然,从技术实现的角度来说,对于这种大用户量的积分功能的设计,实时性要求越低,越容易实现。我们可以把用户分为多个级别,如果只有那些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三位用户。有很多构建和调整这棵树的策略,例如:

  1. 同层节点是有序的,当用户的积分改变时,该用户id在树中的位置就会发生变化。
  2. 同时,每一个非叶子节点也记录了该节点下递归包含的所有用户id数量p,对于每个非叶子节点x有一个包含所有用户数量的上限f(n),以及下限g(n),其中n为该节点的深度:
    1. 当数量超过f(n)的时候,该节点x会分裂出一个新的子节点来;
    2. 当数量小于g(n)的时候,该节点会和兄弟节点合并。
  3. 可以通过树的节点调整和转换,让树的深度和节点的最大子节点树保持在一个合理的范围内。

我们当然也可以参照一些经典的关于树的数据结构的方案来思考,但总的来说,实现略有复杂,但是这种设计方法有较好的适应性,对于不同的积分-用户分布的情况,同一深度的节点所对应的积分区间各不相同,但总是让每个节点下的用户节点的数量保持在一个可接受的范围内。

如果要获知用户所在的排名,就需要遍历树的节点:找到该用户所在节点所有左侧的兄弟节点和所有递归父节点的所有左侧兄弟节点下所有的用户数量(下图中红色叶子节点存储了需要统计的用户id,蓝色节点所包含的所有用户id数量应当被统计进去):

用户积分功能的设计

数据库的选择和设计

数据库(甚至使用某种文件系统)是必不可少的,以持久化积分或排名的数据。通常情况下,这张表的读取和写入频率都很高,考虑一些常见的优化方式:

  1. 用户积分的表是一张大表,因为许多数据库都是按块读取数据的,尽可能减少每一行的大小可以提高数据库表访问的性能,所以,一定要把这张表独立出来(例如,userId是主键,也关联到用户表的外键,还有一个字段是mark),不能给用户表添加一个mark字段了事;
  2. 数据库sharding,把这张表的userId做散列,分布到不同的服务器上,以减轻服务器压力;
  3. 上面说的是水平切分,也可以考虑垂直切分,我们可以考虑把单独的用户积分表放到单独的服务器上;
  4. 把统计和映像功能独立到其他的服务器上去,尽可能让这些异步的辅助功能不影响主功能的运行;
  5. 如果要选用NoSQL的数据库,根据CAP原理,可用性肯定不能牺牲,分区容忍性也显得相对比较重要,只能牺牲一致性了,比如Dynamo、Cassandra等等。

稍微多说一下关于功能独立的问题,把统计和映像功能独立到其它的服务器上去:

用户积分功能的设计

snapshot的作用仅仅是给当前数据做镜像,在很多情况下,用户的积分变更记录我们需要获知,但是也许不需要获取每次的变更,只需要定期取得这样一个镜像(包括数据库的状态)就可以了;而statistics是进行数据统计挖掘的服务器,数据尽可能从snapshot中获取,以免对主数据库造成影响。

批量和异步

批量和异步都是牺牲实时性和一致性来换取性能的做法。对于用户的评分,不需要每次都实时写入数据库,完全可以积攒到一定的程度批量写入,而且,数据库关心的应当是写入请求提供的增量数据,如“用户xxx评分增加15点”,而不是“应将总点数66553写入数据库”:

用户积分功能的设计

如上例,多台server中,每台机器都会触发事件将用户的积分信息批量写入数据库,一旦满足:

  1. 时间超过t而未写入数据库;
  2. 或内存中待写入的用户数量超过100000
  3. 或容器重启。

在读取环节,选用适当的缓存框架(特别是分布式和多层的缓存框架),可以帮助提高读取性能。需要注意的是缓存数据的过期条件,尤其是在集群环境中。有这样一个常见的场景,用户一个登陆操作增加了自己的积分,也许对于其他用户来说也许实时性并不重要,但是你肯定希望用户自己能立刻发现自己的积分上涨了。这时,积分的增加至少要在当前用户会话所在的服务器机器上体现出来,其他集群机器则可以延迟一些。

文章系本人原创,转载请保持完整性并注明出自 《四火的唠叨》

分享到:
你可能也喜欢:

相关 [用户 积分 功能] 推荐:

用户积分功能的设计

- - 四火的唠叨
文章系本人原创,转载请保持完整性并注明出自 《四火的唠叨》. 有一个SNS应用,用户在使用的过程中积累积分,例如登陆+3点,个人空间每次浏览+1点,结交每个朋友+5点等等. 同时,很重要的一点是,用户需要看到自己的积分累计有多少,能够根据积分划分用户等级,在自己的空间展示积分. 在用户量比较大的情况下(例如超过三千万),这是一个比较典型的读写都很频繁的问题,而且写入的次数可能和读取的次数差别不大(大多数SNS应用中,读次数远超写次数的场景居多,例如用户的状态信息,更新一次以后有成千上万的访问).

海量用户的积分排序问题算法的分析

- - SegmentFault 最新的文章
某海量用户网站,用户拥有积分,积分可能会在使用过程中随时更新. 现在要为该网站设计一种算法,在每次用户登录时显示其当前积分排名. 用户最大规模为2亿;积分为非负整数,且小于100万. 表(user_score)的结构可以如下设计:. 通过使用一个简单的SQL语句查询出积分大于该用户积分的用户数量:.

Android用户不想让iOS用户知道的9个杀手性功能

- 可可 - 36氪
今年第三季度,运行Android操作系统的智能手机占据了智能手机的半壁江山,究竟是什么让Android操作系统如此受欢迎呢. 本文列出的Android系统的9个杀手级功能就是这一问题的最好答案. Android设备里的谷歌地图有turn-by-turn导航功能. 虽然iOS设备里也有谷歌地图,但Android里的谷歌地图有turn-by-turn导航功能,它就像是一个GPS设备,告诉你什么时候该拐弯了.

谷奥: Google 向所有用户开放两步验证功能

- Dolphin - 谷奥聚合——谷奥主站+谷安 aggregator
Google 在去年9月份向 Google Apps 付费用户开放的两步验证登录机制终于面向所有 Google 用户开放了. 进入账户管理页面,你应该可以看到一个全新的 Using 2-step verification 链接,点击即可对此功能进行设置. 两步验证机制对于某些对账户安全性要求较高的用户是非常有必要的,并且 Android / iPhone / Blackberry 都可以使用专用 App 生成验证码而绕过短信验证方式,关于更多的两步验证机制的介绍请参考谷奥之前的报道.

[翻译]不要为了让用户高兴,就添加功能

- cong - Some reminiscences, some memories
原文在此:http://www.zurb.com/article/561/dont-add-features-to-make-customers-happy. 原作者:Dmitry Dragilev. 公司中午年饭,喝了几杯红酒……借着酒劲,七里咔喳把这篇早上看到的关于产品设计的文章翻译了出来. 在将来的产品策略中,你其实不需要为了让你的用户开心,而添加他们要求的功能.

调查显示:90%用户不知道Ctrl+F的功能

- 老男人 - cnBeta.COM
大约一年前,谷歌搜索专家丹・罗素(Dan Russell)得知一个朋友在检索自己需要的字段时,花了整整5分钟才找出他们所需要的部分. 于是,他就萌发了一个想法,他想了解一下究竟有多少人跟他的朋友一样,不会使用Ctrl+F组合键的查找功能. 最近,《大西洋月刊》的调查统计显示,竟然有大约90%的人不知道电脑上的组合键Ctrl+F具有“查找”的功能.

你会做Web上的用户登录功能吗?

- Yousri - 酷壳 - CoolShell.cn
Web上的用户登录功能应该是最基本的功能了,可是在我看过一些站点的用户登录功能后,我觉得很有必要写一篇文章教大家怎么来做用户登录功能. 下面的文章告诉大家这个功能可能并没有你所想像的那么简单,这是一个关系到用户安全的功能,希望大家能从下面的文章中能知道什么样的方法才是一个好的用户登录功能. 以下内容,转载时请保持原文一致,并请注明作者和出处.

Chrome扩展为用户带来远程桌面功能

- Tim - Solidot
Google发布了Chrome 远程桌面 BETA,基于浏览器的远程桌面扩展. 这个扩展可以让用户在一台电脑上控制网络中的另一台电脑,只要它们都运行Chrome浏览器. Chrome 远程桌面 BETA支持包括中文在内的数十种语言,支持Windows、Linux、 Mac和Chromebooks,只要输入一个一次性的认证码,用户就可以通过Chrome连接任意两台电脑.

谈产品功能复杂化及用户角色建模

- - 牛国柱
产品一定为是解决某类用户的问题或者需求而存在的. 但在很多失败产品的开发过程中,我们经常会发现一个规律:. 1、初期,我们一阵见血的提出了产品的核心功能,功能是如此的一阵见血,所有参与人员都为这个未来的产品而欢欣鼓舞;. 2、很快,产品设计人员提交了产品的原型,交付评审. 评审会上,每个领导都说目前的功能太简单,我们需要考虑1、2、3、4、5等等功能,相关部门的同事也七嘴八舌的提出了很多功能;.

如何设计“找回用户帐号”功能

- 雪冬 - 酷壳 - CoolShell.cn
因为《腾讯帐号申诉的用户体验》一文中好多人觉得腾讯申诉是世界级先进的,并让我拿出一个找回用户的帐号的功能来. 本来不想写的,因为大家看看其它系统的就行的,但是,很明显有些人就是很懒,也不会思考,而且不会观察,所以,我就只好写下这篇科普性常识性的文章. 在行文之前,我得先感谢腾讯公司的至少30名员工在《腾讯帐号申诉的用户体验》一文后的回帖(我STFG(Search The Fucking Google)看到了你们使用的那个固定IP在各个大学论坛上的腾讯的招聘广告),我感谢你们主要有两点:.