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

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

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

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

初始方法（低效率）：

我的第一次嘗試涉及迭代整個網(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) 開始。 最佳化包括使用單一資料庫查詢的更有效率的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 座標開始搜尋來進一步嘗試最佳化 find() 也未能顯著提高效能。 將整個網(wǎng)格加載到記憶體中以進行更快的檢查被證明過於佔用記憶體。

解：放置塊

可擴展性的關鍵是採用基於區(qū)塊的方法。 我引入了“放置塊”，即 100x100 的圖塊單元，由新的 placement_blocks 資料庫表管理。每個區(qū)塊都會追蹤其最小/最大 X 和 Y 座標以及「完整」布林標誌。

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

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

找出並使用放置塊：

遞歸函數(shù)有效地找到可用的放置區(qū)塊或根據(jù)需要建立新的放置區(qū)塊：

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

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

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

使用最佳化的 canPlaceBlock 方法在放置區(qū)塊中加入圖塊。 目前，不支援大於單一放置塊的圖塊。

並發(fā)性和可擴充性：

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

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

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