用 PHP 填充一百万个图像网格以获取互联网历史

珍惜时间，勤奋学习！今天给大家带来《用 PHP 填充一百万个图像网格以获取互联网历史》，正文内容主要涉及到等等，如果你正在学习文章，或者是对文章有疑问，欢迎大家关注我！后面我会持续更新相关内容的，希望都能帮到正在学习的大家！

10mpage.com：构建一个容纳千万图像的互联网档案馆

我正在开发10mpage.com，旨在捕捉2025年互联网的缩影。任何互联网用户都可以上传64x64像素的小图像，为这个数字档案馆贡献一份力量。

图像添加流程如下：上传的图像首先进入待处理队列。考虑到互联网提交的不可预测性，每个待处理图像都需要人工审核批准。

批准后，图像会被放置到一个网格中。这个网格存储在名为“tiles”的数据库表中，每行记录图像的x和y坐标。

待处理图像可能包含多个1x1的小图块。大型待处理图像会被分割成多个小图块，最终所有图块都统一为1x1大小。

本文将重点介绍我如何将待处理图块高效地放置到网格中，并优化流程以应对大规模数据处理的挑战。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中！它是免费的！

本篇关于《用 PHP 填充一百万个图像网格以获取互联网历史》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！