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

10MPage.com：2025 年互联网档案 - 优化 1000 万张图像的平铺放置

我正在构建 10MPage.com，这是一个雄心勃勃的项目，旨在捕捉 2025 年互联网的状态。每个用户都可以向这个庞大的在线档案贡献 64x64 像素的图像。 添加图像涉及一个多步骤过程：上传创建待处理的图块，在将其放置到网格上之前需要批准。

网格本身是一个数据库表（称为tiles），其中每一行代表一个具有 X 和 Y 坐标的 1x1 图块。较大的待处理图块被分解为多个 1x1 图块。 挑战：有效地将这些图块放置到不断扩展的网格上以容纳 1000 万个条目。

我最初的方法是一个简单的循环搜索空位，结果证明是灾难性的。 添加几千块瓷砖只需几秒钟；推断为 1000 万，预计完成时间需要几年！

初始方法（低效）：

我的第一次尝试涉及迭代整个网格以找到可用空间。 网格动态扩展以保持大致正方形的形状。 这是核心 find() 方法：

public function find(int $blockWidth, int $blockHeight): array
{
    // ... (code to determine grid dimensions) ...

    // Look for a fitting spot
    for ($y = 0; $y < $newHeight; $y++) {
        for ($x = 0; $x < $newWidth; $x++) {
            if ($this->canPlaceBlock($x, $y, $blockWidth, $blockHeight)) {
                return ['x' => $x, 'y' => $y];
            }
        }
    }
    return [0, 0];
}

// ... (canPlaceBlock method) ...

这很慢，因为搜索总是从 (0,0) 开始。 优化包括使用单个数据库查询的更高效的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() 也未能显着提高性能。 将整个网格加载到内存中以进行更快的检查被证明过于占用内存。

解决方案：放置块

可扩展性的关键是采用基于块的方法。 我引入了“放置块”，即 100x100 的图块单元，由新的 placement_blocks 数据库表管理。每个块都会跟踪其最小/最大 X 和 Y 坐标以及“完整”布尔标志。

这种方法有两个主要优点：

1. 减少搜索空间：对空白空间的搜索现在仅限于 100x100 区域。
2. 并发：多个进程可以同时将图块放入不同的块中。

查找和使用放置块：

递归函数有效地找到可用的放置块或根据需要创建新的放置块：

public function find(array $excludeBlocks = []): PlacementBlock
{
    // ... (code to find or create placement blocks) ...
}

place() 方法利用此功能，采用全局锁来协调块选择和每块锁以防止竞争条件：

public function place(PendingTile $pendingTile): void
{
    // ... (code to acquire locks and place tiles) ...
}

使用优化的 canPlaceBlock 方法在放置块中添加图块。 目前，不支持大于单个放置块的图块。

并发性和可扩展性：

Laravel 作业和 Horizo​​n 管理并发的图块放置。 工作人员的数量应等于或小于可用放置块的数量。 这允许轻松水平缩放。

这种改进的方法极大地提高了图块放置过程的速度和可扩展性，使 10MPage.com 的雄心勃勃的目标可以实现。 立即加入该项目并添加您的贡献！

以上是用 PHP 填充一百万个图像网格以获取互联网历史的详细内容。更多信息请关注PHP中文网其他相关文章！