Remplir une grille d'un million d'images avec PHP pour l'historique Internet

10MPage.com : Une archive Internet 2025 – Optimisation du placement des tuiles pour 10 millions d'images

Je suis en train de construire 10MPage.com, un projet ambitieux visant à capturer l'état d'Internet en 2025. Chaque utilisateur peut contribuer une image de 64 x 64 pixels à cette immense archive en ligne. L'ajout d'images implique un processus en plusieurs étapes : les téléchargements créent des vignettes en attente, qui nécessitent une approbation avant d'être placées sur une grille.

La grille elle-même est une table de base de données (appelée tiles) où chaque ligne représente une tuile 1x1 avec des coordonnées X et Y. Les tuiles en attente plus grandes sont divisées en plusieurs tuiles 1x1. Le défi : placer efficacement ces tuiles sur la grille en expansion pour accueillir 10 millions d'entrées.

Mon approche initiale, une simple boucle à la recherche d'emplacements vides, s'est avérée désastreuse. L'ajout de quelques milliers de tuiles a pris quelques secondes ; l'extrapolation à 10 millions a abouti à un délai d'achèvement prévu de plusieurs années !

Approche initiale (inefficace) :

Ma première tentative consistait à parcourir toute la grille pour trouver un espace disponible. La grille s'est développée dynamiquement pour conserver une forme à peu près carrée. Voici la méthode find() de base :

<code class="language-php">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) ...</code>

C'était lent car la recherche commençait toujours à partir de (0,0). Les optimisations comprenaient une canPlaceBlock méthode plus efficace utilisant une seule requête de base de données :

<code class="language-php">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();
}</code>

D'autres tentatives d'optimisation find() en démarrant la recherche aux coordonnées X et Y minimales existantes n'ont pas non plus réussi à améliorer de manière significative les performances. Le chargement de la grille entière en mémoire pour des vérifications plus rapides s'est avéré trop gourmand en mémoire.

La solution : les blocs de placement

La clé de l'évolutivité était d'adopter une approche basée sur les blocs. J'ai introduit des "blocs de placement", des unités de tuiles de 100 x 100, gérées par une nouvelle table de base de données placement_blocks. Chaque bloc suit ses coordonnées X et Y minimum/maximum et un drapeau booléen « complet ».

Cette approche offre deux avantages majeurs :

1. Espace de recherche réduit : La recherche d'un espace vide est désormais limitée à une zone de 100x100.
2. Concurrence : Plusieurs processus peuvent placer simultanément des tuiles dans différents blocs.

Trouver et utiliser des blocs de placement :

Une fonction récursive trouve efficacement un bloc de placement disponible ou en crée de nouveaux selon les besoins :

<code class="language-php">public function find(array $excludeBlocks = []): PlacementBlock
{
    // ... (code to find or create placement blocks) ...
}</code>

La méthode place() utilise cette fonction, en utilisant un verrou global pour coordonner la sélection de blocs et des verrous par bloc pour éviter les conditions de concurrence :

<code class="language-php">public function place(PendingTile $pendingTile): void
{
    // ... (code to acquire locks and place tiles) ...
}</code>

Les tuiles sont ajoutées dans le bloc de placement à l'aide de la méthode canPlaceBlock optimisée. Actuellement, les tuiles plus grandes qu'un seul bloc de placement ne sont pas prises en charge.

Concurrence et évolutivité :

Les tâches Laravel et Horizon gèrent le placement simultané des tuiles. Le nombre de travailleurs doit correspondre ou être inférieur au nombre de blocs de placement disponibles. Cela permet une mise à l'échelle horizontale facile.

Cette approche améliorée augmente considérablement la vitesse et l'évolutivité du processus de placement des tuiles, rendant ainsi l'objectif ambitieux de 10MPage.com réalisable. Rejoignez le projet et ajoutez votre contribution dès aujourd'hui !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!