Filling a Million Image Grid with PHP for Internet History

10MPage.com: A 2025 Internet Archive – Optimizing Tile Placement for 10 Million Images

I'm building 10MPage.com, an ambitious project aiming to capture the internet's state in 2025. Each user can contribute a 64x64 pixel image to this massive online archive. Adding images involves a multi-step process: uploads create pending tiles, which require approval before being placed onto a grid.

The grid itself is a database table (called tiles) where each row represents a 1x1 tile with X and Y coordinates. Larger pending tiles are broken down into multiple 1x1 tiles. The challenge: efficiently placing these tiles onto the expanding grid to accommodate 10 million entries.

My initial approach, a simple loop searching for empty spots, proved disastrous. Adding a few thousand tiles took seconds; extrapolating to 10 million resulted in a projected completion time of several years!

Initial Approach (Inefficient):

My first attempt involved iterating through the entire grid to find an available space. The grid dynamically expanded to maintain a roughly square shape. Here's the core find() method:

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

This was slow because the search always began from (0,0). Optimizations included a more efficient canPlaceBlock method using a single database query:

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

Further attempts to optimize find() by starting the search at the minimum existing X and Y coordinates also failed to significantly improve performance. Loading the entire grid into memory for faster checks proved too memory-intensive.

The Solution: Placement Blocks

The key to scalability was adopting a block-based approach. I introduced "placement blocks," 100x100 tile units, managed by a new placement_blocks database table. Each block tracks its minimum/maximum X and Y coordinates and a "full" boolean flag.

This approach offers two major advantages:

1. Reduced Search Space: The search for an empty space is now limited to a 100x100 area.
2. Concurrency: Multiple processes can concurrently place tiles into different blocks.

Finding and Using Placement Blocks:

A recursive function efficiently finds an available placement block or creates new ones as needed:

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

The place() method utilizes this function, employing a global lock to coordinate block selection and per-block locks to prevent race conditions:

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

Tiles are added within the placement block using the optimized canPlaceBlock method. Currently, tiles larger than a single placement block are not supported.

Concurrency and Scalability:

Laravel jobs and Horizon manage concurrent tile placement. The number of workers should match or be less than the number of available placement blocks. This allows for easy horizontal scaling.

This improved approach dramatically increases the speed and scalability of the tile placement process, making 10MPage.com's ambitious goal achievable. Join the project and add your contribution today!

The above is the detailed content of Filling a Million Image Grid with PHP for Internet History. For more information, please follow other related articles on the PHP Chinese website!