浅谈接龙红包的技术实现

jiyuzi

前言：
　　春节快到了, 今年的互联网红包大战打得特别的火热.
　　阵容强大, 腾讯微信/手Q, 阿里支付宝, 新浪微博, 还有千呼万唤始出来, 犹抱琵琶半遮面的百度钱包.
　　类型多样, 有秒杀型的红包, 如微信的摇一摇, 支付宝的"打地鼠", 也有常规红包, 如支付宝新春红包.
　　与去年的一家独大相比, 今年是你方唱罢我登场, 各领风骚数十载.
　　对于我个人而言, 印象最深的不是戳破手机屏的"打地鼠", 而是接龙红包, 本文尝试去分析接龙红包背后的技术实现, 以及接龙红包本身所隐藏的强大社交性.


游戏模型：
　　让我们先来阐述下接龙游戏怎么玩？
　　1). 大财主发放某个特定数值的红包
　　2). 好友猜测该数字, 若猜中则平分红包，若失败则收敛并继续传递下去(接龙)

　　一图胜千言，大财主发放了66块的红包, 由3个好友分支尝试猜测该数值.
　　1). 小狗旺旺, 刚要猜的时候, 却发现慢了半拍, 接龙游戏已结束
　　2). 小红猜测失败, 但没有继续传递下去
　　3). "斗地主联盟"经过两轮收敛猜对了数值
　　因此该接龙游戏的优胜者是"斗地主联盟", 其接龙传递链上成员共享奖金, 如66元的红包, 每人各得33元
　　当然在一次接龙游戏中, 一个用户只能参与一次, 这样接龙游戏的图模型具备如下约束:
　　1). 不能构成环
　　2). 用户节点不能同时出现在2个及以上的子树分支中
　　结合简单示例, 我们可以最终得出接龙模型为树结构. 而且其树结构有如下特征:
　　1). 节点分支多, 好友社交关系决定
　　2). 树深度浅, 二分逼近收敛快, log(n)指数 (100块, 最多需要7次)
　　3). 向上回溯，树节点只需维护父节点， 不需要维护子节点
架构设计：
　　如何选用合适的存储来维护该树结构，并完美的支撑其业务需求. mysql，key/value系统, 还是自定义存储结构？
　　其实我们不用烦恼了，支付宝已经给了明确的答案.

　　对, 你猜得没错,这就是key/value系统.
　　让我们来简单分析下, 为何key/value系统是最适合的存储技术.
　　1). 接龙游戏本身的树节点本身是松散自由的, 每个节点都是一个信息入口
　　2). key/value能快速访问各个树节点
　　3). key/value读写性能优异
　　对于所发的红包，我们还是采用mysql表来存储：

　　对于接龙的用户而言，采用分布式的key/value来存储，假设这边采用leveldb.
　　key为接龙的数字, 用整数表示
　　value采用protobuf格式

message tw_envelop {
    required int32 user_id = 1;         // 当前节点的用户
    required int32 type = 2;            // type表示用户性质, 0:主人, 1:接龙者
    required int32 envelop_id = 3;  // 红包id
    required int32 pioneer_key = 4; // 承接的上一个接龙key
    required int32 lower_val = 5;   // 当前接龙红包数值的下限
    required int32 upper_val = 6;   // 当前接龙红包数值的上限
};
　key/value系统维护的树结构, 可以用下图来描述:

　　对于每个接龙游戏只允许用户参与一次, 这种情景限定如何实现呢?
　　其实这类去重问题很普遍, 解决的技术手段也容易，这边采用最简单的key/value去重即可.
　　key的设计如下:
envelop_id:user_id

注: envelop_id为红包id, 而user_id则为实际的用户帐号
　　抛开树形结构如何去存储的问题后, 我们来看看, 什么是红包游戏最核心的技术呢?
　　口令ID生成器, 如何保证id生成是唯一的, 另一方面保证ID生成没有规律.
　　这边就不再具体展开, 但这个技术问题, 是有一定挑战性的.
挑战:
　　接龙游戏当前所遇到的问题, 我觉得是安全问题, 随意输入口令是否存在窃取他人红包的风险. 技术本身反而是简单的.
总结:
　　不管怎么说, 支付宝的红包(特别是接龙红包)无疑是成功的, 借助社交(微信)来做病毒式传播, 起到了很好的效果. 本篇文章, 是个人对接龙红包实现的理解, 有不足之处, 还请轻拍. 如有机会, 让我们谈谈秒杀型红包的实现。
写在最后：
　　如果你觉得这篇文章对你有帮助, 请小小打赏下. 其实我想试试, 看看写博客能否给自己带来一点小小的收益.