Loading... <p style="color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> <em><strong>前言:</strong></em><br /> 红包是支付的方式, 也是社交的延伸。群红包在这两块领域串联得很好, 表现尤为的浓墨重彩. <br /> 承接上两篇技术浅谈:<br /> 1). 浅谈接龙红包的技术实现.<br /> 2). 浅谈微信红包摇一摇的技术实现.<br /> 这一次, 让我们谈谈群红包的技术实现. 一为是红包的分配算法, 二为竞抢的技术实现. </p> <p style="color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> <em><strong>分配算法:</strong></em><br /> 最初玩群红包的时候, 并没有意识到分配算法的难度. 下意识的觉得, 不就是个随机算法嘛? so easy! 后来在知乎上看到很多人在讨论, 才意识到该算法或许并不简单. <br /> 好的东西, 往往让人觉得简单, 而其背后默默挨打的小怪兽(精细和缜密), 你是否可曾留意过.<br /> 我们先来看看, 最自然的随机算法, 为何不合理?<br /> 假设T为总金额, k为红包个数, 每次获取先保底(每人至少得最小金额为0.01), 然后取随机剩余数<br /> 则Ai的迭代公式为: </p> <div class="cnblogs_Highlighter sh-gutter" style="margin:10px auto;color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> <div style="margin:10px auto"> <div id="highlighter_848767" class="syntaxhighlighter cpp" style="margin:10px auto;font-size:1em !important;background-color:#FFFFFF !important"> <table border="0" cellpadding="0" cellspacing="0" style="border:1px solid silver;width:655px;height:auto !important;margin:0px !important;padding:0px !important;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important;font-size:12px !important;background:none !important" class="ke-zeroborder"> <tbody> <tr> <td class="gutter" style="border:1px solid silver;vertical-align:baseline !important;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important;color:#AFAFAF !important;background:none !important"> <div class="line number1 index0 alt2" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> 1 </div> <div class="line number2 index1 alt1" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important"> 2 </div> </td> <td class="code" style="border:1px solid silver;vertical-align:baseline !important;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important;background:none !important"> <div class="container" style="margin:10px auto;border:0px !important;padding:0px !important;vertical-align:baseline !important;background:none !important"> <div class="line number1 index0 alt2" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> Ai = random(0.01, T – 0.01 * (k – i) – A0 – … – Ai-1) (0 <= i < k – 1) </div> <div class="line number2 index1 alt1" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important"> Ak-1 = T – A0 – … – Ak-2 (最后玩家所得) </div> </p></div> </td> </tr> </tbody> </table></div> </p></div> </div> <p style="color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> 貌似简单合理, 殊不知<span style="line-height:1.8 !important;color:#FF0000"><strong>头重脚轻</strong></span>, 统计概率上, 排前面的值往往大于排后面的值, 当k很大, 最后几位往往会被收敛为0.01.<br /> 显然不合理, 这篇<<微信红包的算法实现探讨>>博文也证述了该现象. </p> <p style="color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> 结合上面的例子, 一个好的分配算法, 必须具备以下几个条件:<br /> <strong>1). 每个玩家都能领到红包</strong><br /> <span style="line-height:1.8 !important;color:#0000FF"><strong>2). 所有玩家的红包钱数和等于总数</strong></span><br /> <span style="line-height:1.8 !important;color:#800080"><strong>3). 无论哪个顺序位, 在红包分配上的概率是平等公平的</strong></span><br /> 对了条件(3)的解读, 可以这么理解, 每个顺序位的预期红包分配数为<span style="line-height:1.8 !important;color:#FF0000"><strong>N/k</strong></span> (N为红包总素,k为用户数). 一次分配差异大, 但统计重复M次, M越大, 预期平均值越接近N/k. 这就是<strong><span style="line-height:1.8 !important;color:#FF0000">宏观上的平等</span></strong>. </p> <p style="color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> 有人就以平均值做突破口, 引入<strong><span style="line-height:1.8 !important;color:#FF0000">截尾正态分布</span></strong>, 达到了非常好的效果.<br /> <img src="//cto.wang/usr/uploads/2016/07/20160703144948-67.png" alt="" /><br /> 详细见<<微信红包算法探讨>>这篇博文, 这边具体也不展开了. </p> <p style="color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> <strong>工程</strong>的角度, 我们可以简化算法, 用拟合的算法来近似代替.<br /> <strong>概率函数</strong>为: </p> <div class="cnblogs_Highlighter sh-gutter" style="margin:10px auto;color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> <div style="margin:10px auto"> <div id="highlighter_190172" class="syntaxhighlighter cpp" style="margin:10px auto;font-size:1em !important;background-color:#FFFFFF !important"> <table border="0" cellpadding="0" cellspacing="0" style="border:1px solid silver;width:655px;height:auto !important;margin:0px !important;padding:0px !important;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important;font-size:12px !important;background:none !important" class="ke-zeroborder"> <tbody> <tr> <td class="gutter" style="border:1px solid silver;vertical-align:baseline !important;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important;color:#AFAFAF !important;background:none !important"> <div class="line number1 index0 alt2" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> 1 </div> <div class="line number2 index1 alt1" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important"> 2 </div> <div class="line number3 index2 alt2" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> 3 </div> </td> <td class="code" style="border:1px solid silver;vertical-align:baseline !important;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important;background:none !important"> <div class="container" style="margin:10px auto;border:0px !important;padding:0px !important;vertical-align:baseline !important;background:none !important"> <div class="line number1 index0 alt2" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> 对于第i个玩家而言 </div> <div class="line number2 index1 alt1" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important"> 随机生成(k-i)个 Bj (j=0,1,k-i-1), Bj范围在[0, 100]之间. </div> <div class="line number3 index2 alt2" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> 则概率函数P(i) = Bi / (B0 + B1 + … + Bk-i-1) </div> </p></div> </td> </tr> </tbody> </table></div> </p></div> </div> <p style="color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> 对于Ai, 则<strong><span style="line-height:1.8 !important;color:#000000">迭代公式</span></strong>为: </p> <div class="cnblogs_Highlighter sh-gutter" style="margin:10px auto;color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> <div style="margin:10px auto"> <div id="highlighter_3802" class="syntaxhighlighter cpp" style="margin:10px auto;font-size:1em !important;background-color:#FFFFFF !important"> <table border="0" cellpadding="0" cellspacing="0" style="border:1px solid silver;width:655px;height:auto !important;margin:0px !important;padding:0px !important;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important;font-size:12px !important;background:none !important" class="ke-zeroborder"> <tbody> <tr> <td class="gutter" style="border:1px solid silver;vertical-align:baseline !important;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important;color:#AFAFAF !important;background:none !important"> <div class="line number1 index0 alt2" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> 1 </div> <div class="line number2 index1 alt1" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important"> 2 </div> </td> <td class="code" style="border:1px solid silver;vertical-align:baseline !important;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important;background:none !important"> <div class="container" style="margin:10px auto;border:0px !important;padding:0px !important;vertical-align:baseline !important;background:none !important"> <div class="line number1 index0 alt2" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> Ti = T – 0.01 * (k – i) – A0 – … – Ai-1 </div> <div class="line number2 index1 alt1" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important"> 则Ai = Ti * P(i) + 0.01 = Ti * Bi / (B0 + B1 + … + Bk-i-1) + 0.01 </div> </p></div> </td> </tr> </tbody> </table></div> </p></div> </div> <p style="color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> 因为使用<strong>加减乘除</strong>, 比用高级概率分布的<strong>sin/cos/log函数<span style="line-height:1.8 !important;color:#FF0000">计算效率</span></strong>要高. </p> <p style="color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> <em><strong>竞抢技术:</strong></em><br /> 群红包的”抢夺”, 最重要的还是数据安全问题.说白了就是竞态条件下, 如何保证<strong>数据完整性和一致性</strong><br /> 业内对该类问题, 有大致三种主流的做法:<br /> <strong>1). 悲观锁思路</strong><br /> <span style="line-height:1.8 !important;color:#0000FF"><strong>2). FIFO队列思路</strong></span><br /> <span style="line-height:1.8 !important;color:#339966"><strong>3). 乐观锁思路</strong></span><br /> <strong>悲观锁思路</strong>, 常见的是借用mysql的<strong>SELECT … FOR UPDATE</strong>语句来实现. </p> <div class="cnblogs_Highlighter sh-gutter" style="margin:10px auto;color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> <div style="margin:10px auto"> <div id="highlighter_556199" class="syntaxhighlighter sql" style="margin:10px auto;font-size:1em !important;background-color:#FFFFFF !important"> <table border="0" cellpadding="0" cellspacing="0" style="border:1px solid silver;width:655px;height:auto !important;margin:0px !important;padding:0px !important;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important;font-size:12px !important;background:none !important" class="ke-zeroborder"> <tbody> <tr> <td class="gutter" style="border:1px solid silver;vertical-align:baseline !important;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important;color:#AFAFAF !important;background:none !important"> <div class="line number1 index0 alt2" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> 1 </div> <div class="line number2 index1 alt1" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important"> 2 </div> <div class="line number3 index2 alt2" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> 3 </div> <div class="line number4 index3 alt1" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important"> 4 </div> </td> <td class="code" style="border:1px solid silver;vertical-align:baseline !important;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important;background:none !important"> <div class="container" style="margin:10px auto;border:0px !important;padding:0px !important;vertical-align:baseline !important;background:none !important"> <div class="line number1 index0 alt2" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> begin transaction; // (1)开启事务 </div> <div class="line number2 index1 alt1" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important"> select … for update; // (2)锁定某行记录 </div> <div class="line number3 index2 alt2" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> update … set … where …; // (3)进行记录更新 </div> <div class="line number4 index3 alt1" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important"> commit transaction; // (4)事务提交 </div> </p></div> </td> </tr> </tbody> </table></div> </p></div> </div> <p style="color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> 这边重点讲讲<strong>乐观锁机制</strong>, 其不光能用于关系数据库,也能用于NoSQL.<br /> 乐观锁的核心思想是, <strong>基于版本号的更新</strong>, 前提是<strong>操作需保证原子性</strong>.<br /> 设计简化的红包表:<br /> <img src="//cto.wang/usr/uploads/2016/07/20160703144948-48.png" alt="" /><br /> 注释: total_money为总金额, total_number为红包数, left_money为剩余金额数, left_number为剩余红包数<br /> 当用户拆红包时, 触发如下流程<br /> <span style="line-height:1.8 !important;color:#008000">(1) 查询群红包信息</span> </p> <div class="cnblogs_Highlighter sh-gutter" style="margin:10px auto;color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> <div style="margin:10px auto"> <div id="highlighter_253152" class="syntaxhighlighter sql" style="margin:10px auto;font-size:1em !important;background-color:#FFFFFF !important"> <table border="0" cellpadding="0" cellspacing="0" style="border:1px solid silver;width:655px;height:auto !important;margin:0px !important;padding:0px !important;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important;font-size:12px !important;background:none !important" class="ke-zeroborder"> <tbody> <tr> <td class="gutter" style="border:1px solid silver;vertical-align:baseline !important;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important;color:#AFAFAF !important;background:none !important"> <div class="line number1 index0 alt2" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> 1 </div> <div class="line number2 index1 alt1" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important"> 2 </div> <div class="line number3 index2 alt2" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> 3 </div> </td> <td class="code" style="border:1px solid silver;vertical-align:baseline !important;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important;background:none !important"> <div class="container" style="margin:10px auto;border:0px !important;padding:0px !important;vertical-align:baseline !important;background:none !important"> <div class="line number1 index0 alt2" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> SELECT left_money, left_number, version_id </div> <div class="line number2 index1 alt1" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important"> FROM tb_hongbao </div> <div class="line number3 index2 alt2" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> WHERE envelope_id = ‘?’; </div> </p></div> </td> </tr> </tbody> </table></div> </p></div> </div> <p style="color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> <span style="line-height:1.8 !important;color:#008080">(2) 计算所分配的红包</span><br /> 通过上述的方法, 通过left_money, left_number计算出具体的红包: delta_money<br /> <span style="line-height:1.8 !important;color:#0000FF">(3) 更新群红包信息</span> </p> <div class="cnblogs_Highlighter sh-gutter" style="margin:10px auto;color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> <div style="margin:10px auto"> <div id="highlighter_326920" class="syntaxhighlighter sql" style="margin:10px auto;font-size:1em !important;background-color:#FFFFFF !important"> <table border="0" cellpadding="0" cellspacing="0" style="border:1px solid silver;width:655px;height:auto !important;margin:0px !important;padding:0px !important;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important;font-size:12px !important;background:none !important" class="ke-zeroborder"> <tbody> <tr> <td class="gutter" style="border:1px solid silver;vertical-align:baseline !important;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important;color:#AFAFAF !important;background:none !important"> <div class="line number1 index0 alt2" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> 1 </div> <div class="line number2 index1 alt1" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important"> 2 </div> <div class="line number3 index2 alt2" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> 3 </div> <div class="line number4 index3 alt1" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important"> 4 </div> <div class="line number5 index4 alt2" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> 5 </div> <div class="line number6 index5 alt1" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important"> 6 </div> <div class="line number7 index6 alt2" style="margin:10px auto;padding:0px 0.5em !important;text-align:right !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> 7 </div> </td> <td class="code" style="border:1px solid silver;vertical-align:baseline !important;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important;background:none !important"> <div class="container" style="margin:10px auto;border:0px !important;padding:0px !important;vertical-align:baseline !important;background:none !important"> <div class="line number1 index0 alt2" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> UPDATE tb_hongbao </div> <div class="line number2 index1 alt1" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important"> SET </div> <div class="line number3 index2 alt2" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> left_money = left_money – delta_money, </div> <div class="line number4 index3 alt1" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important"> left_number = left_number – 1, </div> <div class="line number5 index4 alt2" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> version_id = version_id + 1 </div> <div class="line number6 index5 alt1" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important"> WHERE </div> <div class="line number7 index6 alt2" style="margin:10px auto;border:0px !important;padding:0px 1em !important;vertical-align:baseline !important;background:none #F4F4F4 !important"> envelope_id = ‘?’ AND version_id = ‘old_version_id’ </div> </p></div> </td> </tr> </tbody> </table></div> </p></div> </div> <p style="color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> SQL是能保证原子性的, 带着上次查询回来的version_id去更新, 若version_id一致, 则更新成功, 版本号递增, 若不一致, 则需要重复1~3步, 直至成功或放弃.<br /> 这边讲述的利用mysql来实现的, 事实上有些Nosql系统也支持(大淘宝的Tair服务). </p> <p style="color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> <em><strong>写在最后:</strong></em><br /> 如果你觉得这篇文章对你有帮助, 请小小打赏下. 其实我想试试, 看看写博客能否给自己带来一点小小的收益. 无论多少, 都是对楼主一种由衷的肯定. </p> <p style="color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> </p> <p style="color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> </p> <p style="color:#333333;font-family:Verdana, Arial, sans-serif, 'Lucida Grande';font-size:13.3333330154419px;background-color:#D6D3D6"> 转自: http://www.cnblogs.com/mumuxinfei/p/4305979.html</p> 最后修改:2021 年 12 月 10 日 10 : 53 AM © 允许规范转载 赞赏 如果觉得我的文章对你有用,请随意赞赏 赞赏作者 支付宝微信