10MPage.com: 2025 年のインターネット アーカイブ – 1,000 萬枚の畫像のタイル配置を最適化

私は 10MPage.com を構(gòu)築しています。これは、2025 年のインターネットの狀態(tài)を把握することを目的とした野心的なプロジェクトです。各ユーザーは、この大規(guī)模なオンライン アーカイブに 64x64 ピクセルの畫像を投稿できます。 畫像の追加には複數(shù)の手順のプロセスが含まれます。アップロードすると保留中のタイルが作成され、グリッドに配置する前に承認(rèn)が必要になります。

グリッド自體はデータベース テーブル (tiles と呼ばれる) であり、各行は X 座標(biāo)と Y 座標(biāo)を持つ 1x1 タイルを表します。大きな保留タイルは複數(shù)の 1x1 タイルに分割されます。 課題は、1,000 萬のエントリに対応するために、拡大するグリッドにこれらのタイルを効率的に配置することです。

私の最初のアプローチは、空のスポットを検索する?yún)g純なループでしたが、悲慘な結(jié)果となりました。 數(shù)千のタイルを追加するには數(shù)秒かかりました。 1,000 萬に推定すると、完成には數(shù)年かかると予想されます!

初期アプローチ (非効率):

私の最初の試みは、グリッド全體を反復(fù)処理して利用可能なスペースを見つけることでした。 グリッドは動(dòng)的に拡張されて、ほぼ正方形の形狀を維持します。 コアの 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 座標(biāo)と Y 座標(biāo)で検索を開始して find() を最適化するさらなる試みも、パフォーマンスを大幅に向上させることはできませんでした。 チェックを高速化するためにグリッド全體をメモリにロードすると、メモリの消費(fèi)量が多すぎることが判明しました。

解決策: 配置ブロック

スケーラビリティの鍵は、ブロックベースのアプローチを採(cǎi)用することでした。 新しい placement_blocks データベース テーブルによって管理される、100x100 タイル ユニットである「配置ブロック」を?qū)毪筏蓼筏俊８鳐芝恁氓?、その最?最大 X 座標(biāo)と Y 座標(biāo)、および「完全な」ブール フラグを追跡します。

このアプローチには 2 つの大きな利點(diǎn)があります:

1. 検索スペースの縮小: 空きスペースの検索が 100x100 のエリアに制限されるようになりました。
2. 同時(shí)実行性: 複數(shù)のプロセスがタイルを異なるブロックに同時(shí)に配置できます。

配置ブロックの検索と使用:

再帰関數(shù)は、使用可能な配置ブロックを効率的に見つけたり、必要に応じて新しい配置ブロックを作成したりします。

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

place() メソッドはこの関數(shù)を利用し、グローバル ロックを使用してブロック選択を調(diào)整し、ブロックごとのロックを使用して競(jìng)合狀態(tài)を防止します。

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

タイルは、最適化された canPlaceBlock メソッドを使用して配置ブロック內(nèi)に追加されます。 現(xiàn)在、単一の配置ブロックより大きいタイルはサポートされていません。

同時(shí)実行性とスケーラビリティ:

Laravel ジョブと Horizo??n はタイルの同時(shí)配置を管理します。 ワーカーの數(shù)は、使用可能な配置ブロックの數(shù)と一致するか、それより少ない必要があります。 これにより、水平方向のスケーリングが容易になります。

この改善されたアプローチにより、タイル配置プロセスの速度とスケーラビリティが大幅に向上し、10MPage.com の野心的な目標(biāo)が達(dá)成可能になります。 プロジェクトに參加して、今すぐ貢獻(xiàn)を追加してください!

以上がインターネットの歴史のために PHP で 100 萬枚の畫像グリッドを埋めるの詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國(guó)語 Web サイトの他の関連記事を參照してください。