Tulis ulang basis data pesan VKontakte dari awal dan bertahan

Pengguna kami menulis pesan satu sama lain tanpa mengetahui kelelahan.

Itu cukup banyak. Jika Anda ingin membaca semua pesan dari semua pengguna, itu akan memakan waktu lebih dari 150 ribu tahun. Asalkan Anda adalah pembaca yang cukup mahir dan menghabiskan tidak lebih dari satu detik untuk setiap pesan.

Dengan volume data sebesar itu, logika untuk menyimpan dan mengaksesnya harus dibangun secara optimal. Jika tidak, dalam satu momen yang tidak terlalu indah, akan menjadi jelas bahwa segala sesuatunya akan menjadi tidak beres.

Bagi kami, momen ini datang satu setengah tahun yang lalu. Bagaimana kami sampai pada hal ini dan apa yang terjadi pada akhirnya - kami ceritakan secara berurutan.

hal ihwal

Pada implementasi pertama, pesan VKontakte bekerja pada kombinasi backend PHP dan MySQL. Ini adalah solusi yang sepenuhnya normal untuk situs web pelajar kecil. Namun, situs ini tumbuh tak terkendali dan mulai menuntut optimalisasi struktur data untuk dirinya sendiri.

Pada akhir tahun 2009, repositori mesin teks pertama ditulis, dan pada tahun 2010 pesan ditransfer ke sana.

Di mesin teks, pesan disimpan dalam daftar - semacam "kotak surat". Setiap daftar tersebut ditentukan oleh uid - pengguna yang memiliki semua pesan ini. Sebuah pesan memiliki sekumpulan atribut: pengenal lawan bicara, teks, lampiran, dan sebagainya. Pengidentifikasi pesan di dalam “kotak” adalah local_id, tidak pernah berubah dan ditetapkan secara berurutan untuk pesan baru. "Kotak-kotak" itu independen dan tidak disinkronkan satu sama lain di dalam mesin; komunikasi di antara mereka terjadi pada tingkat PHP. Anda dapat melihat struktur data dan kemampuan mesin teks dari dalam di sini.

Ini cukup untuk korespondensi antara dua pengguna. Coba tebak apa yang terjadi selanjutnya?

Pada bulan Mei 2011, VKontakte memperkenalkan percakapan dengan beberapa peserta—multi-obrolan. Untuk bekerja dengan mereka, kami memunculkan dua cluster baru - anggota-obrolan dan anggota-obrolan. Yang pertama menyimpan data tentang obrolan pengguna, yang kedua menyimpan data tentang pengguna melalui obrolan. Selain daftar itu sendiri, hal ini mencakup, misalnya, pengguna yang mengundang dan waktu mereka ditambahkan ke obrolan.

“PHP, ayo kirim pesan ke chat,” kata pengguna.
“Ayo, {username},” kata PHP.

Ada kelemahan pada skema ini. Sinkronisasi masih menjadi tanggung jawab PHP. Obrolan besar dan pengguna yang mengirim pesan secara bersamaan adalah cerita yang berbahaya. Karena mesin teks bergantung pada uid, peserta obrolan dapat menerima pesan yang sama pada waktu yang berbeda. Seseorang dapat menerima hal ini jika kemajuan terhenti. Tapi itu tidak akan terjadi.

Pada akhir tahun 2015, kami meluncurkan pesan komunitas, dan pada awal tahun 2016, kami meluncurkan API untuk pesan tersebut. Dengan munculnya chatbot besar di komunitas, distribusi beban yang merata bisa saja dilupakan.

Bot yang bagus menghasilkan beberapa juta pesan per hari - bahkan pengguna yang paling banyak bicara pun tidak dapat membanggakan hal ini. Ini berarti bahwa beberapa contoh mesin teks, tempat bot tersebut hidup, mulai menderita sepenuhnya.

Mesin pesan pada tahun 2016 adalah 100 instance anggota obrolan dan obrolan anggota, dan 8000 mesin teks. Mereka dihosting di seribu server, masing-masing dengan memori 64 GB. Sebagai tindakan darurat pertama, kami menambah memori sebesar 32 GB lagi. Kami memperkirakan perkiraannya. Tanpa perubahan drastis, jumlah ini akan cukup untuk satu tahun lagi. Anda perlu mendapatkan perangkat keras atau mengoptimalkan database itu sendiri.

Karena sifat arsitekturnya, masuk akal untuk meningkatkan perangkat keras secara berlipat ganda. Artinya, setidaknya menggandakan jumlah mobil - jelas ini adalah cara yang agak mahal. Kami akan mengoptimalkan.

Konsep baru

Esensi utama dari pendekatan baru ini adalah obrolan. Obrolan memiliki daftar pesan yang berhubungan dengannya. Pengguna memiliki daftar obrolan.

Minimum yang diperlukan adalah dua database baru:

• mesin obrolan. Ini adalah gudang vektor obrolan. Setiap obrolan memiliki vektor pesan yang berhubungan dengannya. Setiap pesan memiliki teks dan pengidentifikasi pesan unik di dalam obrolan - chat_local_id.
• mesin pengguna. Ini adalah penyimpanan vektor pengguna - tautan ke pengguna. Setiap pengguna memiliki vektor peer_id (lawan bicara - pengguna lain, multi-obrolan, atau komunitas) dan vektor pesan. Setiap peer_id memiliki vektor pesan yang berhubungan dengannya. Setiap pesan memiliki chat_local_id dan ID pesan unik untuk pengguna tersebut - user_local_id.

Cluster baru berkomunikasi satu sama lain menggunakan TCP - ini memastikan urutan permintaan tidak berubah. Permintaan itu sendiri dan konfirmasinya dicatat di hard drive - sehingga kami dapat memulihkan status antrian kapan saja setelah kegagalan atau mesin dihidupkan ulang. Karena mesin pengguna dan mesin obrolan masing-masing berjumlah 4 ribu pecahan, antrian permintaan antar cluster akan didistribusikan secara merata (tetapi kenyataannya tidak ada sama sekali - dan ini bekerja sangat cepat).

Bekerja dengan disk di database kami dalam banyak kasus didasarkan pada kombinasi log perubahan biner (binlog), snapshot statis, dan sebagian gambar di memori. Perubahan pada siang hari ditulis ke binlog, dan cuplikan status saat ini dibuat secara berkala. Snapshot adalah kumpulan struktur data yang dioptimalkan untuk tujuan kita. Ini terdiri dari header (metaindex gambar) dan satu set metafile. Header disimpan secara permanen di RAM dan menunjukkan di mana mencari data dari snapshot. Setiap metafile mencakup data yang mungkin diperlukan dalam waktu dekat—misalnya, terkait dengan satu pengguna. Saat Anda menanyakan database menggunakan header snapshot, metafile yang diperlukan dibaca, dan kemudian perubahan di binlog yang terjadi setelah snapshot dibuat akan diperhitungkan. Anda dapat membaca lebih lanjut tentang manfaat pendekatan ini di sini.

Pada saat yang sama, data pada hard drive itu sendiri hanya berubah sekali sehari - pada larut malam di Moskow, ketika bebannya minimal. Berkat ini (mengetahui bahwa struktur pada disk konstan sepanjang hari), kita dapat mengganti vektor dengan array dengan ukuran tetap - dan karena ini, menambah memori.

Mengirim pesan menurut skema baru terlihat seperti ini:

1. Backend PHP menghubungi mesin pengguna dengan permintaan untuk mengirim pesan.
2. mesin pengguna memproksi permintaan ke mesin obrolan yang diinginkan, yang kembali ke mesin pengguna chat_local_id - pengidentifikasi unik dari pesan baru dalam obrolan ini. Chat_engine kemudian menyiarkan pesan tersebut ke semua penerima dalam obrolan.
3. mesin pengguna menerima chat_local_id dari mesin obrolan dan mengembalikan user_local_id ke PHP - pengidentifikasi pesan unik untuk pengguna ini. Pengidentifikasi ini kemudian digunakan, misalnya, untuk bekerja dengan pesan melalui API.

Namun selain benar-benar mengirim pesan, Anda perlu menerapkan beberapa hal penting lainnya:

• Subdaftar, misalnya, adalah pesan terbaru yang Anda lihat saat membuka daftar percakapan. Pesan yang belum dibaca, pesan dengan tag (“Penting”, “Spam”, dll.).
• Mengompresi pesan di mesin obrolan
• Menyimpan pesan dalam cache di mesin pengguna
• Cari (melalui semua dialog dan dalam dialog tertentu).
• Pembaruan waktu nyata (Longpolling).
• Menyimpan riwayat untuk menerapkan caching pada klien seluler.

Semua sublist mengubah strukturnya dengan cepat. Untuk bekerja dengan mereka, kami menggunakan Perlebar pohon. Pilihan ini dijelaskan oleh fakta bahwa di bagian atas pohon terkadang kami menyimpan seluruh segmen pesan dari snapshot - misalnya, setelah pengindeksan ulang setiap malam, pohon tersebut terdiri dari satu bagian atas, yang berisi semua pesan dari subdaftar. Pohon Splay memudahkan untuk memasukkan ke tengah-tengah simpul tersebut tanpa harus memikirkan keseimbangan. Selain itu, Splay tidak menyimpan data yang tidak perlu, sehingga menghemat memori kita.

Pesan melibatkan sejumlah besar informasi, sebagian besar berupa teks, yang berguna untuk dapat dikompres. Penting bagi kami untuk dapat secara akurat membatalkan pengarsipan bahkan satu pesan individual. Digunakan untuk mengompresi pesan Algoritma Huffman dengan heuristik kita sendiri - misalnya, kita tahu bahwa dalam pesan, kata-kata bergantian dengan "bukan kata" - spasi, tanda baca - dan kita juga mengingat beberapa kekhasan penggunaan simbol untuk bahasa Rusia.

Karena jumlah pengguna jauh lebih sedikit dibandingkan chat, untuk menyimpan permintaan disk akses acak di mesin chat, kami menyimpan pesan dalam cache di mesin pengguna.

Pencarian pesan diimplementasikan sebagai kueri diagonal dari mesin pengguna ke semua mesin obrolan yang berisi obrolan pengguna ini. Hasilnya digabungkan di mesin pengguna itu sendiri.

Nah, semua detail telah diperhitungkan, yang tersisa hanyalah beralih ke skema baru - dan sebaiknya tanpa disadari oleh pengguna.

Migrasi data

Jadi, kami memiliki mesin teks yang menyimpan pesan berdasarkan pengguna, dan dua cluster anggota obrolan dan obrolan anggota yang menyimpan data tentang ruang multi-obrolan dan pengguna di dalamnya. Bagaimana cara beralih dari ini ke mesin pengguna dan mesin obrolan baru?

obrolan anggota dalam skema lama digunakan terutama untuk optimasi. Kami dengan cepat mentransfer data yang diperlukan ke anggota obrolan, dan kemudian tidak lagi berpartisipasi dalam proses migrasi.

Antrian untuk anggota obrolan. Ini mencakup 100 instance, sedangkan mesin obrolan memiliki 4 ribu. Untuk mentransfer data, Anda harus mematuhinya - untuk ini, anggota obrolan dibagi menjadi 4 ribu salinan yang sama, dan kemudian pembacaan binlog anggota obrolan diaktifkan di mesin obrolan.

Sekarang mesin obrolan mengetahui tentang multi-obrolan dari anggota obrolan, tetapi belum mengetahui apa pun tentang dialog dengan dua lawan bicara. Dialog semacam itu terletak di mesin teks dengan referensi ke pengguna. Di sini kami mengambil data secara langsung: setiap mesin obrolan menanyakan semua mesin teks apakah mereka memiliki dialog yang diperlukan.

Hebat - mesin obrolan mengetahui obrolan multi-obrolan apa yang ada dan mengetahui dialog apa yang ada.
Anda perlu menggabungkan pesan dalam obrolan multi-obrolan sehingga Anda mendapatkan daftar pesan di setiap obrolan. Pertama, mesin obrolan mengambil dari mesin teks semua pesan pengguna dari obrolan ini. Dalam beberapa kasus, jumlahnya cukup banyak (hingga ratusan juta), tetapi dengan pengecualian yang sangat jarang, obrolan tersebut sepenuhnya cocok dengan RAM. Kami memiliki pesan yang tidak berurutan, masing-masing dalam beberapa salinan - lagipula, semuanya diambil dari mesin teks berbeda yang sesuai dengan pengguna. Tujuannya adalah untuk menyortir pesan dan membuang salinan yang memakan ruang yang tidak perlu.

Setiap pesan memiliki stempel waktu yang berisi waktu pengiriman dan teks. Kami menggunakan waktu untuk menyortir - kami menempatkan penunjuk ke pesan terlama dari peserta multichat dan membandingkan hash dari teks salinan yang dimaksud, bergerak ke arah peningkatan stempel waktu. Adalah logis bahwa salinan akan memiliki hash dan stempel waktu yang sama, namun dalam praktiknya hal ini tidak selalu terjadi. Seperti yang Anda ingat, sinkronisasi dalam skema lama dilakukan oleh PHP - dan dalam kasus yang jarang terjadi, waktu pengiriman pesan yang sama berbeda untuk pengguna yang berbeda. Dalam kasus ini, kami membiarkan diri kami mengedit stempel waktu - biasanya dalam satu detik. Masalah kedua adalah perbedaan urutan pesan untuk penerima yang berbeda. Dalam kasus seperti itu, kami mengizinkan pembuatan salinan tambahan, dengan opsi pemesanan berbeda untuk pengguna berbeda.

Setelah ini, data tentang pesan di multichat dikirim ke mesin pengguna. Dan inilah fitur yang tidak menyenangkan dari pesan yang diimpor. Dalam pengoperasian normal, pesan yang masuk ke mesin diurutkan secara ketat dalam urutan menaik berdasarkan user_local_id. Pesan yang diimpor dari mesin lama ke mesin pengguna kehilangan properti berguna ini. Pada saat yang sama, untuk kenyamanan pengujian, Anda harus dapat mengaksesnya dengan cepat, mencari sesuatu di dalamnya, dan menambahkan yang baru.

Kami menggunakan struktur data khusus untuk menyimpan pesan yang diimpor.

Ini mewakili ukuran vektor dimana semua orang - berbeda dan diurutkan dalam urutan menurun, dengan urutan elemen khusus. Di setiap segmen dengan indeks elemen diurutkan. Mencari elemen dalam struktur seperti itu membutuhkan waktu melalui pencarian biner. Penambahan suatu elemen diamortisasi .

Jadi, kami menemukan cara mentransfer data dari mesin lama ke mesin baru. Namun proses ini memakan waktu beberapa hari - dan kecil kemungkinannya selama hari-hari tersebut pengguna kami akan melepaskan kebiasaan menulis satu sama lain. Agar tidak kehilangan pesan selama ini, kami beralih ke skema kerja yang menggunakan cluster lama dan baru.

Data ditulis ke anggota obrolan dan mesin pengguna (dan bukan ke mesin teks, seperti dalam operasi normal menurut skema lama). mesin pengguna memproksi permintaan ke mesin obrolan - dan di sini perilakunya bergantung pada apakah obrolan ini sudah digabungkan atau belum. Jika obrolan belum digabungkan, mesin obrolan tidak menulis pesan itu sendiri, dan pemrosesannya hanya terjadi di mesin teks. Jika obrolan telah digabungkan ke dalam mesin obrolan, ia akan mengembalikan chat_local_id ke mesin pengguna dan mengirimkan pesan ke semua penerima. mesin pengguna memproksi semua data ke mesin teks - sehingga jika terjadi sesuatu, kami selalu dapat memutar kembali, dengan semua data terkini ada di mesin lama. mesin teks mengembalikan user_local_id, yang disimpan oleh mesin pengguna dan dikembalikan ke backend.

Hasilnya, proses transisi terlihat seperti ini: kami menghubungkan cluster mesin pengguna dan mesin obrolan yang kosong. mesin obrolan membaca seluruh binlog anggota obrolan, lalu proksi dimulai sesuai dengan skema yang dijelaskan di atas. Kami mentransfer data lama, kami mendapatkan dua cluster yang disinkronkan (lama dan baru). Yang tersisa hanyalah mengalihkan pembacaan dari mesin teks ke mesin pengguna dan menonaktifkan proxy.

Temuan

Berkat pendekatan baru ini, semua metrik kinerja mesin telah ditingkatkan dan masalah konsistensi data telah teratasi. Sekarang kami dapat dengan cepat menerapkan fitur-fitur baru dalam pesan (dan sudah mulai melakukan ini - kami meningkatkan jumlah maksimum peserta obrolan, menerapkan pencarian pesan yang diteruskan, meluncurkan pesan yang disematkan, dan menaikkan batas jumlah total pesan per pengguna) .

Perubahan logika sungguh luar biasa. Dan saya ingin mencatat bahwa ini tidak selalu berarti pengembangan selama bertahun-tahun oleh tim yang besar dan banyak sekali baris kode. mesin obrolan dan mesin pengguna bersama dengan semua cerita tambahan seperti Huffman untuk kompresi pesan, pohon Splay dan struktur untuk pesan yang diimpor kurang dari 20 ribu baris kode. Dan mereka ditulis oleh 3 pengembang hanya dalam 10 bulan (namun, perlu diingat hal itu semua tiga pengembang - juara dunia dalam program olahraga).

Selain itu, alih-alih menggandakan jumlah server, kami mengurangi jumlahnya hingga setengahnya - sekarang mesin pengguna dan mesin obrolan hidup di 500 mesin fisik, sementara skema baru memiliki ruang beban yang besar. Kami menghemat banyak uang untuk peralatan - sekitar $5 juta + $750 ribu per tahun untuk biaya operasional.

Kami berusaha keras untuk menemukan solusi terbaik untuk masalah yang paling kompleks dan berskala besar. Kami memiliki banyak pengembang - dan itulah sebabnya kami mencari pengembang berbakat di departemen basis data. Jika Anda menyukai dan mengetahui cara memecahkan masalah seperti itu, memiliki pengetahuan yang sangat baik tentang algoritma dan struktur data, kami mengundang Anda untuk bergabung dengan tim. Hubungi kami HRuntuk rincian.

Meskipun cerita ini bukan tentang Anda, harap diingat bahwa kami menghargai rekomendasi. Ceritakan pada teman tentang lowongan pengembang, dan jika dia berhasil menyelesaikan masa percobaan, Anda akan menerima bonus 100 ribu rubel.

Sumber: www.habr.com