インターネットの歴史のために PHP で 100 万枚の画像グリッドを埋める

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

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

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

私の最初のアプローチは、空のスポットを検索する単純なループでしたが、悲惨な結果となりました。 数千のタイルを追加するには数秒かかりました。 1,000 万に推定すると、完成には数年かかると予想されます!

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

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

解決策: 配置ブロック

スケーラビリティの鍵は、ブロックベースのアプローチを採用することでした。 新しい placement_blocks データベース テーブルによって管理される、100x100 タイル ユニットである「配置ブロック」を導入しました。各ブロックは、その最小/最大 X 座標と Y 座標、および「完全な」ブール フラグを追跡します。

このアプローチには 2 つの大きな利点があります:

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 で 100 万枚の画像グリッドを埋めるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。