Melayani Kluster Peta 50x Lebih Cepat Menggunakan Caching yang Lebih Cerdas

Komponen peta yang menampilkan penanda lokasi sudah umum di aplikasi seluler saat ini. Misalnya, aplikasi Airbnb secara mencolok menampilkan penanda tersebut, yang diambil dari layanan web, untuk mewakili properti yang tersedia di peta.

Untuk memastikan bahwa volume data yang diambil tidak menjadi tidak terkendali seiring bertambahnya jumlah penanda, server mengelompokkan penanda tersebut bersama-sama sebelum mengirimkannya ke klien. Kluster peta adalah penanda khusus yang posisinya sama dengan posisi rata-rata penanda yang dimasukkannya. Itu diberi label dengan jumlah penanda yang diwakilinya.

Namun, melayani cluster dapat membuat kemacetan kinerja karena layanan web harus mengambil setiap penanda tunggal dalam wilayah geografis tertentu dari database. Untungnya, masalah ini dapat diselesaikan dengan strategi caching. Untuk lebih memahami cara mendesain dan memelihara cache, mari lihat contoh titik akhir API peta yang saya buat untuk aplikasi Playsports.

Masalah Penskalaan dan Solusi Naif

Di peta Playsports, setiap penanda mewakili fasilitas olahraga. Titik akhir API peta perlu mengembalikan daftar penanda dan kluster penanda, dengan tingkat zoom dan kotak pembatas.

Jika jumlah penanda cukup kecil, kita dapat memuat semua penanda di kotak pembatas dari database, mengelompokkan seperlunya, dan mengembalikan penanda dan kelompok yang dihasilkan ke klien.

Pada awalnya, jumlah maksimum penanda di semua kotak pembatas yang dapat dijangkau di Playsports adalah ~400, menghasilkan kecepatan titik akhir ~0,5 detik. Menerapkan solusi naif sudah cukup untuk kasus penggunaan ini.

Ketika jumlah penanda bertambah, bagaimanapun, inefisiensi mekanisme menjadi jelas. Setelah kami menambahkan ~10.000 penanda fasilitas olahraga baru, kecepatan titik akhir melambat menjadi ~4,3 detik di bawah beberapa tingkat zoom. Tingkat ini jauh di bawah durasi satu detik yang umumnya dianggap sebagai penundaan maksimum yang dapat diterima untuk tindakan pengguna di aplikasi seluler.

Untuk lebih memahami inefisiensi solusi naif, mari kita analisis dalam konteks kueri marker:

1. Dari database, ambil semua penanda di kotak pembatas . Untuk sebagian besar aplikasi, langkah ini perlu menyertakan pengambilan detail penanda di luar pemosisian garis lintang/garis bujur. Misalnya, penanda Airbnb menyertakan harga, apakah pengguna telah melihat properti tersebut, dan apakah mereka telah menandainya sebagai favorit.
2. Pada penanda yang diambil, jalankan algoritme pengelompokan peta yang menggabungkan tingkat zoom.
3. Kembalikan cluster dan penanda (rinci) ke klien.

Saat jumlah penanda meningkat, kinerja menurun di Langkah 1 dan 2:

• Ketika kotak pembatas cukup besar, dan ketika lebih dari 10.000 penanda memerlukan pencarian detail melalui GABUNG, kueri database melambat secara dramatis (1 hingga 2 detik).
• Mengumpankan 10.000 item ke algoritme pengelompokan peta membutuhkan waktu ~250 milidetik lagi.

Dengan asumsi ukuran jendela konstan, ketika kotak pembatas relatif besar, tingkat zoom biasanya rendah (yaitu, diperbesar jauh). Di bawah tingkat zoom rendah, hasil cenderung mendukung cluster untuk menghindari kepadatan visual. Dengan demikian, potensi terbesar untuk pengoptimalan terletak pada langkah pertama solusi, di mana ribuan penanda individu dimuat. Kami tidak membutuhkan sebagian besar penanda ini dalam hasil. Kami hanya membutuhkan masing-masing dari mereka untuk dihitung ke dalam sebuah cluster.

Merancang Solusi yang Dioptimalkan

Solusi naif membutuhkan waktu yang jauh lebih lama untuk menyelesaikan kueri kasus terburuk: kotak pembatas maksimum di wilayah padat penanda. Sebaliknya, solusi yang dioptimalkan hanya membutuhkan waktu 73 mdtk, yang menunjukkan percepatan ~58x. Dari level tinggi, terlihat seperti ini:

1. Strategi Caching. Ambil penanda dan kluster dalam kotak pembatas dari cache khusus tingkat zoom.
2. Detail Penanda Tambahan (Opsional). Tingkatkan penanda dengan muatan yang diambil dari database.
3. Mengembalikan Hasil. Kembalikan penanda dan kluster ke klien.

Kompleksitas utama terletak pada arsitektur cache (yaitu, langkah pertama).

Langkah 1: Strategi Caching

Langkah utama ini terdiri dari enam komponen:

Teknologi

Redis adalah database dalam memori yang cepat yang biasanya digunakan sebagai cache. Pengindeksan geospasial bawaannya menggunakan algoritme Geohash untuk penyimpanan dan pengambilan titik lintang-bujur yang efisien, yang persis seperti yang kita butuhkan untuk penanda kita.

Cache untuk Setiap Level Zoom

Tingkat pengelompokan peta (apakah penanda tunggal atau kelompok dikembalikan) ditentukan oleh tingkat zoom yang diteruskan ke titik akhir.

• Untuk tingkat zoom tinggi (yaitu, diperbesar dekat), hasilnya akan mendukung masing-masing penanda, kecuali di wilayah padat penanda.
• Untuk tingkat zoom rendah (yaitu, diperkecil jauh), hasilnya akan mendukung kelompok, kecuali di wilayah yang jarang penanda.

Google Maps mendukung tingkat zoom dari nol hingga maksimum 20, tergantung pada areanya. (Rentang yang didukung oleh layanan peta lainnya serupa. Misalnya, Mapbox menggunakan level zoom dari nol hingga maksimum 23.) Karena level zoom ini juga merupakan nilai integer, kita dapat membuat cache terpisah untuk setiap level zoom.

Untuk mendukung semua level zoom di Google Maps—kecuali level nol, yang terlalu jauh zoom out—kami akan membuat 20 cache berbeda. Setiap cache akan menyimpan semua penanda dan cluster untuk seluruh peta, seperti cluster untuk tingkat zoom yang diwakilinya.

Tipe Data Cache

Setiap cache akan menyimpan cluster dan penanda individu. Untuk kedua jenis entri, kita perlu mengisi beberapa bidang:

Namun, Redis memungkinkan pengguna untuk menyimpan hanya lokasi, ditambah satu string, sebagai nilai dalam set geospasial. Untuk mengatasi batasan ini, kami membuat serial bidang di atas dalam string JSON. Kami kemudian menggunakan string ini sebagai nilai di Redis. Ukuran maksimum kunci dan nilai di Redis adalah 512 MB, yang lebih dari cukup untuk kasus penggunaan ini.

Mengisi Cache

Untuk mengisi cache, kami mengambil semua penanda dari database. Untuk setiap tingkat zoom, kami menjalankan algoritme pengelompokan peta. Kami menggunakan GEOADD Redis untuk memasukkan penanda dan cluster yang dihasilkan ke dalam cache tingkat zoom yang sesuai, dan meneruskan garis lintang dan garis bujur, ditambah string JSON yang dijelaskan sebelumnya.

Menjalankan algoritme pengelompokan peta di seluruh peta pada tahap ini (bukan pada kotak pembatas dari pengguna, sesuai permintaan) mungkin secara teoritis menghasilkan beberapa perbedaan tepi dalam penempatan klaster, tetapi pengalaman pengguna secara keseluruhan akan tetap sama.

Menanyakan Cache

Untuk permintaan yang masuk, kami meneruskan kotak pembatas yang diberikan ke perintah Redis GEOSEARCH , yang menanyakan cache tingkat zoom yang diberikan untuk mengambil kandidat penanda dan cluster di area tersebut.

Merancang Rencana Penyegaran Cache

Penyegaran cache 20 tingkat mahal, jadi yang terbaik adalah menyegarkan sesering mungkin sesuai kebutuhan proyek Anda. Misalnya, penambahan atau penghapusan fasilitas olahraga di Playsports hanya menandai cache sebagai basi; tugas cron setiap jam kemudian menyegarkan cache, jika diperlukan. Lebih lanjut tentang ini di bagian Cache Staleness.

Langkah 2: Detail Penanda Tambahan (Opsional)

Pada titik ini, sebagian besar aplikasi perlu mengambil detail berdasarkan ID penanda individual. Kami dapat menjadikan detail ini sebagai bagian dari nilai JSON yang dirangkai dalam cache, tetapi di banyak aplikasi, detail penanda bersifat khusus untuk pengguna. Karena ada satu cache bersama untuk semua pengguna, kolom tambahan ini tidak dapat disimpan di sana.

Solusi kami yang dioptimalkan mengambil ID masing-masing penanda dari hasil cache dan mengambil detailnya dari database. Sekarang kita hanya mencari penanda individu yang tersisa setelah pengelompokan. Jumlahnya tidak akan terlalu banyak saat peta diperkecil (karena sebagian besar kita akan memiliki cluster) atau saat diperbesar (karena areanya akan kecil).

Sebaliknya, solusi naif mencari semua penanda di kotak pembatas (dan detailnya) sebelum pengelompokan. Jadi, langkah ini—opsional, tetapi untuk banyak aplikasi, sangat penting—kini berjalan lebih cepat.

Langkah 3: Mengembalikan Hasil

Dengan kluster yang dibangun dan penanda individu yang ditingkatkan, kami sekarang dapat mengirimkannya ke klien. Selain beberapa kasus tepi yang tidak penting, data yang dihasilkan hampir identik dengan solusi naif—tetapi kami dapat mengirimkannya lebih cepat.

Pertimbangan Lebih Lanjut

Sekarang mari kita lihat dua faktor tambahan:

Kebutuhan Sumber Daya

Mari kita asumsikan bahwa peta aplikasi berisi total N penanda. Karena ada hingga 20 tingkat zoom, kita perlu menyimpan, paling banyak, 20N item cache. Namun, dalam praktiknya, jumlah item cache yang sebenarnya seringkali jauh lebih rendah karena pengelompokan, terutama di tingkat zoom yang lebih rendah. Faktanya, jumlah total item cache yang didistribusikan di antara semua cache Playsports hanya ~2N.

Selanjutnya, jika kita berasumsi bahwa panjang nilai cache (JSON string) adalah ~250 karakter (asumsi yang masuk akal, setidaknya untuk Playsports) dan ukuran string adalah 1 byte per karakter, maka jumlah penyimpanan cache yang diperlukan untuk Nilai JSON akan menjadi sekitar 2 * N * 250 byte.

Untuk gambar ini kami menambahkan struktur data internal Redis untuk set yang diurutkan yang digunakan oleh GEOADD . Redis menggunakan memori 85 MB untuk 1 juta pasangan nilai kunci kecil, jadi kita dapat mengasumsikan akun internal Redis kurang dari 100 byte per item cache. Itu berarti kita dapat menggunakan instance Redis 1 GB-RAM untuk mendukung sebanyak 1,4 juta marker. Bahkan dalam skenario yang tidak mungkin dari penanda yang tersebar merata di seluruh peta, menghasilkan jumlah item cache mendekati 20N, N masih bisa naik hingga ~140.000. Karena instans Redis dapat menangani lebih dari 4 miliar kunci (2 ³² , tepatnya), ini bukan faktor pembatas.

Kedaluwarsa Cache

Tergantung pada kasus penggunaan, mungkin tidak cukup untuk menyegarkan cache hanya secara berkala. Dalam kasus seperti itu, kita dapat menggunakan antrian tugas dengan kecepatan terbatas. Ini akan mengurangi cache staleness, sementara masih membatasi jumlah cache refresh, dan dengan demikian beban pada sistem.

Setelah setiap pembaruan basis data, kami akan mengantrekan pekerjaan penyegaran cache. Antrian ini akan membatasi jumlah tugas hingga M per jam. Kompromi ini memungkinkan pembaruan lebih cepat dari per jam sambil mempertahankan beban yang relatif rendah pada sistem (tergantung pada M).

Strategi Caching Lebih Besar daripada Algoritma Pengelompokan Peta

Solusi yang dioptimalkan untuk Playsports—lebih dari 50 kali lebih cepat daripada solusi naif—telah bekerja dengan baik. Ini harus terus bekerja dengan baik, hingga mencapai 1,4 juta penanda atau lebih dari 100 kali lipat dari data yang ada.

Untuk sebagian besar permintaan layanan web berbasis peta, beberapa bentuk pra-perhitungan diperlukan untuk memungkinkan skalabilitas. Jenis teknologi yang akan digunakan, serta desain khusus, akan tergantung pada kebutuhan bisnis. Kebutuhan cache staleness, augmentasi marker, dan jumlah marker merupakan karakteristik penting yang harus diperhitungkan saat merancang solusi.

Bacaan Lebih Lanjut di Blog Teknik Toptal:

• Survei Alat Pemetaan Online Terbaik untuk Pengembang Web: Peta Jalan Menuju Peta Jalan
• Petualangan dalam Pemrograman dan Pengembangan GPS: Tutorial Geospasial