Lakukan pengoptimalan di VictoriaMetrics. Alexander Vallyalkin

Saya sarankan Anda membaca transkrip laporan akhir tahun 2019 oleh Alexander Valyalkin “Optimasi Go di VictoriaMetrics”

VictoriaMetrik — DBMS yang cepat dan terukur untuk menyimpan dan memproses data dalam bentuk deret waktu (catatan berupa waktu dan sekumpulan nilai yang sesuai dengan waktu ini, misalnya, diperoleh melalui jajak pendapat berkala terhadap status sensor atau kumpulan metrik).

Berikut ini tautan ke video laporan ini - https://youtu.be/MZ5P21j_HLE

Slide

Ceritakan kepada kami tentang diri Anda. Saya Alexander Valyalkin. Di Sini akun GitHub saya. Saya tertarik dengan Go dan optimalisasi kinerja. Saya menulis banyak perpustakaan yang berguna dan tidak terlalu berguna. Mereka memulai dengan keduanya fast, atau dengan quick awalan.

Saat ini saya sedang mengerjakan VictoriaMetrics. Ada apa dan apa yang aku lakukan di sana? Saya akan membicarakan hal ini dalam presentasi ini.

Garis besar laporannya adalah sebagai berikut:

• Pertama, saya akan memberi tahu Anda apa itu VictoriaMetrics.
• Lalu saya akan memberi tahu Anda apa itu deret waktu.
• Lalu saya akan memberi tahu Anda cara kerja database deret waktu.
• Selanjutnya, saya akan memberi tahu Anda tentang arsitektur database: terdiri dari apa.
• Lalu mari beralih ke pengoptimalan yang dimiliki VictoriaMetrics. Ini adalah optimasi untuk indeks terbalik dan optimasi untuk implementasi bitset di Go.

Apakah ada penonton yang mengetahui apa itu VictoriaMetrics? Wah, sudah banyak yang tahu. Ini kabar baik. Bagi yang belum tahu, ini adalah database deret waktu. Hal ini didasarkan pada arsitektur ClickHouse, pada beberapa rincian implementasi ClickHouse. Misalnya seperti: MergeTree, perhitungan paralel pada semua inti prosesor yang tersedia dan optimalisasi kinerja dengan mengerjakan blok data yang ditempatkan di cache prosesor.

VictoriaMetrics memberikan kompresi data yang lebih baik dibandingkan database deret waktu lainnya.

Skalanya vertikal - yaitu, Anda dapat menambahkan lebih banyak prosesor, lebih banyak RAM pada satu komputer. VictoriaMetrics akan berhasil memanfaatkan sumber daya yang tersedia dan akan meningkatkan produktivitas linier.

VictoriaMetrics juga menskalakan secara horizontal - yaitu, Anda dapat menambahkan node tambahan ke cluster VictoriaMetrics, dan kinerjanya akan meningkat hampir secara linier.

Seperti yang Anda duga, VictoriaMetrics adalah database yang cepat, karena saya tidak bisa menulis yang lain. Dan itu tertulis di Go, jadi saya membicarakannya di pertemuan ini.

Siapa yang tahu apa itu deret waktu? Dia juga kenal banyak orang. Deret waktu adalah rangkaian pasangan (timestamp, значение), yang mana pasangan ini diurutkan berdasarkan waktu. Nilainya adalah angka floating point – float64.

Setiap deret waktu diidentifikasi secara unik dengan sebuah kunci. Terdiri dari apa kunci ini? Ini terdiri dari sekumpulan pasangan nilai kunci yang tidak kosong.

Berikut adalah contoh deret waktu. Kunci dari rangkaian ini adalah daftar pasangan: __name__="cpu_usage" adalah nama metriknya, instance="my-server" - ini adalah komputer tempat metrik ini dikumpulkan, datacenter="us-east" - ini adalah pusat data tempat komputer ini berada.

Kami mendapatkan nama deret waktu yang terdiri dari tiga pasangan nilai kunci. Kunci ini sesuai dengan daftar pasangan (timestamp, value). t1, t3, t3, ..., tN - ini adalah stempel waktu, 10, 20, 12, ..., 15 — nilai yang sesuai. Ini adalah penggunaan CPU pada waktu tertentu untuk seri tertentu.

Di mana deret waktu dapat digunakan? Apakah ada yang tahu?

• Di DevOps, Anda dapat mengukur CPU, RAM, jaringan, rps, jumlah kesalahan, dll.
• IoT - kita dapat mengukur suhu, tekanan, koordinat geografis, dan lainnya.
• Juga keuangan – kita dapat memantau harga semua jenis saham dan mata uang.
• Selain itu, time series dapat digunakan dalam memantau proses produksi di pabrik. Kami memiliki pengguna yang menggunakan VictoriaMetrics untuk memantau turbin angin, untuk robot.
• Deret waktu juga berguna untuk mengumpulkan informasi dari sensor berbagai perangkat. Misalnya untuk mesin; untuk mengukur tekanan ban; untuk mengukur kecepatan, jarak; untuk mengukur konsumsi bensin, dll.
• Deret waktu juga dapat digunakan untuk memantau pesawat. Setiap pesawat memiliki kotak hitam yang mengumpulkan rangkaian waktu untuk berbagai parameter kesehatan pesawat. Deret waktu juga digunakan dalam industri dirgantara.
• Pelayanan kesehatan adalah tekanan darah, denyut nadi, dll.

Mungkin masih banyak lagi aplikasi yang saya lupa, tapi saya harap Anda memahami bahwa deret waktu banyak digunakan di dunia modern. Dan volume penggunaannya terus meningkat setiap tahunnya.

Mengapa Anda memerlukan database deret waktu? Mengapa Anda tidak bisa menggunakan database relasional biasa untuk menyimpan deret waktu?

Karena deret waktu biasanya berisi informasi dalam jumlah besar, sehingga sulit untuk disimpan dan diproses dalam database konvensional. Oleh karena itu, database khusus untuk deret waktu muncul. Pangkalan ini secara efektif menyimpan poin (timestamp, value) dengan kunci yang diberikan. Mereka menyediakan API untuk membaca data yang disimpan berdasarkan kunci, dengan satu pasangan nilai kunci, atau dengan beberapa pasangan nilai kunci, atau dengan regexp. Misalnya, Anda ingin mengetahui beban CPU semua layanan Anda di pusat data di Amerika, maka Anda perlu menggunakan pseudo-query ini.

Biasanya database deret waktu menyediakan bahasa kueri khusus karena SQL deret waktu tidak terlalu cocok. Meskipun ada database yang mendukung SQL, namun kurang cocok. Bahasa kueri seperti PromQL, masuknyaQL, Aliran, Q. Saya harap seseorang pernah mendengar setidaknya satu dari bahasa-bahasa ini. Banyak orang mungkin pernah mendengar tentang PromQL. Ini adalah bahasa kueri Prometheus.

Ini adalah tampilan arsitektur database deret waktu modern dengan menggunakan VictoriaMetrics sebagai contoh.

Ini terdiri dari dua bagian. Ini adalah penyimpanan untuk indeks terbalik dan penyimpanan untuk nilai deret waktu. Repositori ini dipisahkan.

Ketika catatan baru tiba di database, pertama-tama kita mengakses indeks terbalik untuk menemukan pengidentifikasi deret waktu untuk kumpulan tertentu label=value untuk metrik tertentu. Kami menemukan pengidentifikasi ini dan menyimpan nilainya di penyimpanan data.

Ketika ada permintaan untuk mengambil data dari TSDB, pertama-tama kita pergi ke indeks terbalik. Ayo dapatkan semuanya timeseries_ids catatan yang cocok dengan kumpulan ini label=value. Dan kemudian kami mendapatkan semua data yang diperlukan dari gudang data, diindeks oleh timeseries_ids.

Mari kita lihat contoh bagaimana database deret waktu memproses kueri pemilihan yang masuk.

• Pertama-tama dia mendapatkan segalanya timeseries_ids dari indeks terbalik yang berisi pasangan tertentu label=value, atau memenuhi ekspresi reguler tertentu.
• Kemudian ia mengambil semua titik data dari penyimpanan data pada interval waktu tertentu untuk titik data yang ditemukan timeseries_ids.
• Setelah ini, database melakukan beberapa penghitungan pada titik data tersebut, sesuai dengan permintaan pengguna. Dan setelah itu mengembalikan jawabannya.

Dalam presentasi ini saya akan bercerita tentang bagian pertama. Ini adalah pencarian timeseries_ids dengan indeks terbalik. Anda dapat menonton bagian kedua dan bagian ketiga nanti Sumber VictoriaMetrics, atau tunggu sampai saya menyiapkan laporan lainnya :)

Mari beralih ke indeks terbalik. Mungkin banyak yang menganggap ini sederhana. Siapa yang tahu apa itu indeks terbalik dan cara kerjanya? Oh, tidak banyak orang lagi. Mari kita coba memahami apa itu.

Ini sebenarnya sederhana. Ini hanyalah kamus yang memetakan kunci ke suatu nilai. Apa itu kunci? Pasangan ini label=valueDimana label и value - ini adalah garis. Dan nilai-nilainya adalah himpunan timeseries_ids, yang mencakup pasangan tertentu label=value.

Indeks terbalik memungkinkan Anda menemukan semuanya dengan cepat timeseries_ids, yang telah diberikan label=value.

Ini juga memungkinkan Anda menemukannya dengan cepat timeseries_ids deret waktu untuk beberapa pasangan label=value, atau untuk pasangan label=regexp. Bagaimana ini bisa terjadi? Dengan mencari perpotongan himpunan tersebut timeseries_ids untuk setiap pasangan label=value.

Mari kita lihat berbagai implementasi indeks terbalik. Mari kita mulai dengan implementasi naif yang paling sederhana. Dia terlihat seperti ini.

Fungsi getMetricIDs mendapat daftar string. Setiap baris berisi label=value. Fungsi ini mengembalikan daftar metricIDs.

Bagaimana itu bekerja? Di sini kita memiliki variabel global yang disebut invertedIndex. Ini adalah kamus biasa (map), yang akan memetakan string untuk mengiris int. Baris tersebut berisi label=value.

Implementasi fungsi: dapatkan metricIDs untuk yang pertama label=value, lalu kita membahas yang lainnya label=value, kami mengerti metricIDs untuk mereka. Dan panggil fungsinya intersectInts, yang akan dibahas di bawah ini. Dan fungsi ini mengembalikan perpotongan daftar ini.

Seperti yang Anda lihat, menerapkan indeks terbalik tidak terlalu rumit. Namun ini adalah implementasi yang naif. Apa kekurangannya? Kerugian utama dari implementasi naif adalah indeks terbalik disimpan dalam RAM. Setelah memulai ulang aplikasi, kami kehilangan indeks ini. Tidak ada penyimpanan indeks ini ke disk. Indeks terbalik seperti itu sepertinya tidak cocok untuk database.

Kelemahan kedua juga terkait dengan memori. Indeks terbalik harus masuk ke dalam RAM. Jika melebihi ukuran RAM, maka jelas kita akan mendapatkan error out of memory. Dan programnya tidak akan berhasil.

Masalah ini dapat diselesaikan dengan menggunakan solusi siap pakai seperti TingkatDBAtau BatuDB.

Singkatnya, kita memerlukan database yang memungkinkan kita melakukan tiga operasi dengan cepat.

• Operasi pertama adalah perekaman ключ-значение ke basis data ini. Dia melakukan ini dengan sangat cepat, di mana ключ-значение adalah string sewenang-wenang.
• Operasi kedua adalah pencarian cepat untuk suatu nilai menggunakan kunci yang diberikan.
• Dan operasi ketiga adalah pencarian cepat untuk semua nilai dengan awalan tertentu.

LevelDB dan RocksDB - database ini dikembangkan oleh Google dan Facebook. Pertama datang LevelDB. Kemudian orang-orang dari Facebook mengambil LevelDB dan mulai memperbaikinya, mereka membuat RocksDB. Sekarang hampir semua database internal berfungsi di RocksDB di dalam Facebook, termasuk yang telah ditransfer ke RocksDB dan MySQL. Mereka menamainya Batuku.

Indeks terbalik dapat diimplementasikan menggunakan LevelDB. Bagaimana cara melakukannya? Kami menyimpan sebagai kunci label=value. Dan nilainya adalah pengidentifikasi deret waktu di mana pasangan tersebut berada label=value.

Jika kita memiliki banyak deret waktu dengan pasangan tertentu label=value, maka akan ada banyak baris dalam database ini dengan kunci yang sama dan berbeda timeseries_ids. Untuk mendapatkan daftar semuanya timeseries_ids, yang dimulai dengan ini label=prefix, kami melakukan pemindaian rentang yang database ini dioptimalkan. Artinya, kita memilih semua baris yang dimulai dengan label=prefix dan dapatkan yang diperlukan timeseries_ids.

Berikut ini contoh implementasi tampilannya di Go. Kami memiliki indeks terbalik. Ini adalah LevelDB.

Fungsinya sama dengan implementasi naif. Ini mengulangi implementasi yang naif hampir baris demi baris. Satu-satunya poin adalah alih-alih beralih ke map kami mengakses indeks terbalik. Kami mendapatkan semua nilai untuk yang pertama label=value. Lalu kita memeriksa semua pasangan yang tersisa label=value dan dapatkan kumpulan ID metrik yang sesuai untuknya. Kemudian kita menemukan persimpangannya.

Segalanya tampak baik-baik saja, tetapi solusi ini memiliki kelemahan. VictoriaMetrics awalnya menerapkan indeks terbalik berdasarkan LevelDB. Namun pada akhirnya saya harus menyerah.

Mengapa? Karena LevelDB lebih lambat dibandingkan implementasi naif. Dalam implementasi yang naif, jika diberikan kunci tertentu, kami segera mengambil seluruh potongan metricIDs. Ini adalah operasi yang sangat cepat - seluruh irisan siap digunakan.

Di LevelDB, setiap kali suatu fungsi dipanggil GetValues Anda harus melalui semua jalur yang dimulai dengan label=value. Dan dapatkan nilai untuk setiap baris timeseries_ids. Seperti itu timeseries_ids kumpulkan sepotong ini timeseries_ids. Tentu saja, ini jauh lebih lambat daripada sekadar mengakses peta biasa dengan kunci.

Kelemahan kedua adalah LevelDB ditulis dalam C. Memanggil fungsi C dari Go tidak terlalu cepat. Dibutuhkan ratusan nanodetik. Ini tidak terlalu cepat, karena dibandingkan dengan pemanggilan fungsi biasa yang ditulis dalam go, yang memerlukan waktu 1-5 nanodetik, perbedaan performanya puluhan kali lipat. Bagi VictoriaMetrics, ini adalah kesalahan fatal :)

Jadi saya menulis implementasi indeks terbalik saya sendiri. Dan dia meneleponnya penggabungan.

Mergeset didasarkan pada struktur data MergeTree. Struktur data ini dipinjam dari ClickHouse. Jelasnya, mergeset harus dioptimalkan untuk pencarian cepat timeseries_ids sesuai dengan kunci yang diberikan. Mergeset seluruhnya ditulis di Go. Anda bisa melihat Sumber VictoriaMetrics di GitHub. Implementasi mergeset ada di dalam folder /lib/mergeset. Anda dapat mencoba mencari tahu apa yang terjadi di sana.

API mergeset sangat mirip dengan LevelDB dan RocksDB. Artinya, ini memungkinkan Anda dengan cepat menyimpan catatan baru di sana dan dengan cepat memilih catatan berdasarkan awalan tertentu.

Kita akan membicarakan kerugian dari mergeset nanti. Sekarang mari kita bicara tentang masalah apa yang muncul dengan VictoriaMetrics dalam produksi saat menerapkan indeks terbalik.

Mengapa hal itu muncul?

Alasan pertama adalah tingginya churn rate. Diterjemahkan ke dalam bahasa Rusia, ini adalah perubahan deret waktu yang sering terjadi. Ini adalah saat rangkaian waktu berakhir dan rangkaian waktu baru dimulai, atau banyak rangkaian waktu baru dimulai. Dan ini sering terjadi.

Alasan kedua adalah banyaknya rangkaian waktu. Pada awalnya, ketika pemantauan mulai populer, jumlah deret waktu hanya sedikit. Misalnya, untuk setiap komputer Anda perlu memonitor CPU, memori, jaringan dan beban disk. 4 deret waktu per komputer. Katakanlah Anda memiliki 100 komputer dan 400 deret waktu. Ini sangat sedikit.

Seiring waktu, orang-orang menyadari bahwa mereka dapat mengukur informasi yang lebih terperinci. Misalnya, ukur beban bukan seluruh prosesor, tetapi masing-masing inti prosesor secara terpisah. Jika Anda memiliki 40 inti prosesor, maka Anda memiliki deret waktu 40 kali lebih banyak untuk mengukur beban prosesor.

Tapi itu belum semuanya. Setiap inti prosesor dapat memiliki beberapa status, misalnya idle, saat idle. Dan juga bekerja di ruang pengguna, bekerja di ruang kernel, dan status lainnya. Dan masing-masing keadaan tersebut juga dapat diukur sebagai rangkaian waktu yang terpisah. Ini juga menambah jumlah baris sebanyak 7-8 kali lipat.

Dari satu metrik kami mendapatkan 40 x 8 = 320 metrik hanya untuk satu komputer. Kalikan dengan 100, kita mendapatkan 32, bukan 000.

Kemudian Kubernetes hadir. Dan keadaan menjadi lebih buruk karena Kubernetes dapat menghosting banyak layanan berbeda. Setiap layanan di Kubernetes terdiri dari banyak pod. Dan semua ini perlu diawasi. Selain itu, kami terus menerapkan versi baru layanan Anda. Untuk setiap versi baru, rangkaian waktu baru harus dibuat. Akibatnya, jumlah deret waktu bertambah secara eksponensial dan kita dihadapkan pada masalah deret waktu dalam jumlah besar, yang disebut kardinalitas tinggi. VictoriaMetrics berhasil mengatasinya dibandingkan dengan database deret waktu lainnya.

Mari kita lihat lebih dekat tingkat churn yang tinggi. Apa yang menyebabkan tingginya churn rate dalam produksi? Karena beberapa arti label dan tag terus berubah.

Misalnya saja Kubernetes yang memiliki konsep tersebut deployment, yaitu ketika versi baru aplikasi Anda diluncurkan. Untuk beberapa alasan, pengembang Kubernetes memutuskan untuk menambahkan id penerapan ke label.

Hal ini menyebabkan apa? Selain itu, dengan setiap penerapan baru, semua rangkaian waktu lama diinterupsi, dan sebagai gantinya, rangkaian waktu baru dimulai dengan nilai label baru deployment_id. Mungkin ada ratusan ribu bahkan jutaan baris seperti itu.

Yang penting dari semua ini adalah jumlah total deret waktu bertambah, namun jumlah deret waktu yang sedang aktif dan menerima data tetap konstan. Keadaan ini disebut tingkat churn yang tinggi.

Masalah utama dari tingkat churn yang tinggi adalah memastikan kecepatan pencarian yang konstan untuk semua rangkaian waktu untuk kumpulan label tertentu selama interval waktu tertentu. Biasanya ini adalah interval waktu selama satu jam terakhir atau hari terakhir.

Bagaimana cara mengatasi masalah ini? Inilah opsi pertama. Ini untuk membagi indeks terbalik menjadi bagian-bagian independen dari waktu ke waktu. Artinya, beberapa interval waktu berlalu, kami selesai bekerja dengan indeks terbalik saat ini. Dan buat indeks terbalik baru. Interval waktu lain berlalu, kita membuat interval waktu yang lain dan yang lainnya.

Dan saat mengambil sampel dari indeks terbalik ini, kami menemukan sekumpulan indeks terbalik yang berada dalam interval tertentu. Dan karenanya, kami memilih id deret waktu dari sana.

Ini menghemat sumber daya karena kita tidak perlu melihat bagian-bagian yang tidak termasuk dalam interval yang ditentukan. Artinya, biasanya jika kita memilih data untuk satu jam terakhir, maka untuk interval waktu sebelumnya kita melewatkan permintaan.

Ada pilihan lain untuk mengatasi masalah ini. Ini untuk menyimpan setiap hari daftar id deret waktu terpisah yang terjadi pada hari itu.

Keuntungan solusi ini dibandingkan solusi sebelumnya adalah kami tidak menduplikasi informasi deret waktu yang tidak hilang seiring berjalannya waktu. Mereka selalu hadir dan tidak berubah.

Kerugiannya adalah solusi seperti itu lebih sulit diterapkan dan lebih sulit di-debug. Dan VictoriaMetrics memilih solusi ini. Inilah yang terjadi secara historis. Solusi ini juga memiliki kinerja yang baik dibandingkan dengan solusi sebelumnya. Karena solusi ini tidak diterapkan karena perlunya duplikasi data di setiap partisi agar deret waktu tidak berubah, yaitu tidak hilang seiring berjalannya waktu. VictoriaMetrics terutama dioptimalkan untuk konsumsi ruang disk, dan implementasi sebelumnya memperburuk konsumsi ruang disk. Namun implementasi ini lebih cocok untuk meminimalkan konsumsi ruang disk, sehingga dipilih.

Saya harus melawannya. Perjuangannya adalah dalam implementasi ini Anda masih harus memilih jumlah yang jauh lebih besar timeseries_ids untuk data dibandingkan ketika indeks terbalik dipartisi waktu.

Bagaimana kami mengatasi masalah ini? Kami menyelesaikannya dengan cara yang orisinal - dengan menyimpan beberapa pengidentifikasi deret waktu di setiap entri indeks terbalik, bukan satu pengidentifikasi. Artinya, kita punya kuncinya label=value, yang terjadi di setiap deret waktu. Dan sekarang kami menyimpan beberapa timeseries_ids dalam satu entri.

Berikut ini contohnya. Sebelumnya kami memiliki N entri, tetapi sekarang kami memiliki satu entri yang awalannya sama dengan entri lainnya. Untuk entri sebelumnya, nilainya berisi semua id deret waktu.

Hal ini memungkinkan untuk meningkatkan kecepatan pemindaian indeks terbalik hingga 10 kali lipat. Dan ini memungkinkan kami mengurangi konsumsi memori untuk cache, karena sekarang kami menyimpan stringnya label=value hanya sekali di cache bersama N kali. Dan baris ini bisa menjadi besar jika Anda menyimpan baris panjang di tag dan label Anda, yang mana Kubernetes suka memasukkannya ke sana.

Pilihan lain untuk mempercepat pencarian pada indeks terbalik adalah sharding. Membuat beberapa indeks terbalik, bukan satu, dan membagi data di antara indeks tersebut berdasarkan kunci. Ini adalah satu set key=value uap. Artinya, kita mendapatkan beberapa indeks terbalik independen, yang dapat kita kueri secara paralel pada beberapa prosesor. Implementasi sebelumnya hanya mengizinkan operasi dalam mode prosesor tunggal, yaitu memindai data hanya pada satu inti. Solusi ini memungkinkan Anda memindai data pada beberapa inti sekaligus, seperti yang dilakukan ClickHouse. Inilah yang kami rencanakan untuk diterapkan.

Sekarang mari kita kembali ke domba kita - ke fungsi persimpangan timeseries_ids. Mari kita pertimbangkan implementasi apa saja yang mungkin ada. Fungsi ini memungkinkan Anda menemukannya timeseries_ids untuk himpunan tertentu label=value.

Opsi pertama adalah implementasi yang naif. Dua loop bersarang. Di sini kita mendapatkan input fungsi intersectInts dua potong - a и b. Pada output, kita harus mengembalikan perpotongan irisan ini.

Implementasi yang naif terlihat seperti ini. Kami mengulangi semua nilai dari irisan a, di dalam loop ini kita menelusuri semua nilai irisan b. Dan kami membandingkannya. Jika cocok, maka kita telah menemukan persimpangan. Dan simpan di dalamnya result.

Apa kerugiannya? Kompleksitas kuadrat adalah kelemahan utamanya. Misalnya, jika dimensi Anda berupa irisan a и b satu juta sekaligus, maka fungsi ini tidak akan pernah memberikan jawaban kepada Anda. Karena diperlukan satu triliun iterasi, jumlah yang banyak bahkan untuk komputer modern.

Implementasi kedua didasarkan pada peta. Kami membuat peta. Kami memasukkan semua nilai dari irisan ke dalam peta ini a. Lalu kita melewati irisan dalam loop terpisah b. Dan kami memeriksa apakah nilai ini berasal dari irisan b di peta. Jika ada, tambahkan ke hasilnya.

Apa manfaatnya? Keuntungannya adalah hanya terdapat kompleksitas linier. Artinya, fungsi tersebut akan dijalankan lebih cepat untuk irisan yang lebih besar. Untuk potongan berukuran jutaan, fungsi ini akan dijalankan dalam 2 juta iterasi, dibandingkan dengan triliun iterasi pada fungsi sebelumnya.

Kelemahannya adalah fungsi ini memerlukan lebih banyak memori untuk membuat peta ini.

Kelemahan kedua adalah overhead yang besar untuk hashing. Kelemahan ini tidak terlalu kentara. Dan bagi kami itu juga tidak terlalu kentara, jadi pada awalnya di VictoriaMetrics penerapan persimpangan melalui peta. Namun kemudian pembuatan profil menunjukkan bahwa waktu prosesor utama dihabiskan untuk menulis ke peta dan memeriksa keberadaan nilai di peta ini.

Mengapa waktu CPU terbuang sia-sia di tempat-tempat ini? Karena Go melakukan operasi hashing pada baris ini. Artinya, ia menghitung hash kunci untuk kemudian mengaksesnya pada indeks tertentu di HashMap. Operasi perhitungan hash selesai dalam puluhan nanodetik. Ini lambat untuk VictoriaMetrics.

Saya memutuskan untuk menerapkan bitset yang dioptimalkan khusus untuk kasus ini. Seperti inilah perpotongan dua irisan sekarang. Di sini kita membuat bitset. Kami menambahkan elemen dari irisan pertama ke dalamnya. Kemudian kita periksa keberadaan elemen tersebut pada irisan kedua. Dan tambahkan ke hasilnya. Artinya, hampir tidak ada bedanya dengan contoh sebelumnya. Satu-satunya hal di sini adalah kami mengganti akses ke peta dengan fungsi khusus add и has.

Pada pandangan pertama, tampaknya ini akan bekerja lebih lambat, jika sebelumnya peta standar digunakan di sana, dan kemudian beberapa fungsi lain dipanggil, tetapi pembuatan profil menunjukkan bahwa hal ini bekerja 10 kali lebih cepat daripada peta standar dalam kasus VictoriaMetrics.

Selain itu, ia menggunakan lebih sedikit memori dibandingkan dengan implementasi peta. Karena kami menyimpan bit di sini, bukan nilai delapan byte.

Kekurangan dari penerapan ini adalah tidak begitu kentara dan tidak sepele.

Kelemahan lain yang mungkin tidak disadari oleh banyak orang adalah implementasi ini mungkin tidak berfungsi dengan baik dalam beberapa kasus. Artinya, ini dioptimalkan untuk kasus tertentu, untuk kasus perpotongan id deret waktu VictoriaMetrics. Ini tidak berarti cocok untuk semua kasus. Jika digunakan secara tidak benar, kita tidak akan mendapatkan peningkatan performa, melainkan error out of memory dan penurunan performa.

Mari kita pertimbangkan penerapan struktur ini. Kalau mau dilihat, letaknya di sumber VictoriaMetrics, di dalam folder lib/uint64set. Ini dioptimalkan secara khusus untuk kasus VictoriaMetrics, di mana timeseries_id adalah nilai 64-bit, dimana 32 bit pertama pada dasarnya konstan dan hanya 32 bit terakhir yang berubah.

Struktur data ini tidak disimpan di disk, hanya beroperasi di memori.

Ini API-nya. Ini tidak terlalu rumit. API ini dirancang khusus untuk contoh spesifik penggunaan VictoriaMetrics. Artinya, tidak ada fungsi yang tidak perlu di sini. Berikut adalah fungsi yang secara eksplisit digunakan oleh VictoriaMetrics.

Ada fungsi add, yang menambah nilai baru. Ada fungsi has, yang memeriksa nilai baru. Dan ada fungsinya del, yang menghilangkan nilai. Ada fungsi pembantu len, yang mengembalikan ukuran set. Fungsi clone banyak klon. Dan fungsi appendto mengubah set ini menjadi irisan timeseries_ids.

Seperti inilah implementasi struktur data ini. set memiliki dua elemen:

• ItemsCount adalah bidang pembantu untuk mengembalikan jumlah elemen dalam satu set dengan cepat. Bidang tambahan ini dapat dilakukan tanpa bidang tambahan ini, tetapi bidang tambahan ini harus ditambahkan di sini karena VictoriaMetrics sering menanyakan panjang bitset dalam algoritmenya.

• Bidang kedua adalah buckets. Ini adalah potongan dari strukturnya bucket32. Setiap struktur menyimpan hi bidang. Ini adalah 32 bit teratas. Dan dua potong - b16his и buckets dari bucket16 struktur.

16 bit teratas dari bagian kedua dari struktur 64-bit disimpan di sini. Dan di sini bitset disimpan untuk 16 bit terbawah setiap byte.

Bucket64 terdiri dari sebuah array uint64. Panjangnya dihitung menggunakan konstanta ini. Jadi satu bucket16 maksimum dapat disimpan 2^16=65536 sedikit. Jika Anda membaginya dengan 8, maka hasilnya adalah 8 kilobyte. Kalau dibagi 8 lagi jadi 1000 uint64 arti. Itu adalah Bucket16 – ini adalah struktur 8 kilobyte kami.

Mari kita lihat bagaimana salah satu metode struktur untuk menambahkan nilai baru ini diterapkan.

Semuanya dimulai dengan uint64 makna. Kami menghitung 32 bit atas, kami menghitung 32 bit bawah. Mari kita lalui semuanya buckets. Kami membandingkan 32 bit teratas di setiap keranjang dengan nilai tambah. Dan jika cocok, maka kita panggil fungsinya add dalam struktur b32 buckets. Dan tambahkan 32 bit bawah di sana. Dan jika itu kembali true, maka ini berarti kami menambahkan nilai tersebut di sana dan kami tidak memiliki nilai tersebut. Jika itu kembali false, maka makna seperti itu sudah ada. Kemudian kita menambah jumlah elemen dalam struktur.

Jika kami belum menemukan yang Anda butuhkan bucket dengan nilai hi yang diperlukan, lalu kita memanggil fungsinya addAlloc, yang akan menghasilkan yang baru bucket, menambahkannya ke struktur ember.

Ini adalah implementasi fungsinya b32.add. Hal ini serupa dengan penerapan sebelumnya. Kami menghitung 16 bit paling signifikan, 16 bit paling signifikan.

Lalu kita menelusuri semua 16 bit teratas. Kami menemukan kecocokan. Dan jika ada kecocokan, kami memanggil metode penambahan, yang akan kami pertimbangkan di halaman berikutnya bucket16.

Dan inilah level terendah yang harus dioptimalkan semaksimal mungkin. Kami menghitung untuk uint64 nilai id dalam bit irisan dan juga bitmask. Ini adalah topeng untuk nilai 64-bit tertentu, yang dapat digunakan untuk memeriksa keberadaan bit ini, atau mengaturnya. Kami memeriksa untuk melihat apakah bit ini disetel dan menyetelnya, dan mengembalikan keberadaan. Ini adalah implementasi kami, yang memungkinkan kami mempercepat pengoperasian id deret waktu yang berpotongan sebanyak 10 kali lipat dibandingkan peta konvensional.

Selain pengoptimalan ini, VictoriaMetrics memiliki banyak pengoptimalan lainnya. Sebagian besar pengoptimalan ini ditambahkan karena suatu alasan, tetapi setelah membuat profil kode dalam produksi.

Ini adalah aturan utama optimasi - jangan menambahkan optimasi dengan asumsi akan ada hambatan di sini, karena bisa jadi tidak akan ada hambatan di sana. Optimasi biasanya menurunkan kualitas kode. Oleh karena itu, ada baiknya mengoptimalkan hanya setelah pembuatan profil dan sebaiknya dalam produksi, sehingga ini adalah data nyata. Jika ada yang tertarik, Anda dapat melihat kode sumber VictoriaMetrics dan menjelajahi optimasi lain yang ada di sana.

Saya punya pertanyaan tentang bitset. Sangat mirip dengan implementasi bool vektor C++, bitset yang dioptimalkan. Apakah Anda mengambil implementasi dari sana?

Tidak, bukan dari sana. Saat mengimplementasikan bitset ini, saya dipandu oleh pengetahuan tentang struktur rangkaian waktu id ini, yang digunakan di VictoriaMetrics. Dan strukturnya sedemikian rupa sehingga 32 bit teratas pada dasarnya konstan. 32 bit yang lebih rendah dapat berubah. Semakin rendah bitnya, semakin sering ia dapat berubah. Oleh karena itu, implementasi ini dioptimalkan secara khusus untuk struktur data ini. Implementasi C++, sejauh yang saya tahu, dioptimalkan untuk kasus umum. Jika Anda mengoptimalkan untuk kasus umum, artinya ini bukan yang paling optimal untuk kasus tertentu.

Saya juga menyarankan Anda untuk menonton laporan Alexei Milovid. Sekitar sebulan yang lalu, dia berbicara tentang optimasi di ClickHouse untuk spesialisasi tertentu. Dia hanya mengatakan bahwa dalam kasus umum, implementasi C++ atau implementasi lainnya dirancang agar rata-rata bekerja dengan baik di rumah sakit. Performanya mungkin lebih buruk daripada penerapan pengetahuan khusus seperti yang kami miliki, karena kami tahu bahwa 32 bit teratas sebagian besar konstan.

Saya punya pertanyaan kedua. Apa perbedaan mendasar dari InfluxDB?

Ada banyak perbedaan mendasar. Dalam hal kinerja dan konsumsi memori, InfluxDB dalam pengujian menunjukkan konsumsi memori 10 kali lebih banyak untuk rangkaian waktu berkardinalitas tinggi, bila Anda memiliki banyak, misalnya jutaan. Misalnya, VictoriaMetrics menggunakan 1 GB per juta baris aktif, sedangkan InfluxDB menggunakan 10 GB. Dan itu perbedaan besar.

Perbedaan mendasar kedua adalah InfluxDB memiliki bahasa kueri yang aneh - Flux dan InfluxQL. Mereka sangat tidak nyaman untuk bekerja dengan deret waktu dibandingkan dengan PromQL, yang didukung oleh VictoriaMetrics. PromQL adalah bahasa kueri dari Prometheus.

Dan satu lagi perbedaannya adalah InfluxDB memiliki model data yang sedikit aneh, dimana setiap baris dapat menyimpan beberapa field dengan kumpulan tag yang berbeda. Garis-garis ini selanjutnya dibagi menjadi berbagai tabel. Komplikasi tambahan ini mempersulit pekerjaan selanjutnya dengan database ini. Sulit untuk didukung dan dipahami.

Di VictoriaMetrics, segalanya jauh lebih sederhana. Di sana, setiap deret waktu merupakan nilai kunci. Nilainya adalah sekumpulan poin - (timestamp, value), dan kuncinya adalah himpunan label=value. Tidak ada pemisahan antara bidang dan pengukuran. Ini memungkinkan Anda untuk memilih data apa pun dan kemudian menggabungkan, menambah, mengurangi, mengalikan, membagi, tidak seperti InfluxDB di mana perhitungan antara baris yang berbeda masih belum diterapkan sejauh yang saya tahu. Kalaupun diimplementasikan, sulit, Anda harus menulis banyak kode.

Saya punya pertanyaan klarifikasi. Apakah saya memahami dengan benar bahwa ada masalah yang Anda bicarakan, bahwa indeks terbalik ini tidak muat di memori, jadi ada partisi di sana?

Pertama, saya menunjukkan implementasi naif dari indeks terbalik pada peta Go standar. Implementasi ini tidak cocok untuk database karena indeks terbalik ini tidak disimpan ke disk, dan database harus disimpan ke disk agar data ini tetap tersedia saat restart. Dalam implementasi ini, saat Anda memulai ulang aplikasi, indeks terbalik Anda akan hilang. Dan Anda akan kehilangan akses ke semua data karena Anda tidak akan dapat menemukannya.

Halo! Terima kasih atas laporannya! Nama saya Pavel. Saya dari Wildberry. Saya punya beberapa pertanyaan untuk anda. Pertanyaan pertama. Apakah menurut Anda jika Anda memilih prinsip yang berbeda saat membangun arsitektur aplikasi Anda dan mempartisi data dari waktu ke waktu, maka mungkin Anda dapat memotong data saat mencari, hanya berdasarkan fakta bahwa satu partisi berisi data untuk satu partisi? periode waktu , yaitu, dalam satu interval waktu dan Anda tidak perlu khawatir tentang fakta bahwa potongan Anda tersebar secara berbeda? Pertanyaan nomor 2 - karena Anda menerapkan algoritma serupa dengan bitset dan yang lainnya, mungkin Anda mencoba menggunakan instruksi prosesor? Mungkin Anda sudah mencoba optimasi seperti itu?

Saya akan segera menjawab yang kedua. Kita belum sampai pada titik itu. Tapi jika perlu, kami akan sampai ke sana. Dan yang pertama, apa pertanyaannya?

Anda mendiskusikan dua skenario. Dan mereka mengatakan bahwa mereka memilih yang kedua dengan implementasi yang lebih kompleks. Dan mereka tidak menyukai yang pertama, yang datanya dipartisi berdasarkan waktu.

Ya. Dalam kasus pertama, total volume indeks akan lebih besar, karena di setiap partisi kita harus menyimpan data duplikat untuk rangkaian waktu yang berlanjut melalui semua partisi ini. Dan jika tingkat churn deret waktu Anda kecil, yaitu deret yang sama terus digunakan, maka dalam kasus pertama kita akan kehilangan lebih banyak ruang disk yang ditempati dibandingkan dengan kasus kedua.

Jadi - ya, pembagian waktu adalah pilihan yang bagus. Prometheus menggunakannya. Namun Prometheus memiliki kelemahan lain. Saat menggabungkan potongan-potongan data ini, ia perlu menyimpan informasi meta memori untuk semua label dan deret waktu. Oleh karena itu, jika potongan data yang digabungkan berukuran besar, konsumsi memori akan meningkat pesat selama penggabungan, tidak seperti VictoriaMetrics. Saat menggabungkan, VictoriaMetrics tidak menggunakan memori sama sekali; hanya beberapa kilobyte yang digunakan, berapa pun ukuran potongan data yang digabungkan.

Algoritma yang Anda gunakan menggunakan memori. Ini menandai tag rangkaian waktu yang berisi nilai. Dan dengan cara ini Anda memeriksa keberadaan pasangan dalam satu larik data dan larik data lainnya. Dan Anda mengerti apakah terjadi perpotongan atau tidak. Biasanya, database mengimplementasikan kursor dan iterator yang menyimpan kontennya saat ini dan menjalankan data yang diurutkan karena kompleksitas sederhana dari operasi ini.

Mengapa kita tidak menggunakan kursor untuk melintasi data?

Ya.

Kami menyimpan baris yang diurutkan di LevelDB atau mergeset. Kita dapat menggerakkan kursor dan menemukan persimpangannya. Mengapa kita tidak menggunakannya? Karena lambat. Karena kursor berarti Anda perlu memanggil fungsi untuk setiap baris. Panggilan fungsi adalah 5 nanodetik. Dan jika Anda memiliki 100 baris, ternyata kita menghabiskan setengah detik hanya untuk memanggil fungsinya.

Ada hal seperti itu, ya. Dan pertanyaan terakhir saya. Pertanyaannya mungkin terdengar sedikit aneh. Mengapa tidak mungkin membaca semua agregat yang diperlukan pada saat data tiba dan menyimpannya dalam bentuk yang diperlukan? Mengapa menyimpan volume besar di beberapa sistem seperti VictoriaMetrics, ClickHouse, dll., lalu menghabiskan banyak waktu untuk itu?

Saya akan memberikan contoh agar lebih jelas. Katakanlah bagaimana cara kerja speedometer mainan kecil? Ini mencatat jarak yang telah Anda tempuh, sepanjang waktu menambahkannya ke satu nilai, dan yang kedua - kali. Dan membagi. Dan mendapat kecepatan rata-rata. Anda dapat melakukan hal yang sama. Tambahkan semua fakta yang diperlukan dengan cepat.

Oke, saya mengerti pertanyaannya. Teladan Anda ada tempatnya. Jika Anda mengetahui agregat apa yang Anda butuhkan, maka ini adalah penerapan terbaik. Namun masalahnya adalah orang-orang menyimpan metrik ini, beberapa data di ClickHouse dan mereka belum tahu bagaimana mereka akan menggabungkan dan memfilternya di masa mendatang, sehingga mereka harus menyimpan semua data mentah. Tetapi jika Anda tahu Anda perlu menghitung rata-rata sesuatu, mengapa tidak menghitungnya daripada menyimpan banyak nilai mentah di sana? Tapi ini hanya jika Anda tahu persis apa yang Anda butuhkan.

Omong-omong, database untuk menyimpan deret waktu mendukung penghitungan agregat. Misalnya, Prometheus mendukung aturan pencatatan. Artinya, hal ini bisa dilakukan jika Anda mengetahui unit apa saja yang akan dibutuhkan. VictoriaMetrics belum memiliki ini, tetapi biasanya didahului oleh Prometheus, yang dapat dilakukan dalam aturan pengodean ulang.

Misalnya, dalam pekerjaan saya sebelumnya, saya perlu menghitung jumlah kejadian dalam jendela geser selama satu jam terakhir. Masalahnya adalah saya harus membuat implementasi khusus di Go, yaitu layanan untuk menghitung hal ini. Pelayanan ini pada akhirnya tidak sepele, karena sulit dihitung. Penerapannya bisa sederhana jika Anda perlu menghitung beberapa agregat pada interval waktu yang tetap. Jika Anda ingin menghitung peristiwa di jendela geser, ini tidak sesederhana kelihatannya. Saya rasa ini belum diterapkan di ClickHouse atau di database deret waktu, karena sulit untuk diterapkan.

Dan satu pertanyaan lagi. Kami baru saja berbicara tentang rata-rata, dan saya ingat pernah ada yang namanya Grafit dengan backend Karbon. Dan dia tahu cara menipiskan data lama, yaitu menyisakan satu titik per menit, satu titik per jam, dan seterusnya. Pada prinsipnya, ini cukup nyaman jika kita membutuhkan data mentah, secara relatif, untuk sebulan, dan yang lainnya bisa. menjadi tipis. Namun Prometheus dan VictoriaMetrics tidak mendukung fungsi ini. Apakah direncanakan untuk mendukungnya? Jika tidak, mengapa tidak?

Terima kasih atas pertanyaannya. Pengguna kami menanyakan pertanyaan ini secara berkala. Mereka bertanya kapan kami akan menambahkan dukungan untuk downsampling. Ada beberapa masalah di sini. Pertama, setiap pengguna memahami downsampling sesuatu yang berbeda: seseorang ingin mendapatkan titik sembarang pada interval tertentu, seseorang menginginkan nilai maksimum, minimum, rata-rata. Jika banyak sistem menulis data ke database Anda, Anda tidak dapat menggabungkan semuanya. Bisa jadi tiap sistem memerlukan penjarangan yang berbeda-beda. Dan hal ini sulit untuk diterapkan.

Dan yang kedua adalah VictoriaMetrics, seperti ClickHouse, dioptimalkan untuk bekerja pada data mentah dalam jumlah besar, sehingga dapat menyekop satu miliar baris dalam waktu kurang dari satu detik jika Anda memiliki banyak inti di sistem Anda. Memindai titik deret waktu di VictoriaMetrics – 50 poin per detik per inti. Dan kinerja ini disesuaikan dengan inti yang ada. Artinya, jika Anda memiliki 000 core, misalnya, Anda akan memindai satu miliar titik per detik. Dan properti VictoriaMetrics dan ClickHouse ini mengurangi kebutuhan downsamling.

Fitur lainnya adalah VictoriaMetrics secara efektif mengompresi data ini. Kompresi rata-rata dalam produksi adalah 0,4 hingga 0,8 byte per titik. Setiap poin adalah stempel waktu + nilai. Dan rata-rata dikompresi menjadi kurang dari satu byte.

Sergei. Saya punya pertanyaan. Berapa kuantum waktu perekaman minimum?

Satu milidetik. Kami baru-baru ini melakukan percakapan dengan pengembang database deret waktu lainnya. Irisan waktu minimumnya adalah satu detik. Dan di Graphite, misalnya, juga satu detik. Di OpenTSDB juga satu detik. InfluxDB memiliki presisi nanodetik. Di VictoriaMetrics satu milidetik, karena di Prometheus satu milidetik. Dan VictoriaMetrics awalnya dikembangkan sebagai penyimpanan jarak jauh untuk Prometheus. Namun kini bisa menyimpan data dari sistem lain.

Orang yang saya ajak bicara mengatakan bahwa mereka memiliki akurasi detik ke detik - itu cukup bagi mereka karena bergantung pada jenis data yang disimpan dalam database deret waktu. Jika ini adalah data DevOps atau data dari infrastruktur, tempat Anda mengumpulkannya dengan interval 30 detik, per menit, maka akurasi kedua sudah cukup, Anda tidak memerlukan apa pun yang kurang. Dan jika Anda mengumpulkan data ini dari sistem perdagangan frekuensi tinggi, maka Anda memerlukan akurasi nanodetik.

Akurasi milidetik di VictoriaMetrics juga cocok untuk kasus DevOps, dan cocok untuk sebagian besar kasus yang saya sebutkan di awal laporan. Satu-satunya hal yang mungkin tidak cocok adalah sistem perdagangan frekuensi tinggi.

Terima kasih! Dan pertanyaan lainnya. Apa kompatibilitas di PromQL?

Kompatibilitas penuh ke belakang. VictoriaMetrics sepenuhnya mendukung PromQL. Selain itu, ia menambahkan fungsionalitas lanjutan tambahan di PromQL, yang disebut MetrikQL. Ada pembicaraan di YouTube tentang fungsionalitas tambahan ini. Saya berbicara di Pertemuan Pemantauan pada musim semi di St. Petersburg.

Telegram dikirim VictoriaMetrik.

Hanya pengguna terdaftar yang dapat berpartisipasi dalam survei. Masuk, silakan.

Apa yang menghentikan Anda untuk beralih ke VictoriaMetrics sebagai penyimpanan jangka panjang untuk Prometheus? (Tulis di komentar, saya akan menambahkannya ke polling))

• 71,4%Saya tidak menggunakan Prometheus5

• 28,6%Tidak tahu tentang VictoriaMetrics2

7 pengguna memilih. 12 pengguna abstain.

Sumber: www.habr.com