To achieve the lucky red envelope algorithm, there are several places to pay attention to:

  • The expected return of snatching red envelopes should be independent of the sequence
  • Ensure that each user can grab at least one preset minimum amount of money. The minimum amount of RMB red packets is 0.01 yuan. If you need to send red packets of other currencies, such as blockchain currency or points, you need to define a minimum amount.
  • The sum of the sub-red packets received by all the people snatching the red packets adds up to the sum of the total red packets sent by the people giving the red packets. The following implementation is to generate all the child red packets at once, so that the user in order to receive. You can also generate one for each one, and both methods have their own advantages and disadvantages in performance.

I have read an article before that wechat’s red envelope algorithm dynamically obtains the amount of red envelope each time, not once, which will cause storage space waste. Turn the text around

Brief introduction to the architecture design of wechat red envelope

@ From a QCon high availability architecture group collation, collation Zhu Yuhua.

Background: One of my friends asked me about the structure of wechat red envelopes in moments, so I got the following text.

Overview: In 2014, wechat hongbao used the database to resist the entire traffic, and in 2015, it used cache to resist the traffic.

When will the amount of wechat be calculated?

A: the amount of wechat is calculated in real time, not pre-allocated, the use of pure memory calculation, do not need to budget space storage. Take real-time calculation of the amount of consideration: budget needs to account for storage, real-time efficiency is very high, budget efficiency is low.

Real time: why did you find no red envelope when you had grabbed it?

Answer: The red envelope of 2014 will know the amount as soon as it is opened. It can be divided into two operations. First get the amount and then transfer the money. In 2015, the opening and snatching of the red envelope are separated and need to be clicked twice. Therefore, there will be a situation that the red envelope is grabbed, but when clicked, it will be informed that the red envelope has been claimed. Enter the first page does not represent grab, only that there are red envelopes.

Distribution: How to calculate the amount in the red envelope? Why does each red envelope amount differ greatly?

A: Random, between 0.01 and (residual mean 2). For example: send 100 yuan, a total of 10 red envelopes, then the average is 10 yuan each, then the amount of red envelopes sent fluctuates between 0.01 yuan and 20 yuan. If the first 3 red envelopes are 40 yuan in total, 60 yuan is left, there are 7 red envelopes in total, then the limit of 7 red envelopes is between 0.01 ~ (60/72) =17.14. Note: the algorithm here is that after each one is robbed, the others will perform the above algorithm again. (Tim also thinks the above algorithm is too complicated, I don’t know for what reason).

So if it’s not enough at the end, the algorithm follows: Make sure the rest of the users get at least 1 cent.

If the person in front of you is unlucky, then the larger the balance behind you, the larger the red envelope, so the actual probability is the same.

The design of red envelopes

A: Wechat pulls the amount data from Tenpay guo Lai, generates the number/red envelope type/amount and puts it into the Redis cluster. The APP end puts the request of red envelope ID into the request queue. If it finds that the number of red envelopes exceeds, it directly returns. If the token request is successfully obtained according to the naked offering (logic) processing of the red packet, tenpay will conduct consistency call. Like Bitcoin, transaction records are saved on both sides, and the transaction is submitted to the third-party service for audit. If there is any inconsistency in the transaction process, it will be forced to return.

Hair processing: how to calculate the red envelope is robbed?

A: The cache resizes invalid requests and filters them out. The cache records the number of red packets. The number decreases to 0. Tenpay was booked at 200,000 transactions per second, but it was less than 80,000.

How to maintain 8W writes per second?

A: Multi-master Sharding, horizontal extension machine.

What is the capacity?

A: One red packet only accounts for one record and is only valid for a few days, so it doesn’t need much space.

Inquiry red envelope distribution, pressure is not big?

A: The number of people who grabbed the red packets and the red packets are stored in the same cache record, so there is not too much query pressure.

A red envelope a queue?

A: There is no queue, one red packet has one data, and the data has a counter field.

Is there any statistical proof that the probability of each red envelope is equal? A: Not absolute parity, but a simple head-slapping algorithm.

Head slapping algorithm, will there be two best?

Answer: there will be the same amount, but the best luck only one, the first to grab the best.

Update your data every time you get a red envelope?

A: Cas updates the remaining amount and the number of red envelopes every time you grab one.

How to deposit red envelopes?

The database will add up the number and amount received and insert a claim record. Entry is a background asynchronous operation.

What if there is an entry error? For example, the number of red envelopes is out, but the balance is still?

A: There will be a take All operation at the end. There is also a reconciliation for security.

Text link: Wechat red envelope architecture design brief introduction

GitHub full demo: github.com/BothEyes199…

Refer to the link: www.zhihu.com/question/22… Reference links: blog.csdn.net/paincupid/a… Refer to the link: www.cnblogs.com/bestJavaCod…