服务的可用性、可靠性、数据的一致性三个要素
抢红包的需求分析
其实8月的时候就准备搞这个抢红包业务,代替消费后每天固定红包的业务。但后来公司发展需要,希望固定返利维持现状,红包功能戛然而止。写到简书做个记录。
现在互联网金融逐渐发展起来了,随之而来的是各大互联网金融产品的推出。现问题如下:假设公司需要新推出一款理财产品,产品的募集资金为10000000(1千万)元,每位顾客都可以进行购买交易,购买金额为1000元或者1000元的整数倍,只要剩余募集金额>=购买金额则客户购买成功,进行扣款或者冻结资金,相应的募集资金进行更新。此处还需要考虑到,客户如果扣款失败的话,需要再次返还占有的额度。 由于目前市场情况,每推出一款这样的产品,将会有大量用户进行抢购。那么该如何进行处理这种相对高并发的问题,以保证安全性和高效性呢?类似的产品如:腾讯的理财通
抢红包的场景有点像秒杀,但是要比秒杀简单点。
设计思路:
准备3个队列
第一:生成红包队列hongBaoList,比如100元,分成10个,每个红包在10元上下波动,波动范围在[min, max],并呈现一个正态分布。这个point不是我在这里分享的关键,大家可以click进这条link:http://www.jb51.net/article/98620.htm,看下生成算法见的一篇文章。
第二:已消费的红包队列hongBaoConsumedList,就是我每消费一个红包,hongBaoList减少一个,hongBaoConsumedList多增加一个,知道hongBaoList消费完。
第三:去重的队列hongBaoConsumedMap,记录已经抢了红包的用户ID,就是防止用户抢多个红包。当然放在hongBaoConsumedList也行,但比较麻烦,索性新起一个map,记录已经抢了红包的用户ID,到时用redis的hexists直接判断用户ID有没有在去重的Map里面。
此类问题比较类似电商网站的秒杀/抢购、微信抢红包。
因为秒杀通常要和库存相关。而抢红包则可以允许有些红包没有被抢到,因为发红包的人不会有损失,没抢完的钱再退回给发红包的人即可。
为什么用redis+lua:
第一:redis缓存的读写快,lua的轻量级开发。
第二:redis具有原子性,也就是单线程,所以操作红包是安全的,但对于一个列表是安全的,对于多个列表,像hongBaoList,hongBaoConsumedList,hongBaoConsumedMap这三个列表进行逻辑操作,就需要lua脚本,lua也有原子性,而且能保证hongBaoList,hongBaoConsumedList,hongBaoConsumedMap这三个列表在同意线程下统一操作。
所以选择redis+lua来解决抢红包高并发的问题。
实现步骤:
1:按照http://www.jb51.net/article/98620.htm ,写一个生成红包的类HongBaoCreateUtil,:
import java.util.Random;
public class HongBaoCreateUtil {
static Random random = new Random();
static {
random.setSeed(System.currentTimeMillis());
}
public static void main(String[] args) {
long max = 3;
long min = 1;
long[] result = HongBaoCreateUtil.generate(10, 5, max, min);
long total = 0;
for (int i = 0; i < result.length; i++) {
System.out.println("result[" + i + "]:" + result[i]);
System.out.println(result[i]);
total += result[i];
}
//检查生成的红包的总额是否正确
System.out.println("total:" + total);
//统计每个钱数的红包数量,检查是否接近正态分布
int count[] = new int[(int) max + 1];
for (int i = 0; i < result.length; i++) {
count[(int) result[i]] += 1;
}
for (int i = 0; i < count.length; i++) {
System.out.println("" + i + " " + count[i]);
}
}
/**
* 生产min和max之间的随机数,但是概率不是平均的,从min到max方向概率逐渐加大。
* 先平方,然后产生一个平方值范围内的随机数,再开方,这样就产生了一种“膨胀”再“收缩”的效果。
*
* @param min
* @param max
* @return
*/
static long xRandom(long min, long max) {
return sqrt(nextLong(sqr(max - min)));
}
/**
*
* @param total
* 红包总额
* @param count
* 红包个数
* @param max
* 每个小红包的最大额
* @param min
* 每个小红包的最小额
* @return 存放生成的每个小红包的值的数组
*/
public static long[] generate(long total, int count, long max, long min) {
long[] result = new long[count];
long average = total / count;
long a = average - min;
long b = max - min;
//
//这样的随机数的概率实际改变了,产生大数的可能性要比产生小数的概率要小。
//这样就实现了大部分红包的值在平均数附近。大红包和小红包比较少。
long range1 = sqr(average - min);
long range2 = sqr(max - average);
for (int i = 0; i < result.length; i++) {
//因为小红包的数量通常是要比大红包的数量要多的,因为这里的概率要调换过来。
//当随机数>平均值,则产生小红包
//当随机数<平均值,则产生大红包
if (nextLong(min, max) > average) {
// 在平均线上减钱
//long temp = min + sqrt(nextLong(range1));
long temp = min + xRandom(min, average);
result[i] = temp;
total -= temp;
} else {
// 在平均线上加钱
//long temp = max - sqrt(nextLong(range2));
long temp = max - xRandom(average, max);
result[i] = temp;
total -= temp;
}
}
// 如果还有余钱,则尝试加到小红包里,如果加不进去,则尝试下一个。
while (total > 0) {
for (int i = 0; i < result.length; i++) {
if (total > 0 && result[i] < max) {
result[i]++;
total--;
}
}
}
// 如果钱是负数了,还得从已生成的小红包中抽取回来
while (total < 0) {
for (int i = 0; i < result.length; i++) {
if (total < 0 && result[i] > min) {
result[i]--;
total++;
}
}
}
return result;
}
static long sqrt(long n) {
// 改进为查表?
return (long) Math.sqrt(n);
}
static long sqr(long n) {
// 查表快,还是直接算快?
return n * n;
}
static long nextLong(long n) {
return random.nextInt((int) n);
}
static long nextLong(long min, long max) {
return random.nextInt((int) (max - min + 1)) + min;
}
}
2.将生成的红包放进redis的hongBaoList
static public void generateTestData() throws InterruptedException {
Jedis jedis = new Jedis(host, port);
jedis.flushAll();
int total = 10;//10块红包
int count = 5;//分成5份
long max = 3; //最大值3块
long min = 1; //最小值1块
long[] result = HongBaoCreateUtil.generate(total, count, max, min);
JSONObject object = new JSONObject();
for (long l : result) {
object.put("id", l);
object.put("money", l);
jedis.lpush(hongBaoList, object.toJSONString());
}
jedis.close();
}
main函数run一下,在RedisDesktopManager下观察:
hongBaoList.png
成功将五个红包塞进redis
3.写线程模拟抢红包:
static String tryGetHongBaoScript =
"if redis.call('hexists', KEYS[3], KEYS[4]) ~= 0 thenn"
+ "return niln"
+ "elsen"
+ "local hongBao = redis.call('rpop', KEYS[1]);n"
+ "if hongBao thenn"
+ "local x = cjson.decode(hongBao);n"
+ "x['userId'] = KEYS[4];n"
+ "local re = cjson.encode(x);n"
+ "redis.call('hset', KEYS[3], KEYS[4], KEYS[4]);n"
+ "redis.call('lpush', KEYS[2], re);n"
+ "return re;n"
+ "endn"
+ "endn"
+ "return nil";
static public void testTryGetHongBao() throws InterruptedException {
final CountDownLatch latch = new CountDownLatch(threadCount);
long startTime = System.currentTimeMillis();
System.err.println("start:" + startTime);
for(int i = 0; i < threadCount; ++i) {
final int temp = i;
Thread thread = new Thread() {
public void run() {
Jedis jedis = new Jedis(host, port);
String sha = jedis.scriptLoad(tryGetHongBaoScript);
int j = honBaoCount/threadCount * temp;
while(true) {
//抢红包方法
Object object = jedis.eval(tryGetHongBaoScript, 4,
hongBaoList/*预生成的红包队列*/,
hongBaoConsumedList, /*已经消费的红包队列*/
hongBaoConsumedMap, /*去重的map*/
"" + j /*用户id*/
);
j++;
if (object != null) {
//do something...
// System.out.println("get hongBao:" + object);
}else {
//已经取完了
if(jedis.llen(hongBaoList) == 0)
break;
}
}
latch.countDown();
}
};
thread.start();
}
latch.await();
long costTime = System.currentTimeMillis() - startTime;
System.err.println("costTime:" + costTime);
}
其中tryGetHongBaoScript 是lua脚本:
/**
* --
函数:尝试获得红包,如果成功,则返回json字符串,如果不成功,则返回空
* -- 参数:红包队列名, 已消费的队列名,去重的Map名,用户ID
* -- 返回值:nil 或者
json字符串,包含用户ID:userId,红包ID:id,红包金额:money
*
* -- 如果用户已抢过红包,则返回nil
* if redis.call('hexists', KEYS[3], KEYS[4]) ~= 0 then
* return nil
* else
* -- 先取出一个小红包
* local hongBao = redis.call('rpop', KEYS[1]);
* if hongBao then
* local x = cjson.decode(hongBao);
* -- 加入用户ID信息
* x['userId'] = KEYS[4];
* local re = cjson.encode(x);
* -- 把用户ID放到去重的set里
* redis.call('hset', KEYS[3], KEYS[4], KEYS[4]);
* -- 把红包放到已消费队列里
* redis.call('lpush', KEYS[2], re);
* return re;
* end
* end
* return nil
*/
打个断点,main函数debug一下:
程序运行到一半时:
多了已消费了的红包:hongBaoConsumedList;去重表:hongBaoConsumedMap
3list
之前红包列表少了两个包:
l1.png
已消费的红包列表hongBaoConsumedList多了两条数据:
l3.png
去重表hongBaoConsumedMap多了两条用户的id:
l2.png
程序运行完成后时,只剩下hongBaoConsumedList和hongBaoConsumedMap,hongBaoConsumedList如图:
接下来的工作就是宣布谁是手气最佳,和把hongBaoConsumedList的数据塞到DataBase里面。
参考:
红包生成算法:http://www.jb51.net/article/98620.htm
白贺翔老师之前的Redis+Lua视频
此类业务一般都涉及分布式系统。而对于分布式系统而言,由于所谓的CAPS理论:服务的可用性、可靠性、数据的一致性三个要素并不能同时满足,因此一般都遵循所谓的BASE理论。
另外像小米这样的抢购也要比淘宝的要简单,也是因为像小米这样是一个公司的,如果有少量没有抢到,则下次再抢,人工修复下数据是很简单的事。而像淘宝这么多商品,要是每一个都存在着修复数据的风险,那如果出故障了则很麻烦。
CAP理论:
基于redis的抢红包方案
Consistency:一致性, 数据一致更新,所有数据变动都是同步的
下面介绍一种基于Redis的抢红包方案。
Availability:可用性
把原始的红包称为大红包,拆分后的红包称为小红包。
Partition tolerance:分区容错性,系统可靠性
1.小红包预先生成,插到数据库里,红包对应的用户ID是null。生成算法见另一篇文章://
BASE理论:
2.每个大红包对应两个redis队列,一个是未消费红包队列,另一个是已消费红包队列。开始时,把未抢的小红包全放到未消费红包队列里。
Basically Available:基本可用
未消费红包队列里是json字符串,如{userId:'789', money:'300'}。
Soft-state:软状态/柔性事务
3.在redis中用一个map来过滤已抢到红包的用户。
Eventual Consistency:最终一致性
4.抢红包时,先判断用户是否抢过红包,如果没有,则从未消费红包队列中取出一个小红包,再push到另一个已消费队列中,最后把用户ID放入去重的map中。
因此依赖于不同的场景,大家的处理方式不尽相同。
5.用一个单线程批量把已消费队列里的红包取出来,再批量update红包的用户ID到数据库里。
例如像微信红包,发放的红包是可以没被抢到的。而秒杀、抢购一般会被抢光。
上面的流程是很清楚的,但是在第4步时,如果是用户快速点了两次,或者开了两个浏览器来抢红包,会不会有可能用户抢到了两个红包?
又比如像小米抢购手机,由于其限量的手机台数是小米自己定义的,抢购的手机台数可以有一定程度的误差的(多或少一点)。而对于淘宝秒杀、抢购一般要求保证不多也不少。
为了解决这个问题,采用了lua脚本方式,让第4步整个过程是原子性地执行。
在具体使用场景上,互联网金融的投标过程更类似于电商的秒杀和抢购。
下面是在redis上执行的Lua脚本:
此类应用重点要解决如下一些问题:
-- 函数:尝试获得红包,如果成功,则返回json字符串,如果不成功,则返回空 -- 参数:红包队列名, 已消费的队列名,去重的Map名,用户ID -- 返回值:nil 或者 json字符串,包含用户ID:userId,红包ID:id,红包金额:money -- 如果用户已抢过红包,则返回nil if rediscall('hexists', KEYS[3], KEYS[4]) ~= 0 then return nil else -- 先取出一个小红包 local hongBao = rediscall('rpop', KEYS[1]); if hongBao then local x = cjsondecode(hongBao); -- 加入用户ID信息 x['userId'] = KEYS[4]; local re = cjsonencode(x); -- 把用户ID放到去重的set里 rediscall('hset', KEYS[3], KEYS[4], KEYS[4]); -- 把红包放到已消费队列里 rediscall('lpush', KEYS[2], re); return re; end end return nil
1、超卖
下面是测试代码:
例如融资金额为1000万,在最后的抢购中,可投金额只剩下1万元,可能会有多个投资者同一瞬间都投标成功,导致用户投资的金额超过了融资额。
public class TestEval { static String host = "localhost"; static int honBaoCount = 1_0_0000; static int threadCount = 20; static String hongBaoList = "hongBaoList"; static String hongBaoConsumedList = "hongBaoConsumedList"; static String hongBaoConsumedMap = "hongBaoConsumedMap"; static Random random = new Random(); // -- 函数:尝试获得红包,如果成功,则返回json字符串,如果不成功,则返回空 // -- 参数:红包队列名, 已消费的队列名,去重的Map名,用户ID // -- 返回值:nil 或者 json字符串,包含用户ID:userId,红包ID:id,红包金额:money static String tryGetHongBaoScript = // "local bConsumed = rediscall('hexists', KEYS[3], KEYS[4]);n" // + "print('bConsumed:' ,bConsumed);n" "if rediscall('hexists', KEYS[3], KEYS[4]) ~= 0 thenn" + "return niln" + "elsen" + "local hongBao = rediscall('rpop', KEYS[1]);n" // + "print('hongBao:', hongBao);n" + "if hongBao thenn" + "local x = cjsondecode(hongBao);n" + "x['userId'] = KEYS[4];n" + "local re = cjsonencode(x);n" + "rediscall('hset', KEYS[3], KEYS[4], KEYS[4]);n" + "rediscall('lpush', KEYS[2], re);n" + "return re;n" + "endn" + "endn" + "return nil"; static StopWatch watch = new StopWatch(); public static void main(String[] args) throws InterruptedException { // testEval(); generateTestData(); testTryGetHongBao(); } static public void generateTestData() throws InterruptedException { Jedis jedis = new Jedis(host); jedisflushAll(); final CountDownLatch latch = new CountDownLatch(threadCount); for(int i = 0; i threadCount; ++i) { final int temp = i; Thread thread = new Thread() { public void run() { Jedis jedis = new Jedis(host); int per = honBaoCount/threadCount; JSONObject object = new JSONObject(); for(int j = temp * per; j (temp+1) * per; j++) { objectput("id", j); objectput("money", j); jedislpush(hongBaoList, objecttoJSONString()); } latchcountDown(); } }; threadstart(); } latchawait(); } static public void testTryGetHongBao() throws InterruptedException { final CountDownLatch latch = new CountDownLatch(threadCount); Systemerrprintln("start:" + SystemcurrentTimeMillis()/1000); watchstart(); for(int i = 0; i threadCount; ++i) { final int temp = i; Thread thread = new Thread() { public void run() { Jedis jedis = new Jedis(host); String sha = jedisscriptLoad(tryGetHongBaoScript); int j = honBaoCount/threadCount * temp; while(true) { Object object = jediseval(tryGetHongBaoScript, 4, hongBaoList, hongBaoConsumedList, hongBaoConsumedMap, "" + j); j++; if (object != null) { // Systemoutprintln("get hongBao:" + object); }else { //已经取完了 if(jedisllen(hongBaoList) == 0) break; } } latchcountDown(); } }; threadstart(); } latchawait(); watchstop(); Systemerrprintln("time:" + watchgetTotalTimeSeconds()); Systemerrprintln("speed:" + honBaoCount/watchgetTotalTimeSeconds()); Systemerrprintln("end:" + SystemcurrentTimeMillis()/1000); } }
解决超卖问题的方案是保证用户投标过程,对投资金额的增减采用事务,且要保证事务操作的原子性。
测试结果20个线程,每秒可以抢2.5万个,足以应付绝大部分的抢红包场景。
2、少卖
如果是真的应付不了,拆分到几个redis集群里,或者改为批量抢红包,也足够应付。
典型场景题主提到了:用户投标抢到了,但因支付失败等原因没正常完成抢购到订单支付。
总结:
解决少买问题的方案是对抢购订单设定时效性,定时对超过时效未支付的订单释放掉。
redis的抢红包方案,虽然在极端情况下会丢失一秒的数据,但是却是一个扩展性很强,足以应付高并发的抢红包方案。
3、刷单作弊