Two days ago, in the planning feedback of an activity, a prize with a winning rate of about 1/1000 in theory was obtained by the same player four times in a row. He had found several programs to review the code before, and said there was nothing wrong, but from the probability, there must be a problem, so he asked me to “clear the name of the programmer”. After a morning of hard work, I found a bug that had been lurking for 5 years and learned an unspoken rule about mysql.

The entire business scenario looks something like this (the code below is just an illustration, not a direct run) :

First, when each player signs up, insert a row into the database with the activity ID (Activity_id), player UUID (player_uUID), application number (apply_NO) and other player-related information.

At the same time, maintain an integer in memory to record the total number of active applicants apply_total_num. Also use this integer to get apply_no for the next inserted row. Second, the data table filled by the planner is generated into a data structure to represent the reward structure, that is, the number of rewards for each level, as shown below:

awards = {
	1: 1, 
	2: 15, 
	3: 50, 
	...
	}

Third, when the event is signed up, a random apply_NO sequence is generated based on the current apply_total_num and the total bonus sum(award.values ()). For example, if 10,000 people sign up and the total bonus points are 1000, it is possible to generate a sequence of 1000 apply_nos as follows:

lucky_apply_nos = [234, 123, 1356, 8765, 12, ...]
Copy the code

Select lucky_apply_nos from MySQL database where uUID = lucky_apply_nos

lucky_uuids = SELECT player_uuid FROM world_lottery WHERE apply_no IN lucky_apply_nos;
Copy the code

Lucky_uuids [0] for 1st prize, lucky_uuids[1]~lucky_uuids[15] for 2nd prize, and so on.

There seems to be no problem. The problem is actually in the SELECT statement. It is taken for granted that the order of lucky_uuids is the same as that of lucky_apply_nos. For SELECT statements without the ORDER BY clause, the return ORDER is dependent on the engine used:

For MyISAM, the return order is its physical storage order; For the InnoDB engine, the return order is sorted by primary key.

That is, IN either case, the list lucky_apply_nos IN the IN clause is not returned…

In our case, the engine uses InnoDB and the primary key is player_uuid, which means lucky_uuids are returned sorted according to palyer_uuid.

So what’s the problem with that?

If a player’s UUID is extremely small, then once that player makes the bonus list (lucky_apply_NOS), he or she is guaranteed the highest value 1st prize. This gives the player a 0.1^4 chance of winning four first prizes in a row, instead of 0.0001^4.

The bug is not obvious if the probability of winning in the bonus list is not much different from the probability of winning in each award. In this case, however, the plan increased the list of rewards (mainly by increasing the number of low-value rewards), making it easier for a player to hit several high-value rewards in a row.

The solution is as follows: After obtaining the return result lucky_uuids of the database, shuffle again.

conclusion

MySQL has an unwritten rule for return results of SELECT statements without the ORDER BY clause:

  • For MyISAM, the return order is its physical storage order;
  • For the InnoDB engine, the return order is sorted by primary key.

Reprint please indicate the source: blog.guoyb.com/2016/08/17/…

Please use wechat to scan the qr code below and follow my wechat official account TechTalking. Technology · Life · Thinking: