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

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

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

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

初始方法（低效率）：

我的第一次嘗試涉及迭代整個(gè)網(wǎng)格以找到可用空間。 網(wǎng)格動(dòng)態(tài)擴(kuò)展以保持大致正方形的形狀。 這是核心 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) ...

這很慢，因?yàn)樗褜た偸菑?(0,0) 開(kāi)始。 最佳化包括使用單一資料庫(kù)查詢的更有效率的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();
}

透過(guò)從現(xiàn)有的最小 X 和 Y 座標(biāo)開(kāi)始搜尋來(lái)進(jìn)一步嘗試最佳化 find() 也未能顯著提高效能。 將整個(gè)網(wǎng)格加載到記憶體中以進(jìn)行更快的檢查被證明過(guò)於佔(zhàn)用記憶體。

解：放置塊

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

這種方法有兩個(gè)主要優(yōu)點(diǎn)：

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

找出並使用放置塊：

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

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

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

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

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

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

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

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

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