Pada musim luruh 2019, acara yang ditunggu-tunggu telah berlaku dalam pasukan iOS Cloud Mail.ru. Pangkalan data utama untuk penyimpanan berterusan keadaan aplikasi telah menjadi sangat eksotik untuk dunia mudah alih Pangkalan Data Pemetaan Memori Kilat (LMDB). Di bawah potongan kami menawarkan ulasan terperinci mengenainya dalam empat bahagian. Pertama, mari kita bercakap tentang sebab-sebab pilihan yang tidak remeh dan sukar. Kemudian kami akan meneruskan untuk mempertimbangkan tiga tiang di tengah-tengah seni bina LMDB: fail dipetakan memori, B+-tree, pendekatan salin atas tulis untuk melaksanakan transaksi dan multiversi. Akhirnya, untuk pencuci mulut - bahagian praktikal. Di dalamnya kita akan melihat cara mereka bentuk dan melaksanakan skema pangkalan data dengan beberapa jadual, termasuk satu indeks, di atas API nilai kunci peringkat rendah.

Содержание

1. Motivasi untuk pelaksanaan
2. Kedudukan LMDB
3. Tiga tonggak LMDB
   3.1. Paus #1. Fail yang dipetakan memori
   3.2. Paus #2. B+-pokok
   3.3. Paus #3. Salin atas tulis
4. Mereka bentuk skema data di atas API nilai kunci
   4.1. Abstraksi Asas
   4.2. Pemodelan Jadual
   4.3. Memodelkan hubungan antara jadual

1. Motivasi untuk pelaksanaan

Satu tahun pada 2015, kami mengambil masalah untuk mengukur kekerapan antara muka aplikasi kami ketinggalan. Kami melakukan ini atas sebab tertentu. Kami telah menerima lebih kerap aduan bahawa kadangkala aplikasi berhenti bertindak balas kepada tindakan pengguna: butang tidak boleh ditekan, senarai tidak tatal, dsb. Mengenai mekanik pengukuran memberitahu pada AvitoTech, jadi di sini saya hanya memberikan susunan nombor.

Hasil pengukuran menjadi pancuran sejuk untuk kami. Ternyata terdapat banyak lagi masalah yang disebabkan oleh pembekuan daripada yang lain. Jika sebelum menyedari fakta ini penunjuk teknikal utama kualiti adalah bebas kemalangan, maka selepas fokus beralih pada bebas beku.

Setelah membina papan pemuka dengan pembekuan dan selepas berbelanja kuantitatif и kualiti analisis sebab mereka, musuh utama menjadi jelas - logik perniagaan berat dilaksanakan dalam benang utama permohonan itu. Reaksi semula jadi terhadap aib ini adalah keinginan yang membara untuk mendorongnya ke dalam aliran kerja. Untuk menyelesaikan masalah ini secara sistematik, kami menggunakan seni bina berbilang benang berdasarkan pelakon ringan. Saya mendedikasikannya untuk penyesuaiannya untuk dunia iOS dua utas di Twitter kolektif dan artikel tentang Habré. Sebagai sebahagian daripada naratif semasa, saya ingin menekankan aspek keputusan yang mempengaruhi pilihan pangkalan data.​

Model pelakon organisasi sistem menganggap bahawa multithreading menjadi intipati kedua. Model objek di dalamnya suka merentasi sempadan aliran. Dan mereka melakukan ini bukan kadang-kadang dan di sana sini, tetapi hampir secara berterusan dan di mana-mana.​

Pangkalan data adalah salah satu komponen asas dalam rajah yang dibentangkan. Tugas utamanya adalah untuk melaksanakan makropattern Pangkalan Data Dikongsi. Jika dalam dunia perusahaan ia digunakan untuk mengatur penyegerakan data antara perkhidmatan, maka dalam hal seni bina aktor - data antara benang. Oleh itu, kami memerlukan pangkalan data yang tidak akan menyebabkan kesukaran yang minimum apabila bekerja dengannya dalam persekitaran berbilang benang. Khususnya, ini bermakna objek yang diperoleh daripadanya mestilah sekurang-kurangnya selamat untuk benang, dan idealnya tidak boleh berubah sepenuhnya. Seperti yang anda ketahui, yang terakhir boleh digunakan secara serentak dari beberapa benang tanpa menggunakan sebarang penguncian, yang mempunyai kesan yang baik terhadap prestasi.

Faktor penting kedua yang mempengaruhi pilihan pangkalan data ialah API awan kami. Ia diilhamkan oleh pendekatan penyegerakan yang diterima pakai oleh git. Seperti dia, kami menyasarkan API luar talian pertama, yang kelihatan lebih daripada sesuai untuk pelanggan awan. Diandaikan bahawa mereka hanya akan mengepam keluar keadaan penuh awan sekali, dan kemudian penyegerakan dalam kebanyakan kes akan berlaku melalui pelancaran perubahan. Malangnya, peluang ini masih hanya dalam zon teori, dan pelanggan belum belajar bagaimana untuk bekerja dengan patch dalam amalan. Terdapat beberapa sebab objektif untuk ini, yang, untuk tidak menangguhkan pengenalan, kami akan meninggalkan kurungan. Sekarang, perkara yang lebih menarik ialah kesimpulan pengajaran tentang perkara yang berlaku apabila API menyebut "A" dan penggunanya tidak menyebut "B".

Jadi, jika anda bayangkan git, yang, apabila melaksanakan perintah tarik, bukannya menggunakan tampalan pada petikan tempatan, membandingkan keadaan penuhnya dengan keadaan pelayan penuh, maka anda akan mempunyai idea yang agak tepat tentang bagaimana penyegerakan berlaku dalam awan pelanggan. Mudah untuk meneka bahawa untuk melaksanakannya, anda perlu memperuntukkan dua pokok DOM dalam ingatan dengan maklumat meta tentang semua pelayan dan fail setempat. Ternyata jika pengguna menyimpan 500 ribu fail di awan, maka untuk menyegerakkannya adalah perlu untuk mencipta dan memusnahkan dua pokok dengan 1 juta nod. Tetapi setiap nod ialah agregat yang mengandungi graf subobjek. Sehubungan dengan itu, hasil pemprofilan telah dijangkakan. Ternyata walaupun tanpa mengambil kira algoritma penggabungan, prosedur untuk mencipta dan seterusnya memusnahkan sejumlah besar objek kecil menelan kos yang cukup besar. daripada skrip pengguna. Hasilnya, kami menetapkan kriteria penting kedua dalam memilih pangkalan data - keupayaan untuk melaksanakan operasi CRUD tanpa peruntukan objek yang dinamik.

Keperluan lain adalah lebih tradisional dan keseluruhan senarainya adalah seperti berikut.

1. Keselamatan benang.
2. Pemprosesan berbilang. Didiktekan oleh keinginan untuk menggunakan contoh pangkalan data yang sama untuk menyegerakkan keadaan bukan sahaja antara benang, tetapi juga antara aplikasi utama dan sambungan iOS.
3. Keupayaan untuk mewakili entiti yang disimpan sebagai objek tidak boleh ubah.​
4. Tiada peruntukan dinamik dalam operasi CRUD.
5. Sokongan transaksi untuk sifat asas ASID: atomicity, konsistensi, pengasingan dan kebolehpercayaan.
6. Kelajuan pada kes yang paling popular.

Dengan set keperluan ini, SQLite telah dan kekal sebagai pilihan yang baik. Walau bagaimanapun, sebagai sebahagian daripada kajian alternatif, saya terjumpa sebuah buku "Bermula dengan LevelDB". Di bawah kepimpinan beliau, penanda aras telah ditulis membandingkan kelajuan kerja dengan pangkalan data yang berbeza dalam senario awan sebenar. Hasilnya melebihi jangkaan paling liar kami. Dalam kes yang paling popular - mendapatkan kursor pada senarai diisih semua fail dan senarai diisih semua fail untuk direktori tertentu - LMDB ternyata 10 kali lebih pantas daripada SQLite. Pilihan menjadi jelas.

2. Kedudukan LMDB

LMDB ialah perpustakaan yang sangat kecil (hanya 10K baris) yang melaksanakan lapisan asas terendah pangkalan data - storan.

Rajah di atas menunjukkan bahawa membandingkan LMDB dengan SQLite, yang juga melaksanakan tahap yang lebih tinggi, secara amnya tidak lebih betul daripada SQLite dengan Data Teras. Adalah lebih adil untuk memetik enjin storan yang sama seperti pesaing yang sama - BerkeleyDB, LevelDB, Sophia, RocksDB, dll. Malah terdapat perkembangan di mana LMDB bertindak sebagai komponen enjin storan untuk SQLite. Percubaan pertama sedemikian adalah pada tahun 2012 dihabiskan oleh LMDB Howard Chu. Penemuan ternyata sangat menarik sehingga inisiatifnya diambil oleh peminat OSS, dan mendapati kesinambungannya pada orang itu LumoSQL. Pada Januari 2020, pengarang projek ini ialah Den Shearer dibentangkan ia di LinuxConfAu.

LMDB digunakan terutamanya sebagai enjin untuk pangkalan data aplikasi. Perpustakaan berhutang penampilannya kepada pemaju OpenLDAP, yang sangat tidak berpuas hati dengan BerkeleyDB sebagai asas untuk projek mereka. Bermula dari perpustakaan yang sederhana btree, Howard Chu dapat mencipta salah satu alternatif paling popular pada zaman kita. Dia mendedikasikan laporannya yang sangat keren untuk cerita ini, serta struktur dalaman LMDB. "Pangkalan Data Pemetaan Memori Kilat". Contoh yang baik untuk menakluki kemudahan penyimpanan telah dikongsi oleh Leonid Yuryev (aka yleo) daripada Positive Technologies dalam laporannya di Highload 2015 “Enjin LMDB adalah juara istimewa”. Di dalamnya, beliau bercakap tentang LMDB dalam konteks tugas yang sama untuk melaksanakan ReOpenLDAP, dan LevelDB telah pun tertakluk kepada kritikan perbandingan. Hasil daripada pelaksanaan itu, Positive Technologies juga mempunyai fork yang sedang berkembang secara aktif MDBX dengan ciri yang sangat lazat, pengoptimuman dan pembetulan pepijat.

LMDB sering digunakan sebagai storan seperti sedia ada. Contohnya, pelayar Mozilla Firefox memilih ia untuk beberapa keperluan, dan, bermula dari versi 9, Xcode diutamakan SQLite untuk menyimpan indeks.

Enjin itu juga telah membuat tandanya dalam dunia pembangunan mudah alih. Kesan penggunaannya boleh mencari dalam pelanggan iOS untuk Telegram. LinkedIn pergi lebih jauh dan memilih LMDB sebagai storan lalai untuk rangka kerja caching data tempatannya Rocket Data, tentang yang memberitahu dalam artikelnya pada tahun 2016.

LMDB berjaya memperjuangkan tempat di bawah matahari dalam niche yang ditinggalkan oleh BerkeleyDB selepas ia berada di bawah kawalan Oracle. Perpustakaan ini disukai kerana kepantasan dan kebolehpercayaannya, walaupun dibandingkan dengan rakan sebayanya. Seperti yang anda ketahui, tiada makan tengah hari percuma, dan saya ingin menekankan pertukaran yang perlu anda hadapi apabila memilih antara LMDB dan SQLite. Rajah di atas jelas menunjukkan bagaimana peningkatan kelajuan dicapai. Pertama, kami tidak membayar untuk lapisan abstraksi tambahan di atas storan cakera. Jelas sekali bahawa seni bina yang baik masih tidak dapat dilakukan tanpanya, dan ia pasti akan muncul dalam kod aplikasi, tetapi ia akan menjadi lebih halus. Ia tidak akan mengandungi ciri yang tidak diperlukan oleh aplikasi tertentu, contohnya, sokongan untuk pertanyaan dalam bahasa SQL. Kedua, ia menjadi mungkin untuk melaksanakan pemetaan operasi aplikasi secara optimum pada permintaan kepada storan cakera. Jika SQLite dalam kerja saya adalah berdasarkan keperluan statistik purata bagi aplikasi purata, maka anda, sebagai pembangun aplikasi, sangat mengetahui senario beban kerja utama. Untuk penyelesaian yang lebih produktif, anda perlu membayar tanda harga yang meningkat untuk pembangunan penyelesaian awal dan untuk sokongan seterusnya.

3. Tiga tunjang LMDB

Setelah melihat LMDB dari pandangan mata burung, sudah tiba masanya untuk pergi lebih mendalam. Tiga bahagian seterusnya akan ditumpukan kepada analisis tiang utama di mana seni bina storan terletak:

1. Fail yang dipetakan memori sebagai mekanisme untuk bekerja dengan cakera dan menyegerakkan struktur data dalaman.
2. B+-tree sebagai organisasi struktur data yang disimpan.
3. Copy-on-write sebagai pendekatan untuk menyediakan sifat transaksi ACID dan multiversi.

3.1. Paus #1. Fail yang dipetakan memori

Fail yang dipetakan memori adalah elemen seni bina yang penting sehinggakan ia muncul dalam nama repositori. Isu caching dan penyegerakan akses kepada maklumat yang disimpan diserahkan sepenuhnya kepada sistem pengendalian. LMDB tidak mengandungi sebarang cache dalam dirinya sendiri. Ini adalah keputusan sedar oleh pengarang, kerana membaca data terus dari fail yang dipetakan membolehkan anda memotong banyak sudut dalam pelaksanaan enjin. Di bawah adalah senarai yang jauh dari lengkap beberapa daripada mereka.

1. Mengekalkan konsistensi data dalam storan apabila bekerja dengannya daripada beberapa proses menjadi tanggungjawab sistem pengendalian. Dalam bahagian seterusnya, mekanik ini dibincangkan secara terperinci dan dengan gambar.
2. Ketiadaan cache menghapuskan sepenuhnya LMDB daripada overhed yang dikaitkan dengan peruntukan dinamik. Membaca data dalam amalan bermakna menetapkan penunjuk ke alamat yang betul dalam ingatan maya dan tidak lebih. Bunyinya seperti fiksyen sains, tetapi dalam kod sumber storan semua panggilan ke calloc tertumpu pada fungsi konfigurasi storan.
3. Ketiadaan cache juga bermakna ketiadaan kunci yang dikaitkan dengan penyegerakan akses mereka. Pembaca, yang mungkin terdapat bilangan pembaca yang sewenang-wenangnya pada masa yang sama, tidak menemui mutex tunggal dalam perjalanan mereka ke data. Disebabkan ini, kelajuan membaca mempunyai skalabiliti linear yang ideal berdasarkan bilangan CPU. Dalam LMDB, hanya operasi pengubahsuaian disegerakkan. Hanya ada seorang penulis pada satu masa.
4. Minimum caching dan logik penyegerakan menghapuskan jenis ralat yang sangat kompleks yang dikaitkan dengan bekerja dalam persekitaran berbilang benang. Terdapat dua kajian pangkalan data yang menarik di persidangan Usenix OSDI 2014: "Semua Sistem Fail Tidak Dicipta Sama: Mengenai Kerumitan Merangka Aplikasi Konsisten Ranap" и "Menyeksa Pangkalan Data untuk Keseronokan dan Keuntungan". Daripada mereka, anda boleh mendapatkan maklumat tentang kedua-dua kebolehpercayaan LMDB yang tidak pernah berlaku sebelum ini dan pelaksanaan sifat transaksi ACID yang hampir sempurna, yang lebih baik daripada SQLite.
5. Minimalis LMDB membolehkan perwakilan mesin bagi kodnya ditempatkan sepenuhnya dalam cache L1 pemproses dengan ciri-ciri kelajuan berikutnya.

Malangnya, dalam iOS, dengan fail dipetakan memori, segala-galanya tidak seperti yang kita mahukan. Untuk bercakap tentang kekurangan yang berkaitan dengan mereka dengan lebih sedar, perlu mengingati prinsip umum melaksanakan mekanisme ini dalam sistem pengendalian.

Maklumat am tentang fail dipetakan memori

Dengan setiap aplikasi yang berjalan, sistem pengendalian mengaitkan entiti yang dipanggil proses. Setiap proses diperuntukkan julat alamat bersebelahan di mana ia meletakkan semua yang diperlukan untuk beroperasi. Di alamat paling rendah terdapat bahagian dengan kod dan data dan sumber berkod keras. Seterusnya ialah blok ruang alamat dinamik yang semakin meningkat, yang terkenal kepada kami di bawah timbunan nama. Ia mengandungi alamat entiti yang muncul semasa pengendalian program. Di bahagian atas ialah kawasan memori yang digunakan oleh timbunan aplikasi. Ia sama ada tumbuh atau mengecut; dengan kata lain, saiznya juga mempunyai sifat dinamik. Untuk mengelakkan timbunan dan timbunan daripada menolak dan mengganggu antara satu sama lain, ia terletak di hujung ruang alamat yang berbeza.​ Terdapat lubang antara dua bahagian dinamik di bahagian atas dan bawah. Sistem pengendalian menggunakan alamat di bahagian tengah ini untuk mengaitkan pelbagai entiti dengan proses. Khususnya, ia boleh mengaitkan set alamat berterusan tertentu dengan fail pada cakera. Fail sedemikian dipanggil memori-mapped.​

Ruang alamat yang diperuntukkan untuk proses adalah besar. Secara teorinya, bilangan alamat dihadkan hanya oleh saiz penunjuk, yang ditentukan oleh kapasiti bit sistem. Jika ingatan fizikal dipetakan padanya 1-ke-1, maka proses pertama akan memakan keseluruhan RAM, dan tidak akan ada perbincangan tentang sebarang multitasking.​

Walau bagaimanapun, daripada pengalaman kami, kami tahu bahawa sistem pengendalian moden boleh melaksanakan seberapa banyak proses yang dikehendaki secara serentak. Ini mungkin disebabkan oleh fakta bahawa mereka hanya memperuntukkan banyak memori untuk proses di atas kertas, tetapi sebenarnya mereka memuatkan ke dalam ingatan fizikal utama hanya bahagian yang dalam permintaan di sini dan sekarang. Oleh itu, ingatan yang berkaitan dengan proses dipanggil maya.

Sistem pengendalian menyusun memori maya dan fizikal ke dalam halaman dengan saiz tertentu. Sebaik sahaja halaman tertentu memori maya dalam permintaan, sistem pengendalian memuatkannya ke dalam memori fizikal dan memadankannya dalam jadual khas. Sekiranya tiada slot percuma, maka salah satu halaman yang dimuatkan sebelum ini disalin ke cakera, dan yang dalam permintaan mengambil tempatnya. Prosedur ini, yang akan kami kembalikan sebentar lagi, dipanggil pertukaran. Rajah di bawah menggambarkan proses yang diterangkan. Di atasnya, halaman A dengan alamat 0 telah dimuatkan dan diletakkan pada halaman memori utama dengan alamat 4. Fakta ini ditunjukkan dalam jadual surat-menyurat dalam nombor sel 0.​

Ceritanya adalah sama dengan fail yang dipetakan ke ingatan. Secara logiknya, mereka sepatutnya secara berterusan dan sepenuhnya terletak di ruang alamat maya. Walau bagaimanapun, mereka memasuki halaman memori fizikal demi halaman dan hanya atas permintaan. Pengubahsuaian halaman sedemikian disegerakkan dengan fail pada cakera. Dengan cara ini, anda boleh melakukan I/O fail dengan hanya bekerja dengan bait dalam memori - semua perubahan akan dipindahkan secara automatik oleh kernel sistem pengendalian ke fail sumber.​
​
Imej di bawah menunjukkan cara LMDB menyegerakkan keadaannya apabila bekerja dengan pangkalan data daripada proses yang berbeza. Dengan memetakan memori maya proses yang berbeza ke fail yang sama, kami secara de facto mewajibkan sistem pengendalian untuk menyegerakkan secara transitif blok tertentu ruang alamat mereka antara satu sama lain, di mana LMDB kelihatan.​
​

Satu nuansa penting ialah LMDB, secara lalai, mengubah suai fail data melalui mekanisme panggilan sistem tulis, dan memaparkan fail itu sendiri dalam mod baca sahaja. Pendekatan ini mempunyai dua akibat penting.

Akibat pertama adalah biasa kepada semua sistem pengendalian. Intinya adalah untuk menambah perlindungan terhadap kerosakan yang tidak disengajakan pada pangkalan data dengan kod yang salah. Seperti yang anda ketahui, arahan boleh laku proses adalah percuma untuk mengakses data dari mana-mana sahaja dalam ruang alamatnya. Pada masa yang sama, seperti yang baru kita ingat, memaparkan fail dalam mod baca-tulis bermakna sebarang arahan juga boleh mengubah suainya. Jika dia melakukan ini secara tidak sengaja, cuba, sebagai contoh, untuk benar-benar menulis ganti elemen tatasusunan pada indeks yang tidak wujud, maka dia secara tidak sengaja boleh menukar fail yang dipetakan ke alamat ini, yang akan membawa kepada kerosakan pangkalan data. Jika fail dipaparkan dalam mod baca sahaja, maka percubaan untuk menukar ruang alamat yang sepadan akan membawa kepada penamatan kecemasan program dengan isyarat SIGSEGV, dan fail akan kekal utuh.

Akibat kedua sudah khusus untuk iOS. Baik pengarang mahupun mana-mana sumber lain secara eksplisit menyebutnya, tetapi tanpanya LMDB tidak akan sesuai untuk dijalankan pada sistem pengendalian mudah alih ini. Bahagian seterusnya dikhaskan untuk pertimbangannya.

Spesifikasi fail dipetakan memori dalam iOS

Terdapat laporan yang menarik di WWDC pada tahun 2018 "Selam Dalam Memori iOS". Ia memberitahu kami bahawa dalam iOS, semua halaman yang terletak dalam memori fizikal adalah salah satu daripada 3 jenis: kotor, dimampatkan dan bersih.

Memori bersih ialah koleksi halaman yang boleh dipunggah tanpa rasa sakit daripada ingatan fizikal. Data yang terkandung di dalamnya boleh dimuat semula mengikut keperluan daripada sumber asalnya. Fail yang dipetakan memori baca sahaja termasuk dalam kategori ini. iOS tidak takut untuk memunggah halaman yang dipetakan ke fail dari memori pada bila-bila masa, kerana ia dijamin disegerakkan dengan fail pada cakera.
​
Semua halaman yang diubah suai berakhir dalam ingatan yang kotor, tidak kira di mana ia berada pada asalnya. Khususnya, fail dipetakan memori yang diubah suai dengan menulis ke memori maya yang dikaitkan dengannya akan diklasifikasikan dengan cara ini. Membuka LMDB dengan bendera MDB_WRITEMAP, selepas membuat perubahan padanya, anda boleh mengesahkannya secara peribadi.​

Sebaik sahaja aplikasi mula mengambil terlalu banyak memori fizikal, iOS menundukkannya kepada pemampatan halaman yang kotor. Jumlah memori yang diduduki oleh halaman yang kotor dan dimampatkan membentuk apa yang dipanggil jejak memori aplikasi. Sebaik sahaja ia mencapai nilai ambang tertentu, daemon sistem pembunuh OOM datang selepas proses dan menamatkannya secara paksa. Ini adalah keistimewaan iOS berbanding sistem pengendalian desktop. Sebaliknya, mengurangkan jejak memori dengan menukar halaman daripada memori fizikal kepada cakera tidak disediakan dalam iOS. Sebabnya hanya boleh diteka. Mungkin prosedur mengalihkan halaman secara intensif ke cakera dan belakang terlalu memakan tenaga untuk peranti mudah alih, atau iOS menjimatkan sumber menulis semula sel pada pemacu SSD, atau mungkin pereka bentuk tidak berpuas hati dengan prestasi keseluruhan sistem, di mana segala-galanya sentiasa bertukar. Walau apa pun, fakta tetap fakta.

Berita baik, yang telah disebutkan sebelum ini, ialah LMDB secara lalai tidak menggunakan mekanisme mmap untuk mengemas kini fail. Ini bermakna bahawa data yang dipaparkan diklasifikasikan oleh iOS sebagai memori bersih dan tidak menyumbang kepada jejak memori. Anda boleh mengesahkan ini menggunakan alat Xcode yang dipanggil VM Tracker. Tangkapan skrin di bawah menunjukkan keadaan memori maya iOS aplikasi Cloud semasa operasi. Pada permulaannya, 2 tika LMDB telah dimulakan di dalamnya. Yang pertama dibenarkan untuk memaparkan failnya pada 1GiB memori maya, yang kedua - 512MiB. Walaupun fakta bahawa kedua-dua storan menduduki sejumlah memori pemastautin, kedua-duanya tidak menyumbang saiz yang kotor.

Dan kini tiba masanya untuk berita buruk. Terima kasih kepada mekanisme swap dalam sistem pengendalian desktop 64-bit, setiap proses boleh menduduki sebanyak mungkin ruang alamat maya seperti yang dibenarkan oleh ruang cakera keras percuma untuk potensi swapnya. Menggantikan swap dengan pemampatan dalam iOS secara radikal mengurangkan maksimum teori. Sekarang semua proses hidup mesti dimuatkan ke dalam memori utama (baca RAM), dan semua yang tidak sesuai mesti dipaksa untuk ditamatkan. Ini dinyatakan seperti yang dinyatakan di atas lapor, dan dalam dokumentasi rasmi. Akibatnya, iOS sangat mengehadkan jumlah memori yang tersedia untuk peruntukan melalui mmap. Di sini di sini Anda boleh melihat had empirikal jumlah memori yang boleh diperuntukkan pada peranti berbeza menggunakan panggilan sistem ini. Pada model telefon pintar yang paling moden, iOS telah menjadi murah hati sebanyak 2 gigabait, dan pada versi teratas iPad - sebanyak 4. Dalam amalan, sudah tentu, anda perlu memberi tumpuan kepada model peranti yang paling rendah disokong, di mana semuanya sangat menyedihkan. Lebih teruk lagi, dengan melihat keadaan memori aplikasi dalam VM Tracker, anda akan mendapati bahawa LMDB jauh daripada satu-satunya yang menuntut memori dipetakan memori. Potongan yang baik dimakan oleh pengagih sistem, fail sumber, rangka kerja imej dan pemangsa lain yang lebih kecil.

Berdasarkan hasil percubaan dalam Cloud, kami mencapai nilai kompromi berikut untuk memori yang diperuntukkan oleh LMDB: 384 megabait untuk peranti 32-bit dan 768 untuk peranti 64-bit. Selepas kelantangan ini habis digunakan, sebarang operasi pengubahsuaian mula berakhir dengan kod MDB_MAP_FULL. Kami melihat ralat sedemikian dalam pemantauan kami, tetapi ia cukup kecil sehingga pada peringkat ini ia boleh diabaikan.

Alasan yang tidak jelas untuk penggunaan memori yang berlebihan oleh storan boleh menjadi transaksi jangka panjang. Untuk memahami bagaimana kedua-dua fenomena ini disambungkan, kami akan dibantu dengan mempertimbangkan baki dua tonggak LMDB.

3.2. Paus #2. B+-pokok

Untuk meniru jadual di atas storan nilai kunci, operasi berikut mesti ada dalam APInya:

1. Memasukkan elemen baharu.
2. Cari elemen dengan kunci yang diberikan.
3. Mengalih keluar elemen.
4. Lelaran pada selang kekunci mengikut susunan ia diisih.

Struktur data paling mudah yang boleh melaksanakan keempat-empat operasi dengan mudah ialah pepohon carian binari. Setiap nodnya mewakili kunci yang membahagikan keseluruhan subset kunci anak kepada dua subpokok. Yang kiri mengandungi yang lebih kecil daripada induk, dan yang kanan mengandungi yang lebih besar. Mendapatkan set kunci yang dipesan dicapai melalui salah satu traversal pokok klasik.​

Pokok binari mempunyai dua kelemahan asas yang menghalangnya daripada berkesan sebagai struktur data berasaskan cakera. Pertama, tahap keseimbangan mereka tidak dapat diramalkan. Terdapat risiko yang besar untuk mendapatkan pokok di mana ketinggian cawangan yang berbeza boleh berbeza-beza, yang secara ketara memburukkan kerumitan algoritma carian berbanding dengan apa yang dijangkakan. Kedua, banyaknya pautan silang antara nod menghalang pepohon binari daripada lokaliti dalam ingatan. Nod rapat (dari segi sambungan antara mereka) boleh terletak pada halaman yang sama sekali berbeza dalam ingatan maya. Akibatnya, walaupun melalui laluan mudah beberapa nod jiran dalam pokok mungkin memerlukan melawati bilangan halaman yang setanding. Ini adalah masalah walaupun apabila kita bercakap tentang keberkesanan pepohon binari sebagai struktur data dalam memori, kerana halaman yang sentiasa berputar dalam cache pemproses bukanlah kesenangan yang murah. Apabila ia berkaitan dengan kerap mendapatkan halaman yang dikaitkan dengan nod daripada cakera, keadaan menjadi sepenuhnya menyedihkan.

B-pokok, sebagai evolusi pokok binari, menyelesaikan masalah yang dikenal pasti dalam perenggan sebelumnya. Pertama, mereka mengimbangkan diri. Kedua, setiap nod mereka membahagikan set kunci anak bukan kepada 2, tetapi kepada subset tertib M, dan nombor M boleh menjadi agak besar, mengikut susunan beberapa ratus, atau bahkan ribuan.

Oleh itu:

1. Setiap nod mengandungi sejumlah besar kunci yang telah dipesan dan pokok-pokoknya sangat pendek.
2. Pokok itu memperoleh sifat lokaliti lokasi dalam ingatan, kerana kunci yang nilainya hampir secara semula jadi terletak bersebelahan antara satu sama lain pada nod yang sama atau berjiran.
3. Bilangan nod transit apabila menuruni pokok semasa operasi carian dikurangkan.
4. Bilangan nod sasaran yang dibaca semasa pertanyaan julat dikurangkan, kerana setiap daripadanya sudah mengandungi sejumlah besar kekunci tersusun.

LMDB menggunakan variasi pokok B yang dipanggil pokok B+ untuk menyimpan data. Rajah di atas menunjukkan tiga jenis nod yang wujud di dalamnya:

1. Di bahagian atas adalah akar. Ia tidak lebih daripada konsep pangkalan data di dalam gudang. Dalam satu contoh LMDB, anda boleh mencipta beberapa pangkalan data yang berkongsi ruang alamat maya yang dipetakan. Setiap daripada mereka bermula dari akarnya sendiri.
2. Pada peringkat paling rendah ialah daun. Mereka dan hanya mereka mengandungi pasangan nilai kunci yang disimpan dalam pangkalan data. By the way, ini adalah keanehan B+-pokok. Jika pokok B biasa menyimpan bahagian nilai dalam nod semua peringkat, maka variasi B+ hanya pada yang paling rendah. Setelah membetulkan fakta ini, kami akan memanggil subjenis pokok yang digunakan dalam LMDB hanya sebagai pokok B.
3. Di antara akar dan daun terdapat 0 atau lebih tahap teknikal dengan nod navigasi (cawangan). Tugas mereka adalah untuk membahagikan set kunci yang disusun antara daun.

Secara fizikal, nod ialah blok memori dengan panjang yang telah ditetapkan. Saiznya ialah berbilang saiz halaman memori dalam sistem pengendalian, yang kami bincangkan di atas. Struktur nod ditunjukkan di bawah. Pengepala mengandungi maklumat meta, yang paling jelas contohnya ialah checksum. Seterusnya datang maklumat tentang offset di mana sel dengan data berada. Data boleh sama ada kunci, jika kita bercakap tentang nod navigasi atau keseluruhan pasangan nilai kunci dalam kes daun.​ Anda boleh membaca lebih lanjut tentang struktur halaman dalam kerja "Penilaian Kedai Nilai Kunci Berprestasi Tinggi".

Setelah menangani kandungan dalaman nod halaman, kami akan mewakili pokok B LMDB dengan cara yang dipermudahkan dalam bentuk berikut.

Halaman dengan nod terletak secara berurutan pada cakera. Halaman bernombor lebih tinggi terletak di hujung fail. Halaman meta yang dipanggil mengandungi maklumat tentang offset yang mana akar semua pokok boleh ditemui. Apabila membuka fail, LMDB mengimbas halaman fail mengikut halaman dari hujung ke permulaan untuk mencari halaman meta yang sah dan melaluinya mencari pangkalan data sedia ada.​

Sekarang, mempunyai idea tentang struktur logik dan fizikal organisasi data, kita boleh meneruskan untuk mempertimbangkan tiang ketiga LMDB. Dengan bantuannya semua pengubahsuaian storan berlaku secara urus niaga dan secara berasingan antara satu sama lain, memberikan pangkalan data secara keseluruhan harta multiversi.

3.3. Paus #3. Salin atas tulis

Sesetengah operasi B-tree melibatkan membuat satu siri perubahan pada nodnya. Satu contoh ialah menambah kunci baharu pada nod yang telah mencapai kapasiti maksimumnya. Dalam kes ini, adalah perlu, pertama, untuk membahagikan nod kepada dua, dan kedua, untuk menambah pautan kepada nod anak tunas baharu dalam induknya. Prosedur ini berpotensi sangat berbahaya. Jika atas sebab tertentu (kemalangan, gangguan bekalan elektrik, dll.) hanya sebahagian daripada perubahan daripada siri berlaku, maka pokok itu akan kekal dalam keadaan tidak konsisten.

Satu penyelesaian tradisional untuk menjadikan pangkalan data toleran kesalahan ialah menambah struktur data pada cakera tambahan di sebelah B-tree - log transaksi, juga dikenali sebagai log tulis ke hadapan (WAL). Ia adalah fail pada penghujung operasi yang dimaksudkan ditulis dengan ketat sebelum mengubah suai B-tree itu sendiri. Oleh itu, jika rasuah data dikesan semasa diagnosis kendiri, pangkalan data merujuk log untuk menyusun dirinya sendiri.

LMDB telah memilih kaedah yang berbeza sebagai mekanisme toleransi kesalahan, dipanggil salin atas tulis. Intipatinya ialah daripada mengemas kini data pada halaman sedia ada, ia mula-mula menyalinnya sepenuhnya dan membuat semua pengubahsuaian dalam salinan.​

Seterusnya, untuk membolehkan data yang dikemas kini tersedia, adalah perlu untuk menukar pautan ke nod yang telah menjadi semasa dalam nod induknya. Oleh kerana ia juga perlu diubah suai untuk ini, ia juga disalin terlebih dahulu. Proses ini berterusan secara rekursif sehingga ke akar. Perkara terakhir yang perlu diubah ialah data pada halaman meta.​​

Jika tiba-tiba proses ranap semasa prosedur kemas kini, maka sama ada halaman meta baharu tidak akan dibuat, atau ia tidak akan ditulis ke cakera sepenuhnya, dan jumlah semaknya tidak betul. Dalam salah satu daripada dua kes ini, halaman baharu tidak akan dapat dicapai, tetapi halaman lama tidak akan terjejas. Ini menghapuskan keperluan untuk LMDB menulis log ke hadapan untuk mengekalkan konsistensi data. Secara de facto, struktur storan data pada cakera yang diterangkan di atas serentak mengambil alih fungsinya. Ketiadaan log transaksi yang jelas adalah salah satu ciri LMDB yang menyediakan kelajuan membaca data yang tinggi.​

Reka bentuk yang terhasil, dipanggil pokok B tambahan sahaja, secara semula jadi menyediakan pengasingan transaksi dan berbilang versi. Dalam LMDB, setiap transaksi terbuka dikaitkan dengan akar pokok yang berkaitan pada masa ini. Sehingga urus niaga selesai, halaman pokok yang dikaitkan dengannya tidak akan ditukar atau digunakan semula untuk versi baharu data. Oleh itu, anda boleh bekerja selama mana yang anda suka dengan tepat set data yang relevan pada masa itu transaksi telah dibuka, walaupun storan terus dikemas kini secara aktif pada masa ini. Ini adalah intipati multiversi, menjadikan LMDB sumber data yang ideal untuk kesayangan kita UICollectionView. Setelah membuka urus niaga, tiada keperluan untuk meningkatkan jejak memori aplikasi dengan tergesa-gesa mengepam data semasa ke dalam beberapa struktur dalam ingatan, kerana takut tiada apa-apa. Ciri ini membezakan LMDB daripada SQLite yang sama, yang tidak boleh membanggakan pengasingan total tersebut. Setelah membuka dua urus niaga dalam yang terakhir dan memadamkan rekod tertentu dalam salah satu daripadanya, tidak mungkin lagi untuk mendapatkan rekod yang sama dalam baki kedua.

Bahagian sebalik syiling ialah penggunaan memori maya yang berpotensi lebih tinggi. Slaid menunjukkan rupa struktur pangkalan data jika ia diubah suai serentak dengan 3 transaksi baca terbuka melihat versi pangkalan data yang berbeza. Memandangkan LMDB tidak boleh menggunakan semula nod yang boleh dicapai daripada akar yang dikaitkan dengan urus niaga semasa, kedai tidak mempunyai pilihan selain memperuntukkan satu lagi punca keempat dalam ingatan dan sekali lagi mengklon halaman yang diubah suai di bawahnya.​

Di sini adalah berguna untuk mengingat kembali bahagian pada fail yang dipetakan memori. Nampaknya penggunaan tambahan memori maya tidak sepatutnya membimbangkan kami, kerana ia tidak menyumbang kepada jejak memori aplikasi. Walau bagaimanapun, pada masa yang sama, diperhatikan bahawa iOS sangat kedekut dalam memperuntukkannya, dan kami tidak boleh, seperti pada pelayan atau desktop, menyediakan rantau LMDB sebanyak 1 terabait dan tidak memikirkan ciri ini sama sekali. Jika boleh, anda harus cuba menjadikan sepanjang hayat urus niaga sesingkat mungkin.

4. Mereka bentuk skema data di atas API nilai kunci

Mari mulakan analisis API kami dengan melihat abstraksi asas yang disediakan oleh LMDB: persekitaran dan pangkalan data, kunci dan nilai, urus niaga dan kursor.

Nota tentang penyenaraian kod

Semua fungsi dalam API LMDB awam mengembalikan hasil kerja mereka dalam bentuk kod ralat, tetapi dalam semua penyenaraian berikutnya pengesahannya ditinggalkan demi ringkasnya.​ Dalam amalan, kami juga menggunakan milik kami sendiri untuk berinteraksi dengan repositori garpu Pembalut C++ lmdbxx, di mana ralat diwujudkan sebagai pengecualian C++.

Sebagai cara terpantas untuk menyambungkan LMDB ke projek untuk iOS atau macOS, saya mencadangkan CocoaPod saya POSLMDB.

4.1. Abstraksi asas

Persekitaran

Struktur MDB_env ialah repositori keadaan dalaman LMDB. Keluarga fungsi awalan mdb_env membolehkan anda mengkonfigurasi beberapa sifatnya. Dalam kes paling mudah, permulaan enjin kelihatan seperti ini.

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

Dalam aplikasi Cloud Mail.ru, kami menukar nilai lalai hanya dua parameter.

Yang pertama ialah saiz ruang alamat maya tempat fail storan dipetakan. Malangnya, walaupun pada peranti yang sama, nilai khusus boleh berbeza dengan ketara dari larian ke larian. Untuk mengambil kira ciri iOS ini, volum storan maksimum dipilih secara dinamik. Bermula dari nilai tertentu, ia dibahagi dua secara berurutan sehingga fungsi mdb_env_open tidak akan mengembalikan hasil yang berbeza daripada ENOMEM. Secara teori, terdapat juga cara yang bertentangan - mula-mula memperuntukkan memori minimum ke enjin, dan kemudian, apabila ralat diterima, MDB_MAP_FULL, tingkatkan. Namun, ia jauh lebih berduri. Sebabnya ialah prosedur untuk memperuntukkan semula memori (remap) menggunakan fungsi tersebut mdb_env_set_map_size membatalkan semua entiti (kursor, urus niaga, kunci dan nilai) yang diterima sebelum ini daripada enjin. Mengambil kira kejadian ini dalam kod akan membawa kepada komplikasi yang ketara. Walau bagaimanapun, jika ingatan maya sangat penting kepada anda, maka ini mungkin sebab untuk melihat lebih dekat pada garpu yang telah pergi jauh ke hadapan MDBX, di mana antara ciri yang diumumkan terdapat "pelarasan saiz pangkalan data secara automatik".

Parameter kedua, nilai lalai yang tidak sesuai dengan kami, mengawal mekanisme memastikan keselamatan benang. Malangnya, sekurang-kurangnya iOS 10 mempunyai masalah dengan sokongan untuk storan setempat benang. Atas sebab ini, dalam contoh di atas, repositori dibuka dengan bendera MDB_NOTLS. Di samping itu, ia juga perlu garpu Pembalut C++ lmdbxxuntuk memotong pembolehubah dengan atribut ini dan di dalamnya.

Pangkalan data

Pangkalan data ialah contoh B-tree yang berasingan, yang kami bincangkan di atas. Pembukaannya berlaku dalam transaksi, yang mungkin kelihatan agak pelik pada mulanya.

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);

Sesungguhnya, transaksi dalam LMDB ialah entiti storan, bukan entiti pangkalan data tertentu. Konsep ini membolehkan anda melakukan operasi atom pada entiti yang terletak dalam pangkalan data yang berbeza. Secara teori, ini membuka kemungkinan memodelkan jadual dalam bentuk pangkalan data yang berbeza, tetapi pada satu masa saya mengambil jalan yang berbeza, diterangkan secara terperinci di bawah.

Kunci dan nilai

Struktur MDB_val memodelkan konsep kunci dan nilai. Repositori tidak mempunyai idea tentang semantik mereka. Baginya, sesuatu yang lain hanyalah tatasusunan bait saiz tertentu. Saiz kunci maksimum ialah 512 bait.

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

Menggunakan pembanding, kedai mengisih kunci dalam tertib menaik. Jika anda tidak menggantikannya dengan anda sendiri, maka yang lalai akan digunakan, yang menyusunnya bait demi bait dalam susunan leksikografi.​

Transaksi

Struktur transaksi diterangkan secara terperinci dalam bab sebelumnya, jadi di sini saya akan mengulangi sifat utama mereka secara ringkas:

1. Menyokong semua sifat asas ASID: atomicity, konsistensi, pengasingan dan kebolehpercayaan. Saya tidak dapat membantu tetapi menyedari bahawa terdapat pepijat dari segi ketahanan pada macOS dan iOS yang telah diperbaiki dalam MDBX. Anda boleh membaca lebih lanjut dalam mereka README.
2. Pendekatan kepada multithreading diterangkan oleh skema "penulis tunggal / berbilang pembaca". Penulis sekat antara satu sama lain, tetapi jangan sekat pembaca. Pembaca tidak menghalang penulis atau satu sama lain.
3. Sokongan untuk transaksi bersarang.
4. Sokongan berbilang versi.

Multiversi dalam LMDB sangat bagus sehingga saya ingin menunjukkannya dalam tindakan. Daripada kod di bawah, anda boleh melihat bahawa setiap transaksi berfungsi dengan betul-betul versi pangkalan data yang terkini pada masa ia dibuka, diasingkan sepenuhnya daripada semua perubahan berikutnya. Memulakan storan dan menambah rekod ujian padanya tidak mewakili apa-apa yang menarik, jadi ritual ini dibiarkan di bawah spoiler.

Menambah entri ujian

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 syorkan anda mencuba helah yang sama dengan SQLite dan lihat apa yang berlaku.

Multiversi membawa faedah yang sangat bagus kepada kehidupan pembangun iOS. Menggunakan sifat ini, anda boleh dengan mudah dan semula jadi melaraskan kadar kemas kini sumber data untuk borang skrin, berdasarkan pertimbangan pengalaman pengguna. Sebagai contoh, mari kita ambil ciri aplikasi Cloud Mail.ru seperti autoloading kandungan daripada galeri media sistem. Dengan sambungan yang baik, pelanggan dapat menambah beberapa foto sesaat pada pelayan. Jika anda mengemas kini selepas setiap muat turun UICollectionView dengan kandungan media dalam awan pengguna, anda boleh melupakan kira-kira 60 fps dan menatal lancar semasa proses ini. Untuk mengelakkan kemas kini skrin yang kerap, anda perlu mengehadkan kadar perubahan data dalam asas UICollectionViewDataSource.

Jika pangkalan data tidak menyokong multiversi dan membenarkan anda bekerja hanya dengan keadaan semasa, maka untuk mencipta petikan data yang stabil masa anda perlu menyalinnya sama ada ke beberapa struktur data dalam memori atau ke jadual sementara. Mana-mana pendekatan ini sangat mahal. Dalam kes storan dalam memori, kita mendapat kos dalam ingatan, disebabkan oleh menyimpan objek yang dibina, dan dalam masa, dikaitkan dengan transformasi ORM yang berlebihan. Bagi jadual sementara, ini adalah keseronokan yang lebih mahal, masuk akal hanya dalam kes yang tidak remeh.

Penyelesaian pelbagai versi LMDB menyelesaikan masalah mengekalkan sumber data yang stabil dengan cara yang sangat elegan. Cukup sekadar membuka transaksi dan voila - sehingga kami melengkapkannya, set data dijamin akan diperbaiki. Logik untuk kelajuan kemas kininya kini sepenuhnya berada di tangan lapisan pembentangan, tanpa overhed sumber penting.

Kursor

Kursor menyediakan mekanisme untuk lelaran teratur ke atas pasangan nilai kunci melalui traversal B-tree. Tanpa mereka, adalah mustahil untuk memodelkan jadual dalam pangkalan data dengan berkesan, yang kini kita beralih kepada.

4.2. Pemodelan Jadual

Sifat susunan kunci membolehkan anda membina abstraksi peringkat tinggi seperti jadual di atas abstraksi asas. Mari kita pertimbangkan proses ini menggunakan contoh jadual utama klien awan, yang menyimpan maklumat cache tentang semua fail dan folder pengguna.

Skema jadual

Salah satu senario biasa yang struktur jadual dengan pepohon folder harus disesuaikan ialah pemilihan semua elemen yang terletak dalam direktori tertentu. Model organisasi data yang baik untuk pertanyaan yang cekap seperti ini ialah Senarai Kecukupan. Untuk melaksanakannya di atas storan nilai kunci, adalah perlu untuk mengisih kunci fail dan folder dengan cara yang ia dikumpulkan berdasarkan keahlian mereka dalam direktori induk. Di samping itu, untuk memaparkan kandungan direktori dalam bentuk yang biasa kepada pengguna Windows (folder pertama, kemudian fail, kedua-duanya disusun mengikut abjad), adalah perlu untuk memasukkan medan tambahan yang sepadan dalam kekunci.

Gambar di bawah menunjukkan bagaimana, berdasarkan tugasan di tangan, perwakilan kunci dalam bentuk tatasusunan bait mungkin kelihatan seperti. Bait dengan pengecam direktori induk (merah) diletakkan dahulu, kemudian dengan jenis (hijau) dan di ekor dengan nama (biru). Diisih oleh pembanding LMDB lalai dalam susunan leksikografi, ia disusun dalam cara yang diperlukan. Merentasi kekunci secara berurutan dengan awalan merah yang sama memberi kita nilai yang berkaitan dalam susunan ia harus dipaparkan dalam antara muka pengguna (di sebelah kanan), tanpa memerlukan sebarang pemprosesan pasca tambahan.

Mensiri Kunci dan Nilai

Banyak kaedah untuk mensiri objek telah dicipta di dunia. Oleh kerana kami tidak mempunyai keperluan lain selain daripada kelajuan, kami memilih sepantas mungkin untuk diri kami sendiri - longgokan memori yang diduduki oleh contoh struktur bahasa C. Oleh itu, kunci elemen direktori boleh dimodelkan dengan struktur berikut NodeKey.

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

Untuk menyelamatkan NodeKey dalam simpanan yang diperlukan dalam objek MDB_val letakkan penunjuk data ke alamat permulaan struktur, dan hitung saiznya dengan fungsi sizeof.

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

Dalam bab pertama mengenai kriteria pemilihan pangkalan data, saya menyebut meminimumkan peruntukan dinamik dalam operasi CRUD sebagai faktor pemilihan yang penting. Kod fungsi serialize menunjukkan bagaimana dalam kes LMDB mereka boleh dielakkan sepenuhnya apabila memasukkan rekod baharu ke dalam pangkalan data. Tatasusunan bait yang masuk daripada pelayan mula-mula diubah menjadi struktur tindanan, dan kemudiannya dibuang secara remeh ke dalam storan. Memandangkan tiada juga peruntukan dinamik di dalam LMDB, anda boleh mendapatkan situasi yang hebat mengikut piawaian iOS - gunakan hanya memori tindanan untuk bekerja dengan data di sepanjang laluan dari rangkaian ke cakera!

Memesan kunci dengan pembanding binari

Hubungan susunan kunci ditentukan oleh fungsi khas yang dipanggil pembanding. Memandangkan enjin tidak mengetahui apa-apa tentang semantik bait yang terkandung di dalamnya, pembanding lalai tidak mempunyai pilihan selain menyusun kekunci dalam susunan leksikografik, menggunakan perbandingan bait demi bait. Menggunakannya untuk menyusun struktur adalah serupa dengan mencukur dengan kapak pemotong. Walau bagaimanapun, dalam kes mudah saya dapati kaedah ini boleh diterima. Alternatifnya diterangkan di bawah, tetapi di sini saya akan perhatikan beberapa garu yang bertaburan di sepanjang laluan ini.

Perkara pertama yang perlu diingat ialah perwakilan memori jenis data primitif. Oleh itu, pada semua peranti Apple, pembolehubah integer disimpan dalam format Endian kecil. Ini bermakna bahawa bait paling tidak ketara akan berada di sebelah kiri, dan tidak mungkin untuk mengisih integer menggunakan perbandingan bait demi bait. Sebagai contoh, cuba melakukan ini dengan set nombor dari 0 hingga 511 akan menghasilkan keputusan berikut.

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

Untuk menyelesaikan masalah ini, integer mesti disimpan dalam kekunci dalam format yang sesuai untuk pembanding bait-bait. Fungsi dari keluarga akan membantu anda melakukan transformasi yang diperlukan hton* (khususnya htons untuk nombor dua bait daripada contoh).

Format untuk mewakili rentetan dalam pengaturcaraan adalah, seperti yang anda tahu, keseluruhan Sejarah. Jika semantik rentetan, serta pengekodan yang digunakan untuk mewakilinya dalam ingatan, menunjukkan bahawa mungkin terdapat lebih daripada satu bait setiap aksara, maka adalah lebih baik untuk segera meninggalkan idea menggunakan pembanding lalai.

Perkara kedua yang perlu diingat ialah prinsip penjajaran penyusun medan struktur. Kerana mereka, bait dengan nilai sampah boleh dibentuk dalam ingatan antara medan, yang, tentu saja, memecahkan pengisihan bait-bait. Untuk menghapuskan sampah, anda perlu sama ada mengisytiharkan medan dalam susunan yang ditetapkan dengan ketat, mengingati peraturan penjajaran atau menggunakan atribut dalam pengisytiharan struktur packed.

Memesan kunci dengan pembanding luaran

Logik perbandingan utama mungkin terlalu kompleks untuk pembanding binari. Salah satu daripada banyak sebab ialah kehadiran bidang teknikal dalam struktur. Saya akan menggambarkan kejadian mereka menggunakan contoh kunci untuk elemen direktori yang sudah biasa kepada kita.

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

Walaupun kesederhanaannya, dalam kebanyakan kes ia menggunakan terlalu banyak ingatan. Penampan untuk nama mengambil 256 bait, walaupun secara purata nama fail dan folder jarang melebihi 20-30 aksara.

Salah satu teknik standard untuk mengoptimumkan saiz rekod ialah "memangkas"nya kepada saiz sebenar. Intipatinya ialah kandungan semua medan pembolehubah-panjang disimpan dalam penimbal pada penghujung struktur, dan panjangnya disimpan dalam pembolehubah berasingan.​ Menurut pendekatan ini, kunci NodeKey diubah seperti berikut.

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

Selanjutnya, apabila bersiri, saiz data tidak ditentukan sizeof keseluruhan struktur, dan saiz semua medan ialah panjang tetap ditambah saiz bahagian penimbal yang sebenarnya digunakan.

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

Hasil daripada pemfaktoran semula, kami menerima penjimatan yang ketara dalam ruang yang diduduki oleh kunci. Namun, disebabkan bidang teknikal nameLength, pembanding binari lalai tidak lagi sesuai untuk perbandingan utama. Jika kita tidak menggantikannya dengan nama kita sendiri, maka panjang nama akan menjadi faktor keutamaan yang lebih tinggi dalam menyusun daripada nama itu sendiri.

LMDB membenarkan setiap pangkalan data mempunyai fungsi perbandingan utamanya sendiri. Ini dilakukan menggunakan fungsi mdb_set_compare ketat sebelum dibuka. Atas sebab yang jelas, ia tidak boleh diubah sepanjang hayat pangkalan data. Pembanding menerima dua kunci dalam format binari sebagai input, dan pada output ia mengembalikan hasil perbandingan: kurang daripada (-1), lebih besar daripada (1) atau sama dengan (0). Pseudokod untuk NodeKey nampak macam tu.

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 // ...
}​

Selagi semua kunci dalam pangkalan data adalah daripada jenis yang sama, menghantar perwakilan baitnya tanpa syarat kepada jenis struktur kunci aplikasi adalah sah. Terdapat satu nuansa di sini, tetapi ia akan dibincangkan di bawah dalam subseksyen "Rekod Membaca".

Mensiri Nilai

LMDB berfungsi dengan sangat intensif dengan kunci rekod yang disimpan. Perbandingan mereka antara satu sama lain berlaku dalam rangka kerja mana-mana operasi yang digunakan, dan prestasi keseluruhan penyelesaian bergantung pada kelajuan pembanding. Dalam dunia yang ideal, pembanding binari lalai sepatutnya cukup untuk membandingkan kekunci, tetapi jika anda terpaksa menggunakan kekunci anda sendiri, maka prosedur untuk menyahsiri kekunci di dalamnya hendaklah secepat mungkin.

Pangkalan data tidak begitu berminat dengan bahagian nilai rekod (nilai). Penukarannya daripada perwakilan bait kepada objek berlaku hanya apabila ia sudah diperlukan oleh kod aplikasi, contohnya, untuk memaparkannya pada skrin. Memandangkan perkara ini jarang berlaku, keperluan kelajuan untuk prosedur ini tidak begitu kritikal, dan dalam pelaksanaannya kami lebih bebas untuk menumpukan pada kemudahan. Contohnya, untuk mensirikan metadata tentang fail yang belum dimuat turun, kami menggunakan NSKeyedArchiver.

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

Walau bagaimanapun, ada kalanya prestasi masih penting. Contohnya, apabila menyimpan metamaklumat tentang struktur fail awan pengguna, kami menggunakan longgokan objek memori yang sama. Kemuncak tugas menjana perwakilan bersiri mereka adalah hakikat bahawa unsur-unsur direktori dimodelkan oleh hierarki kelas.​

Untuk melaksanakannya dalam bahasa C, bidang khusus waris diletakkan dalam struktur berasingan, dan sambungannya dengan asas ditentukan melalui bidang kesatuan jenis. Kandungan sebenar kesatuan ditentukan melalui jenis atribut teknikal.

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

Menambah dan mengemas kini rekod

Kunci dan nilai bersiri boleh ditambah ke kedai. Untuk melakukan ini, gunakan fungsi mdb_put.

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

Pada peringkat konfigurasi, storan boleh dibenarkan atau dilarang daripada menyimpan berbilang rekod dengan kunci yang sama. Jika penduaan kunci dilarang, maka apabila memasukkan rekod, anda boleh menentukan sama ada mengemas kini rekod sedia ada dibenarkan atau tidak. Jika fraying hanya boleh berlaku akibat ralat dalam kod, maka anda boleh melindungi diri anda daripadanya dengan menyatakan bendera NOOVERWRITE.

Membaca entri

Untuk membaca rekod dalam LMDB, gunakan fungsi mdb_get. Jika pasangan nilai kunci diwakili oleh struktur yang dibuang sebelum ini, maka prosedur ini kelihatan 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;​
}

Penyenaraian yang dibentangkan menunjukkan cara penyirian melalui pembuangan struktur membolehkan anda menyingkirkan peruntukan dinamik bukan sahaja semasa menulis, tetapi semasa membaca data. Berasal daripada fungsi mdb_get penunjuk melihat tepat pada alamat memori maya di mana pangkalan data menyimpan perwakilan bait objek. Malah, kami mendapat sejenis ORM yang menyediakan kelajuan bacaan data yang sangat tinggi hampir percuma. Walaupun semua keindahan pendekatan, adalah perlu untuk mengingati beberapa ciri yang berkaitan dengannya.

1. Untuk transaksi baca sahaja, penunjuk kepada struktur nilai dijamin kekal sah hanya sehingga transaksi ditutup. Seperti yang dinyatakan sebelum ini, halaman B-tree di mana objek terletak, terima kasih kepada prinsip salin-tulis, kekal tidak berubah selagi ia dirujuk oleh sekurang-kurangnya satu transaksi. Pada masa yang sama, sebaik sahaja transaksi terakhir yang dikaitkan dengan mereka selesai, halaman boleh digunakan semula untuk data baharu. Sekiranya objek itu perlu untuk bertahan dalam transaksi yang menjananya, maka ia masih perlu disalin.
2. Untuk transaksi tulis baca, penunjuk kepada struktur nilai yang terhasil hanya sah sehingga prosedur pengubahsuaian pertama (menulis atau memadam data).
3. Walaupun struktur NodeValue tidak sepenuhnya, tetapi dipangkas (lihat subseksyen "Memesan kunci menggunakan pembanding luaran"), anda boleh mengakses medannya dengan selamat melalui penuding. Perkara utama bukanlah untuk membatalkan rujukan!
4. Dalam apa jua keadaan, struktur tidak boleh diubah suai melalui penunjuk yang diterima. Semua perubahan mesti dibuat hanya melalui kaedah mdb_put. Walau bagaimanapun, tidak kira betapa sukarnya anda ingin melakukan ini, ia tidak akan dapat dilakukan, kerana kawasan memori di mana struktur ini terletak dipetakan dalam mod baca sahaja.
5. Petakan semula fail ke ruang alamat proses untuk tujuan, contohnya, meningkatkan saiz storan maksimum menggunakan fungsi tersebut mdb_env_set_map_size membatalkan sepenuhnya semua urus niaga dan entiti berkaitan secara umum dan menunjuk kepada objek tertentu khususnya.

Akhir sekali, ciri lain adalah sangat berbahaya sehingga mendedahkan intipatinya tidak sesuai dengan perenggan lain. Dalam bab tentang pokok B, saya memberikan gambar rajah bagaimana halamannya disusun dalam ingatan. Ia berikutan daripada ini bahawa alamat permulaan penimbal dengan data bersiri boleh menjadi sewenang-wenangnya. Kerana ini, penunjuk kepada mereka diterima dalam struktur MDB_val dan dikurangkan kepada penunjuk kepada struktur, ia ternyata tidak sejajar dalam kes umum. Pada masa yang sama, seni bina beberapa cip (dalam kes iOS ini adalah armv7) memerlukan alamat mana-mana data ialah gandaan saiz perkataan mesin atau, dengan kata lain, saiz bit sistem ( untuk armv7 ia adalah 32 bit). Dalam erti kata lain, operasi seperti *(int *foo)0x800002 ke atas mereka adalah sama dengan melarikan diri dan membawa kepada pelaksanaan dengan keputusan EXC_ARM_DA_ALIGN. Terdapat dua cara untuk mengelakkan nasib yang menyedihkan.

Yang pertama bermuara kepada penyalinan awal data ke dalam struktur yang sejajar dengan jelas. Sebagai contoh, pada pembanding tersuai ini akan ditunjukkan seperti 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 alternatif ialah memberitahu pengkompil terlebih dahulu bahawa struktur nilai kunci mungkin tidak diselaraskan dengan atribut aligned(1). Pada ARM anda boleh mempunyai kesan yang sama capai dan menggunakan atribut packed. Memandangkan ia juga membantu untuk mengoptimumkan ruang yang diduduki oleh struktur, kaedah ini kelihatan lebih baik kepada saya, walaupun приводит kepada peningkatan dalam kos operasi capaian data.

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

Pertanyaan julat

Untuk mengulangi sekumpulan rekod, LMDB menyediakan abstraksi kursor. Mari lihat cara bekerja dengannya menggunakan contoh jadual dengan metadata awan pengguna yang sudah biasa kepada kita.

Sebagai sebahagian daripada memaparkan senarai fail dalam direktori, adalah perlu untuk mencari semua kunci yang dikaitkan dengan fail anak dan foldernya. Dalam subseksyen sebelumnya kami mengisih kunci NodeKey supaya mereka terutamanya dipesan oleh ID direktori induk. Oleh itu, secara teknikal, tugas untuk mendapatkan semula kandungan folder adalah untuk meletakkan kursor pada sempadan atas kumpulan kunci dengan awalan yang diberikan dan kemudian beralih ke sempadan bawah.

Sempadan atas boleh didapati secara langsung dengan carian berurutan. Untuk melakukan ini, kursor diletakkan pada permulaan keseluruhan senarai kunci dalam pangkalan data dan terus meningkat sehingga kunci dengan pengecam direktori induk muncul di bawahnya. Pendekatan ini mempunyai 2 kelemahan yang jelas:

1. Kerumitan carian linear, walaupun, seperti yang diketahui, dalam pokok secara umum dan dalam B-pokok khususnya ia boleh dijalankan dalam masa logaritma.​
2. Dengan sia-sia, semua halaman sebelum halaman yang dicari diangkat dari fail ke memori utama, yang sangat mahal.

Nasib baik, API LMDB menyediakan cara yang berkesan untuk meletakkan kursor pada mulanya. Untuk melakukan ini, anda perlu menjana kunci yang nilainya jelas kurang daripada atau sama dengan kunci yang terletak di sempadan atas selang. Sebagai contoh, berhubung dengan senarai dalam rajah di atas, kita boleh membuat kunci di mana medan parentId akan sama dengan 2, dan semua yang lain diisi dengan sifar. Kunci yang terisi separa itu dibekalkan kepada 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 sempadan atas sekumpulan kunci ditemui, maka kita akan mengulanginya sehingga sama ada kita bertemu atau kunci bertemu yang lain parentId, atau kunci 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​​

Apa yang menarik ialah sebagai sebahagian daripada lelaran menggunakan mdb_cursor_get, kita bukan sahaja mendapat kunci, tetapi juga nilainya. Jika, untuk memenuhi syarat pensampelan, anda perlu menyemak, antara lain, medan daripada bahagian nilai rekod, maka ia agak boleh diakses tanpa gerak isyarat tambahan.

4.3. Memodelkan hubungan antara jadual

Pada masa ini, kami telah berjaya mempertimbangkan semua aspek mereka bentuk dan bekerja dengan pangkalan data satu jadual. Kita boleh mengatakan bahawa jadual ialah satu set rekod diisih yang terdiri daripada jenis pasangan nilai kunci yang sama. Jika anda memaparkan kunci sebagai segi empat tepat dan nilai yang berkaitan sebagai parallelepiped, anda mendapat gambar rajah visual pangkalan data.

​

Walau bagaimanapun, dalam kehidupan sebenar ia jarang dapat bertahan dengan sedikit pertumpahan darah. Selalunya dalam pangkalan data diperlukan, pertama, untuk mempunyai beberapa jadual, dan kedua, untuk membuat pilihan di dalamnya dalam susunan yang berbeza daripada kunci utama. Bahagian terakhir ini ditumpukan kepada isu penciptaan dan kesalinghubungan mereka.

Jadual indeks

Aplikasi awan mempunyai bahagian "Galeri". Ia memaparkan kandungan media dari keseluruhan awan, disusun mengikut tarikh. Untuk melaksanakan pemilihan sedemikian secara optimum, di sebelah jadual utama anda perlu membuat satu lagi dengan jenis kekunci baharu. Ia akan mengandungi medan dengan tarikh fail dibuat, yang akan bertindak sebagai kriteria pengisihan utama. Kerana kunci baharu merujuk data yang sama seperti kunci dalam jadual utama, ia dipanggil kunci indeks. Dalam gambar di bawah mereka diserlahkan dalam warna oren.

Untuk memisahkan kekunci jadual yang berbeza antara satu sama lain dalam pangkalan data yang sama, tableId medan teknikal tambahan telah ditambahkan pada kesemuanya. Dengan menjadikannya keutamaan tertinggi untuk pengisihan, kami akan mencapai pengumpulan kunci terlebih dahulu mengikut jadual, dan dalam jadual - mengikut peraturan kami sendiri.​

Kunci indeks merujuk data yang sama seperti kunci utama. Pelaksanaan terus sifat ini melalui mengaitkan dengannya salinan bahagian nilai kunci utama tidak optimum dari beberapa sudut pandangan:

1. Dari segi ruang yang digunakan, metadata boleh menjadi agak kaya.
2. Dari sudut prestasi, kerana apabila mengemas kini metadata sesuatu nod, anda perlu menulis semula menggunakan dua kekunci.
3. Dari sudut pandangan sokongan kod, jika kita terlupa untuk mengemas kini data untuk salah satu kunci, kita akan mendapat pepijat yang sukar difahami ketidakkonsistenan data dalam storan.

Seterusnya, kami akan mempertimbangkan bagaimana untuk menghapuskan kekurangan ini.

Mengatur hubungan antara jadual

Corak ini sangat sesuai untuk menghubungkan jadual indeks dengan jadual utama "kunci sebagai nilai". Seperti namanya, bahagian nilai rekod indeks ialah salinan nilai kunci utama. Pendekatan ini menghapuskan semua kelemahan yang disebutkan di atas yang berkaitan dengan menyimpan salinan bahagian nilai rekod utama. Satu-satunya kos ialah untuk mendapatkan nilai dengan kunci indeks, anda perlu membuat 2 pertanyaan kepada pangkalan data dan bukannya satu. Secara skematik, skema pangkalan data yang terhasil kelihatan seperti ini.

Corak lain untuk mengatur hubungan antara jadual ialah "kunci berlebihan". Intipatinya adalah untuk menambah atribut tambahan pada kunci, yang diperlukan bukan untuk menyusun, tetapi untuk mencipta semula kunci yang berkaitan. Dalam aplikasi Cloud Mail.ru terdapat contoh sebenar penggunaannya, bagaimanapun, untuk mengelakkan penyelaman mendalam ke dalam konteks rangka kerja iOS tertentu, saya akan memberikan contoh rekaan, tetapi contoh yang lebih jelas.​

Pelanggan mudah alih awan mempunyai halaman yang memaparkan semua fail dan folder yang telah dikongsi pengguna dengan orang lain. Memandangkan terdapat agak sedikit fail sedemikian, dan terdapat banyak jenis maklumat khusus yang berbeza tentang publisiti yang dikaitkan dengannya (siapa yang diberikan akses, dengan hak apa, dsb.), adalah tidak rasional untuk membebankan bahagian nilai rekod dalam jadual utama dengannya. Walau bagaimanapun, jika anda ingin memaparkan fail tersebut di luar talian, anda masih perlu menyimpannya di suatu tempat. Penyelesaian semula jadi ialah membuat jadual berasingan untuknya. Dalam rajah di bawah, kuncinya diawali dengan "P", dan "propname" pemegang tempat boleh digantikan dengan nilai yang lebih khusus "maklumat awam".​

Semua metadata unik, demi menyimpan jadual baharu yang dibuat, diletakkan di bahagian nilai rekod. Pada masa yang sama, anda tidak mahu menduplikasi data tentang fail dan folder yang telah disimpan dalam jadual utama. Sebaliknya, data berlebihan ditambahkan pada kunci "P" dalam bentuk medan "nod ID" dan "cap masa". Terima kasih kepada mereka, anda boleh membina kunci indeks, dari mana anda boleh mendapatkan kunci utama, yang akhirnya, anda boleh mendapatkan metadata nod.

Kesimpulan

Kami menilai hasil pelaksanaan LMDB secara positif. Selepas itu, bilangan pegun aplikasi berkurangan sebanyak 30%.

Hasil kerja yang dilakukan bergema di luar pasukan iOS. Pada masa ini, salah satu bahagian "Fail" utama dalam aplikasi Android juga telah beralih kepada menggunakan LMDB, dan bahagian lain sedang dalam perjalanan. Bahasa C, di mana stor nilai kunci dilaksanakan, merupakan bantuan yang baik untuk mula-mula mencipta rangka kerja aplikasi di sekelilingnya merentas platform dalam C++. Penjana kod telah digunakan untuk menyambungkan perpustakaan C++ yang terhasil dengan lancar dengan kod platform dalam Objective-C dan Kotlin Djinni daripada Dropbox, tetapi itu cerita yang sama sekali berbeza.

Sumber: www.habr.com