Keunggulan Sistem yang Tidak Sempurna: Timeline Lossy di Bluesky

• Saat merancang sistem, pada praktiknya sangat sulit memenuhi secara bersamaan konsistensi sempurna, ketersediaan, latensi rendah, dan throughput tinggi
  • Yang penting adalah menemukan desain yang tepat dengan mencari titik keseimbangan yang sesuai untuk aplikasi
• Dalam desain feed/timeline following Bluesky, mereka menerapkan trade-off dengan mengorbankan sebagian konsistensi untuk meningkatkan performa tulis
  • Hasilnya, mereka mendapatkan efek penurunan latensi P99 lebih dari 96% tanpa memberi dampak negatif bagi pengguna

Fanout timeline

• Saat pengguna memposting di Bluesky, posting tersebut diindeks oleh sistem, disimpan di database, lalu disajikan melalui respons API
• Pada saat yang sama, sistem menjalankan proses “fanout” yang memasukkan posting tersebut ke tabel timeline masing-masing follower
• Ini dilakukan dengan mengambil daftar follower, lalu melakukan penyisipan urutan terbalik ke tabel timeline tiap follower
• Tabel timeline dipartisi per pengguna dan disimpan di database terdistribusi (ScyllaDB), lalu direplikasi ke beberapa shard untuk ketersediaan tinggi
  • Setiap pengguna dapat ditempatkan pada shard yang berbeda
• Untuk menghemat ruang penyimpanan, timeline yang melewati panjang tertentu akan secara berkala menghapus referensi posting lama

Masalah hot shard

• Bluesky memiliki sekitar 32 juta pengguna, dan database timeline dibagi ke ratusan shard
• Dalam sistem dengan jutaan pengguna, bisa ada pengguna dengan relasi following yang sangat ekstrem
  • Contoh: pengguna yang mengikuti ratusan ribu akun
• Satu shard menyimpan banyak timeline pengguna secara bersamaan
• Jika pengguna tertentu memicu sangat banyak penulisan, shard tersebut menjadi kelebihan beban (“hot shard”)
• Hot shard seperti ini membuat operasi tulis atau baca terkonsentrasi, sehingga latensi ikut menyebar ke pengguna lain pada shard yang sama

Akumulasi latensi

• Jika satu pengguna memiliki 2.000.000 follower, menulis secara berurutan bisa memakan waktu lebih dari 20 menit
• Untuk mengurangi hal ini, fanout diparalelkan sehingga latensi rata-rata menjadi lebih pendek
• Namun, latensi P99 (sekitar 15 milidetik atau lebih) dapat muncul berkali-kali dan menunda keseluruhan pekerjaan paralel
• Jika jumlah follower sangat besar, latensi P99 atau P99.9 dapat membuat total waktu fanout membengkak, dari hitungan menit hingga puluhan menit dalam kasus terburuk

Timeline lossy

• Untuk pengguna yang mengikuti terlalu banyak akun, menampilkan semua posting secara akurat dan berurutan pada praktiknya tidak realistis
• Manusia juga sulit benar-benar mengonsumsi semua posting tersebut
• Karena itu, untuk timeline pengguna dengan jumlah following yang melewati ambang tertentu (misalnya reasonable_limit), diterapkan cara yang secara probabilistik “men-drop” sebagian penulisan
• Mereka menggunakan rumus loss_factor = min(reasonable_limit / num_follows, 1)
• Saat fanout, sistem menghasilkan nilai acak dan melewati penulisan ke timeline jika nilainya lebih besar dari loss_factor
• Dengan cara ini, penulisan berlebihan ke timeline pengguna tertentu dapat dibatasi, sekaligus mencegah penurunan performa pada seluruh shard

Tentang caching

• Karena penulisan timeline terjadi lebih dari jutaan kali per detik, jika pada setiap penulisan jumlah following pengguna diambil langsung dari DB, bebannya akan sangat besar
• Sebagai gantinya, akun dengan jumlah following tinggi di-cache di Redis dalam bentuk sorted set
• Setiap instance layanan fanout memuat informasi cache ini ke memori setiap 30 detik
• Hasilnya, bahkan selama proses fanout, informasi pengguna dengan following tinggi dapat diambil dengan cepat
• Karena data cache tidak harus selalu benar-benar mutakhir, pendekatan ini menerima sedikit ketidaksempurnaan demi meningkatkan performa dan skalabilitas

Hasil

• Setelah timeline lossy diperkenalkan, hot shard pada database Timelines pada dasarnya menghilang
• Latensi P99 untuk memproses satu halaman fanout berkurang lebih dari 90%
• Jika melihat total waktu pekerjaan fanout, tugas yang sebelumnya memakan 5–10 menit pada basis P99 dipersingkat menjadi kurang dari 10 detik
• Ini menunjukkan bahwa meski sebagian konsistensi dikorbankan, ekspektasi pengguna layanan tetap bisa dipenuhi sambil mempertahankan skalabilitas skala besar
• Arsitektur timeline Bluesky masih memiliki ruang untuk perbaikan, tetapi perubahan ini secara signifikan meningkatkan throughput tulis dan skalabilitas

[GN⁺]

Komentar Hacker News

• Sebagai penggemar sistem, saya termasuk orang yang menikmati artikel seperti ini. Mudah terjebak pada pola pikir bahwa "semuanya harus sempurna"

  • Di backend mesin pencari Blekko, mereka membangun indeks yang 'eventually consistent'. Ini memberi pembaruan lebih cepat kepada pengguna, tetapi dua pengguna yang menjalankan kueri yang sama bisa mendapatkan hasil yang sedikit berbeda
  • Banyak teori sistem yang berlaku di sini, dan jika ada umpan balik positif, sistem bisa berosilasi. Pada mesin pencari, pemeringkat yang memberi bobot pada tautan yang diklik pengguna memberikan umpan balik positif
  • Penting untuk menjaga agar sistem tetap "critically damped". Ini membuatnya cepat konvergen
  • Cara timeline pengguna di-shard dan memiliki loop umpan balik (misalnya 'like' atau 'repost') tampak seperti ruang masalah yang menarik

• Saya penasaran mengapa timeline tidak diimplementasikan secara hibrida berdasarkan popularitas akun

  • Untuk akun selebritas, alih-alih menyebarkan setiap pesan ke jutaan pengikut, akan lebih murah jika postingan selebritas diambil dan digabungkan saat timeline pengikut disajikan
  • Jika jutaan pengikut melakukannya, mengambilnya sebagai baca-saja dari hot cache akan murah

• Solusi yang menarik untuk masalah yang menarik. Terima kasih sudah membagikannya

  • Saya kesulitan memahami bagian saat penulis beralih dari "selebritas" ke "bot"
  • Rasanya penulis tiba-tiba memperkenalkan konsep yang sepenuhnya berbeda, yaitu "lossy timeline"

• Saya penasaran dengan strategi yang mengorbankan konsistensi ini. Ingin tahu apakah ada pemikiran tentang pendekatan selain fan-out penuh saat baca atau tulis

  • Daripada menulis ke timeline semua pengguna, saya membayangkan menulis hanya sekali ke setiap shard yang memiliki setidaknya satu pengikut
  • Saat membaca, ambil konten untuk pengguna tertentu lalu filter pengikut yang sebenarnya
  • Karena pembacaan berada di dalam shard, latensinya rendah
  • Untuk mega-follower, halaman tidak akan melihat item yang sudah lama

• Tidak perlu menyajikan secara kronologis sempurna semua yang diposting oleh ribuan pengguna yang diikuti setiap orang, tetapi masuk akal untuk menyediakan cukup konten agar selalu ada konten baru di timeline

  • Solusinya tampak bukan urutan waktu yang tidak sempurna, melainkan seperti ada postingan yang hilang dari feed

• Saya penasaran bagaimana pembatasan jumlah pengikut akan bekerja untuk menghindari masalah hot shard

  • Setiap pengguna memiliki timeline terpisah untuk setiap 1000 pengikut, lalu klien menggabungkannya
  • Jika perlu, hanya sebagian dari timeline sebenarnya yang dimuat untuk menjalankan bagian lossy

• AWS punya pendekatan umum yang keren untuk masalah ini

  • Mereka menetapkan setiap pengguna ke beberapa shard untuk mengurangi kemungkinan pengguna lain berbagi semua shard yang sama
  • Jika dari awal menggunakan shuffle sharding, mereka mungkin bisa menyelesaikan masalah baru tanpa memengaruhi banyak pengguna lain

• Akun yang mengikuti ratusan ribu pengguna jelas merupakan akun bot pengumpul konten. Saya akan memblokirnya dan selesai

  • Saya suka membaca tentang tantangan teknis. Twitter memiliki arsitektur khusus untuk selebritas dengan jutaan pengikut
  • Jika Bluesky adalah klon yang serupa, saya penasaran mengapa mereka tidak mengikuti pendekatan itu

• Saat membuka langsung profil pengguna untuk melihat semua postingan, kadang ada postingan yang seharusnya ada di timeline tetapi tidak muncul

  • Ini menjelaskan mengapa di Bluesky, meskipun saya mengikuti kurang dari 100 pengguna, kadang saya tidak melihat postingan seseorang di timeline

• Saya penasaran mengapa fan-out diimplementasikan dengan cara setiap "halaman" memblokir pengambilan halaman berikutnya

  • Aktivitas pengambilan halaman harus mengambil pengikut secara berurutan, dan tidak perlu menunggu sampai semua item di halaman diperbarui
  • Saya membayangkan ada komponen pengambil yang mengambil halaman, menyimpannya ke S3, lalu memublikasikan metadata dan lokasi S3 ke antrean (SQS)
  • Dalam sistem ini, konkurensi bisa dikendalikan lebih baik, dan pekerjaan bisa "diperlambat" dengan mempartisi dari antrean menggunakan shard sebagai kunci