Feed Berita

Push versus pull serta fan-out saat tulis versus saat baca pada feed.

Daftar isi

Feed berita, sering disebut timeline, adalah daftar postingan dari akun yang diikuti dan tersusun dari yang terbaru, serta menjadi permukaan utama layanan berbagi postingan. Topik ini merancang feed tersebut dengan kerangka studi kasus yang sama dan memusatkan perhatian pada satu keputusan, yaitu mengirim postingan ke timeline pembaca saat tulis (push) atau menyusunnya saat baca (pull). Perbandingan biayanya dihitung dengan program Python, dan desain tingkat tingginya menggabungkan keduanya sesuai ukuran akunnya.

Kebutuhan dan estimasi#

Secara fungsional, setiap pengguna memiliki satu timeline pribadi yang berisi postingan terbaru dari seluruh akun yang diikutinya, dan halaman pertama timeline harus terbuka cepat karena permukaan inilah yang dibuka paling sering. Postingan baru dari akun yang diikuti harus muncul tanpa pengaturan manual, dan urutan waktunya konsisten. Secara nonfungsional, bebannya sangat timpang, yaitu membaca timeline jauh lebih sering daripada menulis postingan.

Estimasinya memakai angka layanan berbagi postingan berukuran sedang, yaitu 1.000.000 pengguna aktif yang masing-masing menulis 1 postingan per hari dan membaca timeline 10 kali per hari. Rata-rata setiap pengguna mengikuti 100 akun, sedangkan dua puluh akun besar masing-masing memiliki 1.000.000 pengikut. Keempat angka inilah yang menjadi parameter perhitungan biaya pada bagian perbandingan, sehingga setiap angka pada topik ini dapat dihitung ulang dari yang sama.

Antarmuka#

Antarmuka feed memisahkan daftar pengenal postingan dari isinya, karena daftar yang tersimpan pada timeline cukup menunjuk ke penyimpanan postingan yang menjadi sumber tunggal isi.

text Contoh: API feed

POST /api/postingan
  isi   : {"teks": "hari ini belajar membagi basis data"}
  jawab : {"id": "postingan-7341"}

GET /api/feed
  jawab : daftar pengenal postingan dari timeline pembaca,
          sudah digabung dengan postingan akun besar yang diikuti

GET /api/postingan/{id}
  jawab : isi lengkap satu postingan

Pembacaan feed mengembalikan daftar pengenal saja, sehingga ukuran jawabannya kecil dan isinya diambil satu per satu ketika halaman benar-benar menampilkannya. Pemisahan ini juga membuat penyusunan ulang halaman feed, misalnya saat sesi membaca dimulai kembali, tidak perlu membaca isi seluruh postingan yang belum terlihat. Daftar yang dikembalikan sudah berurutan dari yang terbaru karena urutannya dijaga oleh penyimpanan timeline, sehingga antarmuka tidak menawarkan parameter penyusunan ulang. Perubahan aturan peringkat di kemudian hari cukup dikerjakan di atas daftar yang sama tanpa mengubah format jawabannya.

Push: fan-out saat tulis#

Pendekatan fan-out saat tulis mengisi timeline di muka. Saat postingan diterbitkan, sistem menyisipkan pengenal postingan itu ke timeline setiap pengikutnya, sehingga membaca timeline cukup membaca satu daftar yang sudah tersusun. Latensi baca menjadi rendah dan stabil, karena pekerjaan menggabungkan ratusan akun sudah selesai jauh sebelum pembaca datang.

Biayanya pindah ke saat tulis dan dibayar sekali untuk setiap postingan, yaitu sebanyak jumlah pengikutnya. Pengguna biasa dengan 100 pengikut menimbulkan 100 sisipan, tetapi satu postingan akun besar menimbulkan 1.000.000 sisipan sekaligus, beban yang datang tanpa peringatan ke queue fan-out. Pendekatan ini juga menampung postingan di timeline pengguna yang tidak pernah membacanya, yaitu biaya penyimpanan untuk pembacaan yang tidak pernah terjadi. Isi postingannya sendiri tidak disalin ke timeline, karena timeline hanya menyimpan penunjuk ke penyimpanan postingan. Dengan begitu biaya sisipan tetap sebanding jumlah pengikut, tanpa berlipat sebesar ukuran postingannya.

Pull: fan-out saat baca#

Pendekatan fan-out saat baca menyusun timeline tepat ketika diminta. Sistem mengambil postingan terbaru dari setiap akun yang diikuti pembaca, menggabungkannya sesuai urutan waktu, lalu mengembalikan hasilnya. Biaya tulis menjadi murah karena tidak ada timeline yang perlu diisi, dan tidak ada penyimpanan timeline sama sekali.

Dua sifatnya menjadi kelebihan sekaligus kelemahan. Pengguna yang jarang membaca tidak menimbulkan biaya apa pun, sedangkan setiap pembacaan mengulang pekerjaan gabungan yang sama untuk pengguna yang berbeda, sehingga biaya berkembang seiring frekuensi baca. Latensi baca juga naik karena menyusun, alih-alih membaca satu daftar, dan latensi inilah yang paling dirasakan pengguna. Biaya ini juga sulit diberi cache secara merata, karena setiap pembaca memiliki gabungan akun yang diikutinya sendiri, kecuali bagian akun besar yang disentuh hampir semua orang. Perbedaan itu kembali menunjuk pada pola akses yang timpang antara pengguna biasa dan akun besar.

Perbandingan biaya#

Berkas berikut menghitung biaya harian kedua pendekatan dari empat parameter estimasi, beserta porsi akun besar pada masing-masing.

python hitung-biaya-feed.py

"""Perbandingan biaya fan-out saat tulis (push) dan saat baca (pull).

Semua angka diturunkan dari empat parameter dasar dengan hitungan
sederhana dan tanpa bilangan acak, sehingga setiap baris keluaran dapat
dihitung ulang dengan kalkulator biasa.
"""

PENGGUNA_AKTIF = 1_000_000        # pengguna aktif per hari
POSTINGAN_PER_PENGGUNA = 1        # postingan per hari per pengguna
PEMBACAAN_PER_PENGGUNA = 10       # pembacaan feed per hari per pengguna
RATA_RATA_DIIKUTI = 100           # akun yang diikuti, termasuk akun besar
JUMLAH_AKUN_BESAR = 20            # akun dengan pengikut sangat banyak
PENGIKUT_PER_AKUN_BESAR = 1_000_000

if __name__ == "__main__":
    postingan = PENGGUNA_AKTIF * POSTINGAN_PER_PENGGUNA
    pembacaan = PENGGUNA_AKTIF * PEMBACAAN_PER_PENGGUNA

    push_total = postingan * RATA_RATA_DIIKUTI
    push_akun_besar = JUMLAH_AKUN_BESAR * PENGIKUT_PER_AKUN_BESAR

    pull_total = pembacaan * RATA_RATA_DIIKUTI
    pull_akun_besar = pembacaan * JUMLAH_AKUN_BESAR

    print(f"parameter: {PENGGUNA_AKTIF:,} pengguna aktif, "
          f"{POSTINGAN_PER_PENGGUNA} postingan/hari, "
          f"{PEMBACAAN_PER_PENGGUNA} pembacaan feed/hari")
    print(f"rata-rata {RATA_RATA_DIIKUTI} akun diikuti, "
          f"{JUMLAH_AKUN_BESAR} akun besar dengan "
          f"{PENGIKUT_PER_AKUN_BESAR:,} pengikut")
    print()
    print(f"postingan per hari        : {postingan:>13,}")
    print(f"pembacaan feed per hari   : {pembacaan:>13,}")
    print()
    print(f"push (fan-out saat tulis) : {push_total:>13,} penulisan timeline/hari")
    print(f"  termasuk akun besar     : {push_akun_besar:>13,} penulisan/hari")
    print()
    print(f"pull (fan-out saat baca)  : {pull_total:>13,} pembacaan sumber/hari")
    print(f"  termasuk akun besar     : {pull_akun_besar:>13,} pembacaan/hari")
    print()
    push_hibrida = push_total - push_akun_besar
    print(f"hibrida                   : {push_hibrida:>13,} penulisan timeline/hari")
    print(f"  akun besar lewat baca   : {JUMLAH_AKUN_BESAR:>13,} postingan unik/hari, "
          f"dilayani cache saat pembacaan")

text Keluaran

parameter: 1,000,000 pengguna aktif, 1 postingan/hari, 10 pembacaan feed/hari
rata-rata 100 akun diikuti, 20 akun besar dengan 1,000,000 pengikut

postingan per hari        :     1,000,000
pembacaan feed per hari   :    10,000,000

push (fan-out saat tulis) :   100,000,000 penulisan timeline/hari
  termasuk akun besar     :    20,000,000 penulisan/hari

pull (fan-out saat baca)  : 1,000,000,000 pembacaan sumber/hari
  termasuk akun besar     :   200,000,000 pembacaan/hari

hibrida                   :    80,000,000 penulisan timeline/hari
  akun besar lewat baca   :            20 postingan unik/hari, dilayani cache saat pembacaan

Perbandingannya ditentukan oleh rasio baca dan tulis. Biaya push per hari adalah $T \cdot F$ untuk $T$ postingan per pengguna dan $F$ rata-rata pengikut, sedangkan biaya pull adalah $B \cdot F$ untuk $B$ pembacaan per pengguna, sehingga perbandingannya $B/T$ , dan pada estimasi ini nilainya 10. Pull melakukan sepuluh kali lebih banyak pekerjaan daripada push pada pola baca yang sering, kecuali penggunanya jarang membaca. Porsi akun besar memperlihatkan masalah sebaliknya, yaitu 20.000.000 penulisan sisipan untuk dua puluh postingan pada push, sementara pada pull, postingan yang sama hanya ada dua puluh salinan unik per hari. Salinan yang sedikit dan dibaca berkali-kali adalah profil data yang paling cocok untuk cache, sehingga desain gabungannya jelas, yaitu push untuk pengguna biasa dan ambil saat baca melalui cache untuk akun besar.

Desain tingkat tinggi#

Desainnya memisahkan alur tulis dan alur baca sebagaimana pembanding biayanya. Pada alur tulis, layanan postingan menerbitkan kejadian penerbitan ke queue fan-out, pekerja fan-out mengambilnya dan menyisipkan pengenal postingan ke timeline setiap pengikut biasa, dan postingan akun besar dilewatkan. Pada alur baca, layanan feed membaca timeline pembaca, menambahkan postingan terbaru akun besar yang diikutinya dari cache, lalu menggabungkan keduanya.

Alur tulis mengisi timeline setiap pengikut biasa, sedangkan alur baca menggabungkan timeline dengan cache akun besar

Timeline hanya menyimpan pengenal postingan, bukan isinya, sehingga isi tersimpan sekali di penyimpanan postingan dan setiap timeline tinggal menunjuk padanya. Pekerja fan-out mencatat kemajuan per postingan, misalnya pengikut terakhir yang sudah dilayani, sehingga pekerjaan yang terputus dapat dilanjutkan dari posisinya. Cache akun besar kecil, yaitu hanya berisi postingan terbaru dari dua puluh kunci, tetapi melayani seluruh pembacaan. Kapasitas pekerja fan-out dinaikkan dengan menambah pekerja yang menarik dari queue yang sama, dan catatan kemajuan itulah yang menjaga penambahan pekerja tidak menciptakan sisipan ganda. Sementara itu, layanan feed pada alur baca tidak menyimpan keadaan, sehingga jumlahnya cukup mengikuti trafik baca.

Mode kegagalan#

Pekerja fan-out mati di tengah postingan. Sebagian pengikut tidak menerima pengenal postingan itu, sehingga timeline yang bersangkutan bolong. Catatan kemajuan per postingan memungkinkan pekerja berikutnya melanjutkan dari posisi terakhir, atau alur baca melengkapi kekurangannya saat menggabungkan.
Queue fan-out terbanjiri saat akun besar memposting. Satu kejadian yang memicu jutaan sisipan menahan postingan pengguna lain di belakangnya. Pemisahan queue untuk akun besar, atau pengecualiannya dari fan-out seperti desain hibrida, menjaga latensi pengguna biasa.
Penyimpanan timeline menjadi hotspot. Timeline pengguna paling aktif dibaca puluhan kali sehari, sehingga penyimpanannya dipartisi dengan sharding, yaitu pembagian data berdasarkan kunci ke beberapa node.
Cache akun besar mati. Pembacaan akun besar jatuh ke penyimpanan postingan selama cache terisi ulang, dan beban ekstranya terbatas pada dua puluh kunci, sehingga gangguan ini paling ringan di antara yang lain.
Layanan postingan mati. Tidak ada postingan baru dan tidak ada pekerjaan fan-out, sedangkan pembacaan timeline tetap berjalan dari penyimpanan yang ada.

Kesalahan umum#

Menerapkan push tanpa pengecualian untuk akun besar. Satu postingan berpengikut jutaan membanjiri antrean fan-out dan menunda postingan pengguna biasa. Pengecualian akun besar dan penyediaan cache baca menjadi perbaikannya.
Menyimpan isi postingan penuh di setiap timeline. Penyimpanan melipatgandakan sebesar rata-rata pengikut, padahal pengenal postingan cukup untuk menyusun daftar.
Menggabungkan postingan akun besar saat baca tanpa cache. Setiap pembacaan menyentuh penyimpanan postingan untuk data yang sama, sedangkan dua puluh kunci panas muat seluruhnya di cache.
Menghitung ulang seluruh timeline untuk setiap permintaan baca pada pendekatan push. Timeline yang sudah tersusun justru sumber keunggulannya, sehingga pembacaan cukup membaca daftar beserta penunjuk posisi terakhirnya.
Mengabaikan penunjuk posisi baca pada antarmuka. Klien yang membuka ulang feed membaca daftar dari awal lagi, sedangkan penunjuk posisi terakhir pada jawaban feed cukup untuk melanjutkan pembacaan dari tempat yang sama.

Ringkasan#

Push memindahkan biaya ke saat tulis dan membuat baca menjadi satu pembacaan daftar, sedangkan pull memindahkan biaya ke saat baca dan menghilangkan penyimpanan timeline.
Pada rasio baca terhadap tulis 10 berbanding 1, pull melakukan sepuluh kali pekerjaan push, yaitu 1.000.000.000 pembacaan sumber berbanding 100.000.000 penulisan timeline per hari pada estimasi.
Akun besar mematahkan kedua pendekatan murni, dan desain hibrida menjawabnya, yaitu push untuk pengguna biasa, ambil saat baca dari cache kecil yang hanya berisi dua puluh postingan unik per hari untuk akun besar.
Pemulihan fan-out yang terputus ditopang catatan kemajuan per postingan, sehingga timeline tidak bolong saat pekerja mati.

Referensi#

The Architecture Twitter Uses to Deal with 150M Active Users — High Scalability — Arsitektur feed layanan mikroblog besar yang menulis timeline ke cluster Redis saat tulis.
Timelines at Scale — InfoQ — Presentasi Raffi Krikorian tentang fan-out saat tulis dan saat baca pada timeline berskala besar.