10mpage.com：构建一个容纳千万图像的互联网档案馆
我正在开发10mpage.com，旨在捕捉2025年互联网的缩影。任何互联网用户都可以上传64x64像素的小图像，为这个数字档案馆贡献一份力量。
图像添加流程如下：上传的图像首先进入待处理队列。考虑到互联网提交的不可预测性，每个待处理图像都需要人工审核批准。
批准后，图像会被放置到一个网格中。这个网格存储在名为“tiles”的数据库表中，每行记录图像的x和y坐标。
待处理图像可能包含多个1x1的小图块。大型待处理图像会被分割成多个小图块，最终所有图块都统一为1x1大小。
立即学习“PHP免费学习笔记（深入）”；
本文将重点介绍我如何将待处理图块高效地放置到网格中，并优化流程以应对大规模数据处理的挑战。10mpage的目标是容纳一千万个小图块。
预告：我的第一版算法在处理几千个图块时，添加新图块需要几秒钟，随着网格规模的扩大，速度显著下降。我粗略估算了一下，添加一千万个图块需要的时间……几年……
让我们分析一下我的初始方法。它很简单：循环遍历网格，寻找空位并放置待处理图块。这其中包含了一些关于网格如何随着数据增长而扩展的逻辑。
以下是根据待处理图块的宽度和高度查找可用位置的函数：
public function find(int $blockwidth, int $blockheight): array
{
$currentmaxx = tile::query()->max('x') ?? 0;
$currentmaxy = tile::query()->max('y') ?? 0;
$currentwidth = $currentmaxx + 1;
$currentheight = $currentmaxy + 1;
$newwidth = $currentwidth;
$newheight = $currentheight;
if ($currentwidth > $currentheight) {
$newheight++;
} elseif ($currentheight > $currentwidth) {
$newwidth++;
} else {
$newwidth++;
}
for ($y = 0; $y canplaceblock($x, $y, $blockwidth, $blockheight)) {
return ['x' => $x, 'y' => $y];
}
}
}
return [0,0];
}
protected function canplaceblock(int $startx, int $starty, int $blockwidth, int $blockheight): bool
{
for ($y = $starty; $y where('x', $x)->where('y', $y)->exists()) {
return false;
}
}
}
return true;
}
这种方法在图块数量较少时表现良好，但随着网格规模的扩大，速度急剧下降。这是因为循环总是从零开始遍历。
对于大型图块，一个简单的优化是重写canplaceblock函数，使其只执行单个数据库查询：
public function canplaceblock(int $startx, int $starty, int $blockwidth, int $blockheight): bool
{
$ys = range($starty, $starty + $blockheight - 1);
$xs = range($startx, $startx + $blockwidth - 1);
return ! tile::wherein('x', $xs)->wherein('y', $ys)->exists();
}
我们还可以尝试从数据库中已存在的最小x和y坐标开始优化find函数：
$maxx = tile::query()->max('x') ?? 1000;
$maxy = tile::query()->max('y') ?? 1000;
$minx = tile::query()->min('x') ?? 0;
$miny = tile::query()->min('y') ?? 0;
$occupiedtiles = tile::query()
->where('x', '>=', $minx)
->where('x', 'where('y', '>=', $miny)
->where('y', 'get()
->mapwithkeys(fn (tile $tile) => [$tile->x.','.$tile->y => true]);
// ... (rest of the find function)
然而，这种方法并没有显著改善性能，因为最小值仍然为零，而且加载整个网格会消耗更多内存。此外，仍然需要执行查询来检查整个图块是否合适（仅适用于尺寸大于1的待处理图块，但这尚未实现）。
上述两种解决方案都存在以下两个问题：
- 图块数量较多时速度慢
- 只能一次放置一个待处理图块
如果我们使用更小的块呢？假设使用100x100的块。这可以解决这两个问题：首先，我们不必检查大于100x100的网格；其次，我们可以使用并发进程将待处理图块放置到不同的块中。
为了实现并发，我们需要确保每个块只被同时访问一次，并且待处理图块不会溢出块。
我将这些块称为“放置块”，并创建了一个名为placement_blocks的新数据库表。对于每个块，我们存储最小/最大x/y坐标和一个布尔值（指示块是否已满）。
一旦所有块都已满，就需要在网格的右侧和底部创建新的块。如下图所示：
放置过程现在必须从查找可用的放置块开始。我使用递归函数来查找可用块，如果没有可用块，则创建新的放置块：
// ... (find function implementation) ...
这是place函数使用的代码。此函数使用两种锁：全局锁和特定于放置块的锁。它首先锁定全局锁来查找可用的放置块。一旦找到放置块，它就会被锁定，并且全局锁被释放，以便下一个进程也能找到放置块。
// ... (place function implementation) ...
查找可用位置使用我们之前编写的canplaceblock函数，其中图块仅限于放置块内查找。一旦找到位置，它将添加图块并释放放置块锁定。
但是，如果待处理图块不适合可用的放置块，该怎么办？必须等到网格扩展才能放置。目前不支持添加大于单个放置块的待处理图块。
我使用Laravel作业和Laravel Horizon运行此程序，有多个worker处理放置任务。通过这种实现，可以同时放置的图块数量受到worker数量和可用放置块数量的限制。随着项目的发展，我可以增加worker数量来同时放置更多图块，只需确保worker数量等于或小于放置块的数量即可。
感谢您的阅读。如果您喜欢这篇文章，欢迎将您最喜欢的编程语言、加密货币或宠物添加到10mpage中！它是免费的！
