高并发抽奖

高并发库存防控超量

在秒杀，抽奖等活动中，避免商品超卖甚至库存变负数的问题。

锁

锁是用来做并发最简单的方式，其代价也是最高的

数据库锁

通过update返回值来判断库存:

update set number=number-1 where number > 0

update set number=if(number>0, number-1, number)

文件锁

if (flock($fp, LOCK_EX)) {
    flock($fp, LOCK_UN);
}

消息队列

把奖品塞到队列里, 按照FIFO顺序执行

Beanstalk

Beanstalk is a simple, fast work queue.

Redis

redis的数据类list可以用来实现队列, 左边压入lpush, 右边弹出rpop。

MemcacheQ

Simple Queue Service over Memcache

抽奖算法

逢“几”中奖

微博转发得奖就常常使用这种算法，即根据转发次数来决定奖品归属，透明而且具有激励性。

基本算法

“几”=(抽奖人数/奖品数)*第几个奖品+特定数, 如果是实时抽奖, 则需要预估抽奖人数和奖品数。

美团抽奖

依赖开奖日收盘时的上证指数 & 收盘时的深证成指 这种不可控的物理随机数A，算法约等为：

“几”=不可空物理随机数%抽奖人数 + 特定数*第几个奖品

概率抽奖

概率抽奖可以理解为一个转盘，指针最终都会指向某个扇形区域, 触发概率为100%即1

TP线

指针最终都会指向扇形的弧上的某一点，因而可以把转盘展开成一条长为周长的线段，命名为TP线（Total probability-Line）。在TP线上随机任取一点。随机取出的这一点出自哪一条线段，则此线段对应的项目被抽中。

项目概率
A0.3
B0.2
C0.4

将项目A, B, C的概率进行求和以作为TP线的总长。用函数random(0,1)*TP线的长度来取TP线上的点。若取得的结果在[0，0.3）时，项目A被抽中；取得的结果在[0.3，0.5）时，项目B被抽中；取得的结果在[0.6，0.9）时，项目C被抽中；

离散算法

function random($prizes) {
  $index = null;
  $probabilitySum = array_sum($prizes);
  $rand = mt_rand(1, $probabilitySum);
  foreach ($prizes as $key => $probability) {
    if ($rand <= $probability) {
      $index = $key;
      break;
    } else {
      $rand -= $probability;
    }
  }
  return $index;
}

优先级算法

function random($prizes) {
  $index = null;
  $probabilitySum = array_sum($prize);
  foreach ($prizes as $key => $probability) {
    $rand = mt_rand(1, $probabilitySum);
    if ($rand <= $probability) {
      $index = $key;
      break;
    } else {
      $probabilitySum -= $probability;
    }
  }
  return $index;
}

参考

美团网的抽奖是什么原理? 如何高效设计游戏——从抽奖模型到圆桌算法（上） 如何高效设计游戏——从抽奖模型到圆桌算法（下） 游戏命中判定：圆桌算法和程序实现 用JavaScript玩转游戏编程(一)掉宝类型概率 Darts, Dice, and Coins: Sampling from a Discrete Distribution

双11抽奖活动平台测试总结 一种高效无锁内存队列的实现 Beanstalk is a simple, fast work queue Redis 命令参考 使用 Redis 实现分布式锁

Yan Peipan 08 December 2014