Füllen eines Millionen-Bild-Rasters mit PHP für den Internetverlauf

10MPage.com: Ein Internetarchiv für 2025 – Optimierung der Kachelplatzierung für 10 Millionen Bilder

Ich baue 10MPage.com auf, ein ehrgeiziges Projekt mit dem Ziel, den Zustand des Internets im Jahr 2025 zu erfassen. Jeder Benutzer kann ein 64x64 Pixel großes Bild zu diesem riesigen Online-Archiv beitragen. Das Hinzufügen von Bildern erfordert einen mehrstufigen Prozess: Durch Uploads werden ausstehende Kacheln erstellt, die genehmigt werden müssen, bevor sie in einem Raster platziert werden.

Das Raster selbst ist eine Datenbanktabelle (genannt tiles), in der jede Zeile eine 1x1-Kachel mit X- und Y-Koordinaten darstellt. Größere ausstehende Kacheln werden in mehrere 1x1-Kacheln unterteilt. Die Herausforderung: Diese Kacheln effizient auf dem expandierenden Raster platzieren, um 10 Millionen Einträge aufzunehmen.

Mein ursprünglicher Ansatz, eine einfache Schleife zur Suche nach leeren Stellen, erwies sich als katastrophal. Das Hinzufügen einiger tausend Kacheln dauerte Sekunden. Eine Hochrechnung auf 10 Millionen ergab eine voraussichtliche Fertigstellungszeit von mehreren Jahren!

Erstansatz (ineffizient):

Mein erster Versuch bestand darin, das gesamte Raster zu durchlaufen, um einen verfügbaren Platz zu finden. Das Gitter wurde dynamisch erweitert, um eine ungefähr quadratische Form beizubehalten. Hier ist die Kernmethode find():

<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>

Das war langsam, da die Suche immer bei (0,0) begann. Zu den Optimierungen gehörte eine effizientere canPlaceBlock Methode mit einer einzigen Datenbankabfrage:

<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>

Weitere Optimierungsversuche find() durch Starten der Suche bei den minimal vorhandenen X- und Y-Koordinaten konnten die Leistung ebenfalls nicht wesentlich verbessern. Das Laden des gesamten Rasters in den Speicher für schnellere Überprüfungen erwies sich als zu speicherintensiv.

Die Lösung: Platzierungsblöcke

Der Schlüssel zur Skalierbarkeit lag in der Annahme eines blockbasierten Ansatzes. Ich habe „Platzierungsblöcke“ eingeführt, 100 x 100 Kacheleinheiten, die von einer neuen placement_blocks Datenbanktabelle verwaltet werden. Jeder Block verfolgt seine minimalen/maximalen X- und Y-Koordinaten und ein „vollständiges“ boolesches Flag.

Dieser Ansatz bietet zwei große Vorteile:

1. Reduzierter Suchraum:Die Suche nach einem leeren Raum ist jetzt auf einen Bereich von 100x100 beschränkt.
2. Gleichzeitigkeit: Mehrere Prozesse können gleichzeitig Kacheln in verschiedenen Blöcken platzieren.

Platzierungsblöcke finden und verwenden:

Eine rekursive Funktion findet effizient einen verfügbaren Platzierungsblock oder erstellt bei Bedarf neue:

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

Die place()-Methode nutzt diese Funktion und verwendet eine globale Sperre, um die Blockauswahl zu koordinieren, und Sperren pro Block, um Race-Bedingungen zu verhindern:

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

Kacheln werden innerhalb des Platzierungsblocks mit der optimierten canPlaceBlock-Methode hinzugefügt. Derzeit werden Kacheln, die größer als ein einzelner Platzierungsblock sind, nicht unterstützt.

Parallelität und Skalierbarkeit:

Laravel-Jobs und Horizon verwalten die gleichzeitige Kachelplatzierung. Die Anzahl der Arbeiter sollte der Anzahl der verfügbaren Platzierungsblöcke entsprechen oder kleiner sein. Dies ermöglicht eine einfache horizontale Skalierung.

Dieser verbesserte Ansatz erhöht die Geschwindigkeit und Skalierbarkeit des Kachelplatzierungsprozesses erheblich und macht das ehrgeizige Ziel von 10MPage.com erreichbar. Treten Sie dem Projekt bei und fügen Sie noch heute Ihren Beitrag hinzu!

Das obige ist der detaillierte Inhalt vonFüllen eines Millionen-Bild-Rasters mit PHP für den Internetverlauf. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!