Design Spotify Top-K

Prompt latihan

1. Problem Statement, Functional Requirements, and Scale Assumptions

   Tentukan ruang lingkup leaderboard lagu Top-K: sistem harus melacak jumlah putar (play count) semua lagu secara real-time dan menampilkan K lagu yang paling banyak diputar dalam sebuah window waktu (jam terakhir, 24 jam terakhir, sepanjang waktu). Pengguna (pendengar) dapat men-query daftar top-K saat ini dan jumlah putar sebuah lagu individual. Kecualikan secara eksplisit: pemutaran musik itu sendiri, mesin rekomendasi, kalkulasi royalti artis, dan riwayat putar level-pengguna. Nyatakan asumsi skala: total lagu dalam katalog, event putar per detik saat puncak, jumlah lagu unik yang diputar per jam, granularitas window waktu yang didukung, dan rentang nilai K yang diinginkan.

2. Non-Functional Requirements

   Tentukan NFR utama: throughput tulis event putar (jutaan per detik, dapatkah sistem menerima penghitungan aproksimasi jika mengurangi biaya tulis?), latensi query top-K (daftar terurut harus dikembalikan dalam 50ms, struktur data apa yang memungkinkan pengambilan O(K)?), trade-off akurasi hitungan vs. kesegaran (apakah daftar top-K boleh tertinggal dari real-time hingga 60 detik? Bolehkah hitungan bersifat aproksimasi dalam 1%?), dan semantik window waktu (sliding window: hitungan eksak atas 60 menit terakhir yang bergulir; tumbling window: hitungan eksak atas bucket 1-jam tetap, mana yang lebih sulit diimplementasikan pada skala besar?).

3. Quantitative Analysis

   Estimasikan: laju ingestion event putar (500 juta pengguna aktif harian × 10 lagu/jam / 3600 = ~1,4 juta event putar per detik pada kondisi tunak, dengan lonjakan puncak 3–5×), total lagu unik yang diputar per window 1-jam (asumsikan 5 juta lagu aktif), memori yang dibutuhkan untuk menyimpan sorted set dari 5 juta lagu beserta play count-nya (5 juta × 24 byte per entri ≈ 120MB di Redis, muat di memori), dan QPS query top-K (100 ribu query/detik untuk chart global). Identifikasi jalur tulis (jutaan/s) sebagai tantangan penskalaan utama, bukan jalur baca.

4. API Design

   Tentukan operasi API untuk: mencatat event putar (POST /plays dengan song_id, user_id, dan timestamp, digunakan oleh layanan pemutaran; harus fire-and-forget dari perspektif pemanggil), men-query K lagu teratas untuk sebuah window waktu (GET /charts/top?k=50&window=1h, mengembalikan daftar terurut beserta play count), dan men-query play count untuk lagu tertentu atas sebuah window waktu (GET /charts/songs/{song_id}?window=1h). Bahas idempotensi untuk event putar (pengiriman duplikat dari retry), rate limiting untuk query chart (API yang menghadap publik), dan bagaimana parameter window diinterpretasikan (tumbling vs. sliding).

5. High-Level Design

   Usulkan komponen utama: play event producer (layanan pemutaran mem-publish event putar ke Kafka), stream processing job (Flink atau Spark Streaming mengonsumsi dari Kafka, mengagregasi play count per lagu per window waktu, memperbarui sorted set), Redis sorted set store (song_id → play count, mendukung ZINCRBY untuk increment atomik dan ZREVRANGE untuk pengambilan top-K), dan chart query service (membaca dari Redis sorted set). Jelaskan jalur tulis (event putar → Kafka → stream processor → Redis) dan jalur baca (query chart → Redis ZREVRANGE K).

6. Additional High-Level Design Prompts

   Bahas tiga area lanjutan: (1) Penghitungan aproksimasi vs. eksak, pada 1,4 juta event putar per detik, mampukah Anda melakukan penghitungan eksak? Count-Min Sketch adalah struktur data probabilistik yang menggunakan array berukuran tetap untuk mengestimasi hitungan dengan error terbatas (biasanya overcount 1%); ia secara drastis mengurangi memori dibandingkan menyimpan hitungan eksak untuk setiap lagu; kapan penghitungan aproksimasi dapat diterima (top chart di mana lagu #50 vs. #51 tidak penting) vs. kapan penghitungan eksak diperlukan (kalkulasi royalti)? (2) Beberapa window waktu, sistem harus mendukung window 1h, 24h, dan sepanjang-waktu secara bersamaan; pendekatan naif: satu Redis sorted set per window; pendekatan efisien: gunakan tumbling window (bucket 1-menit) dan agregasi 60 bucket terakhir untuk 1h, 1440 bucket terakhir untuk 24h; trade-off: storage (60 sorted set × 5 juta lagu) vs. latensi query; (3) Chart top-K regional, pengguna Spotify di Indonesia mungkin memiliki lagu teratas yang berbeda dari pengguna di AS; bagaimana Anda merancang pipeline chart regional bersamaan dengan chart global?

7. Deep Dives

   Deep dive ke tiga area: (1) Count-Min Sketch, array 2D dari d fungsi hash × w counter; untuk menghitung event untuk song_id: hash song_id dengan masing-masing dari d fungsi hash, naikkan counter pada posisi yang bersesuaian; untuk mengestimasi hitungan: ambil minimum di semua d baris; batas error adalah O(N/w) dengan probabilitas (1 - 1/e^d); d=5, w=2000 memberi akurasi 99%+ untuk 5 juta lagu; ukuran in-memory: 5 × 2000 × 4 byte = 40KB vs. 120MB untuk Redis sorted set eksak; trade-off: tidak dapat menghitung semua lagu di atas ambang (perlu dipasangkan dengan heap kecil untuk top-K); (2) Sliding window dengan tumbling bucket, simpan 60 sorted set satu-menit untuk window 1h; pada setiap batas menit, buang bucket tertua dan tambahkan yang baru; untuk menjawab query top-K, merge (jumlahkan score di) 60 bucket saat ini; merge naif 60 sorted set dengan 5 juta entri itu mahal; optimasi: pelihara sorted set 'merged 1h' terpisah yang diperbarui saat rollover bucket; hanya delta (hitungan bucket baru - hitungan bucket kedaluwarsa) yang perlu diterapkan; (3) Backpressure stream processing, pada 1,4 juta event/s, stream processor harus mengikuti ingestion Kafka; backpressure terjadi saat lag pemrosesan melebihi buffer; mitigasi: penskalaan horizontal (tambah instance processor), kurangi pekerjaan per event (pra-partisi berdasarkan song_id untuk menghindari agregasi lintas-shard), dan gunakan ZINCRBY dalam batch (akumulasikan 1000 event secara lokal lalu terapkan batch ZINCRBY untuk mengurangi round trip Redis).

8. Final Review Handoff Readiness

   Ringkas keputusan desain utama: stream event putar Kafka untuk pemisahan throughput tulis, stream processor (Flink) untuk agregasi berjendela, Redis sorted set untuk pengambilan top-K (ZINCRBY + ZREVRANGE), Count-Min Sketch untuk penghitungan aproksimasi, strategi tumbling bucket untuk beberapa window waktu, dan partisi chart regional. Soroti dua pertanyaan terbuka terbesar yang tersisa (akurasi Count-Min Sketch vs. biaya Redis sorted set, pada ukuran katalog berapa sketch menjadi benar-benar diperlukan, dan biaya merge tumbling bucket, apa dampak latensi strategi delta-update terhadap kesegaran query top-K?) dan usulkan rollout bertahap: Redis sorted set eksak dulu (lebih sederhana), lalu Count-Min Sketch saat katalog melebihi 50 juta lagu.

Preview solusi

Solusi Referensi, Merancang Spotify Top-K Insight Inti Spotify Top-K adalah problem streaming aggregation yang write-heavy . Kesulitannya bukan pada sisi baca (mengambil top K lagu adalah trivial dengan sebuah sorted set), melainkan menangani 1,4M play event per detik sambil menjaga leaderboard tetap up-to-date. Desain harus memisahkan (decouple) ingestion d…