紅包的架構(gòu)設(shè)計(jì)簡(jiǎn)介

本文是基于平臺(tái)創(chuàng)建紅包活動(dòng)時(shí)即提前分配好紅包金額的策略
需要輸入條件：總金額弃酌，紅包數(shù)量，最小金額手蝎，最大金額 金額浮動(dòng)閥值[0.0, 1.0]
我們可以通過(guò)調(diào)節(jié)閥值來(lái)達(dá)到正態(tài)分布的效果

圖片.png

public class RedPacketUtils {

  private static final Random random = new Random();


  /**
   * 根據(jù)總數(shù)分割個(gè)數(shù)及限定區(qū)間進(jìn)行數(shù)據(jù)隨機(jī)處理
   * 數(shù)列浮動(dòng)閥值為0.95
   *
   * @param totalMoney    - 被分割的總數(shù)
   * @param splitNum - 分割的個(gè)數(shù)
   * @param min      - 單個(gè)數(shù)字下限
   * @param max      - 單個(gè)數(shù)字上限
   * @return - 返回符合要求的數(shù)字列表
   */
 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;
  }

  /**
   * 根據(jù)總數(shù)分割個(gè)數(shù)及限定區(qū)間進(jìn)行數(shù)據(jù)隨機(jī)處理
   *
   * @param total - 被分割的總數(shù)
   * @param splitNum - 分割的個(gè)數(shù)
   * @param min - 單個(gè)數(shù)字下限
   * @param max - 單個(gè)數(shù)字上限
   * @param thresh - 數(shù)列浮動(dòng)閥值[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 : "請(qǐng)校驗(yàn)紅包參數(shù)設(shè)置的合理性";
    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);
      }
    }
    // 如果浮動(dòng)閥值為0則不進(jìn)行數(shù)據(jù)隨機(jī)處理
    if (thresh == 0) {
      return list;
    }
    // 根據(jù)閥值進(jìn)行數(shù)據(jù)隨機(jī)處理
    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) {//錢(qián)發(fā)少了 給低于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) {//錢(qián)發(fā)多了 給超過(guò)高于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) {
    //參考簡(jiǎn)書(shū)CoderZS http://www.reibang.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("======耗時(shí)=========:" + (endTi - startTi) / 1000 + "秒");
  }
}

// 共10000隨機(jī)分成500份局蚀，最小值為1彻桃，最大值為200。
genRandList(10000, 300, 1, 200, 0.95f)

圖片.png

圖片.png

// 共10000隨機(jī)分成500份澎媒，最小值為1搞乏，最大值為200。
genRandList(10000, 300, 1, 200, 0.5f)

圖片.png

圖片.png

微信紅包的架構(gòu)設(shè)計(jì)簡(jiǎn)介

1.微信的金額什么時(shí)候算戒努？

答：微信金額是拆的時(shí)候?qū)崟r(shí)算出來(lái)请敦，不是預(yù)先分配的，采用的是純內(nèi)存計(jì)算储玫，不需要預(yù)算空間存儲(chǔ)侍筛。。
采取實(shí)時(shí)計(jì)算金額的考慮：預(yù)算需要占存儲(chǔ)撒穷，實(shí)時(shí)效率很高匣椰，預(yù)算才效率低。

2. 實(shí)時(shí)性：為什么明明搶到紅包端礼，點(diǎn)開(kāi)后發(fā)現(xiàn)沒(méi)有禽笑？

答：2014年的紅包一點(diǎn)開(kāi)就知道金額，分兩次操作齐媒，先搶到金額，然后再轉(zhuǎn)賬纷跛。
2015年的紅包的拆和搶是分離的喻括，需要點(diǎn)兩次，因此會(huì)出現(xiàn)搶到紅包了贫奠，但點(diǎn)開(kāi)后告知紅包已經(jīng)被領(lǐng)完的狀況唬血。進(jìn)入到第一個(gè)頁(yè)面不代表?yè)尩剑槐硎井?dāng)時(shí)紅包還有唤崭。

分配：紅包里的金額怎么算拷恨？為什么出現(xiàn)各個(gè)紅包金額相差很大？

3. 答：隨機(jī)谢肾，額度在0.01和剩余平均值*2之間腕侄。

例如：發(fā)100塊錢(qián)，總共10個(gè)紅包芦疏，那么平均值是10塊錢(qián)一個(gè)冕杠，那么發(fā)出來(lái)的紅包的額度在0.01元～20元之間波動(dòng)。
當(dāng)前面3個(gè)紅包總共被領(lǐng)了40塊錢(qián)時(shí)酸茴，剩下60塊錢(qián)分预，總共7個(gè)紅包，那么這7個(gè)紅包的額度在：0.01～（60/7*2）=17.14之間薪捍。
注意：這里的算法是每被搶一個(gè)后笼痹，剩下的會(huì)再次執(zhí)行上面的這樣的算法（Tim老師也覺(jué)得上述算法太復(fù)雜配喳，不知基于什么樣的考慮）。

這樣算下去凳干，會(huì)超過(guò)最開(kāi)始的全部金額晴裹，因此到了最后面如果不夠這么算，那么會(huì)采取如下算法：保證剩余用戶能拿到最低1分錢(qián)即可纺座。

如果前面的人手氣不好息拜，那么后面的余額越多，紅包額度也就越多净响，因此實(shí)際概率一樣的少欺。

4. 紅包的設(shè)計(jì)

答：微信從財(cái)付通拉取金額數(shù)據(jù)郭萊，生成個(gè)數(shù)/紅包類型/金額放到redis集群里馋贤，app端將紅包ID的請(qǐng)求放入請(qǐng)求隊(duì)列中赞别，如果發(fā)現(xiàn)超過(guò)紅包的個(gè)數(shù)，直接返回配乓。根據(jù)紅包的裸祭處理成功得到令牌請(qǐng)求仿滔，則由財(cái)付通進(jìn)行一致性調(diào)用，通過(guò)像比特幣一樣犹芹，兩邊保存交易記錄崎页，交易后交給第三方服務(wù)審計(jì)，如果交易過(guò)程中出現(xiàn)不一致就強(qiáng)制回歸腰埂。

5. 發(fā)性處理：紅包如何計(jì)算被搶完飒焦？

答：cache會(huì)抵抗無(wú)效請(qǐng)求，將無(wú)效的請(qǐng)求過(guò)濾掉屿笼，實(shí)際進(jìn)入到后臺(tái)的量不大牺荠。cache記錄紅包個(gè)數(shù)，原子操作進(jìn)行個(gè)數(shù)遞減驴一，到0表示被搶光休雌。財(cái)付通按照20萬(wàn)筆每秒入賬準(zhǔn)備，但實(shí)際還不到8萬(wàn)每秒肝断。

6. 通如何保持8w每秒的寫(xiě)入杈曲？

答：多主sharding，水平擴(kuò)展機(jī)器胸懈。

7. 據(jù)容量多少鱼蝉？

答：一個(gè)紅包只占一條記錄，有效期只有幾天箫荡，因此不需要太多空間魁亦。

8.詢紅包分配，壓力大不羔挡？

答：搶到紅包的人數(shù)和紅包都在一條cache記錄上洁奈，沒(méi)有太大的查詢壓力间唉。

9.一個(gè)紅包一個(gè)隊(duì)列？

答：沒(méi)有隊(duì)列利术，一個(gè)紅包一條數(shù)據(jù)呈野，數(shù)據(jù)上有一個(gè)計(jì)數(shù)器字段。

10.有沒(méi)有從數(shù)據(jù)上證明每個(gè)紅包的概率是不是均等印叁？

答：不是絕對(duì)均等被冒，就是一個(gè)簡(jiǎn)單的拍腦袋算法。

11.拍腦袋算法轮蜕，會(huì)不會(huì)出現(xiàn)兩個(gè)最佳昨悼？

答：會(huì)出現(xiàn)金額一樣的，但是手氣最佳只有一個(gè)跃洛，先搶到的那個(gè)最佳率触。

12. 每領(lǐng)一個(gè)紅包就更新數(shù)據(jù)么？

答：每搶到一個(gè)紅包汇竭，就cas更新剩余金額和紅包個(gè)數(shù)葱蝗。

13.紅包如何入庫(kù)入賬？

數(shù)據(jù)庫(kù)會(huì)累加已經(jīng)領(lǐng)取的個(gè)數(shù)與金額细燎，插入一條領(lǐng)取記錄两曼。入賬則是后臺(tái)異步操作。

14.入帳出錯(cuò)怎么辦玻驻？比如紅包個(gè)數(shù)沒(méi)了悼凑，但余額還有？

答：最后會(huì)有一個(gè)take all操作击狮。另外還有一個(gè)對(duì)賬來(lái)保障佛析。