Representasikan graf sosial

Pertanyaan

Bagaimana menyimpan siapa mengikuti siapa supaya dua arah pertanyaan tetap cepat, dan kapan basis data graf beneran perlu?

Setelah baca ini, kamu bisa mendesain tabel edge dengan reverse edge, memilih partition key tanpa membuat akun populer jadi hotspot, dan memutuskan apakah kebutuhanmu perlu basis data graf.

Prasyarat dan contoh

Kamu sudah paham pola akses dan indeks (M04), serta partisi dan hotspot (M07).

Aplikasi sosial punya 10 juta pengguna, rata-rata mengikuti 50 akun. Itu 500 juta edge. Ada dua pertanyaan utama: "siapa saja yang saya ikuti?" (buat feed) dan "siapa saja yang mengikuti saya?" (buat daftar pengikut dan fan-out). Desain yang cepat di satu arah dan scan penuh di arah lain itu desain yang setengah jadi.

Mekanisme

Tabel adjacency. Satu baris per edge:

follows(follower_id, followee_id, created_at) dengan primary key (follower_id, followee_id).

Primary key itu menjawab "siapa yang saya ikuti" dengan satu range scan dan sekaligus mencegah edge ganda. Ukuran: dua ID 8 byte + timestamp 8 byte = 24 byte, dan dengan overhead baris serta indeks mudah jadi sekitar 60 sampai 100 byte per edge. Untuk 500 juta edge itu 30 sampai 50 GB: masih muat di satu mesin yang layak, tapi tumbuh cepat.

Reverse edge. "Siapa yang mengikuti saya" butuh akses menurut followee_id. Dua pilihan:

• Indeks sekunder (followee_id, follower_id) di tabel yang sama. Sederhana, konsisten dalam satu transaksi, selama masih satu partisi.
• Tabel kedua followers(followee_id, follower_id) yang ditulis bersama atau lewat event (outbox, M10). Dibutuhkan saat tabel dipartisi, karena dua arah nggak bisa partisi menurut kolom yang sama. Konsekuensinya: dua tulis, dan jendela waktu di mana keduanya beda. Tentukan tabel mana yang jadi sumber kebenaran dan perbaiki yang lain dari situ.

Partition key. Tabel follows dipartisi menurut follower_id: semua yang saya ikuti ada di satu partisi. Tabel followers menurut followee_id. Masalahnya: akun dengan 20 juta pengikut membuat satu partisi followers jauh lebih besar dan panas dari lainnya. Atasi dengan pagination berbasis kursor (jangan OFFSET), dan untuk akun sangat besar, pecah partisi dengan bucket (followee_id, bucket) di mana bucket = hash(follower_id) mod 16.

Hitungan. Menyimpan jumlah pengikut sebagai COUNT(*) di akun 20 juta itu scan besar. Simpan counter terdenormalisasi dan perbarui asinkron. Angkanya boleh telat beberapa detik, dan kalau perlu diperbaiki berkala dari data edge.

Pertanyaan turunan. Teman bersama dua akun = irisan dua daftar. Dengan 200 dan 300 edge, itu kerja kecil di aplikasi atau dengan satu join. Teman dari teman (dua hop): 200 × 200 = 40.000 edge diperiksa, masih wajar. Tiga hop: 200³ = 8 juta, mulai berat dan butuh batas.

Saat rancangan ini gagal

• Hanya satu arah diindeks. Query "pengikut saya" scan seluruh tabel, dan halaman profil akun besar timeout.
• Hotspot akun populer. Satu partisi followers menerima ribuan follow per detik saat akun viral, sementara partisi lain nganggur.
• Dua tabel tak sinkron. Salah satu tulis gagal, jadi A muncul di "mengikuti" B tapi B tak punya A di "pengikut". Perlu rekonsiliasi dan sumber kebenaran yang jelas.
• OFFSET pada daftar besar. Halaman ke 10.000 membaca dan membuang jutaan baris.
• Counter dihitung ulang tiap tampil. Beban baca naik tanpa batas seiring akun membesar.

Contoh tandingan: tim memilih basis data graf untuk "siapa mengikuti siapa" dengan 2 juta edge dan pertanyaan satu hop. Mereka menambah komponen baru dengan keahlian operasional baru, padahal satu tabel Postgres dengan dua indeks sudah menjawab semuanya.

Latihan

Platform dengan 5 juta pengguna, rata-rata 100 yang diikuti. Satu selebritas punya 8 juta pengikut.

1. Berapa jumlah edge, dan perkiraan ukuran di 80 byte per edge?
2. Rancang tabel dan indeks untuk dua pertanyaan: "yang saya ikuti" dan "pengikut saya".
3. Tentukan partition key kalau tabel harus dipartisi, dan masalah apa yang muncul pada selebritas.
4. Apakah kamu butuh basis data graf kalau fitur terjauhnya "teman bersama"?

Lihat pembahasan+

1. 5 juta × 100 = 500 juta edge. 500 juta × 80 byte = 40 GB.
2. follows(follower_id, followee_id, created_at) PK (follower_id, followee_id), plus indeks (followee_id, follower_id) atau tabel followers terpisah kalau dipartisi.
3. follows menurut follower_id, followers menurut followee_id. Selebritas membuat satu partisi followers berisi 8 juta baris dan panas. Gunakan kursor, bucket hash(follower_id) mod 16, dan counter terdenormalisasi untuk jumlah pengikut.
4. Tidak. Teman bersama adalah irisan dua daftar satu hop (sekitar 100 sampai 300 baris). Tabel edge dengan indeks cukup.

Terkait

• Sebelumnya: M13.03 Kirim pesan chat.
• Lanjut ke M13.05 Buat feed, yang memakai daftar pengikut untuk fan-out.
• Pola akses dan indeks dari M04, serta partition key dan hotspot dari M07, dipakai di sini. Rancangan D15 belum tersedia.

Catatan

• Asumsi: relasi diikuti satu arah, pengguna nyata, bukan graf pengetahuan umum.
• Ukuran per baris hanya perkiraan kasar. Ukur dengan data dan engine yang kamu pakai.
• Yang nggak dibahas: rekomendasi "orang yang mungkin kamu kenal", pemblokiran, dan akun privat.
• Kriteria basis data graf adalah pedoman praktis, bukan aturan mutlak.
• Terakhir ditinjau: 26 Oktober 2026.