10MPage.com: Arkib Internet 2025 – Mengoptimumkan Peletakan Jubin untuk 10 Juta Imej

Saya sedang membina 10MPage.com, sebuah projek bercita-cita tinggi yang bertujuan untuk menangkap keadaan internet pada tahun 2025. Setiap pengguna boleh menyumbangkan imej 64x64 piksel ke arkib dalam talian yang besar ini. Menambah imej melibatkan proses berbilang langkah: muat naik menghasilkan jubin yang belum selesai, yang memerlukan kelulusan sebelum diletakkan pada grid.

Grid itu sendiri ialah jadual pangkalan data (dipanggil tiles) di mana setiap baris mewakili jubin 1x1 dengan koordinat X dan Y. Jubin belum selesai yang lebih besar dipecahkan kepada berbilang jubin 1x1. Cabarannya: meletakkan jubin ini dengan cekap pada grid yang berkembang untuk menampung 10 juta penyertaan.

Pendekatan awal saya, gelung mudah mencari tempat kosong, terbukti membawa bencana. Menambah beberapa ribu jubin mengambil masa beberapa saat; mengekstrapolasi kepada 10 juta menghasilkan jangkaan masa siap selama beberapa tahun!

Pendekatan Awal (Tidak Cekap):

Percubaan pertama saya melibatkan lelaran melalui keseluruhan grid untuk mencari ruang yang tersedia. Grid berkembang secara dinamik untuk mengekalkan bentuk kira-kira empat segi. Inilah kaedah find() teras:

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

Ini lambat kerana carian sentiasa bermula dari (0,0). Pengoptimuman termasuk kaedah canPlaceBlock yang lebih cekap menggunakan satu pertanyaan pangkalan data:

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();
}

Percubaan lanjut untuk mengoptimumkan find() dengan memulakan carian pada minimum koordinat X dan Y sedia ada juga gagal meningkatkan prestasi dengan ketara. Memuatkan keseluruhan grid ke dalam memori untuk pemeriksaan yang lebih pantas terbukti terlalu intensif memori.

Penyelesaian: Blok Peletakan

Kunci kepada kebolehskalaan ialah menggunakan pendekatan berasaskan blok. Saya memperkenalkan "blok peletakan," unit jubin 100x100, diuruskan oleh jadual pangkalan data placement_blocks baharu. Setiap blok menjejaki koordinat X dan Y minimum/maksimum dan bendera boolean "penuh".

Pendekatan ini menawarkan dua kelebihan utama:

1. Ruang Carian Dikurangkan: Pencarian ruang kosong kini terhad kepada kawasan 100x100.
2. Keselarasan: Berbilang proses serentak boleh meletakkan jubin ke dalam blok yang berbeza.

Mencari dan Menggunakan Blok Peletakan:

Fungsi rekursif mencari blok peletakan yang tersedia dengan cekap atau mencipta yang baharu mengikut keperluan:

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

Kaedah place() menggunakan fungsi ini, menggunakan kunci global untuk menyelaraskan pemilihan blok dan kunci setiap blok untuk mengelakkan keadaan perlumbaan:

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

Jubin ditambah dalam blok peletakan menggunakan kaedah canPlaceBlock yang dioptimumkan. Pada masa ini, jubin yang lebih besar daripada satu blok peletakan tidak disokong.

Keselarasan dan Kebolehskalaan:

Kerja Laravel dan Horizon menguruskan peletakan jubin serentak. Bilangan pekerja hendaklah sepadan atau kurang daripada bilangan blok penempatan yang tersedia. Ini membolehkan penskalaan mendatar yang mudah.

Pendekatan yang dipertingkatkan ini secara mendadak meningkatkan kelajuan dan kebolehskalaan proses peletakan jubin, menjadikan matlamat bercita-cita tinggi 10MPage.com boleh dicapai. Sertai projek dan tambah sumbangan anda hari ini!

Atas ialah kandungan terperinci Mengisi Juta Grid Imej dengan PHP untuk Sejarah Internet. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!