Java 實現紅包隨機金額算法
作者：CoderZS
鏈接：https://www.jianshu.com/p/0174a026b9c9
紅包的架構設計簡介
本文是基於平臺創建紅包活動時即提前分配好紅包金額的策略
需要輸入條件：總金額，紅包數量，最小金額，最大金額 金額浮動閥值 [0.0, 1.0]
我們可以通過調節閥值來達到正態分佈的效果
public class RedPacketUtils {
private static final Random random = new Random();
/**
* 根據總數分割個數及限定區間進行數據隨機處理
* 數列浮動閥值爲0.95
*
* @param totalMoney - 被分割的總數
* @param splitNum - 分割的個數
* @param min - 單個數字下限
* @param max - 單個數字上限
* @return - 返回符合要求的數字列表
*/
public static List<BigDecimal> genRanddomList(BigDecimal totalMoney, Integer splitNum, BigDecimal min, BigDecimal max) {
totalMoney = totalMoney.multiply(new BigDecimal(100));
min = min.multiply(new BigDecimal(100));
max = max.multiply(new BigDecimal(100));
List<Integer> li = genRandList(totalMoney.intValue(), splitNum, min.intValue(), max.intValue(), 0.95f);
List<BigDecimal> randomList = new CopyOnWriteArrayList<>();
for (Integer v : li) {
BigDecimal randomVlue = new BigDecimal(v).divide(new BigDecimal(100));
randomList.add(randomVlue);
}
randomList = randomArrayList(randomList);
return randomList;
}
/**
* 根據總數分割個數及限定區間進行數據隨機處理
*
* @param total - 被分割的總數
* @param splitNum - 分割的個數
* @param min - 單個數字下限
* @param max - 單個數字上限
* @param thresh - 數列浮動閥值[0.0, 1.0]
*/
public static List<Integer> genRandList(int total, int splitNum, int min, int max, float thresh) {
assert total >= splitNum * min && total <= splitNum * max : "請校驗紅包參數設置的合理性";
assert thresh >= 0.0f && thresh <= 1.0f;
// 平均分配
int average = total / splitNum;
List<Integer> list = new ArrayList<>(splitNum);
int rest = total - average * splitNum;
for (int i = 0; i < splitNum; i++) {
if (i < rest) {
list.add(average + 1);
} else {
list.add(average);
}
}
// 如果浮動閥值爲0則不進行數據隨機處理
if (thresh == 0) {
return list;
}
// 根據閥值進行數據隨機處理
int randOfRange = 0;
int randRom = 0;
int nextIndex = 0;
int nextValue = 0;
int surplus = 0;//多餘
int lack = 0;//缺少
for (int i = 0; i < splitNum - 1; i++) {
nextIndex = i + 1;
int itemThis = list.get(i);
int itemNext = list.get(nextIndex);
boolean isLt = itemThis < itemNext;
int rangeThis = isLt ? max - itemThis : itemThis - min;
int rangeNext = isLt ? itemNext - min : max - itemNext;
int rangeFinal = (int) Math.ceil(thresh * (Math.min(rangeThis, rangeNext) + 100));
randOfRange = random.nextInt(rangeFinal);
randRom = isLt ? 1 : -1;
int iValue = list.get(i) + randRom * randOfRange;
nextValue = list.get(nextIndex) + randRom * randOfRange * -1;
if (iValue > max) {
surplus += (iValue - max);
list.set(i, max);
} else if (iValue < min) {
list.set(i, min);
lack += (min - iValue);
} else {
list.set(i, iValue);
}
list.set(nextIndex, nextValue);
}
if (nextValue > max) {
surplus += (nextValue - max);
list.set(nextIndex, max);
}
if (nextValue < min) {
lack += (min - nextValue);
list.set(nextIndex, min);
}
if (surplus - lack > 0) {//錢發少了 給低於max的湊到max
for (int i = 0; i < list.size(); i++) {
int value = list.get(i);
if (value < max) {
int tmp = max - value;
if (surplus >= tmp) {
surplus -= tmp;
list.set(i, max);
} else {
list.set(i, value + surplus);
return list;
}
}
}
} else if (lack - surplus > 0) {//錢發多了 給超過高於min的人湊到min
for (int i = 0; i < list.size(); i++) {
int value = list.get(i);
if (value > min) {
int tmp = value - min;
if (lack >= tmp) {
lack -= tmp;
list.set(i, min);
} else {
list.set(i, min + tmp - lack);
return list;
}
}
}
}
return list;
}
/**
* 打亂ArrayList
*/
public static List<BigDecimal> randomArrayList(List<BigDecimal> sourceList) {
if (sourceList == null || sourceList.isEmpty()) {
return sourceList;
}
List<BigDecimal> randomList = new CopyOnWriteArrayList<>();
do {
int randomIndex = Math.abs(new Random().nextInt(sourceList.size()));
randomList.add(sourceList.remove(randomIndex));
} while (sourceList.size() > 0);
return randomList;
}
public static void main(String[] args) {
//參考簡書CoderZS https://www.jianshu.com/p/0174a026b9c9
Long startTi = System.currentTimeMillis();
List<BigDecimal> li = genRanddomList(new BigDecimal(100000), 26000, new BigDecimal(2), new BigDecimal(30));
li = randomArrayList(li);
BigDecimal total = BigDecimal.ZERO;
// System.out.println("======li=========li:"+li);
System.out.println("======total=========total:" + total);
System.out.println("======size=========size:" + li.size());
Long endTi = System.currentTimeMillis();
System.out.println("======耗時=========:" + (endTi - startTi) / 1000 + "秒");
}
}// 共 10000 隨機分成 500 份，最小值爲 1，最大值爲 200。
genRandList(10000, 300, 1, 200, 0.95f)
// 共 10000 隨機分成 500 份，最小值爲 1，最大值爲 200。
genRandList(10000, 300, 1, 200, 0.5f)
微信紅包的架構設計簡介
1. 微信的金額什麼時候算？
答：微信金額是拆的時候實時算出來，不是預先分配的，採用的是純內存計算，不需要預算空間存儲。。
採取實時計算金額的考慮：預算需要佔存儲，實時效率很高，預算才效率低。
2. 實時性：爲什麼明明搶到紅包，點開後發現沒有？
答：2014 年的紅包一點開就知道金額，分兩次操作，先搶到金額，然後再轉賬。
2015 年的紅包的拆和搶是分離的，需要點兩次，因此會出現搶到紅包了，但點開後告知紅包已經被領完的狀況。進入到第一個頁面不代表搶到，只表示當時紅包還有。
分配：紅包裏的金額怎麼算？爲什麼出現各個紅包金額相差很大？
3. 答：隨機，額度在 0.01 和剩餘平均值 * 2 之間。
例如：發 100 塊錢，總共 10 個紅包，那麼平均值是 10 塊錢一個，那麼發出來的紅包的額度在 0.01 元～20 元之間波動。
當前面 3 個紅包總共被領了 40 塊錢時，剩下 60 塊錢，總共 7 個紅包，那麼這 7 個紅包的額度在：0.01～（60/7*2）=17.14 之間。
注意：這裏的算法是每被搶一個後，剩下的會再次執行上面的這樣的算法（Tim 老師也覺得上述算法太複雜，不知基於什麼樣的考慮）。
這樣算下去，會超過最開始的全部金額，因此到了最後面如果不夠這麼算，那麼會採取如下算法：保證剩餘用戶能拿到最低 1 分錢即可。
如果前面的人手氣不好，那麼後面的餘額越多，紅包額度也就越多，因此實際概率一樣的。
4. 紅包的設計
答：微信從財付通拉取金額數據郭萊，生成個數 / 紅包類型 / 金額放到 redis 集羣裏，app 端將紅包 ID 的請求放入請求隊列中，如果發現超過紅包的個數，直接返回。根據紅包的裸祭處理成功得到令牌請求，則由財付通進行一致性調用，通過像比特幣一樣，兩邊保存交易記錄，交易後交給第三方服務審計，如果交易過程中出現不一致就強制迴歸。
5. 發性處理：紅包如何計算被搶完？
答：cache 會抵抗無效請求，將無效的請求過濾掉，實際進入到後臺的量不大。cache 記錄紅包個數，原子操作進行個數遞減，到 0 表示被搶光。財付通按照 20 萬筆每秒入賬準備，但實際還不到 8 萬每秒。
6. 通如何保持 8w 每秒的寫入？
答：多主 sharding，水平擴展機器。
7. 據容量多少？
答：一個紅包只佔一條記錄，有效期只有幾天，因此不需要太多空間。
8. 詢紅包分配，壓力大不？
答：搶到紅包的人數和紅包都在一條 cache 記錄上，沒有太大的查詢壓力。
9. 一個紅包一個隊列？
答：沒有隊列，一個紅包一條數據，數據上有一個計數器字段。
10. 有沒有從數據上證明每個紅包的概率是不是均等？
答：不是絕對均等，就是一個簡單的拍腦袋算法。
11. 拍腦袋算法，會不會出現兩個最佳？
答：會出現金額一樣的，但是手氣最佳只有一個，先搶到的那個最佳。
12. 每領一個紅包就更新數據麼？
答：每搶到一個紅包，就 cas 更新剩餘金額和紅包個數。
13. 紅包如何入庫入賬？
數據庫會累加已經領取的個數與金額，插入一條領取記錄。入賬則是後臺異步操作。
14. 入帳出錯怎麼辦？比如紅包個數沒了，但餘額還有？
答：最後會有一個 take all 操作。另外還有一個對賬來保障。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/xLaIc1InzXVHGhsqWBFi6A