Peringkat yang Cepat dan Andal di Datastore

Peringkat: Masalah sederhana, namun sangat sulit

Tomoaki Suzuki (Gambar 1), lead engineer App Engine di Applibot, telah mencoba memecahkan masalah yang sangat umum, tetapi sangat sulit yang dihadapi oleh setiap layanan game besar: Peringkat.

Gambar 1: Tomoaki Suzuki, lead engineer App Engine di Applibot, Inc.

Applibot adalah salah satu penyedia aplikasi sosial utama di Jepang. Keunikan perusahaan ini adalah pengetahuan dan pengalaman mereka yang luas dalam membangun layanan game sosial yang sangat skalabel di Google App Engine, yang ditawarkan Platform as a Service (PaaS) dari Google. Dengan memanfaatkan kekuatan platform, Applibot telah cukup sukses dalam menangkap peluang bisnis di pasar game sosial, tidak hanya di Jepang, tetapi juga di Amerika Serikat. Applibot tentu saja bisa membuktikan keberhasilannya. Legend of the Cryptids (Gambar 2), salah satu judul terbesar mereka, menduduki posisi #1 di kategori game Apple AppStore Amerika Utara pada Oktober 2012. Seri Legenda mencatatkan 4,7 juta download. Game lainnya, Gang Road, menduduki peringkat 1 di peringkat total penjualan AppStore Jepang pada Desember 2012.

Gambar 2: Legend of the Criptids, game peringkat #1 di Apple AppStore pada Oktober 2012.

Judul-judul game ini mampu menskalakan dengan lancar dan menangani traffic yang berkembang sangat pesat. Applibot tidak perlu bersusah payah membangun cluster server virtual yang kompleks atau database dengan sharding. Mereka memanfaatkan kecanggihan App Engine dan mencapai skalabilitas serta ketersediaan secara efisien.

Namun, pembaruan peringkat pemain bukanlah masalah yang mudah untuk dipecahkan, bukan bagi Tomoaki, dan mungkin juga tidak bagi developer mana pun, terutama dalam skala ini. Persyaratannya sederhana:

Game Anda memiliki ratusan ribu (atau lebih) pemain.
Setiap kali pemain melawan musuh (atau melakukan aktivitas lain), skor mereka akan berubah.
Anda ingin menampilkan peringkat terbaru untuk pemain di halaman portal web.

Bagaimana cara menghitung peringkat?

Mendapatkan peringkat itu mudah, jika tidak diharapkan terukur dan cepat juga. Misalnya, Anda dapat menjalankan kueri berikut:

SELECT count(key) FROM Players WHERE Score > YourScore

Kueri ini menghitung semua pemain yang memiliki skor lebih tinggi dari milik Anda (Gambar 4). Namun, apakah Anda ingin menjalankan kueri ini untuk setiap permintaan dari halaman portal? Berapa lama waktu yang dibutuhkan jika kamu memiliki satu juta pemain?

Tomoaki awalnya menerapkan pendekatan ini, tetapi perlu waktu beberapa detik untuk mendapatkan setiap respons. Proses ini terlalu lambat, terlalu mahal, dan secara bertahap berperforma lebih buruk seiring peningkatan skala.

Gambar 4: Cara termudah: Pindai semua pemain.

Selanjutnya, Tomoaki mencoba mempertahankan data peringkat di Memcache. Ini cepat, tetapi tidak dapat diandalkan. Entri Memcache dapat dikeluarkan kapan saja, dan terkadang layanan Memcache itu sendiri tidak tersedia. Dengan layanan peringkat yang hanya bergantung pada nilai kunci dalam memori, konsistensi dan ketersediaan sulit dipertahankan.

Sebagai solusi sementara, Tomoaki memutuskan untuk menurunkan tingkat layanan. Alih-alih menghitung peringkat untuk setiap permintaan, dia menyiapkan tugas terjadwal yang memindai dan memperbarui peringkat setiap pemain satu jam sekali. Dengan cara ini, permintaan dari halaman portal bisa langsung mendapatkan peringkat pemain, tetapi mungkin baru berlangsung hingga satu jam.

Pada akhirnya, Tomoaki mencari implementasi peringkat yang persisten, transaksional, cepat, dan skalabel yang dapat menerima 300 permintaan pembaruan skor per detik dan mendapatkan peringkat untuk setiap pemain dalam ratusan milidetik. Untuk menemukan solusi, Tomoaki menghubungi Kaz Sato, Arsitek Solusi (SA) serta Manajer Akun Teknis (TAM) di tim Google Cloud Platform dan ditugaskan ke Applibot berdasarkan kontrak dukungan tingkat premium.

Cara Cepat untuk Menyelesaikan Masalah

Banyak pelanggan atau partner besar Google Cloud Platform, seperti Applibot, berlangganan ke kontrak dukungan tingkat premium. Dengan kontrak dukungan tersebut, selain dukungan 24/7 dari tim Dukungan Pelanggan Cloud dan dukungan bisnis dari tim Penjualan Cloud, Google menetapkan Manajer Akun Teknis (TAM) untuk setiap pelanggan.

TAM mewakili pelanggan kepada Google Engineering, yang membangun infrastruktur cloud sebenarnya. TAM memahami sistem dan arsitektur pelanggan secara mendetail, dan setelah mereka mengajukan kasus kritis, mereka menggunakan pengetahuan dan jaringan mereka sebagai perwakilan Google Engineering di perusahaan untuk menyelesaikan masalah tersebut. TAM dapat mengeskalasikan masalah kepada Arsitek Solusi dalam tim atau ke Software Engineer di tim Cloud Platform. Dukungan tingkat premium merupakan jalan cepat untuk menemukan solusi dengan Google Cloud Platform.

Kaz, TAM yang mendukung Applibot, tahu bahwa peringkat merupakan masalah yang klasik tapi sulit dipecahkan untuk setiap layanan terdistribusi yang skalabel. Ia mulai meninjau implementasi yang diketahui untuk penentuan peringkat di Google Cloud Datastore dan datastore NoSQL lainnya untuk menemukan solusi yang memenuhi persyaratan Applibot.

Mencari Algoritma O(log n)

Solusi kueri sederhana mengharuskan pemindaian semua pemain yang memiliki skor lebih tinggi untuk menghitung peringkat satu pemain. Kompleksitas waktu algoritma ini adalah O(n); yaitu, waktu yang diperlukan untuk eksekusi kueri meningkat secara proporsional dengan jumlah pemain. Dalam praktiknya, ini berarti bahwa algoritma tidak dapat diskalakan. Sebagai gantinya, kita memerlukan algoritma O(log n) atau yang lebih cepat, di mana waktu akan bertambah secara logaritmis seiring dengan bertambahnya jumlah pemain.

Jika pernah mengikuti kursus ilmu komputer, Anda mungkin ingat bahwa algoritma pohon, seperti pohon biner, pohon merah-hitam, atau B-Trees, dapat dilakukan pada kompleksitas waktu O(log n) untuk menemukan elemen. Algoritma pohon juga dapat digunakan untuk menghitung nilai agregat dari berbagai elemen, seperti jumlah, maks/mnt, dan rata-rata dengan menyimpan nilai yang telah diagregasi pada setiap node cabang. Dengan menggunakan teknik ini, Anda dapat menerapkan algoritma peringkat dengan performa O(log n).

Kaz menemukan implementasi open source dari algoritma peringkat berbasis hierarki untuk Datastore, yang ditulis oleh engineer Google: Google Code Jam Ranking Library.

Library berbasis Python ini mengekspos dua metode:

SetScore untuk menetapkan skor pemain.
FindRank untuk mendapatkan peringkat dari skor tertentu.

Saat pasangan skor pemain dibuat dan diperbarui dengan metode SetScore, library peringkat Code Jam akan membuat hierarki N-ary¹. Misalnya, mari kita pertimbangkan pohon tersier yang dapat menghitung jumlah pemain dengan skor dalam rentang 0 hingga 80 (Gambar 5). Library menyimpan node root, yang menyimpan tiga angka, sebagai satu entity. Setiap nomor sesuai dengan jumlah pemain dengan skor di sub-rentang 0 - 26, 27 - 53 dan 54 - 80. Simpul akar memiliki simpul anak untuk setiap rentang, yang pada gilirannya menyimpan tiga nilai untuk pemain di sub-rentang sub-rentang. Hierarki membutuhkan empat tingkat untuk menyimpan jumlah pemain untuk 81 nilai skor yang berbeda.

Gambar 5: Mendapatkan peringkat skor di pohon tersier.

Untuk menentukan peringkat pemain yang memiliki skor 30, library hanya perlu membaca empat entitas—node yang dilingkari oleh garis putus-putus pada diagram—untuk menjumlahkan jumlah pemain yang memiliki skor lebih dari 30. Dengan 22 pemain di sebelah "kanan" dalam empat entitas, peringkat pemain ada di urutan ke-23.

Demikian juga, panggilan ke SetScore hanya perlu memperbarui empat entitas. Meskipun Anda memiliki skor yang berbeda dalam jumlah besar, akses Datastore hanya akan meningkat di O(log n) dan tidak terpengaruh oleh jumlah pemain. Dalam praktiknya, library peringkat Code Jam menggunakan 100 (bukan 3) sebagai jumlah nilai default per node, sehingga hanya dua (atau tiga, jika rentang skor lebih besar dari 100.000) entitas yang perlu diakses.

Kaz menggunakan alat pengujian beban populer Apache JMeter untuk melakukan uji beban pada library peringkat Code Jam dan mengonfirmasi bahwa library merespons dengan cepat. SetScore dan FindRank dapat menyelesaikan tugas mereka dalam ratusan milidetik menggunakan algoritma pohon N-ary yang bekerja pada kompleksitas waktu O(log n).

Skalabilitas Batas Update Serentak

Namun, selama pengujian beban, Kaz menemukan batasan kritis pada library peringkat Code Jam. Skalabilitasnya dalam hal throughput update cukup rendah. Saat ia meningkatkan beban menjadi tiga update per detik, library mulai menampilkan error percobaan ulang transaksi. Jelas bahwa library tersebut tidak dapat memenuhi persyaratan Applibot untuk 300 update per detik. Server tersebut hanya dapat menangani sekitar 1% dari throughput tersebut.

Mengapa demikian? Alasannya adalah biaya untuk mempertahankan konsistensi pohon. Di Datastore, Anda harus menggunakan grup entity untuk memastikan konsistensi yang kuat saat mengupdate beberapa entity dalam transaksi—lihat "Menyeimbangkan Konsistensi yang Kuat dan Berakhir dengan Google Cloud Datastore". Library peringkat Code Jam menggunakan satu grup entitas untuk menampung seluruh hierarki untuk memastikan konsistensi jumlah dalam elemen hierarki.

Namun, grup entity di Datastore memiliki batasan performa. Datastore hanya mendukung sekitar satu transaksi per detik pada grup entity. Selain itu, jika grup entitas yang sama diubah dalam transaksi serentak, grup tersebut kemungkinan akan gagal dan harus dicoba lagi. Library peringkat Code Jam sangat konsisten, transaksional, dan cukup cepat, tetapi tidak mendukung update serentak dalam jumlah besar.

Solusi Tim Datastore: Agregasi Tugas

Kaz ingat bahwa software engineer di tim Datastore telah menyebutkan teknik untuk mendapatkan throughput yang jauh lebih tinggi daripada satu update per detik pada entity group. Hal ini dapat dilakukan dengan menggabungkan sekumpulan update menjadi satu transaksi, bukan mengeksekusi setiap update sebagai transaksi terpisah. Namun, karena transaksi menyertakan banyak pembaruan, setiap transaksi memerlukan waktu lebih lama, sehingga meningkatkan kemungkinan konflik dari transaksi serentak.

Sebagai respons atas permintaan Kaz, tim Datastore mulai membahas masalah ini dan menyarankan kami untuk mempertimbangkan penggunaan Job Aggregation, yang merupakan salah satu pola desain yang digunakan di Megastore.

Megastore adalah lapisan penyimpanan dasar Datastore, serta mengelola konsistensi dan transaksional grup entity. Batas satu pembaruan per detik berasal dari lapisan tersebut. Karena Megastore digunakan secara ekstensif oleh berbagai layanan Google, para engineer telah mengumpulkan dan membagikan praktik terbaik serta pola desain di dalam perusahaan untuk membangun sistem yang skalabel dan konsisten dengan datastore NoSQL ini.

Ide dasar Agregasi Tugas adalah menggunakan satu thread untuk memproses sekumpulan pembaruan. Karena hanya ada satu thread dan hanya satu transaksi yang terbuka di grup entitas, tidak ada kegagalan transaksi akibat update serentak. Anda dapat menemukan ide serupa di produk penyimpanan lainnya seperti VoltDb dan Redis.

Namun, ada kelemahan dari pola Agregasi Tugas: pola ini hanya menggunakan satu thread untuk menggabungkan semua update, dan menerapkan batas kecepatan pengiriman update ke Datastore. Oleh karena itu, penting untuk menentukan apakah Agregasi Pekerjaan dapat memenuhi persyaratan throughput Applibot sebesar 300 pembaruan per detik.

Agregasi Tugas berdasarkan Pull Queue

Berdasarkan saran dari tim Datastore, Kaz menulis kode Proof of Concept (PoC) yang menggabungkan pola Job Aggregation dengan library peringkat Code Jam. PoC memiliki komponen berikut:

Frontend: Menerima permintaan SetScore dari pengguna dan menambahkannya sebagai tugas ke pull queue.
Antrean Tarik: Menerima dan menahan permintaan update SetScore dari frontend.
Backend: Menjalankan loop tanpa batas dengan satu thread yang menarik permintaan update dari antrean dan menjalankannya dengan library peringkat Code Jam.

PoC membuat pull queue, yang merupakan semacam Task Queue di App Engine yang memungkinkan developer menerapkan satu atau beberapa pekerja yang memakai tugas yang ditambahkan ke antrean. Backend instance memiliki satu thread dalam loop tak terbatas yang terus menarik tugas sebanyak mungkin (hingga 1.000) dari antrean. Thread meneruskan setiap permintaan update ke library peringkat Code Jam, yang akan mengeksekusinya sebagai batch dalam satu transaksi. Transaksi mungkin terbuka selama satu detik atau lebih, tetapi karena ada satu thread yang mendorong library dan Datastore, maka tidak ada pertentangan dan masalah modifikasi serentak.

Instance backend didefinisikan sebagai modul, fitur App Engine yang memungkinkan developer menentukan Instance Aplikasi dengan berbagai karakteristik. Dalam PoC ini, instance backend didefinisikan sebagai instance penskalaan manual. Hanya satu instance tersebut yang berjalan pada satu waktu tertentu.

Kaz menguji PoC dengan uji beban menggunakan JMeter. Ia mengonfirmasi bahwa PoC dapat memproses 200 permintaan SetScore per detik, dengan batch 500 hingga 600 update per transaksi. Agregasi Tugas berfungsi.

Sharding Antrean untuk Performa Stabil

Tapi Kaz tak lama kemudian menemukan masalah lain. Ketika ia melanjutkan pengujian selama beberapa menit, ia melihat throughput pull queue berfluktuasi dari waktu ke waktu (Gambar 6). Khususnya ketika ia terus menambahkan permintaan ke antrean dengan 200 tugas per detik selama beberapa menit, antrean tiba-tiba berhenti meneruskan tugas ke backend, dan latensi untuk setiap tugas meningkat secara dramatis.

Gambar 6: Fluktuasi performa pull queue.

Kaz berkonsultasi dengan tim Task Queue untuk mempelajari mengapa hal ini terjadi. Menurut tim Task Queue, ini adalah perilaku yang diketahui untuk implementasi pull queue saat ini yang bergantung pada Bigtable sebagai lapisan persistensinya. Ketika ukuran tablet Bigtable terlalu besar, tablet akan dibagi menjadi beberapa tablet. Saat tablet dibagi, tugas tidak dikirimkan, dan hal ini menimbulkan fluktuasi performa saat antrean menerima tugas dengan kecepatan tinggi. Tim Antrean Tugas sedang berupaya meningkatkan karakteristik performa ini.

Michael Tang, seorang Arsitek Solusi, merekomendasikan solusi menggunakan Sharding Antrean. Alih-alih hanya menggunakan satu antrean, ia menyarankan untuk mendistribusikan beban ke beberapa antrean. Setiap antrean dapat disimpan di server tablet Bigtable berbeda untuk meminimalkan efek pemisahan tablet dan mempertahankan kecepatan pemrosesan tugas yang tinggi. Saat satu antrean memproses pemisahan, antrean lain terus berfungsi, dan sharding mengurangi beban pada setiap antrean, sehingga pemisahan tablet lebih jarang terjadi.

Loop instance backend yang disempurnakan akan mengeksekusi algoritma berikut:

Menyewakan tugas SetScore dari 10 antrean.
Panggil metode SetScores dengan tugas.
Hapus tugas yang disewakan dari antrean.

Pada langkah 1, setiap antrean menyediakan hingga 1.000 tugas, setiap tugas menyimpan nama pemain dan skor. Setelah menggabungkan semua pasangan skor pemain ke dalam kamus, langkah 2 akan meneruskan batch update ke metode SetScores dari library peringkat Code Jam, yang membuka transaksi untuk menyimpannya di Datastore. Jika tidak ada error saat mengeksekusi metode, langkah 3 akan menghapus tugas yang di-lease dari antrean.

Jika terjadi error atau penonaktifan loop atau instance backend yang tidak terduga, tugas update tetap berada dalam task queue, sehingga dapat diproses saat instance dimulai ulang. Dalam sistem produksi, Anda mungkin memiliki backend lain yang bertindak sebagai watchdog dalam mode standby, yang siap mengambil alih jika instance pertama gagal.

Solusi yang Diusulkan: Berjalan pada 300 Update per Detik Berkelanjutan²

Gambar 7 menunjukkan hasil pengujian beban dari implementasi PoC akhir dengan Queue Sharding. Hal ini secara efektif meminimalkan fluktuasi performa dalam antrean dan dapat mempertahankan 300 update per detik selama beberapa jam. Dalam pemuatan biasa, setiap update diterapkan ke Datastore dalam beberapa detik setelah permintaan diterima.

Solusi ini memenuhi semua persyaratan awal Applibot:

Skalabel untuk menangani puluhan ribu pemain.
Persisten dan konsisten karena semua update dijalankan dalam transaksi Datastore.
Cukup cepat untuk menangani 300 update per detik.

Dengan hasil pengujian beban dan kode PoC, Kaz memberikan solusi kepada Tomoaki dan engineer Applibot lainnya. Tomoaki berencana mengintegrasikan solusi ini ke dalam sistem produksi mereka, dan diharapkan dapat mengurangi latensi pembaruan info peringkat dari satu jam menjadi beberapa detik, dan berharap dapat meningkatkan pengalaman pengguna secara signifikan.

Ringkasan Hierarki Peringkat dengan Agregasi Tugas

Solusi yang diusulkan memiliki beberapa kelebihan dan satu kekurangan:

Kelebihan:

Cepat: Panggilan FindRank membutuhkan waktu beberapa ratus milidetik atau kurang.
Cepat: SetScore hanya mengirimkan tugas, yang diproses oleh backend dalam beberapa detik.
Sangat konsisten dan terus ada di Datastore.
Peringkat akurat.
Skalabel untuk berapa pun jumlah pemain.

Kekurangan:

Throughput memiliki batasan (sekitar 300 update/dtk dengan penerapan saat ini).

Karena menggunakan pola Agregasi Tugas, solusi ini bergantung pada satu thread untuk menggabungkan semua update. Pekerjaan atau kompleksitas tambahan diperlukan untuk mencapai throughput yang lebih tinggi dari 300 update/dtk dengan daya CPU saat ini dari instance App Engine dan performa Datastore.

Solusi yang Lebih Skalabel dengan Sharded Tree

Jika memerlukan kecepatan update yang lebih besar, Anda mungkin perlu melakukan sharding pada hierarki peringkat. Anda akan membuat beberapa implementasi dari sistem di atas—serangkaian antrean yang masing-masing mendorong modul backend yang memperbarui hierarki peringkatnya sendiri.

Secara umum, mengoordinasikan pohon tidak diperlukan atau diharapkan. Dalam kasus yang paling sederhana, setiap update SetScore dikirim secara acak ke antrean. Dengan tiga pohon tersebut, masing-masing dengan grup entity Datastore dan server backend-nya sendiri, throughput update yang diharapkan akan tiga kali lebih besar. Konsekuensinya, FindRank harus melakukan kueri pada setiap pohon peringkat untuk mendapatkan peringkat skor, lalu menjumlahkan peringkat dari setiap pohon untuk menemukan peringkat sebenarnya, yang akan memakan waktu sedikit lebih lama. Waktu kueri untuk FindRank dapat dikurangi secara substansial dengan mempertahankan entity di Memcache.

Hal ini serupa dengan pendekatan terkenal dalam penggunaan penghitung shard: setiap penghitung ditambahkan secara independen, dan jumlah total hanya dihitung jika diperlukan oleh klien.

Misalnya, dengan tiga pohon, FindRank(865) mungkin menemukan tiga peringkat 124, 183, dan 156, yang menunjukkan bahwa setiap pohon memiliki jumlah skor masing-masing lebih tinggi dari 865. Maka jumlah skor yang dihitung lebih besar dari 865 adalah 124 + 183 + 156 = 463.

Pendekatan ini tidak dapat digunakan untuk semua jenis algoritma terdistribusi, tetapi karena peringkat pada dasarnya merupakan masalah penghitungan komutatif, pendekatan ini seharusnya dapat berfungsi untuk masalah peringkat volume yang besar.

Solusi yang Lebih Skalabel dengan Pendekatan Perkiraan

Jika aplikasi Anda membutuhkan skalabilitas lebih dari sekadar akurasi peringkat, dan dapat menoleransi tingkat ketidakakuratan atau perkiraan tertentu, Anda dapat memilih pendekatan stokastik seperti:

Bucket dengan Kueri Global
Metode Penghitungan lossy
Streaming Hemat

Pendekatan perkiraan ini merupakan varian dari satu ide: Bagaimana cara mengompresi penyimpanan untuk informasi peringkat dengan memungkinkan penurunan tertentu pada akurasi peringkat?

Bucket dengan Global Query adalah solusi alternatif yang diusulkan oleh tim Datastore dan Alex Amies, seorang TAM. Alex menerapkan PoC berdasarkan ide tim Datastore dan melakukan analisis performa yang ekstensif. Ia membuktikan bahwa Buckets dengan Global Query adalah solusi peringkat skalabel dengan penurunan minimal pada akurasi peringkat dan bisa cocok untuk aplikasi yang memerlukan throughput lebih tinggi daripada library peringkat Code Jam. Lihat Lampiran untuk deskripsi mendetail dan hasil pengujian.

Lossy Counting Method dan Frugal Streaming disebut algoritma online dan algoritma streaming tempat Anda dapat menggunakan penyimpanan dalam memori yang sangat kecil untuk menghitung perkiraan stokastik peringkat teratas dari aliran pasangan skor pemain. Algoritma ini akan cocok untuk aplikasi yang memerlukan latensi sangat rendah dan bandwidth super tinggi, seperti ribuan update per detik, dengan akurasi dan cakupan hasil peringkat yang lebih terbatas. Misalnya, jika Anda ingin memiliki dasbor waktu nyata yang menampilkan 100 kata kunci teratas yang diketik ke dalam aliran jaringan sosial, algoritma ini akan membantu.

Kesimpulan

Peringkat adalah masalah klasik, tetapi sulit dipecahkan jika Anda memerlukan algoritma yang skalabel, konsisten, dan cepat. Dalam artikel ini, kami menjelaskan bagaimana TAM Google bekerja sama dengan pelanggan dan tim Google Engineering untuk mengatasi tantangan ini dan memberikan solusi yang dapat mengurangi latensi pembaruan peringkat dari satu jam menjadi beberapa detik. Pola desain yang ditemukan dalam proses tersebut—Agregasi Tugas dan Sharding Antrean—juga dapat diterapkan ke masalah umum dalam desain sistem berbasis Datastore lainnya yang memerlukan ratusan update per detik dengan konsistensi kuat.

Notes

Library peringkat Code Jam mengambil parameter yang disebut "branching factor" yang menentukan berapa banyak skor yang akan dimiliki setiap entitas. Secara default, library menggunakan 100 sebagai parameter. Dalam hal ini, skor mulai dari 0 hingga 9999 akan disimpan pada 100 entitas sebagai turunan dari node root. Jika perlu menangani rentang skor yang lebih luas, Anda dapat mengubah faktor percabangan ke nilai yang lebih tinggi untuk mengoptimalkan jumlah akses entity.
Setiap angka performa yang dijelaskan dalam artikel ini adalah nilai sampel sebagai referensi dan tidak menjamin performa mutlak apa pun dari App Engine, Datastore, atau layanan lainnya.

Lampiran: Bucket dengan Solusi Kueri Global

Seperti yang disebutkan di bagian Cara Mendapatkan Peringkat, membuat kueri database untuk setiap permintaan peringkat terasa mahal. Pendekatan alternatif ini secara berkala memperoleh jumlah semua skor, menghitung peringkat skor yang dipilih, dan menyediakan titik data tersebut untuk digunakan dalam peringkat komputasi bagi pemain tertentu. Total rentang skor dipartisi menjadi ‘bucket’. Setiap bucket ditandai dengan sub-rentang skor dan jumlah pemain dengan skor dalam rentang tersebut. Dari data itu, peringkat setiap skor dapat ditemukan dengan perkiraan yang mendekati. Bucket ini mirip dengan node tingkat atas pada pohon peringkat, tetapi algoritma ini hanya berinterpolasi dalam bucket, bukan menurun ke node yang lebih mendetail.

Pengambilan peringkat oleh pengguna dari frontend dipisahkan dari komputasi peringkat pada bucket di backend untuk meminimalkan waktu pencarian peringkat. Saat peringkat pemain diminta, bucket yang sesuai akan ditemukan berdasarkan skor pemain. Bucket ini mencakup batas peringkat atas dan jumlah pemain dalam bucket. Jenis interpolasi linear dalam bucket digunakan untuk memperkirakan peringkat pemain dalam bucket. Dalam pengujian, kami dapat memperoleh peringkat pemain dalam waktu kurang dari 400 milidetik untuk perjalanan bolak-balik HTTP lengkap. Biaya metode FindRank tidak bergantung pada jumlah pemain dalam populasi.

Menghitung peringkat untuk skor tertentu

Jumlah dan peringkat paling atas (yaitu peringkat tertinggi yang mungkin dalam bucket ini) dicatat untuk setiap bucket. Untuk skor antara batas skor rendah dan tinggi dalam bucket, kita menggunakan interpolasi linier untuk memperkirakan peringkat. Misalnya, jika pemain memiliki skor 60, maka kita melihat bucket [50, 74], menggunakan jumlah (jumlah pemain/skor dalam bucket) (42) dan peringkat teratas (5) untuk menghitung peringkat pemain dengan rumus ini:

    rank = 5  + (74 - 60)*42/(74 - 50) =  30

Menghitung jumlah dan rentang untuk setiap bucket

Di latar belakang, dengan menggunakan cron job atau task queue, jumlah untuk setiap bucket dihitung dan disimpan dengan melakukan iterasi ke semua bucket. Kami menyebutnya sebagai kueri global, karena kueri ini menghitung parameter yang diperlukan untuk memperkirakan peringkat dengan memeriksa skor semua pemain. Contoh kode Python untuk melakukannya dengan skor dalam rentang [low_score, high_score] untuk setiap bucket ditampilkan di bawah ini.

next_upper_rank = 1
for b in buckets:
  count = GetCountInRange(b.low_score, b.high_score)
  b.count = count
  b.upper_rank = next_upper_rank
  b.put()
  next_upper_rank += count

Metode GetCountInRange() menghitung setiap pemain dengan skor dalam rentang yang dicakup oleh bucket. Karena Datastore mempertahankan indeks yang diurutkan pada skor pemain, jumlah ini dapat dihitung secara efisien.

Jika perlu menemukan peringkat pemain tertentu, kita dapat menggunakan kode seperti yang ditampilkan di bawah ini.

b = GetBucketByScore(score)
rank = RankInBucket(b, score)
return rank + b.upper_rank - 1

Metode GetBucketByScore(score) mengambil bucket yang berisi skor yang diberikan. Metode RankInBucket() akan memperkirakan peringkat dalam bucket. Peringkat pemain adalah jumlah peringkat teratas dalam bucket, dan peringkat dalam bucket tertentu yang mengelompokkan skor pemain. Kita perlu mengurangi 1 dari hasil karena peringkat teratas pada bucket teratas adalah 1, dan peringkat pemain teratas dalam bucket tertentu juga akan menjadi 1.

Bucket disimpan ke Datastore dan Memcache. Untuk menghitung peringkat, baca bucket dari Memcache (atau Datastore, jika Memcache tidak ada data). Dalam implementasi algoritme ini, kami menggunakan Library Klien Python NDB yang menggunakan Memcache untuk meng-cache data yang disimpan di Datastore.

Karena bucket (atau metode lain) digunakan untuk mewakili data secara ringkas, peringkat yang dihasilkan tidak pasti. Peringkat dalam bucket diperkirakan dengan interpolasi linear. Metode interpolasi lain yang lebih akurat dapat digunakan untuk mendapatkan perkiraan yang lebih baik dalam bucket, seperti formula regresi.

Biaya

Biaya pencarian peringkat dan pembaruan skor pemain adalah O(1); yaitu, terlepas dari jumlah pemain.

Biaya tugas kueri global adalah O(Players) * frekuensi update cache.

Biaya komputasi data bucket di tugas backend juga terkait dengan jumlah bucket karena kueri jumlah dilakukan untuk setiap bucket. Kueri count dioptimalkan untuk menggunakan kueri khusus kunci, tetapi meskipun demikian, daftar kunci lengkap harus diambil.

Kelebihan

Metode ini sangat cepat untuk memperbarui skor pemain serta mencari peringkat skor. Meskipun hasil didasarkan pada tugas latar belakang, jika skor pemain berubah, peringkat akan segera menunjukkan perubahan ke arah yang sesuai. Hal ini karena interpolasi yang digunakan dalam bucket.

Karena penghitungan peringkat teratas bucket dilakukan di latar belakang dengan tugas terjadwal, skor pemain dapat diperbarui tanpa perlu terus menyinkronkan data bucket. Jadi, throughput pembaruan skor pemain tidak dibatasi oleh pendekatan ini.

Kekurangan

Waktu untuk menghitung semua skor pemain, menghitung peringkat global, dan memperbarui kategori pemain perlu dipertimbangkan. Dalam pengujian kami, dengan populasi sepuluh juta pemain, waktunya 8 menit 34 detik untuk sistem pengujian kami di App Engine. Waktu ini lebih cepat daripada jam yang dibutuhkan untuk menghitung peringkat setiap pemain, tetapi komprominya adalah perkiraan skor dalam setiap kategori. Sebaliknya, algoritme hierarki menghitung 'rentang bucket' (node teratas hierarki) secara bertahap setiap beberapa detik, tetapi memiliki kompleksitas implementasi yang lebih besar dan throughput yang terbatas.

Dalam semua kasus, waktu untuk FindRank juga bergantung pada pengambilan data yang cepat (bucket atau node hierarki) dari Memcache. Jika dikeluarkan dari Memcache, data tersebut harus diambil ulang dari Datastore dan disimpan dalam cache ulang untuk permintaan FindRank selanjutnya.

Akurasi

Keakuratan metode bucket bergantung pada berapa banyak bucket yang ada, peringkat pemain, dan distribusi skor. Gambar 9 menunjukkan hasil dari studi kami mengenai keakuratan perkiraan peringkat dengan jumlah bucket yang berbeda.

Pengujian dilakukan pada populasi 10.000 pemain dengan skor yang terdistribusi secara seragam dalam rentang [0-9999]. Error relatifnya adalah sekitar 1% meskipun hanya untuk 5 bucket.

Akurasi tidak berlaku untuk pemain dengan peringkat tinggi, terutama karena hukum angka besar tidak berlaku saat melihat skor teratas saja. Dalam banyak kasus, sebaiknya gunakan algoritme yang lebih tepat untuk mempertahankan peringkat satu atau dua ribu pemain dengan skor tertinggi. Masalah ini berkurang secara signifikan, karena jumlah pemain yang dilacak lebih sedikit, dan rasio agregat update juga lebih rendah.

Dalam pengujian di atas, penggunaan angka acak yang terdistribusi secara seragam, dengan fungsi distribusi kumulatif yang bersifat linier, mendukung penggunaan interpolasi linier dalam bucket, tetapi interpolasi dalam bucket berfungsi dengan baik untuk distribusi skor yang padat. Gambar 10 menunjukkan perkiraan peringkat dan peringkat aktual untuk distribusi skor yang kira-kira normal.

Gambar 10: Perkiraan peringkat dengan distribusi normal

Dalam eksperimen ini, populasi 100 pemain digunakan untuk menguji akurasi dengan set data yang kecil. Setiap skor dibuat dengan mengambil rata-rata 4 angka acak antara 0 dan 100, yang kira-kira mendekati distribusi skor normal. Perkiraan peringkat dihitung menggunakan metode kueri global dengan interpolasi linier pada 10 bucket. Dapat dilihat bahwa bahkan untuk set data yang sangat kecil dan distribusi yang tidak seragam, hasilnya sangat baik.