10MPage.com：2025 年互聯(lián)網(wǎng)檔案 - 優(yōu)化 1000 萬張圖像的平鋪放置

我正在構(gòu)建 10MPage.com，這是一個雄心勃勃的項目，旨在捕捉 2025 年互聯(lián)網(wǎng)的狀態(tài)。每個用戶都可以向這個龐大的在線檔案貢獻(xiàn) 64x64 像素的圖像。 添加圖像涉及一個多步驟過程：上傳創(chuàng)建待處理的圖塊，在將其放置到網(wǎng)格上之前需要批準(zhǔn)。

網(wǎng)格本身是一個數(shù)據(jù)庫表（稱為tiles），其中每一行代表一個具有 X 和 Y 坐標(biāo)的 1x1 圖塊。較大的待處理圖塊被分解為多個 1x1 圖塊。 挑戰(zhàn)：有效地將這些圖塊放置到不斷擴展的網(wǎng)格上以容納 1000 萬個條目。

我最初的方法是一個簡單的循環(huán)搜索空位，結(jié)果證明是災(zāi)難性的。 添加幾千塊瓷磚只需幾秒鐘；推斷為 1000 萬，預(yù)計完成時間需要幾年！

初始方法（低效）：

我的第一次嘗試涉及迭代整個網(wǎng)格以找到可用空間。 網(wǎng)格動態(tài)擴展以保持大致正方形的形狀。 這是核心 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) 開始。 優(yōu)化包括使用單個數(shù)據(jù)庫查詢的更高效的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();
}

通過從現(xiàn)有的最小 X 和 Y 坐標(biāo)開始搜索來進(jìn)一步嘗試優(yōu)化 find() 也未能顯著提高性能。 將整個網(wǎng)格加載到內(nèi)存中以進(jìn)行更快的檢查被證明過于占用內(nèi)存。

解決方案：放置塊

可擴展性的關(guān)鍵是采用基于塊的方法。 我引入了“放置塊”，即 100x100 的圖塊單元，由新的 placement_blocks 數(shù)據(jù)庫表管理。每個塊都會跟蹤其最小/最大 X 和 Y 坐標(biāo)以及“完整”布爾標(biāo)志。

這種方法有兩個主要優(yōu)點：

1. 減少搜索空間：對空白空間的搜索現(xiàn)在僅限于 100x100 區(qū)域。
2. 并發(fā)：多個進(jìn)程可以同時將圖塊放入不同的塊中。

查找和使用放置塊：

遞歸函數(shù)有效地找到可用的放置塊或根據(jù)需要創(chuàng)建新的放置塊：

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

place() 方法利用此功能，采用全局鎖來協(xié)調(diào)塊選擇和每塊鎖以防止競爭條件：

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

使用優(yōu)化的 canPlaceBlock 方法在放置塊中添加圖塊。 目前，不支持大于單個放置塊的圖塊。

并發(fā)性和可擴展性：

Laravel 作業(yè)和 Horizo??n 管理并發(fā)的圖塊放置。 工作人員的數(shù)量應(yīng)等于或小于可用放置塊的數(shù)量。 這允許輕松水平縮放。

這種改進(jìn)的方法極大地提高了圖塊放置過程的速度和可擴展性，使 10MPage.com 的雄心勃勃的目標(biāo)可以實現(xiàn)。 立即加入該項目并添加您的貢獻(xiàn)！

以上是用 PHP 填充一百萬個圖像網(wǎng)格以獲取互聯(lián)網(wǎng)歷史的詳細(xì)內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！