这是我第一个与可扩展性相关的问题。
为了简化问题,我将使用宾果应用程序的想法:
我们有一个宾果应用程序。每个用户都有一个票证,其中包含 90 个中的 15 个随机数。每周都会举行宾果游戏以找到获胜者。数字是实时抽奖的,直到有赢家。前任:
- 抽取第15个号码->搜索表->不匹配
- 抽出第 16 个数字 ->搜索表 ->不匹配
- 。
- 第30个号码被抽出 ->搜索表 ->获胜者 ->停止
问题1:
哪种方式更好/更快来表示表中的数据并搜索该表?表将有 10+ 百万行
想法1:
桌票
id user_id week ticket created
====================================================================================================
1 100022312 1 1,3,5,7,9,14,15,77,78,79,80,81,82,83,84 <timestamp>
2 102232123 1 2,5,9,22,33,44,55,66,77,,78,79,80,88,89 <timestamp>
3 201141028 1 7,8,9,11,22,33,34,35,37,39,51,55,58,63,66 <timestamp>
...
9.000.000 126387125 1 8,18,28,38,48,58,68,78,79,80,81,82,83,84,85 <timestamp>
10.000.000 126387126 1 1,4,14,24,34,45,56,66,67,68,79,80,81,82,83 <timestamp>
菲律宾比索
$drawn_numbers = '1,2,3,4,5,6,7,89,10,11,12,13,14,15,16,17,18,19,20,21,22, ...';
$result = query("SELECT * FROM Tickets WHERE sksf('$drawn_numbers')");
其中sksf
是在MySql中完成的某种子字符串函数/正则表达式/LIKE。
想法2:
桌票
id user_id week n1 n2 n3 ... n15 created
=============================================================================
1 100022312 1 11 32 52 ... 76 <timestamp>
2 102232123 1 22 52 55 78 <timestamp>
3 201141028 1 77 82 83 ... 89 <timestamp>
...
9.000.000 126387125 1 81 55 32 ... 10 <timestamp>
10.000.000 126387126 1 12 42 13 ... 77 <timestamp>
菲律宾比索
$drawn_numbers = '1,2,3,4,5,6,7,89,10,11,12,13,14,15,16,17,18,19,20,21,22, ...';
$result = query("SELECT * FROM Tickets WHERE contidion1 AND condition2 AND ...");
不幸的是,在这里我仍然对条件一无所知。
想法3:
我选择所有票证,通过检查开奖号码是否包含任何票证来迭代它们。
$drawn_numbers = '1,2,3,4,5,6,7,89,10,11,12,13,14,15,16,17,18,19,20,21,22, ...';
$all_tickets = query("SELECT * FROM Tickets");
foreach ($all_tickets as $ticket) {
if $drawn_numbers.contains($ticket['ticket'])
return $ticket['id'];
}
问题2:
无论如何,对数字进行排序会有所帮助吗?(这15个号码和抽奖号码)
问题3:
当第 2 周到来时会发生什么?我应该使用相同的表,添加一个条件WHERE week=2
,还是每张桌子只有 1 周更好?
更新
在原始游戏中,一张彩票有 3 行 15 个数字,每行有 5 个数字。每个号码实时开奖后,他们还能够计算在抽奖号码中找到一行的彩票(他们也知道 2 行的彩票)。在开奖号码中找到 3 行的彩票将意味着中奖彩票。
这些信息让我认为表示看起来像:
想法4:
桌票
id user_id week row1 row2 row3 created
===============================================================================================================
1 100022312 1 1, 3, 5, 7, 9 14,15,77,78,79, 80,81,82,83,84 <timestamp>
2 102232123 1 2, 5, 9,22,33, 44,55,66,77,78, 79,80,87,88,89 <timestamp>
3 201141028 1 7, 8, 9,11,22, 33,34,35,37,39, 51,55,58,63,66 <timestamp>
...
9.000.000 126387125 1 8,18,28,38,48, 58,68,78,79,80, 81,82,83,84,85 <timestamp>
10.000.000 126387126 1 1, 4,14,24,34, 45,56,66,67,68, 79,80,81,82,83 <timestamp>
车票示例:
__ 13 __ 33 40 __ __ 70 __
2 __ 22 37 __ 52 62 __ 81
__ 19 23 __ 44 __ 63 __ 89
抽奖号码示例(不一定按排序顺序)
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 19, 23, 44, 63, 89
-> there is a winner, no more numbers are drawn.
-> Our ticket did not win jackpot, but we won one row [19, 23, 44, 63, 89] (free ticket)
-> One can win also 2 rows.
我会使用两个BIGINT
列,每个位代表一个宾果值(1..90)。 构建一组球需要一点操作,但搜索将很容易,存储将更加紧凑,等等。
让我们有 2 列,一列的数字为 1..60,另一列的数字为 61..90。 (选择有些随意,但很容易可视化。 现在我们可以用一个BIGINT
和一个INT
来做到这一点。
IF($value <= 60, 1 << $value, 0) -- the bit for the BIGINT
IF($value > 60, 1 << ($value - 60), 0) -- the bit for the INT
现在,将位组合在一起会给你一对数字来代表一张中奖彩票。 使用|
运算符执行此任务。
每个玩家的当前球也将是 or'd - 每次比赛后都会打开一个新位。
然后测试变成这样:
-- The balls owned by a user:
user_60 BIGINT,
user_30 INT
-- winning balls (12 rows, a total of 5 bits on for each row)
win_60 BIGINT,
win_30 INT
-- Note: FREE SPACE should be pre-populated in both structures
BIT_COUNT(user_60 & win_60) +
BIT_COUNT(user_30 & win_30) = 5 -- he's a winner!
我遗漏了一个重要的步骤——每个用户板上数字的排列。 这将需要一些前期工作,特别是因为 15 个数字只能放在卡片的第一列中。 等。
你从我的答案中得到的收获是使用位而不是其他结构。
另一个想法是有 5 个SMALLINT UNSIGNED
,卡片上的每一列一个。
(将来,在MySQL 8.0中,BINARY(16)
将允许单个列表示一组90个值,从而使代码更清晰。
重新想法4
构建 3 位模式 - 每个"行"一个,有 5 个数字。 将它们与已发行的票进行比较:对于每张票,比较 3 种模式;数一数匹配的数量。
两者都不是。
一种方法是使用票号的位图。您需要 2 个 BIGINT 来存储值。如果票号和所选号码的 AND 返回的值与票号相同,则您具有匹配项。但是您不能为此使用索引。
如果仅通过匹配某些数字就可以获胜,那么您引用的两种方法都将非常低效 - 您需要规范化数据:
create table ticket (
id integer auto_increment,
user_id /* appropriate type for FK to your data about users */,
week_number integer,
PRIMARY KEY (id),
);
create table numbers (
number integer not null,
ticket_id integer not null,
FOREIGN KEY ticket_id references ticket(id)
);
这看起来像是一个精心设计的场景来测试可伸缩性方法 - 您是否要求我们在这里做功课?