Pada musim gugur 2019, peristiwa yang telah lama ditunggu-tunggu terjadi di tim Mail.ru Cloud iOS. Basis data utama untuk penyimpanan persisten status aplikasi telah menjadi sangat eksotis bagi dunia seluler Basis Data yang Dipetakan Memori Lightning (LMDB). Di bawah potongan kami menawarkan Anda tinjauan rinci dalam empat bagian. Pertama, mari kita bicara tentang alasan dari pilihan yang tidak sepele dan sulit tersebut. Kemudian kita akan melanjutkan dengan mempertimbangkan tiga pilar di jantung arsitektur LMDB: file yang dipetakan memori, B+-tree, pendekatan copy-on-write untuk mengimplementasikan transaksionalitas dan multiversi. Terakhir, untuk hidangan penutup - bagian praktisnya. Di dalamnya kita akan melihat bagaimana merancang dan mengimplementasikan skema database dengan beberapa tabel, termasuk tabel indeks, di atas API nilai kunci tingkat rendah.

kadar

1. Motivasi untuk implementasi
2. Penempatan LMDB
3. Tiga pilar LMDB
   3.1. Paus #1. File yang dipetakan memori
   3.2. Paus #2. pohon B+
   3.3. Paus #3. Salin-saat-tulis
4. Merancang skema data di atas API nilai kunci
   4.1. Abstraksi dasar
   4.2. Pemodelan Tabel
   4.3. Memodelkan hubungan antar tabel

1. Motivasi pelaksanaan

Suatu tahun di tahun 2015, kami bersusah payah mengukur seberapa sering antarmuka aplikasi kami mengalami kelambatan. Kami melakukan ini karena suatu alasan. Kami lebih sering menerima keluhan bahwa terkadang aplikasi berhenti merespons tindakan pengguna: tombol tidak dapat ditekan, daftar tidak dapat digulir, dll. Tentang mekanisme pengukuran diceritakan di AvitoTech, jadi disini saya hanya memberikan urutan angkanya saja.

Hasil pengukuran menjadi mandi air dingin bagi kami. Ternyata lebih banyak masalah yang disebabkan oleh macet dibandingkan masalah lainnya. Jika sebelum menyadari fakta ini indikator teknis utama kualitas adalah bebas kecelakaan, maka setelah fokus bergeser pada pembekuan bebas.

Setelah dibangun dasbor dengan macet dan setelah menghabiskan kuantitatif и kualitas analisis alasan mereka, musuh utama menjadi jelas - logika bisnis yang berat dieksekusi di thread utama aplikasi. Reaksi alami terhadap aib ini adalah keinginan membara untuk memasukkannya ke dalam dunia kerja. Untuk mengatasi masalah ini secara sistematis, kami menggunakan arsitektur multi-thread berdasarkan aktor ringan. Saya mendedikasikannya untuk adaptasinya untuk dunia iOS dua benang di Twitter kolektif dan artikel tentang Habré. Sebagai bagian dari narasi saat ini, saya ingin menekankan aspek-aspek keputusan yang memengaruhi pilihan database.​

​Model aktor organisasi sistem mengasumsikan bahwa multithreading menjadi esensi kedua. Memodelkan objek di dalamnya seperti melintasi batas aliran sungai. Dan mereka melakukan ini tidak kadang-kadang dan di sana-sini, tetapi hampir terus-menerus dan di mana saja.​

​Database adalah salah satu komponen landasan dalam diagram yang disajikan. Tugas utamanya adalah mengimplementasikan pola makro Basis Data Bersama. Jika di dunia perusahaan digunakan untuk mengatur sinkronisasi data antar layanan, maka dalam kasus arsitektur aktor - data antar thread. Oleh karena itu, kami memerlukan database yang tidak akan menimbulkan kesulitan minimal saat bekerja dengannya di lingkungan multi-thread. Secara khusus, ini berarti bahwa objek yang diperoleh darinya setidaknya harus aman untuk thread, dan idealnya sepenuhnya tidak dapat diubah. Seperti yang Anda ketahui, yang terakhir dapat digunakan secara bersamaan dari beberapa thread tanpa harus melakukan penguncian apa pun, yang memiliki efek menguntungkan pada kinerja.

Faktor penting kedua yang memengaruhi pilihan database adalah API cloud kami. Itu terinspirasi oleh pendekatan sinkronisasi yang diadopsi oleh git. Seperti dia, kami membidik API offline-pertama, yang terlihat lebih cocok untuk klien cloud. Diasumsikan bahwa mereka hanya akan memompa seluruh keadaan cloud satu kali, dan kemudian sinkronisasi dalam sebagian besar kasus akan terjadi melalui peluncuran perubahan. Sayangnya, peluang ini masih sebatas teori, dan klien belum mempelajari cara bekerja dengan patch dalam praktiknya. Ada sejumlah alasan obyektif untuk hal ini, yang, agar tidak menunda pengenalan, kami akan meninggalkan tanda kurung. Sekarang, yang lebih menarik adalah kesimpulan instruktif dari pelajaran tentang apa yang terjadi ketika API mengatakan “A” dan konsumennya tidak mengatakan “B”.

Jadi, jika Anda membayangkan git, yang, ketika menjalankan perintah pull, alih-alih menerapkan patch ke snapshot lokal, membandingkan status penuhnya dengan status server lengkap, maka Anda akan memiliki gambaran yang cukup akurat tentang bagaimana sinkronisasi terjadi di cloud. klien. Mudah ditebak bahwa untuk mengimplementasikannya, Anda perlu mengalokasikan dua pohon DOM di memori dengan informasi meta tentang semua server dan file lokal. Ternyata jika pengguna menyimpan 500 ribu file di cloud, maka untuk menyinkronkannya perlu membuat ulang dan menghancurkan dua pohon dengan 1 juta node. Namun setiap node merupakan agregat yang berisi grafik subobjek. Dalam hal ini, hasil profiling diharapkan. Ternyata bahkan tanpa memperhitungkan algoritme penggabungan, prosedur untuk membuat dan kemudian menghancurkan sejumlah besar objek kecil membutuhkan biaya yang cukup besar. Situasi ini diperburuk oleh fakta bahwa operasi sinkronisasi dasar disertakan dalam sejumlah besar skrip pengguna. Hasilnya, kami memperbaiki kriteria penting kedua dalam memilih database - kemampuan untuk mengimplementasikan operasi CRUD tanpa alokasi objek secara dinamis.

Persyaratan lainnya lebih tradisional dan seluruh daftarnya adalah sebagai berikut.

1. Keamanan benang.
2. Multiproses. Ditentukan oleh keinginan untuk menggunakan instance database yang sama untuk menyinkronkan status tidak hanya antar thread, tetapi juga antara aplikasi utama dan ekstensi iOS.
3. Kemampuan untuk mewakili entitas yang disimpan sebagai objek yang tidak dapat diubah.​
4. Tidak ada alokasi dinamis dalam operasi CRUD.
5. Dukungan transaksi untuk properti dasar ACID: atomisitas, konsistensi, isolasi dan keandalan.
6. Kecepatan pada kasus paling populer.

Dengan serangkaian persyaratan ini, SQLite telah dan tetap menjadi pilihan yang baik. Namun, sebagai bagian dari studi alternatif, saya menemukan sebuah buku "Memulai dengan LevelDB". Di bawah kepemimpinannya, sebuah tolok ukur ditulis untuk membandingkan kecepatan kerja dengan berbagai database dalam skenario cloud nyata. Hasilnya melebihi ekspektasi terliar kami. Dalam kasus yang paling populer - mengarahkan kursor ke daftar semua file yang diurutkan dan daftar semua file yang diurutkan untuk direktori tertentu - LMDB ternyata 10 kali lebih cepat daripada SQLite. Pilihannya menjadi jelas.

2. Penentuan Posisi LMDB

LMDB adalah perpustakaan yang sangat kecil (hanya 10 ribu baris) yang mengimplementasikan lapisan fundamental terendah dari database - penyimpanan.

Diagram di atas menunjukkan bahwa membandingkan LMDB dengan SQLite, yang juga mengimplementasikan level yang lebih tinggi, umumnya tidak lebih tepat dibandingkan SQLite dengan Data Inti. Akan lebih adil untuk mengutip mesin penyimpanan yang sama dengan pesaing yang setara - BerkeleyDB, LevelDB, Sophia, RocksDB, dll. Bahkan ada perkembangan di mana LMDB bertindak sebagai komponen mesin penyimpanan untuk SQLite. Eksperimen pertama dilakukan pada tahun 2012 dihabiskan oleh LMDB Howard Chu. Temuan ternyata begitu menarik sehingga inisiatifnya diambil oleh para penggemar OSS, dan dilanjutkan oleh orang tersebut LumoSQL. Pada Januari 2020, penulis proyek ini adalah Den Shearer disajikan itu di LinuxConfAu.

LMDB terutama digunakan sebagai mesin untuk database aplikasi. Perpustakaan berutang kemunculannya kepada para pengembang OpenLDAP, yang sangat tidak puas dengan BerkeleyDB sebagai dasar proyek mereka. Berawal dari perpustakaan sederhana pohon, Howard Chu mampu menciptakan salah satu alternatif paling populer di zaman kita. Dia mendedikasikan laporannya yang sangat keren untuk cerita ini, serta struktur internal LMDB. "Database yang Dipetakan Memori Lightning". Contoh bagus dalam menaklukkan fasilitas penyimpanan dibagikan oleh Leonid Yuryev (alias yleo) dari Positive Technologies dalam laporannya di Highload 2015 “Mesin LMDB adalah juara istimewa”. Di dalamnya, ia berbicara tentang LMDB dalam konteks tugas serupa dalam mengimplementasikan ReOpenLDAP, dan LevelDB telah menjadi sasaran kritik komparatif. Sebagai hasil dari implementasinya, Teknologi Positif bahkan memiliki perkembangan yang aktif MDBX dengan fitur yang sangat enak, optimasi dan perbaikan kerusakan.

LMDB sering digunakan sebagai penyimpanan apa adanya. Misalnya saja browser Mozilla Firefox memilih untuk sejumlah kebutuhan, dan, mulai dari versi 9, Xcode disukai SQLite-nya untuk menyimpan indeks.

Mesinnya juga telah berhasil dalam dunia pengembangan seluler. Jejak penggunaannya mungkin menemukan di klien iOS untuk Telegram. LinkedIn melangkah lebih jauh dan memilih LMDB sebagai penyimpanan default untuk kerangka cache data buatan sendiri, Rocket Data, tentang hal itu diberi tahu dalam artikelnya pada tahun 2016.

LMDB berhasil memperjuangkan tempat di ceruk yang ditinggalkan oleh BerkeleyDB setelah berada di bawah kendali Oracle. Perpustakaan disukai karena kecepatan dan keandalannya, bahkan dibandingkan dengan perpustakaan sejenisnya. Seperti yang Anda ketahui, tidak ada makan siang gratis, dan saya ingin menekankan trade-off yang harus Anda hadapi ketika memilih antara LMDB dan SQLite. Diagram di atas dengan jelas menunjukkan bagaimana peningkatan kecepatan dicapai. Pertama, kami tidak membayar untuk lapisan abstraksi tambahan selain penyimpanan disk. Jelas bahwa arsitektur yang baik tetap tidak dapat berjalan tanpanya, dan mereka pasti akan muncul dalam kode aplikasi, namun akan jauh lebih halus. Mereka tidak akan berisi fitur yang tidak diperlukan oleh aplikasi tertentu, misalnya, dukungan untuk kueri dalam bahasa SQL. Kedua, menjadi mungkin untuk mengimplementasikan pemetaan operasi aplikasi secara optimal berdasarkan permintaan ke penyimpanan disk. Jika SQLite dalam pekerjaan saya didasarkan pada kebutuhan statistik rata-rata suatu aplikasi rata-rata, maka Anda, sebagai pengembang aplikasi, mengetahui dengan baik skenario beban kerja utama. Untuk solusi yang lebih produktif, Anda harus membayar harga yang lebih mahal baik untuk pengembangan solusi awal maupun untuk dukungan selanjutnya.

3. Tiga pilar LMDB

Setelah melihat LMDB dari sudut pandang luas, sekarang saatnya untuk mendalami lebih dalam. Tiga bagian berikutnya akan dikhususkan untuk analisis pilar utama yang menjadi sandaran arsitektur penyimpanan:

1. File yang dipetakan memori sebagai mekanisme untuk bekerja dengan disk dan menyinkronkan struktur data internal.
2. B+-tree sebagai organisasi struktur data yang disimpan.
3. Copy-on-write sebagai pendekatan untuk menyediakan properti transaksi ACID dan multiversi.

3.1. Paus #1. File yang dipetakan memori

File yang dipetakan memori adalah elemen arsitektur yang penting sehingga file tersebut bahkan muncul dalam nama repositori. Masalah caching dan sinkronisasi akses ke informasi yang disimpan sepenuhnya diserahkan kepada sistem operasi. LMDB tidak mengandung cache apa pun di dalamnya. Ini adalah keputusan sadar penulis, karena membaca data langsung dari file yang dipetakan memungkinkan Anda mengambil banyak jalan pintas dalam implementasi mesin. Di bawah ini adalah daftar beberapa di antaranya yang masih jauh dari lengkap.

1. Menjaga konsistensi data dalam penyimpanan ketika dikerjakan dari beberapa proses menjadi tanggung jawab sistem operasi. Pada bagian selanjutnya, mekanisme ini dibahas secara detail dan disertai gambar.
2. Tidak adanya cache sepenuhnya menghilangkan LMDB dari overhead yang terkait dengan alokasi dinamis. Membaca data dalam praktiknya berarti menyetel penunjuk ke alamat yang benar di memori virtual dan tidak lebih. Kedengarannya seperti fiksi ilmiah, tetapi dalam kode sumber penyimpanan, semua panggilan ke calloc terkonsentrasi pada fungsi konfigurasi penyimpanan.
3. Tidak adanya cache juga berarti tidak adanya kunci yang terkait dengan sinkronisasi aksesnya. Pembaca, yang jumlahnya bisa berubah-ubah pada saat yang sama, tidak menemukan satu mutex pun dalam perjalanan mereka ke data. Oleh karena itu, kecepatan membaca memiliki skalabilitas linier yang ideal berdasarkan jumlah CPU. Di LMDB, hanya operasi modifikasi yang disinkronkan. Hanya ada satu penulis dalam satu waktu.
4. Logika caching dan sinkronisasi minimum menghilangkan jenis kesalahan yang sangat kompleks yang terkait dengan bekerja di lingkungan multi-thread. Ada dua studi database yang menarik pada konferensi Usenix OSDI 2014: "Semua Sistem File Tidak Diciptakan Sama: Tentang Kompleksitas Pembuatan Aplikasi yang Konsisten dengan Crash" и "Menyiksa Database untuk Kesenangan dan Keuntungan". Dari mereka Anda dapat memperoleh informasi tentang keandalan LMDB yang belum pernah ada sebelumnya dan implementasi properti transaksi ACID yang hampir sempurna, yang lebih unggul dari SQLite.
5. Minimalisme LMDB memungkinkan representasi mesin dari kodenya ditempatkan sepenuhnya di cache L1 prosesor dengan karakteristik kecepatan berikutnya.

Sayangnya, di iOS, dengan file yang dipetakan ke memori, semuanya tidak secerah yang kita inginkan. Untuk membicarakan kekurangan yang terkait dengannya secara lebih sadar, perlu diingat prinsip umum penerapan mekanisme ini dalam sistem operasi.

Informasi umum tentang file yang dipetakan memori

Dengan setiap aplikasi yang berjalan, sistem operasi mengaitkan suatu entitas yang disebut proses. Setiap proses dialokasikan sejumlah alamat yang berdekatan di mana ia menempatkan segala sesuatu yang diperlukan untuk beroperasi. Di alamat terendah terdapat bagian dengan kode dan data serta sumber daya yang dikodekan secara keras. Berikutnya adalah blok ruang alamat dinamis yang terus berkembang, yang kita kenal dengan nama heap. Ini berisi alamat entitas yang muncul selama pengoperasian program. Di bagian atas adalah area memori yang digunakan oleh tumpukan aplikasi. Ia tumbuh atau menyusut; dengan kata lain, ukurannya juga bersifat dinamis. Untuk mencegah tumpukan dan heap saling mendorong dan mengganggu, keduanya ditempatkan di ujung ruang alamat yang berbeda.​ Terdapat lubang di antara dua bagian dinamis di bagian atas dan bawah. Sistem operasi menggunakan alamat di bagian tengah ini untuk mengaitkan berbagai entitas dengan proses. Secara khusus, ia dapat mengaitkan serangkaian alamat tertentu yang berkesinambungan dengan file di disk. File seperti itu disebut dipetakan memori.​

Ruang alamat yang dialokasikan untuk proses ini sangat besar. Secara teoritis, jumlah alamat hanya dibatasi oleh ukuran pointer, yang ditentukan oleh kapasitas bit sistem. Jika memori fisik dipetakan 1-ke-1 ke dalamnya, maka proses pertama akan menghabiskan seluruh RAM, dan tidak akan ada pembicaraan tentang multitasking apa pun.​

​Namun, dari pengalaman kami, kami mengetahui bahwa sistem operasi modern dapat menjalankan sebanyak mungkin proses secara bersamaan sesuai keinginan. Hal ini dimungkinkan karena fakta bahwa mereka hanya mengalokasikan banyak memori untuk proses di atas kertas, namun kenyataannya mereka memuat ke dalam memori fisik utama hanya bagian yang dibutuhkan di sini dan saat ini. Oleh karena itu, memori yang terkait dengan suatu proses disebut virtual.

Sistem operasi mengatur memori virtual dan fisik ke dalam halaman-halaman dengan ukuran tertentu. Segera setelah halaman tertentu dari memori virtual dibutuhkan, sistem operasi memuatnya ke dalam memori fisik dan mencocokkannya dalam tabel khusus. Jika tidak ada slot kosong, maka salah satu halaman yang dimuat sebelumnya akan disalin ke disk, dan halaman yang diminta akan menggantikannya. Prosedur ini, yang akan segera kita bahas lagi, disebut swapping. Gambar di bawah mengilustrasikan proses yang dijelaskan. Di atasnya, halaman A dengan alamat 0 dimuat dan ditempatkan pada halaman memori utama dengan alamat 4. Fakta ini tercermin dalam tabel korespondensi di sel nomor 0.​

Ceritanya persis sama dengan file yang dipetakan ke memori. Logikanya, mereka seharusnya terus menerus dan seluruhnya berada di ruang alamat virtual. Namun, mereka memasuki memori fisik halaman demi halaman dan hanya berdasarkan permintaan. Modifikasi halaman tersebut disinkronkan dengan file di disk. Dengan cara ini, Anda dapat melakukan I/O file hanya dengan bekerja dengan byte di memori - semua perubahan akan secara otomatis ditransfer oleh kernel sistem operasi ke file sumber.​
​,war
Gambar di bawah menunjukkan bagaimana LMDB menyinkronkan statusnya saat bekerja dengan database dari berbagai proses. Dengan memetakan memori virtual dari berbagai proses ke file yang sama, kami secara de facto mewajibkan sistem operasi untuk secara transit menyinkronkan blok-blok tertentu dari ruang alamatnya satu sama lain, di mana LMDB terlihat.​
​,war

Nuansa penting adalah bahwa LMDB, secara default, memodifikasi file data melalui mekanisme panggilan sistem tulis, dan menampilkan file itu sendiri dalam mode read-only. Pendekatan ini mempunyai dua konsekuensi penting.

Konsekuensi pertama umum terjadi pada semua sistem operasi. Esensinya adalah untuk menambahkan perlindungan terhadap kerusakan yang tidak disengaja pada database karena kode yang salah. Seperti yang Anda ketahui, instruksi yang dapat dieksekusi dari suatu proses bebas mengakses data dari mana saja di ruang alamatnya. Pada saat yang sama, seperti yang baru kita ingat, menampilkan file dalam mode baca-tulis berarti bahwa instruksi apa pun juga dapat memodifikasinya. Jika dia melakukan ini secara tidak sengaja, mencoba, misalnya, untuk menimpa elemen array pada indeks yang tidak ada, maka dia dapat secara tidak sengaja mengubah file yang dipetakan ke alamat ini, yang akan menyebabkan kerusakan pada database. Jika file ditampilkan dalam mode read-only, maka upaya untuk mengubah ruang alamat yang sesuai akan mengakibatkan penghentian darurat program dengan sinyal SIGSEGV, dan file akan tetap utuh.

Konsekuensi kedua sudah spesifik untuk iOS. Baik penulis maupun sumber lain tidak menyebutkannya secara eksplisit, namun tanpanya LMDB tidak akan cocok dijalankan di sistem operasi seluler ini. Bagian selanjutnya dikhususkan untuk pertimbangannya.

Spesifik file yang dipetakan memori di iOS

Ada laporan luar biasa di WWDC pada tahun 2018 "Memori iOS Menyelami Lebih Dalam". Ini memberi tahu kita bahwa di iOS, semua halaman yang terletak di memori fisik adalah salah satu dari 3 jenis: kotor, terkompresi, dan bersih.

Memori bersih adalah kumpulan halaman yang dapat dengan mudah dikeluarkan dari memori fisik. Data yang dikandungnya dapat dimuat ulang sesuai kebutuhan dari sumber aslinya. File yang dipetakan memori hanya-baca termasuk dalam kategori ini. iOS tidak takut untuk membongkar halaman yang dipetakan ke file dari memori kapan saja, karena halaman tersebut dijamin akan disinkronkan dengan file di disk.
​,war
Semua halaman yang dimodifikasi berakhir di memori kotor, di mana pun halaman aslinya berada. Secara khusus, file yang dipetakan memori yang dimodifikasi dengan menulis ke memori virtual yang terkait dengannya akan diklasifikasikan dengan cara ini. Membuka LMDB dengan bendera MDB_WRITEMAP, setelah melakukan perubahan, Anda dapat memverifikasinya secara pribadi.​

​Segera setelah aplikasi mulai menggunakan terlalu banyak memori fisik, iOS akan menerapkan kompresi halaman yang kotor. Total memori yang ditempati oleh halaman yang kotor dan terkompresi merupakan jejak memori aplikasi. Setelah mencapai nilai ambang batas tertentu, daemon sistem pembunuh OOM muncul setelah proses dan menghentikannya secara paksa. Inilah kekhasan iOS dibandingkan sistem operasi desktop. Sebaliknya, mengurangi jejak memori dengan menukar halaman dari memori fisik ke disk tidak disediakan di iOS. Alasannya hanya bisa ditebak. Mungkin prosedur memindahkan halaman secara intensif ke disk dan sebaliknya terlalu memakan energi untuk perangkat seluler, atau iOS menghemat sumber daya untuk menulis ulang sel pada drive SSD, atau mungkin para perancang tidak puas dengan kinerja sistem secara keseluruhan, di mana semuanya baik-baik saja. terus-menerus bertukar. Meski begitu, faktanya tetaplah fakta.

Kabar baiknya, yang telah disebutkan sebelumnya, adalah LMDB secara default tidak menggunakan mekanisme mmap untuk memperbarui file. Artinya, data yang ditampilkan diklasifikasikan oleh iOS sebagai memori bersih dan tidak berkontribusi terhadap jejak memori. Anda dapat memverifikasi ini menggunakan alat Xcode yang disebut VM Tracker. Tangkapan layar di bawah menunjukkan status memori virtual iOS aplikasi Cloud selama pengoperasian. Pada awalnya, 2 instance LMDB diinisialisasi di dalamnya. Yang pertama diizinkan untuk menampilkan filenya pada memori virtual 1GiB, yang kedua - 512MiB. Terlepas dari kenyataan bahwa kedua penyimpanan menempati sejumlah memori tetap, tidak satupun dari keduanya memberikan kontribusi ukuran kotor.

Dan sekarang waktunya untuk kabar buruk. Berkat mekanisme swap dalam sistem operasi desktop 64-bit, setiap proses dapat menempati ruang alamat virtual sebanyak yang dimungkinkan oleh ruang hard disk kosong untuk potensi pertukarannya. Mengganti swap dengan kompresi di iOS secara radikal mengurangi maksimum teoritis. Sekarang semua proses yang hidup harus masuk ke dalam memori utama (baca RAM), dan semua proses yang tidak sesuai harus dihentikan secara paksa. Hal ini dinyatakan seperti yang disebutkan di atas melaporkan, dan masuk dokumentasi resmi. Akibatnya, iOS sangat membatasi jumlah memori yang tersedia untuk alokasi melalui mmap. Di Sini di sini Anda dapat melihat batasan empiris jumlah memori yang dapat dialokasikan pada perangkat berbeda menggunakan panggilan sistem ini. Pada model ponsel cerdas paling modern, iOS menjadi lebih murah sebesar 2 gigabyte, dan pada versi teratas iPad - sebesar 4. Dalam praktiknya, tentu saja, Anda harus fokus pada model perangkat yang didukung terendah, di mana semuanya sangat menyedihkan. Lebih buruk lagi, dengan melihat status memori aplikasi di VM Tracker, Anda akan menemukan bahwa LMDB bukanlah satu-satunya yang mengklaim telah dipetakan memori. Bagian yang bagus akan dimakan habis oleh pengalokasi sistem, file sumber daya, kerangka gambar, dan predator kecil lainnya.

Berdasarkan hasil percobaan di Cloud, kami sampai pada nilai kompromi berikut untuk memori yang dialokasikan oleh LMDB: 384 megabyte untuk perangkat 32-bit dan 768 untuk perangkat 64-bit. Setelah volume ini habis, setiap operasi modifikasi mulai diakhiri dengan kode MDB_MAP_FULL. Kami mengamati kesalahan seperti ini dalam pemantauan kami, namun kesalahan tersebut cukup kecil sehingga pada tahap ini kesalahan tersebut dapat diabaikan.

Alasan yang tidak jelas atas konsumsi memori yang berlebihan oleh penyimpanan bisa jadi adalah transaksi yang berumur panjang. Untuk memahami keterkaitan kedua fenomena ini, kita akan terbantu dengan mempertimbangkan dua pilar LMDB lainnya.

3.2. Paus #2. B+-pohon

Untuk meniru tabel di atas penyimpanan nilai kunci, operasi berikut harus ada di API-nya:

1. Memasukkan elemen baru.
2. Cari elemen dengan kunci tertentu.
3. Menghapus sebuah elemen.
4. Ulangi interval kunci sesuai urutan pengurutannya.

Struktur data paling sederhana yang dapat dengan mudah mengimplementasikan keempat operasi tersebut adalah pohon pencarian biner. Masing-masing nodenya mewakili sebuah kunci yang membagi seluruh subset kunci anak menjadi dua subpohon. Yang kiri berisi yang lebih kecil dari induknya, dan yang kanan berisi yang lebih besar. Memperoleh serangkaian kunci yang terurut dicapai melalui salah satu penjelajahan pohon klasik.​

Pohon biner memiliki dua kelemahan mendasar yang mencegahnya menjadi efektif sebagai struktur data berbasis disk. Pertama, tingkat keseimbangannya tidak dapat diprediksi. Ada risiko besar untuk mendapatkan pohon yang ketinggian cabangnya bisa sangat bervariasi, yang secara signifikan memperburuk kompleksitas algoritmik pencarian dibandingkan dengan yang diharapkan. Kedua, banyaknya tautan silang antar node menghilangkan lokalitas pohon biner di memori.Node yang berdekatan (dalam hal koneksi di antara mereka) dapat ditempatkan pada halaman yang sama sekali berbeda dalam memori virtual. Sebagai konsekuensinya, bahkan traversal sederhana dari beberapa node yang bertetangga dalam sebuah pohon mungkin memerlukan mengunjungi jumlah halaman yang sebanding. Ini adalah masalah bahkan ketika kita berbicara tentang efektivitas pohon biner sebagai struktur data dalam memori, karena terus-menerus memutar halaman dalam cache prosesor bukanlah suatu kesenangan yang murah. Ketika sering mengambil halaman yang terkait dengan node dari disk, situasinya menjadi sepenuhnya tercela.

B-tree, yang merupakan evolusi dari pohon biner, memecahkan masalah yang diidentifikasi di paragraf sebelumnya. Pertama, mereka menyeimbangkan diri. Kedua, masing-masing nodenya membagi kumpulan kunci anak bukan menjadi 2, tetapi menjadi himpunan bagian terurut M, dan jumlah M bisa sangat besar, dalam urutan beberapa ratus, atau bahkan ribuan.

Dengan demikian:

1. Setiap node berisi sejumlah besar kunci yang sudah diurutkan dan pohonnya sangat pendek.
2. Pohon memperoleh properti lokalitas lokasi dalam memori, karena kunci yang nilainya dekat secara alami terletak bersebelahan pada node yang sama atau bertetangga.
3. Jumlah node transit saat menuruni pohon selama operasi pencarian berkurang.
4. Jumlah node target yang dibaca selama kueri rentang berkurang, karena masing-masing node sudah berisi sejumlah besar kunci yang dipesan.

LMDB menggunakan variasi pohon B yang disebut pohon B+ untuk menyimpan data. Diagram di atas menunjukkan tiga jenis node yang ada di dalamnya:

1. Di bagian atas adalah akarnya. Ini terwujud tidak lebih dari konsep database di dalam gudang. Dalam satu instans LMDB, Anda dapat membuat beberapa database yang berbagi ruang alamat virtual yang dipetakan. Masing-masing dimulai dari akarnya sendiri.
2. Yang paling bawah adalah daunnya. Mereka dan hanya mereka yang berisi pasangan nilai kunci yang disimpan dalam database. Omong-omong, inilah kekhasan pohon B+. Jika pohon B biasa menyimpan bagian nilai dalam node di semua tingkatan, maka variasi B+ hanya berada pada tingkat yang paling rendah. Setelah memperbaiki fakta ini, kami selanjutnya akan menyebut subtipe pohon yang digunakan di LMDB sebagai pohon-B.
3. Di antara akar dan daun terdapat 0 atau lebih tingkat teknis dengan simpul navigasi (cabang). Tugas mereka adalah membagi kumpulan kunci yang diurutkan di antara daun-daun.

Secara fisik, node adalah blok memori dengan panjang yang telah ditentukan. Ukurannya merupakan kelipatan dari ukuran halaman memori dalam sistem operasi, yang telah kita bahas di atas. Struktur node ditunjukkan di bawah ini. Header berisi informasi meta, yang paling jelas misalnya adalah checksum. Berikutnya adalah informasi tentang offset di mana sel-sel dengan data berada. Data dapat berupa kunci, jika kita berbicara tentang node navigasi, atau seluruh pasangan nilai kunci dalam kasus daun.​ Anda dapat membaca lebih lanjut tentang struktur halaman dalam karya "Evaluasi Penyimpanan Nilai-Kunci Berkinerja Tinggi".

Setelah menangani konten internal node halaman, kami selanjutnya akan merepresentasikan pohon B LMDB dengan cara yang disederhanakan dalam bentuk berikut.

Halaman dengan node disusun secara berurutan pada disk. Halaman bernomor lebih tinggi terletak di bagian akhir file. Halaman meta yang disebut berisi informasi tentang offset yang dapat digunakan untuk menemukan akar semua pohon. Saat membuka file, LMDB memindai file halaman demi halaman dari akhir ke awal untuk mencari halaman meta yang valid dan melaluinya menemukan database yang ada.​

Sekarang, setelah memiliki gambaran tentang struktur logis dan fisik organisasi data, kita dapat beralih ke pilar ketiga LMDB. Dengan bantuannya semua modifikasi penyimpanan terjadi secara transaksional dan terisolasi satu sama lain, memberikan database secara keseluruhan properti multiversi.

3.3. Paus #3. Salin-saat-tulis

Beberapa operasi B-tree melibatkan pembuatan serangkaian perubahan pada nodenya. Salah satu contohnya adalah menambahkan kunci baru ke node yang telah mencapai kapasitas maksimumnya. Dalam hal ini, pertama-tama, perlu untuk membagi node menjadi dua, dan kedua, menambahkan tautan ke node anak pemula yang baru di induknya. Prosedur ini berpotensi sangat berbahaya. Jika karena alasan tertentu (kerusakan, pemadaman listrik, dll.) hanya sebagian perubahan dari rangkaian yang terjadi, maka pohon akan tetap berada dalam keadaan tidak konsisten.

Salah satu solusi tradisional untuk membuat database toleran terhadap kesalahan adalah dengan menambahkan struktur data tambahan pada disk di sebelah B-tree - log transaksi, juga dikenal sebagai write-ahead log (WAL). Ini adalah file yang pada akhirnya operasi yang dimaksudkan ditulis secara ketat sebelum memodifikasi B-tree itu sendiri. Jadi, jika kerusakan data terdeteksi selama diagnosis mandiri, database akan berkonsultasi dengan log untuk mengaturnya sendiri.

LMDB telah memilih metode berbeda sebagai mekanisme toleransi kesalahan, yang disebut copy-on-write. Esensinya adalah alih-alih memperbarui data pada halaman yang sudah ada, ia terlebih dahulu menyalin seluruhnya dan membuat semua modifikasi pada salinan tersebut.​

Selanjutnya agar data yang terupdate dapat tersedia maka perlu dilakukan perubahan link node yang sudah menjadi kekinian pada node induknya. Karena juga perlu dimodifikasi untuk ini, maka disalin juga terlebih dahulu. Proses ini berlanjut secara rekursif hingga ke root. Hal terakhir yang diubah adalah data pada halaman meta.​​

Jika tiba-tiba proses terhenti selama prosedur pembaruan, halaman meta baru tidak akan dibuat, atau halaman meta baru tidak akan ditulis ke disk sepenuhnya, dan checksumnya salah. Dalam salah satu dari dua kasus ini, halaman baru tidak akan dapat dijangkau, namun halaman lama tidak akan terpengaruh. Hal ini menghilangkan kebutuhan LMDB untuk menulis log terlebih dahulu untuk menjaga konsistensi data. Secara de facto, struktur penyimpanan data pada disk yang dijelaskan di atas secara bersamaan menjalankan fungsinya. Tidak adanya log transaksi eksplisit menjadi salah satu fitur LMDB yang memberikan kecepatan membaca data yang tinggi.​

Desain yang dihasilkan, disebut append-only B-tree, secara alami menyediakan isolasi transaksi dan multi-versi. Di LMDB, setiap transaksi terbuka dikaitkan dengan akar pohon yang relevan saat ini. Sampai transaksi selesai, halaman pohon yang terkait dengannya tidak akan pernah diubah atau digunakan kembali untuk versi data baru. Dengan demikian, Anda dapat bekerja selama yang Anda suka dengan kumpulan data yang relevan pada saat itu. transaksi telah dibuka, meskipun penyimpanan terus diperbarui secara aktif saat ini. Inilah inti dari multiversi, menjadikan LMDB sebagai sumber data yang ideal untuk kita tercinta UICollectionView. Setelah membuka transaksi, tidak perlu menambah jejak memori aplikasi dengan terburu-buru memompa data saat ini ke dalam beberapa struktur di dalam memori, karena takut tidak ada yang tersisa. Fitur ini membedakan LMDB dari SQLite yang sama, yang tidak dapat membanggakan isolasi total tersebut. Setelah membuka dua transaksi pada transaksi terakhir dan menghapus catatan tertentu dalam salah satunya, maka tidak mungkin lagi memperoleh catatan yang sama dalam sisa catatan kedua.

Sisi lain dari hal ini adalah potensi konsumsi memori virtual yang jauh lebih tinggi. Slide menunjukkan seperti apa struktur database jika dimodifikasi secara bersamaan dengan 3 transaksi baca terbuka dengan melihat versi database yang berbeda. Karena LMDB tidak dapat menggunakan kembali node yang dapat dijangkau dari akar yang terkait dengan transaksi saat ini, penyimpanan tidak punya pilihan selain mengalokasikan akar keempat lagi di memori dan sekali lagi mengkloning halaman yang dimodifikasi di bawahnya.​

Di sini akan berguna untuk mengingat bagian file yang dipetakan memori. Tampaknya konsumsi tambahan memori virtual tidak perlu terlalu membuat kita khawatir, karena tidak berkontribusi pada penggunaan memori aplikasi. Namun, pada saat yang sama, tercatat bahwa iOS sangat pelit dalam mengalokasikannya, dan kami tidak dapat, seperti di server atau desktop, menyediakan wilayah LMDB sebesar 1 terabyte dan tidak memikirkan fitur ini sama sekali. Jika memungkinkan, Anda harus mencoba membuat masa transaksi sesingkat mungkin.

4. Merancang skema data di atas API nilai kunci

Mari kita mulai analisis API kita dengan melihat abstraksi dasar yang disediakan oleh LMDB: lingkungan dan database, kunci dan nilai, transaksi dan kursor.

Catatan tentang daftar kode

Semua fungsi di API LMDB publik mengembalikan hasil kerjanya dalam bentuk kode kesalahan, tetapi di semua daftar berikutnya verifikasinya dihilangkan demi singkatnya.​ Dalam praktiknya, kami bahkan menggunakan fungsi kami sendiri untuk berinteraksi dengan repositori garpu Pembungkus C++ lmdbxx.dll, di mana kesalahan diwujudkan sebagai pengecualian C++.

Sebagai cara tercepat untuk menghubungkan LMDB ke proyek untuk iOS atau macOS, saya menyarankan CocoaPod saya POSLMDB.

4.1. Abstraksi Dasar

Lingkungan

Struktur MDB_env adalah gudang keadaan internal LMDB. Keluarga fungsi yang diawali mdb_env memungkinkan Anda mengonfigurasi beberapa propertinya. Dalam kasus paling sederhana, inisialisasi mesin terlihat seperti ini.

mdb_env_create(env);​
mdb_env_set_map_size(*env, 1024 * 1024 * 512)​
mdb_env_open(*env, path.UTF8String, MDB_NOTLS, 0664);

Di aplikasi Mail.ru Cloud, kami mengubah nilai default hanya dua parameter.

Yang pertama adalah ukuran ruang alamat virtual tempat file penyimpanan dipetakan. Sayangnya, bahkan pada perangkat yang sama, nilai spesifiknya dapat sangat bervariasi dari satu proses ke proses lainnya. Untuk memperhitungkan fitur iOS ini, volume penyimpanan maksimum dipilih secara dinamis. Mulai dari nilai tertentu, berurutan dibelah dua hingga fungsinya mdb_env_open tidak akan mengembalikan hasil yang berbeda dari ENOMEM. Secara teori, ada juga cara sebaliknya - pertama-tama alokasikan memori minimum ke mesin, dan kemudian, ketika kesalahan diterima, MDB_MAP_FULL, tingkatkan. Namun, ini jauh lebih sulit. Pasalnya, prosedur alokasi ulang memori (remap) menggunakan fungsi mdb_env_set_map_size membatalkan semua entitas (kursor, transaksi, kunci, dan nilai) yang sebelumnya diterima dari mesin. Mempertimbangkan kejadian ini dalam kode akan menyebabkan komplikasi yang signifikan. Namun, jika memori virtual sangat penting bagi Anda, maka ini mungkin menjadi alasan untuk melihat lebih dekat pada fork yang telah berjalan jauh ke depan. MDBX, di mana di antara fitur-fitur yang diumumkan terdapat “penyesuaian ukuran database on-the-fly otomatis”.

Parameter kedua, yang nilai defaultnya tidak sesuai dengan kami, mengatur mekanisme untuk memastikan keamanan benang. Sayangnya, setidaknya iOS 10 memiliki masalah dengan dukungan penyimpanan lokal thread. Oleh karena itu, pada contoh di atas, repositori dibuka dengan flag MDB_NOTLS. Selain itu, hal itu juga diperlukan garpu pembungkus C++ lmdbxx.dlluntuk memotong variabel dengan atribut ini dan di dalamnya.

Database

Basis data adalah contoh pohon B terpisah, yang telah kita bahas di atas. Pembukaannya terjadi di dalam suatu transaksi, yang mungkin tampak sedikit aneh pada awalnya.

MDB_txn *txn;​
MDB_dbi dbi;​
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn);​
mdb_dbi_open(txn, NULL, MDB_CREATE, &dbi);​
mdb_txn_abort(txn);

Memang benar, transaksi di LMDB adalah entitas penyimpanan, bukan entitas database tertentu. Konsep ini memungkinkan Anda untuk melakukan operasi atom pada entitas yang terletak di database berbeda. Secara teori, ini membuka kemungkinan untuk memodelkan tabel dalam bentuk database yang berbeda, tetapi pada suatu waktu saya mengambil jalur yang berbeda, dijelaskan secara rinci di bawah.

Kunci dan nilai

Struktur MDB_val memodelkan konsep kunci dan nilai. Repositori tidak mengetahui semantiknya. Baginya, sesuatu yang lain hanyalah sebuah array byte dengan ukuran tertentu. Ukuran kunci maksimum adalah 512 byte.

typedef struct MDB_val {​
    size_t mv_size;​
    void *mv_data;​
} MDB_val;​​

Dengan menggunakan pembanding, toko mengurutkan kunci dalam urutan menaik. Jika Anda tidak menggantinya dengan milik Anda sendiri, maka yang default akan digunakan, yang mengurutkannya byte demi byte dalam urutan leksikografis.​

Transaksi

Struktur transaksi dijelaskan secara rinci di bab sebelumnya, jadi di sini saya akan mengulangi secara singkat properti utamanya:

1. Mendukung semua properti dasar ACID: atomisitas, konsistensi, isolasi dan keandalan. Saya tidak bisa tidak mencatat bahwa ada bug dalam hal daya tahan pada macOS dan iOS yang telah diperbaiki di MDBX. Anda dapat membaca lebih lanjut di mereka README.
2. Pendekatan multithreading digambarkan dengan skema “penulis tunggal / banyak pembaca”. Penulis saling memblokir, tapi jangan memblokir pembaca. Pembaca tidak menghalangi penulis atau satu sama lain.
3. Dukungan untuk transaksi bersarang.
4. Dukungan multiversi.

Multiversi di LMDB sangat bagus sehingga saya ingin mendemonstrasikannya dalam bentuk tindakan. Dari kode di bawah ini Anda dapat melihat bahwa setiap transaksi bekerja dengan versi database yang sama persis dengan versi terkini pada saat dibuka, dan sepenuhnya terisolasi dari semua perubahan selanjutnya. Menginisialisasi penyimpanan dan menambahkan catatan pengujian ke dalamnya tidak mewakili sesuatu yang menarik, jadi ritual ini dibiarkan dalam spoiler.

Menambahkan entri tes

MDB_env *env;
MDB_dbi dbi;
MDB_txn *txn;

mdb_env_create(&env);
mdb_env_open(env, "./testdb", MDB_NOTLS, 0664);

mdb_txn_begin(env, NULL, 0, &txn);
mdb_dbi_open(txn, NULL, 0, &dbi);
mdb_txn_abort(txn);

char k = 'k';
MDB_val key;
key.mv_size = sizeof(k);
key.mv_data = (void *)&k;

int v = 997;
MDB_val value;
value.mv_size = sizeof(v);
value.mv_data = (void *)&v;

mdb_txn_begin(env, NULL, 0, &txn);
mdb_put(txn, dbi, &key, &value, MDB_NOOVERWRITE);
mdb_txn_commit(txn);

MDB_txn *txn1, *txn2, *txn3;
MDB_val val;

// Открываем 2 транзакции, каждая из которых смотрит
// на версию базы данных с одной записью.
mdb_txn_begin(env, NULL, 0, &txn1); // read-write
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn2); // read-only

// В рамках первой транзакции удаляем из базы данных существующую в ней запись.
mdb_del(txn1, dbi, &key, NULL);
// Фиксируем удаление.
mdb_txn_commit(txn1);

// Открываем третью транзакцию, которая смотрит на
// актуальную версию базы данных, где записи уже нет.
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn3);
// Убеждаемся, что запись по искомому ключу уже не существует.
assert(mdb_get(txn3, dbi, &key, &val) == MDB_NOTFOUND);
// Завершаем транзакцию.
mdb_txn_abort(txn3);

// Убеждаемся, что в рамках второй транзакции, открытой на момент
// существования записи в базе данных, её всё ещё можно найти по ключу.
assert(mdb_get(txn2, dbi, &key, &val) == MDB_SUCCESS);
// Проверяем, что по ключу получен не абы какой мусор, а валидные данные.
assert(*(int *)val.mv_data == 997);
// Завершаем транзакцию, работающей хоть и с устаревшей, но консистентной базой данных.
mdb_txn_abort(txn2);

Saya menyarankan Anda mencoba trik yang sama dengan SQLite dan melihat apa yang terjadi.

Multiversi memberikan keuntungan yang sangat bagus bagi kehidupan pengembang iOS. Dengan menggunakan properti ini, Anda dapat dengan mudah dan alami menyesuaikan kecepatan pembaruan sumber data untuk formulir layar, berdasarkan pertimbangan pengalaman pengguna. Sebagai contoh, mari kita ambil fitur aplikasi Mail.ru Cloud seperti memuat konten secara otomatis dari galeri media sistem. Dengan koneksi yang baik, klien dapat menambahkan beberapa foto per detik ke server. Jika Anda memperbarui setelah setiap unduhan UICollectionView dengan konten media di cloud pengguna, Anda bisa melupakan sekitar 60 fps dan pengguliran mulus selama proses ini. Untuk mencegah pembaruan layar yang sering, Anda perlu membatasi laju perubahan data pada dasarnya UICollectionViewDataSource.

Jika database tidak mendukung multiversi dan memungkinkan Anda bekerja hanya dengan status saat ini, maka untuk membuat snapshot data yang stabil waktu, Anda perlu menyalinnya ke beberapa struktur data dalam memori atau ke tabel sementara. Salah satu pendekatan ini sangat mahal. Dalam kasus penyimpanan dalam memori, kita mendapatkan biaya baik dalam memori, yang disebabkan oleh penyimpanan objek yang dibangun, dan dalam waktu, terkait dengan transformasi ORM yang berlebihan. Sedangkan untuk meja sementara, ini adalah kesenangan yang bahkan lebih mahal, hanya masuk akal dalam kasus-kasus yang tidak sepele.

Solusi multiversi LMDB memecahkan masalah pemeliharaan sumber data yang stabil dengan cara yang sangat elegan. Cukup buka transaksi saja dan voila - sampai selesai, kumpulan data dijamin diperbaiki. Logika untuk kecepatan pembaruannya kini sepenuhnya berada di tangan lapisan presentasi, tanpa overhead sumber daya yang signifikan.

Kursor

Kursor menyediakan mekanisme untuk melakukan iterasi secara teratur pada pasangan nilai kunci melalui traversal B-tree. Tanpa mereka, mustahil untuk secara efektif memodelkan tabel-tabel dalam database, yang sekarang kita bahas.

4.2. Pemodelan Tabel

Properti pengurutan kunci memungkinkan Anda membuat abstraksi tingkat tinggi seperti tabel di atas abstraksi dasar. Mari kita pertimbangkan proses ini menggunakan contoh tabel utama klien cloud, yang menyimpan informasi tentang semua file dan folder pengguna.

Skema tabel

Salah satu skenario umum di mana struktur tabel dengan pohon folder harus disesuaikan adalah pemilihan semua elemen yang terletak dalam direktori tertentu. Model organisasi data yang baik untuk kueri yang efisien semacam ini adalah Daftar Kedekatan. Untuk mengimplementasikannya di atas penyimpanan nilai kunci, kunci file dan folder perlu diurutkan sedemikian rupa sehingga dikelompokkan berdasarkan keanggotaannya di direktori induk. Selain itu, untuk menampilkan isi direktori dalam bentuk yang familiar bagi pengguna Windows (pertama folder, lalu file, keduanya diurutkan berdasarkan abjad), perlu untuk menyertakan bidang tambahan yang sesuai di kunci.

​Gambar di bawah menunjukkan bagaimana, berdasarkan tugas yang ada, tampilan representasi kunci dalam bentuk array byte. Byte dengan pengidentifikasi direktori induk (merah) ditempatkan terlebih dahulu, kemudian dengan tipe (hijau) dan di bagian ekor dengan nama (biru). Diurutkan berdasarkan komparator LMDB default dalam urutan leksikografis, byte tersebut diurutkan dalam cara yang diperlukan. Melintasi kunci secara berurutan dengan awalan merah yang sama memberi kita nilai terkaitnya sesuai urutan tampilannya di antarmuka pengguna (di sebelah kanan), tanpa memerlukan pasca-pemrosesan tambahan.

Serialisasi Kunci dan Nilai

Banyak metode untuk membuat serialisasi objek telah ditemukan di dunia. Karena kami tidak memiliki persyaratan lain selain kecepatan, kami memilih sendiri yang tercepat - dump memori yang ditempati oleh instance struktur bahasa C. Jadi, kunci elemen direktori dapat dimodelkan dengan struktur berikut NodeKey.

typedef struct NodeKey {​
    EntityId parentId;​
    uint8_t type;​
    uint8_t nameBuffer[256];​
} NodeKey;

Untuk menyimpan NodeKey dalam penyimpanan yang dibutuhkan dalam objek MDB_val posisikan penunjuk data ke alamat awal struktur, dan hitung ukurannya dengan fungsi sizeof.

MDB_val serialize(NodeKey * const key) {
    return MDB_val {
        .mv_size = sizeof(NodeKey),
        .mv_data = (void *)key
    };
}

Pada bab pertama tentang kriteria pemilihan database, saya menyebutkan meminimalkan alokasi dinamis dalam operasi CRUD sebagai faktor pemilihan yang penting. Kode fungsi serialize menunjukkan bagaimana dalam kasus LMDB hal ini dapat dihindari sepenuhnya saat memasukkan catatan baru ke dalam database. Array byte yang masuk dari server pertama-tama diubah menjadi struktur tumpukan, dan kemudian dibuang ke penyimpanan. Mengingat juga tidak ada alokasi dinamis di dalam LMDB, Anda bisa mendapatkan situasi yang fantastis menurut standar iOS - gunakan hanya memori tumpukan untuk bekerja dengan data di sepanjang jalur dari jaringan ke disk!

Mengurutkan kunci dengan pembanding biner

Hubungan urutan kunci ditentukan oleh fungsi khusus yang disebut komparator. Karena mesin tidak mengetahui apa pun tentang semantik byte yang dikandungnya, pembanding default tidak punya pilihan selain menyusun kunci dalam urutan leksikografis, menggunakan perbandingan byte demi byte. Menggunakannya untuk mengatur struktur mirip dengan mencukur dengan kapak pemotong. Namun, dalam kasus sederhana menurut saya metode ini dapat diterima. Alternatifnya dijelaskan di bawah, tapi di sini saya akan mencatat beberapa garu yang tersebar di sepanjang jalur ini.

Hal pertama yang perlu diingat adalah representasi memori dari tipe data primitif. Jadi, di semua perangkat Apple, variabel integer disimpan dalam format Endian kecil. Ini berarti byte terkecil akan berada di sebelah kiri, dan tidak mungkin mengurutkan bilangan bulat menggunakan perbandingan byte demi byte. Misalnya, mencoba melakukan ini dengan serangkaian angka dari 0 hingga 511 akan menghasilkan hasil sebagai berikut.

// value (hex dump)
000 (0000)
256 (0001)
001 (0100)
257 (0101)
...
254 (fe00)
510 (fe01)
255 (ff00)
511 (ff01)

Untuk mengatasi masalah ini, bilangan bulat harus disimpan dalam kunci dalam format yang sesuai untuk pembanding byte-byte. Fungsi dari keluarga akan membantu Anda melakukan transformasi yang diperlukan hton* (khususnya htons untuk nomor double-byte dari contoh).

Format untuk merepresentasikan string dalam pemrograman, seperti yang Anda ketahui, adalah keseluruhan sejarah. Jika semantik string, serta pengkodean yang digunakan untuk mewakilinya dalam memori, menunjukkan bahwa mungkin ada lebih dari satu byte per karakter, maka lebih baik segera meninggalkan gagasan menggunakan pembanding default.

Hal kedua yang perlu diingat adalah prinsip penyelarasan kompiler bidang struktur. Karenanya, byte dengan nilai sampah dapat terbentuk di memori antar bidang, yang tentu saja merusak penyortiran byte-byte. Untuk menghilangkan sampah, Anda perlu mendeklarasikan bidang dalam urutan yang ditentukan secara ketat, dengan mengingat aturan penyelarasan, atau menggunakan atribut dalam deklarasi struktur packed.

Memesan kunci dengan pembanding eksternal

Logika perbandingan kunci mungkin terlalu rumit untuk pembanding biner. Salah satu dari banyak alasannya adalah adanya bidang teknis dalam struktur. Saya akan mengilustrasikan kemunculannya menggunakan contoh kunci untuk elemen direktori yang sudah kita kenal.

typedef struct NodeKey {​
    EntityId parentId;​
    uint8_t type;​
    uint8_t nameBuffer[256];​
} NodeKey;

Meskipun sederhana, dalam sebagian besar kasus, ini menghabiskan terlalu banyak memori. Buffer untuk nama tersebut memakan 256 byte, meskipun rata-rata nama file dan folder jarang melebihi 20-30 karakter.

​Salah satu teknik standar untuk mengoptimalkan ukuran rekaman adalah dengan “memangkas” rekaman tersebut ke ukuran sebenarnya. Esensinya adalah bahwa isi dari semua bidang dengan panjang variabel disimpan dalam buffer di akhir struktur, dan panjangnya disimpan dalam variabel terpisah.​ Menurut pendekatan ini, kuncinya NodeKey ditransformasikan sebagai berikut.

typedef struct NodeKey {​
    EntityId parentId;​
    uint8_t type;​
    uint8_t nameLength;​
    uint8_t nameBuffer[256];​
} NodeKey;

Selanjutnya, saat membuat serial, ukuran data tidak ditentukan sizeof seluruh struktur, dan ukuran semua bidang adalah panjang tetap ditambah ukuran bagian buffer yang sebenarnya digunakan.

MDB_val serialize(NodeKey * const key) {
    return MDB_val {
        .mv_size = offsetof(NodeKey, nameBuffer) + key->nameLength,
        .mv_data = (void *)key
    };
}

Sebagai hasil dari pemfaktoran ulang, kami menerima penghematan yang signifikan pada ruang yang ditempati oleh kunci. Namun karena bidang teknis nameLength, komparator biner default tidak lagi cocok untuk perbandingan kunci. Jika kita tidak menggantinya dengan milik kita sendiri, maka panjang nama akan menjadi faktor prioritas penyortiran yang lebih tinggi dibandingkan nama itu sendiri.

LMDB memungkinkan setiap database memiliki fungsi perbandingan kuncinya sendiri. Ini dilakukan dengan menggunakan fungsi tersebut mdb_set_compare secara ketat sebelum dibuka. Untuk alasan yang jelas, ini tidak dapat diubah sepanjang umur database. Pembanding menerima dua kunci dalam format biner sebagai masukan, dan pada keluarannya ia mengembalikan hasil perbandingan: kurang dari (-1), lebih besar dari (1) atau sama dengan (0). Kode semu untuk NodeKey terlihat seperti itu.

int compare(MDB_val * const a, MDB_val * const b) {​
    NodeKey * const aKey = (NodeKey * const)a->mv_data;​
    NodeKey * const bKey = (NodeKey * const)b->mv_data;​
    return // ...
}​

Selama semua kunci dalam database memiliki tipe yang sama, memasukkan representasi byte mereka tanpa syarat ke tipe struktur kunci aplikasi adalah sah. Ada satu nuansa di sini, tetapi akan dibahas di bawah pada subbagian “Catatan Bacaan”.

Serialisasi Nilai

LMDB bekerja sangat intensif dengan kunci dari catatan yang disimpan. Perbandingannya satu sama lain terjadi dalam kerangka operasi apa pun yang diterapkan, dan kinerja seluruh solusi bergantung pada kecepatan pembanding. Di dunia yang ideal, komparator biner default seharusnya cukup untuk membandingkan kunci, tetapi jika Anda harus menggunakan milik Anda sendiri, maka prosedur deserialisasi kunci di dalamnya harus secepat mungkin.

Basis data tidak terlalu tertarik pada bagian nilai dari catatan (nilai). Konversinya dari representasi byte ke objek hanya terjadi jika sudah diperlukan oleh kode aplikasi, misalnya, untuk menampilkannya di layar. Karena hal ini relatif jarang terjadi, persyaratan kecepatan untuk prosedur ini tidak terlalu penting, dan dalam implementasinya kami lebih bebas fokus pada kenyamanan. Misalnya, untuk membuat serial metadata tentang file yang belum diunduh, kami menggunakan NSKeyedArchiver.

NSData *data = serialize(object);​
MDB_val value = {​
    .mv_size = data.length,​
    .mv_data = (void *)data.bytes​
};

Namun, ada kalanya performa tetap penting. Misalnya, saat menyimpan metainformasi tentang struktur file cloud pengguna, kami menggunakan dump memori objek yang sama. Puncak dari tugas menghasilkan representasi serial adalah kenyataan bahwa elemen direktori dimodelkan oleh hierarki kelas.​

Untuk mengimplementasikannya dalam bahasa C, bidang ahli waris tertentu ditempatkan dalam struktur terpisah, dan hubungannya dengan bidang dasar ditentukan melalui bidang penyatuan tipe. Isi sebenarnya dari gabungan ditentukan melalui tipe atribut teknis.

typedef struct NodeValue {​
    EntityId localId;​
    EntityType type;​
    union {​
        FileInfo file;​
        DirectoryInfo directory;​
    } info;​
    uint8_t nameLength;​
    uint8_t nameBuffer[256];​
} NodeValue;​

Menambah dan memperbarui catatan

Kunci dan nilai serial dapat ditambahkan ke penyimpanan. Untuk melakukan ini, gunakan fungsinya mdb_put.

// key и value имеют тип MDB_val​
mdb_put(..., &key, &value, MDB_NOOVERWRITE);

Pada tahap konfigurasi, penyimpanan dapat diperbolehkan atau dilarang menyimpan beberapa record dengan kunci yang sama.Jika duplikasi kunci dilarang, maka saat memasukkan record, Anda dapat menentukan apakah memperbarui record yang ada diperbolehkan atau tidak. Jika keretakan hanya dapat terjadi karena kesalahan dalam kode, maka Anda dapat melindungi diri dari kesalahan tersebut dengan menentukan tandanya NOOVERWRITE.

Membaca entri

Untuk membaca catatan di LMDB, gunakan fungsinya mdb_get. Jika pasangan nilai kunci diwakili oleh struktur yang sebelumnya dibuang, maka prosedurnya terlihat seperti ini.

NodeValue * const readNode(..., NodeKey * const key) {​
    MDB_val rawKey = serialize(key);​
    MDB_val rawValue;​
    mdb_get(..., &rawKey, &rawValue);​
    return (NodeValue * const)rawValue.mv_data;​
}

Daftar yang disajikan menunjukkan bagaimana serialisasi melalui struktur dump memungkinkan Anda menghilangkan alokasi dinamis tidak hanya saat menulis, tetapi juga saat membaca data. Berasal dari fungsi mdb_get penunjuknya terlihat persis di alamat memori virtual tempat database menyimpan representasi byte objek. Faktanya, kami mendapatkan semacam ORM yang memberikan kecepatan membaca data sangat tinggi dan hampir gratis. Terlepas dari keindahan pendekatan ini, perlu diingat beberapa fitur yang terkait dengannya.

1. Untuk transaksi readonly, penunjuk ke struktur nilai dijamin tetap valid hanya sampai transaksi ditutup. Seperti disebutkan sebelumnya, halaman B-tree tempat suatu objek berada, berkat prinsip copy-on-write, tetap tidak berubah selama direferensikan oleh setidaknya satu transaksi. Pada saat yang sama, segera setelah transaksi terakhir yang terkait dengannya selesai, halaman tersebut dapat digunakan kembali untuk data baru. Jika objek perlu bertahan dari transaksi yang menghasilkannya, maka objek tersebut masih harus disalin.
2. ​​Untuk transaksi baca tulis, penunjuk ke struktur nilai yang dihasilkan hanya akan valid hingga prosedur modifikasi pertama (menulis atau menghapus data).
3. Meskipun strukturnya NodeValue tidak lengkap, tetapi dipangkas (lihat subbagian “Memesan kunci menggunakan pembanding eksternal”), Anda dapat mengakses bidangnya dengan aman melalui penunjuk. Hal utama adalah jangan meremehkannya!
4. Dalam situasi apa pun struktur tidak boleh diubah melalui penunjuk yang diterima. Semua perubahan harus dilakukan hanya melalui metode mdb_put. Namun, betapapun kerasnya Anda ingin melakukan hal ini, hal ini tidak akan mungkin terjadi, karena area memori tempat struktur ini berada dipetakan dalam mode hanya baca.
5. Memetakan ulang file ke ruang alamat proses untuk tujuan, misalnya, meningkatkan ukuran penyimpanan maksimum menggunakan fungsi tersebut mdb_env_set_map_size sepenuhnya membatalkan semua transaksi dan entitas terkait secara umum dan menunjuk ke objek tertentu pada khususnya.

Terakhir, fitur lainnya begitu berbahaya sehingga pengungkapan esensinya tidak bisa dimasukkan ke dalam paragraf lain. Dalam bab tentang pohon-B, saya memberikan diagram bagaimana halaman-halamannya disusun dalam memori. Oleh karena itu, alamat awal buffer dengan data serial bisa berubah-ubah. Karena itu, penunjuk ke sana diterima dalam struktur MDB_val dan direduksi menjadi penunjuk ke suatu struktur, ternyata tidak selaras dalam kasus umum. Pada saat yang sama, arsitektur beberapa chip (dalam kasus iOS ini adalah armv7) mengharuskan alamat data apa pun adalah kelipatan dari ukuran kata mesin atau, dengan kata lain, ukuran bit sistem ( untuk armv7 itu 32 bit). Dengan kata lain, operasi seperti itu *(int *foo)0x800002 pada mereka sama dengan melarikan diri dan mengarah pada eksekusi dengan hukuman EXC_ARM_DA_ALIGN. Ada dua cara untuk menghindari nasib menyedihkan tersebut.

Yang pertama adalah penyalinan awal data ke dalam struktur yang jelas-jelas selaras. Misalnya, pada pembanding khusus, hal ini akan tercermin sebagai berikut.

int compare(MDB_val * const a, MDB_val * const b) {
    NodeKey aKey, bKey;
    memcpy(&aKey, a->mv_data, a->mv_size);
    memcpy(&bKey, b->mv_data, b->mv_size);
    return // ...
}

Cara alternatifnya adalah dengan memberi tahu kompiler terlebih dahulu bahwa struktur nilai kunci mungkin tidak selaras dengan atribut aligned(1). Di ARM Anda bisa mendapatkan efek yang sama untuk mencapai dan menggunakan atribut yang dikemas. Mengingat metode ini juga membantu mengoptimalkan ruang yang ditempati oleh struktur, metode ini menurut saya lebih disukai приводит terhadap peningkatan biaya operasi akses data.

typedef struct __attribute__((packed)) NodeKey {
    uint8_t parentId;
    uint8_t type;
    uint8_t nameLength;
    uint8_t nameBuffer[256];
} NodeKey;

Rentang kueri

Untuk mengulangi sekelompok catatan, LMDB menyediakan abstraksi kursor. Mari kita lihat cara menggunakannya menggunakan contoh tabel dengan metadata cloud pengguna yang sudah kita kenal.

Sebagai bagian dari menampilkan daftar file dalam direktori, penting untuk menemukan semua kunci yang terkait dengan file dan folder turunannya. Di subbagian sebelumnya kami mengurutkan kunci NodeKey sedemikian rupa sehingga mereka terutama diurutkan berdasarkan ID direktori induk. Jadi, secara teknis, tugas mengambil konten folder adalah menempatkan kursor di batas atas grup kunci dengan awalan tertentu dan kemudian mengulanginya ke batas bawah.

Batas atas dapat ditemukan langsung dengan pencarian berurutan. Untuk melakukan ini, kursor ditempatkan di awal seluruh daftar kunci dalam database dan selanjutnya bertambah hingga kunci dengan pengidentifikasi direktori induk muncul di bawahnya. Pendekatan ini memiliki 2 kelemahan yang jelas:

1. Kompleksitas pencarian linier, meskipun, seperti diketahui, pada pohon pada umumnya dan pada pohon B pada khususnya dapat dilakukan dalam waktu logaritmik.​
2. Sia-sia, semua halaman sebelum halaman yang dicari diangkat dari file ke memori utama, yang biayanya sangat mahal.

Untungnya, API LMDB menyediakan cara yang efektif untuk memposisikan kursor pada awalnya.Untuk melakukan ini, Anda perlu membuat kunci yang nilainya jelas kurang dari atau sama dengan kunci yang terletak di batas atas interval. Misalnya, sehubungan dengan daftar pada gambar di atas, kita dapat membuat kunci di dalam field tersebut parentId akan sama dengan 2, dan sisanya diisi dengan nol. Kunci yang terisi sebagian tersebut dipasok ke input fungsi mdb_cursor_get menunjukkan operasi MDB_SET_RANGE.

NodeKey upperBoundSearchKey = {​
    .parentId = 2,​
    .type = 0,​
    .nameLength = 0​
};​
MDB_val value, key = serialize(upperBoundSearchKey);​
MDB_cursor *cursor;​
mdb_cursor_open(..., &cursor);​
mdb_cursor_get(cursor, &key, &value, MDB_SET_RANGE);

Jika batas atas sekelompok kunci ditemukan, maka kita melakukan iterasi sampai kita bertemu atau kunci bertemu yang lain parentId, atau kuncinya tidak akan habis sama sekali.​

do {​
    rc = mdb_cursor_get(cursor, &key, &value, MDB_NEXT);​
    // processing...​
} while (MDB_NOTFOUND != rc && // check end of table​
         IsTargetKey(key));    // check end of keys group​​

Yang menyenangkan adalah sebagai bagian dari iterasi menggunakan mdb_cursor_get, kita tidak hanya mendapatkan kuncinya, tetapi juga nilainya. Jika, untuk memenuhi kondisi pengambilan sampel, Anda perlu memeriksa, antara lain, bidang dari bagian nilai rekaman, maka bidang tersebut cukup dapat diakses tanpa isyarat tambahan.

4.3. Memodelkan hubungan antar tabel

Saat ini, kami telah berhasil mempertimbangkan semua aspek perancangan dan bekerja dengan database tabel tunggal. Kita dapat mengatakan bahwa tabel adalah kumpulan catatan yang diurutkan yang terdiri dari jenis pasangan kunci-nilai yang sama. Jika Anda menampilkan kunci sebagai persegi panjang dan nilai terkait sebagai paralelepiped, Anda mendapatkan diagram visual database.

​,war

Namun, dalam kehidupan nyata jarang sekali kita bisa bertahan dengan sedikit pertumpahan darah. Seringkali dalam database diperlukan, pertama, memiliki beberapa tabel, dan kedua, membuat pilihan di dalamnya dalam urutan yang berbeda dari kunci utama. Bagian terakhir ini dikhususkan untuk masalah penciptaan dan interkoneksinya.

Tabel indeks

Aplikasi cloud memiliki bagian "Galeri". Ini menampilkan konten media dari seluruh cloud, diurutkan berdasarkan tanggal. Untuk menerapkan pilihan seperti itu secara optimal, di sebelah tabel utama Anda perlu membuat tabel lain dengan jenis kunci baru. Mereka akan berisi bidang dengan tanggal pembuatan file, yang akan bertindak sebagai kriteria penyortiran utama. Karena kunci baru mereferensikan data yang sama dengan kunci di tabel utama, maka disebut kunci indeks. Pada gambar di bawah, mereka disorot dengan warna oranye.

Untuk memisahkan kunci tabel yang berbeda satu sama lain dalam database yang sama, bidang teknis tambahan tableId telah ditambahkan ke semuanya. Dengan menjadikannya prioritas tertinggi untuk pengurutan, kami akan mencapai pengelompokan kunci terlebih dahulu berdasarkan tabel, dan di dalam tabel - sesuai dengan aturan kami sendiri.​

Kunci indeks mereferensikan data yang sama dengan kunci utama. Implementasi langsung dari properti ini dengan mengasosiasikannya dengan salinan bagian nilai dari kunci utama tidak optimal dari beberapa sudut pandang:

1. Dalam hal ruang yang digunakan, metadatanya bisa sangat kaya.
2. Dari sudut pandang kinerja, karena ketika memperbarui metadata sebuah node, Anda harus menulis ulang menggunakan dua kunci.
3. Dari sudut pandang dukungan kode, jika kita lupa memperbarui data untuk salah satu kunci, kita akan mendapatkan bug ketidakkonsistenan data dalam penyimpanan yang sulit dipahami.

Selanjutnya, kami akan mempertimbangkan cara menghilangkan kekurangan tersebut.

Mengatur hubungan antar tabel

Pola ini sangat cocok untuk menghubungkan tabel indeks dengan tabel utama "kunci sebagai nilai". Seperti namanya, bagian nilai dari catatan indeks adalah salinan dari nilai kunci utama. Pendekatan ini menghilangkan semua kelemahan yang disebutkan di atas terkait dengan penyimpanan salinan bagian nilai dari catatan utama. Satu-satunya biaya adalah untuk mendapatkan nilai berdasarkan kunci indeks, Anda perlu membuat 2 kueri ke database, bukan satu. Secara skematis, skema database yang dihasilkan terlihat seperti ini.

Pola lain untuk mengatur hubungan antar tabel adalah "kunci berlebihan". Esensinya adalah menambahkan atribut tambahan ke kunci, yang diperlukan bukan untuk menyortir, tetapi untuk membuat ulang kunci terkait. Namun, dalam aplikasi Mail.ru Cloud terdapat contoh nyata penggunaannya, untuk menghindari pendalaman lebih dalam dalam konteks kerangka kerja iOS tertentu, saya akan memberikan contoh fiktif, namun lebih jelas.​

Klien seluler cloud memiliki halaman yang menampilkan semua file dan folder yang telah dibagikan pengguna dengan orang lain. Karena jumlah file tersebut relatif sedikit, dan terdapat banyak jenis informasi spesifik tentang publisitas yang terkait dengannya (siapa yang diberikan akses, dengan hak apa, dll.), maka tidak rasional untuk membebani bagian nilai dari file tersebut. rekam di tabel utama dengannya. Namun, jika Anda ingin menampilkan file tersebut secara offline, Anda tetap perlu menyimpannya di suatu tempat. Solusi alami adalah dengan membuat tabel terpisah untuknya. Pada diagram di bawah, kuncinya diawali dengan “P”, dan placeholder “propname” dapat diganti dengan nilai yang lebih spesifik “info publik”.​

Semua metadata unik, untuk tujuan penyimpanan tabel baru yang dibuat, ditempatkan di bagian nilai catatan. Pada saat yang sama, Anda tidak ingin menduplikasi data tentang file dan folder yang sudah disimpan di tabel utama. Sebaliknya, data berlebihan ditambahkan ke kunci “P” dalam bentuk kolom “ID node” dan “cap waktu”. Berkat mereka, Anda dapat membuat kunci indeks, yang darinya Anda dapat memperoleh kunci utama, yang akhirnya, Anda dapat memperoleh metadata simpul.

Kesimpulan

Kami menilai hasil penerapan LMDB positif. Setelah itu, jumlah aplikasi yang dibekukan menurun sebesar 30%.

Hasil pekerjaan yang dilakukan bergema di luar tim iOS. Saat ini, salah satu bagian "File" utama di aplikasi Android juga telah beralih menggunakan LMDB, dan bagian lainnya sedang dalam proses. Bahasa C, di mana penyimpanan nilai kunci diimplementasikan, merupakan bantuan yang baik untuk awalnya membuat kerangka aplikasi lintas platform di C++. Generator kode digunakan untuk menghubungkan pustaka C++ yang dihasilkan dengan kode platform di Objective-C dan Kotlin secara lancar Jin dari Dropbox, tapi itu cerita yang berbeda.

Sumber: www.habr.com