2019 sonbaharında Mail.ru Cloud iOS ekibinde uzun zamandır beklenen bir etkinlik gerçekleşti. Uygulama durumunun kalıcı olarak saklanması için ana veritabanı, mobil dünya için oldukça egzotik hale geldi (LMDB). Kesimin altında, dört bölüm halinde detaylı incelemesine dikkatinizi çekiyor. İlk olarak, bu kadar önemsiz ve zor bir seçimin nedenlerinden bahsedelim. Ardından, LMDB mimarisinin kalbinde yer alan üç balinanın ele alınmasına geçelim: bellek eşlemeli dosyalar, B + ağaç, işlemsel ve çoklu sürümlemeyi uygulamak için yazma üzerine kopyalama yaklaşımı. Son olarak, tatlı için - pratik kısım. İçinde, düşük seviyeli anahtar/değer API'sinin üzerinde, bir dizin bir de dahil olmak üzere birkaç tablo içeren bir temel şemanın nasıl tasarlanıp uygulanacağına bakacağız.
Içerik
3.1
3.2
3.3
4.1
4.2
4.3
1. Uygulama motivasyonu
Yılda bir kez, 2015 yılında, uygulamamızın arayüzünün ne sıklıkla geciktiğine dair bir ölçüm yapmaya özen gösterdik. Bunu sadece biz yapmadık. Uygulamanın bazen kullanıcı eylemlerine yanıt vermeyi bırakmasıyla ilgili giderek daha fazla şikayet alıyoruz: düğmelere basılmıyor, listeler kaymıyor vb. Ölçüm mekaniği hakkında AvitoTech'te, bu yüzden burada sadece sayıların sırasını veriyorum.
Ölçüm sonuçları bizim için soğuk bir duş oldu. Donmalardan kaynaklanan sorunların diğerlerinden çok daha fazla olduğu ortaya çıktı. Bu gerçeği fark etmeden önce, kalitenin ana teknik göstergesi çarpışma olmamasıysa, o zaman odaktan sonra ücretsiz dondurma.
İnşa edilmiş ve harcadıktan и nedenlerinin analizi, ana düşman netleşti - uygulamanın ana iş parçacığında yürütülen ağır iş mantığı. Bu rezalete doğal bir tepki, onu iş akışlarına sokmak için yanıp tutuşan bir arzuydu. Bu sorunun sistematik bir çözümü için hafif aktörlere dayalı çok iş parçacıklı bir mimariye başvurduk. Uyarlamalarını iOS dünyasına adadım. toplu twitter ve . Mevcut hikayenin bir parçası olarak, kararın veri tabanı seçimini etkileyen yönlerini vurgulamak istiyorum.
Sistem organizasyonunun aktör modeli, çoklu iş parçacığının ikinci özü olduğunu varsayar. İçindeki model nesneleri, iş parçacığı sınırlarını aşmayı sever. Ve bunu bazen ve bazı yerlerde değil, neredeyse sürekli ve her yerde yapıyorlar.
Veritabanı, sunulan şemadaki köşe taşı bileşenlerinden biridir. Ana görevi, bir makro kalıbı uygulamaktır. . Kurumsal dünyada hizmetler arasında veri senkronizasyonunu düzenlemek için kullanılıyorsa, o zaman bir aktör mimarisi söz konusu olduğunda, iş parçacıkları arasındaki veriler. Bu nedenle, çok iş parçacıklı bir ortamda çalışmanın en az zorluğa bile neden olmadığı böyle bir veritabanına ihtiyacımız vardı. Özellikle bu, ondan türetilen nesnelerin en azından iş parçacığı açısından güvenli olması ve ideal olarak hiç değişken olmaması gerektiği anlamına gelir. Bildiğiniz gibi, ikincisi, performans üzerinde olumlu bir etkiye sahip olan herhangi bir kilide başvurmadan aynı anda birkaç iş parçacığından kullanılabilir.
Veritabanı seçimini etkileyen ikinci önemli faktör bulut API'mizdi. Senkronizasyona yönelik git yaklaşımından ilham almıştır. Onun gibi hedefledik , bulut istemcileri için fazlasıyla uygun görünüyor. Bulutun tam durumunu yalnızca bir kez dışarı pompalayacakları ve ardından vakaların büyük çoğunluğunda senkronizasyonun döngüsel değişiklikler yoluyla gerçekleşeceği varsayılmıştır. Ne yazık ki, bu olasılık hala sadece teorik alanda ve pratikte müşteriler yamalarla nasıl çalışacaklarını öğrenmediler. Bunun, girişi geciktirmemek için parantez dışında bırakacağımız bir dizi nesnel nedeni var. Şimdi çok daha ilginç olanı, API "A" dediğinde ve tüketicisi "B" demediğinde ne olduğuyla ilgili dersin öğretici sonuçları.
Bu nedenle, yerel bir anlık görüntüye yamalar uygulamak yerine bir çekme komutu yürütürken tam durumunu tam sunucu durumuyla karşılaştıran git'i hayal ederseniz, o zaman senkronizasyonun nasıl olduğu konusunda oldukça doğru bir fikriniz olur. bulut istemcilerinde oluşur. Uygulaması için, tüm sunucu ve yerel dosyalar hakkında meta bilgilerle bellekte iki DOM ağacı ayırmanın gerekli olduğunu tahmin etmek kolaydır. Bir kullanıcı bulutta 500 bin dosya depolarsa, senkronize etmek için 1 milyon düğümlü iki ağacı yeniden oluşturup yok etmesi gerektiği ortaya çıktı. Ancak her düğüm, alt nesnelerin bir grafiğini içeren bir toplamdır. Bu ışıkta, profil oluşturma sonuçları bekleniyordu. Birleştirme algoritmasını hesaba katmadan bile, çok sayıda küçük nesne oluşturma ve ardından yok etme prosedürünün oldukça pahalıya mal olduğu ortaya çıktı.Temel senkronizasyon işleminin çok sayıda dahil edilmesiyle durum daha da kötüleşiyor. kullanıcı betiklerinden. Sonuç olarak, bir veritabanı seçerken ikinci önemli kriteri - nesnelerin dinamik tahsisi olmadan CRUD işlemlerini uygulama yeteneği - düzeltiyoruz.
Diğer gereksinimler daha gelenekseldir ve tam listesi aşağıdaki gibidir.
- İplik güvenliği.
- çoklu işleme Durumu yalnızca iş parçacıkları arasında değil, aynı zamanda ana uygulama ile iOS uzantıları arasında da senkronize etmek için aynı veritabanı örneğini kullanma arzusu tarafından belirlenir.
- Saklanan varlıkları değiştirilemez nesneler olarak temsil etme yeteneği.
- CRUD operasyonlarında dinamik tahsis eksikliği.
- Temel Özellikler için İşlem Desteği Anahtar kelimeler: atomiklik, tutarlılık, izolasyon ve güvenilirlik.
- En popüler vakalarda hız.
Bu gereksinimler kümesiyle, SQLite iyi bir seçimdi ve hala da öyle. Ancak, alternatifler çalışmasının bir parçası olarak bir kitapla karşılaştım. . Onun liderliğinde, gerçek bulut senaryolarında farklı veritabanlarıyla çalışma hızını karşılaştıran bir kıyaslama yazıldı. Sonuç, en çılgın beklentileri aştı. En popüler durumlarda - belirli bir dizin için tüm dosyaların sıralanmış bir listesinde ve tüm dosyaların sıralanmış bir listesinde bir imleç almak - LMDB'nin SQLite'tan 10 kat daha hızlı olduğu ortaya çıktı. Seçim belli oldu.
2. LMDB Konumlandırması
LMDB, veritabanlarının en düşük temel katmanını - depolamayı - uygulayan çok küçük (yalnızca 10K satırlık) bir kitaplıktır.
Yukarıdaki şema, LMDB'yi daha da yüksek seviyeler uygulayan SQLite ile karşılaştırmanın genellikle SQLite ile Core Data'dan daha doğru olmadığını göstermektedir. Aynı depolama motorlarını - BerkeleyDB, LevelDB, Sophia, RocksDB, vb. - eşit rakipler olarak belirtmek daha adil olur. Hatta LMDB'nin SQLite için bir depolama motoru bileşeni olarak işlev gördüğü gelişmeler bile vardır. 2012'de bu tür ilk deney yazar LMDB . o kadar merak uyandırdı ki, girişimi OSS meraklıları tarafından benimsendi ve devamını . Ocak 2020'de bu projenin yazarı Den Shearer'dır. LinuxConfAu'da.
LMDB'nin ana kullanımı, uygulama veritabanları için bir motor işlevi görmesidir. Kütüphane görünümünü geliştiricilere borçludur. projelerinin temeli olarak BerkeleyDB'den kesinlikle memnun olmayanlar. Mütevazi kütüphaneden uzaklaşmak Howard Chu, zamanımızın en popüler alternatiflerinden birini yaratmayı başardı. Çok havalı raporunu bu hikayeye ve LMDB'nin iç yapısına adadı. . Leonid Yuryev (aka ) Highload 2015'teki konuşmasında Pozitif Teknolojilerden . İçinde, benzer bir ReOpenLDAP uygulama görevi bağlamında LMDB'den bahsediyor ve LevelDB zaten karşılaştırmalı eleştirilere maruz kaldı. Uygulamanın bir sonucu olarak, Positive Technologies aktif olarak gelişen bir çatal bile aldı. çok lezzetli özellikler, optimizasyonlar ve .
LMDB genellikle depolama alanı olarak da kullanılır. Örneğin, Mozilla Firefox tarayıcısı bir dizi ihtiyaç için ve sürüm 9'dan başlayarak Xcode dizinleri depolamak için SQLite.
Motor, mobil geliştirme dünyasında da yakalandı. Kullanım izleri olabilir Telegram için iOS istemcisinde. LinkedIn bir adım daha ileri gitti ve yerel veri önbelleğe alma çerçevesi Rocket Data için varsayılan depolama alanı olarak LMDB'yi seçti. 2016 yılında bir makalede.
LMDB, Oracle'ın kontrolüne geçişin ardından BerkeleyDB'nin bıraktığı nişte güneşte bir yer için başarılı bir şekilde mücadele ediyor. Kütüphane, kendi türüne kıyasla hızı ve güvenilirliği ile bile seviliyor. Bildiğiniz gibi, bedava öğle yemeği yoktur ve LMDB ile SQLite arasında seçim yaparken yüzleşmek zorunda kalacağınız dengeyi vurgulamak isterim. Yukarıdaki şema, artan hızın nasıl elde edildiğini açıkça göstermektedir. İlk olarak, disk depolamanın yanı sıra ek soyutlama katmanları için ödeme yapmıyoruz. Elbette iyi bir mimaride yine de onlarsız yapamazsınız ve kaçınılmaz olarak uygulama kodunda görünecekler ama çok daha ince olacaklar. Belirli bir uygulamanın gerektirmediği, örneğin SQL dilinde sorgu desteği gibi özelliklere sahip olmayacaklar. İkinci olarak, uygulama işlemlerinin eşlemesini disk depolama isteklerine en uygun şekilde uygulamak mümkün hale gelir. Eğer SQLite ortalama bir uygulamanın ortalama ihtiyaçlarından geliyorsa, bir uygulama geliştiricisi olarak siz ana yük senaryolarının gayet iyi farkındasınızdır. Daha üretken bir çözüm için, hem ilk çözümün geliştirilmesi hem de sonraki desteği için daha yüksek bir fiyat etiketi ödemeniz gerekecektir.
3. Üç balina LMDB
LMDB'ye kuş bakışı baktıktan sonra, daha derine inme zamanı. Sonraki üç bölüm, depolama mimarisinin dayandığı ana balinaların analizine ayrılacaktır:
- Diskle çalışmak ve dahili veri yapılarını senkronize etmek için bir mekanizma olarak bellek eşlemeli dosyalar.
- Saklanan veri yapısının bir organizasyonu olarak B+-ağacı.
- ACID işlem özellikleri ve çoklu sürüm sağlamak için bir yaklaşım olarak yazma sırasında kopyala.
3.1. 1 numaralı balina. Bellek eşlemeli dosyalar
Hafıza eşlemeli dosyalar o kadar önemli bir mimari unsurdur ki, depo adında bile görünürler. Depolanan bilgilere erişimi önbelleğe alma ve eşitleme sorunları tamamen işletim sisteminin insafına kalmıştır. LMDB kendi içinde önbellek barındırmaz. Bu, yazarın bilinçli bir kararıdır, çünkü verileri doğrudan eşlenen dosyalardan okumak, motorun uygulanmasında pek çok köşeyi kesmenize izin verir. Aşağıda, bazılarının tam bir listesi olmaktan uzaktır.
- Birkaç işlemden verilerle çalışırken depolamadaki verilerin tutarlılığını korumak, işletim sisteminin sorumluluğu haline gelir. Bir sonraki bölümde bu mekanik ayrıntılı ve resimlerle ele alınmıştır.
- Önbelleklerin olmaması, LMDB'yi dinamik ayırmalarla ilişkili ek yükten tamamen kurtarır. Pratikte veri okumak, işaretçiyi sanal bellekte doğru adrese ayarlamaktır, başka bir şey değil. Kulağa hayal gibi geliyor, ancak depo kaynağında, tüm calloc çağrıları depo yapılandırma işlevinde yoğunlaşıyor.
- Önbelleklerin olmaması, bunlara erişmek için senkronizasyonla ilişkili kilitlerin olmaması anlamına da gelir. Aynı anda rastgele bir sayıda bulunabilen okuyucular, verilere giderken tek bir muteks ile karşılaşmazlar. Bu nedenle okuma hızı, CPU sayısı açısından ideal bir doğrusal ölçeklenebilirliğe sahiptir. LMDB'de yalnızca değiştirme işlemleri senkronize edilir. Aynı anda yalnızca bir yazar olabilir.
- Minimum önbelleğe alma ve senkronizasyon mantığı, kodu çok iş parçacıklı bir ortamda çalışmakla ilişkili son derece karmaşık hata türlerinden kurtarır. Usenix OSDI 2014 konferansında iki ilginç veri tabanı çalışması vardı: и . Onlardan hem LMDB'nin benzeri görülmemiş güvenilirliği hem de aynı SQLite'ta onu aşan işlemlerin ASİT özelliklerinin neredeyse kusursuz uygulaması hakkında bilgi alabilirsiniz.
- LMDB'nin minimalizmi, kodunun makine temsilinin, ortaya çıkan hız özellikleriyle birlikte işlemcinin L1 önbelleğine tamamen yerleştirilmesine izin verir.
Ne yazık ki, iOS'ta bellek eşlemeli dosyalar istediğimiz kadar pembe değil. Onlarla ilgili dezavantajlardan daha bilinçli olarak bahsetmek için, bu mekanizmanın işletim sistemlerinde uygulanmasına ilişkin genel ilkeleri hatırlamak gerekir.
Bellek eşlemeli dosyalar hakkında genel bilgiler
Yürütülebilir her uygulama ile işletim sistemi, işlem adı verilen bir varlığı ilişkilendirir. Her işleme, çalışması için ihtiyaç duyduğu her şeyi yerleştirdiği bitişik bir adres aralığı tahsis edilir. En düşük adresler, kod ve sabit kodlanmış veri ve kaynakları içeren bölümleri içerir. Ardından, bizim için yığın olarak iyi bilinen, yukarı doğru büyüyen dinamik adres alanı bloğu gelir. Programın çalışması sırasında görünen varlıkların adreslerini içerir. En üstte uygulama yığını tarafından kullanılan bellek alanı bulunur. Büyür ya da küçülür yani boyutu da dinamik bir yapıya sahiptir. Stack ve heap birbirini itip engellemesin diye adres uzayının farklı uçlarında ayrılıyor, üstte ve altta iki dinamik bölüm arasında boşluk var. Bu orta bölümdeki adresler, işletim sistemi tarafından çeşitli varlıklardan oluşan bir işlemle ilişkilendirmek için kullanılır. Özellikle, belirli bir sürekli adres kümesini diskteki bir dosyaya eşleyebilir. Böyle bir dosyaya bellek eşlemeli dosya denir.
Bir işleme ayrılan adres alanı çok büyüktür. Teorik olarak, adres sayısı yalnızca sistemin bit derinliği tarafından belirlenen işaretçinin boyutuyla sınırlıdır. Ona 1'i 1 arada fiziksel bellek atanırsa, ilk işlem tüm RAM'i yutar ve herhangi bir çoklu görev söz konusu olmaz.
Ancak modern işletim sistemlerinin aynı anda istediğiniz kadar işlem çalıştırabileceğini deneyimlerimizden biliyoruz. Bu, yalnızca kağıt üzerindeki işlemlere çok fazla bellek ayırmaları nedeniyle mümkündür, ancak gerçekte ana fiziksel belleğe yalnızca burada ve şimdi talep edilen kısmı yüklerler. Bu nedenle, işlemle ilişkilendirilen belleğe sanal denir.
İşletim sistemi, sanal ve fiziksel belleği belirli bir boyuttaki sayfalar halinde düzenler. Belirli bir sanal bellek sayfası talep edildiğinde, işletim sistemi onu fiziksel belleğe yükler ve aralarındaki yazışmayı özel bir tabloya koyar. Boş alan yoksa, önceden yüklenen sayfalardan biri diske kopyalanır ve istenen sayfa yerini alır. Birazdan döneceğimiz bu işleme takas denir. Aşağıdaki şekil açıklanan süreci göstermektedir. Üzerinde 0 adresli A sayfası yüklenip 4 adresli ana bellek sayfasına yerleştirildi. Bu durum 0 numaralı hücredeki yazışma tablosuna yansıdı.
Hafıza eşlemeli dosyalarda hikaye tamamen aynıdır. Mantıksal olarak, sözde sürekli ve tamamen sanal adres alanına yerleştirilirler. Ancak, sayfa sayfa ve yalnızca istek üzerine fiziksel belleğe girerler. Bu tür sayfaların değiştirilmesi, diskteki dosya ile senkronize edilir. Böylece, yalnızca bellekteki baytlarla çalışarak dosya G / Ç gerçekleştirebilirsiniz - tüm değişiklikler işletim sistemi çekirdeği tarafından otomatik olarak orijinal dosyaya aktarılacaktır.
Aşağıdaki görüntü, LMDB'nin farklı işlemlerden veritabanıyla çalışırken durumunu nasıl eşitlediğini gösterir. Farklı işlemlerin sanal belleğini aynı dosyaya eşleyerek, işletim sistemini fiili olarak, adres alanlarının belirli bloklarını birbiriyle geçişli olarak senkronize etmeye mecbur bırakıyoruz, LMDB burada görünüyor.
Önemli bir nüans, LMDB'nin veri dosyasını varsayılan olarak yazma sistemi çağrı mekanizması aracılığıyla değiştirmesi ve dosyanın kendisinin salt okunur modda görüntülenmesidir. Bu yaklaşımın iki önemli sonucu vardır.
İlk sonuç, tüm işletim sistemlerinde ortaktır. Özü, yanlış kodla veritabanına yanlışlıkla zarar verilmesine karşı koruma eklemektir. Bildiğiniz gibi, bir işlemin yürütülebilir komutları, adres alanındaki herhangi bir yerden verilere erişmek için ücretsizdir. Aynı zamanda, az önce hatırladığımız gibi, bir dosyayı okuma-yazma modunda görüntülemek, herhangi bir talimatın onu ek olarak değiştirebileceği anlamına gelir. Bunu yanlışlıkla yaparsa, örneğin var olmayan bir dizindeki bir dizi öğesinin üzerine yazmaya çalışırsa, bu şekilde bu adrese eşlenen dosyayı yanlışlıkla değiştirebilir ve bu da veritabanının bozulmasına neden olur. Dosya salt okunur modda görüntüleniyorsa, buna karşılık gelen adres alanını değiştirme girişimi, programın sinyalle çökmesine neden olur. SIGSEGV, ve dosya olduğu gibi kalacaktır.
İkinci sonuç zaten iOS'a özgüdür. Ne yazar ne de başka herhangi bir kaynak bundan açıkça bahsetmez, ancak onsuz, LMDB bu mobil işletim sisteminde çalışmak için uygun olmayacaktır. Bir sonraki bölüm onun değerlendirilmesine ayrılmıştır.
iOS'ta bellek eşlemeli dosyaların özellikleri
2018'de WWDC'de harika bir rapor vardı . İOS'ta fiziksel bellekte bulunan tüm sayfaların 3 türden birine ait olduğunu söyler: kirli, sıkıştırılmış ve temiz.
Temiz bellek, fiziksel bellekten güvenli bir şekilde çıkarılabilen bir sayfa koleksiyonudur. İçerdikleri veriler, gerektiğinde orijinal kaynaklarından yeniden yüklenebilir. Salt okunur bellek eşlemeli dosyalar bu kategoriye girer. iOS, diskteki dosyayla senkronize edilmeleri garanti edildiğinden, bir dosyaya eşlenen sayfaları herhangi bir zamanda bellekten kaldırmaktan korkmaz.
Değiştirilen tüm sayfalar, orijinal olarak nerede bulunduklarına bakılmaksızın kirli belleğe girer. Özellikle kendileriyle ilişkili sanal belleğe yazılarak değiştirilen bellek eşlemeli dosyalar da bu şekilde sınıflandırılacaktır. LMDB'yi bayrakla açma MDB_WRITEMAPüzerinde değişiklik yaptıktan sonra kendiniz görebilirsiniz.
Bir uygulama çok fazla fiziksel bellek kaplamaya başlar başlamaz, iOS onun kirli sayfalarını sıkıştırır. Kirli ve sıkıştırılmış sayfaların kapladığı bellek koleksiyonu, uygulamanın sözde bellek ayak izidir. Belirli bir eşik değere ulaştığında OOM killer sistem daemon'u process'in peşine düşer ve onu zorla sonlandırır. Bu, masaüstü işletim sistemlerine kıyasla iOS'un özelliğidir. Buna karşılık, sayfaları fiziksel bellekten diske değiştirerek bellek ayak izinin düşürülmesi iOS'ta sağlanmaz, ancak nedenleri hakkında tahmin edilebilir. Belki de sayfaları yoğun bir şekilde diske ve geriye taşıma prosedürü, mobil cihazlar için çok fazla enerji tüketiyor veya iOS, SSD disklerindeki hücreleri yeniden yazma kaynağını koruyor veya belki de tasarımcılar, her şeyin olduğu sistemin genel performansından memnun değildi. sürekli değiştirilir. Ne olursa olsun, gerçek devam ediyor.
Daha önce bahsedilen iyi haber, LMDB'nin varsayılan olarak dosyaları güncellemek için mmap mekanizmasını kullanmamasıdır. Sonuç olarak, işlenen veriler iOS tarafından temiz bellek olarak sınıflandırılır ve bellek ayak izine katkıda bulunmaz. Bu, VM Tracker adlı Xcode aracı kullanılarak doğrulanabilir. Aşağıdaki ekran görüntüsü, işletim sırasında iOS Cloud uygulamasının sanal bellek durumunu gösterir. Başlangıçta, içinde 2 LMDB bulut sunucusu başlatıldı. İlkinin dosyasını 1GiB sanal belleğe, ikincisinin - 512MiB'ye eşlemesine izin verildi. Her iki deponun da belirli bir miktarda yerleşik bellek kaplamasına rağmen, hiçbiri kirli boyuta katkıda bulunmaz.
Şimdi kötü haber zamanı. 64-bit masaüstü işletim sistemlerindeki takas mekanizması sayesinde, her işlem, potansiyel takası için sabit diskteki boş alanın izin verdiği kadar sanal adres alanı kaplayabilir. iOS'ta takası sıkıştırma ile değiştirmek, teorik maksimumu büyük ölçüde azaltır. Artık tüm canlı süreçler ana (RAM okuma) belleğe sığmalıdır ve sığmayanların tümü zorunlu sonlandırmaya tabidir. Yukarıda belirtildiği gibi ve . Sonuç olarak iOS, mmap aracılığıyla tahsis edilebilecek bellek miktarını ciddi şekilde sınırlar. Burada bu sistem çağrısını kullanarak farklı aygıtlara ayrılabilecek bellek miktarının ampirik sınırlarına bakabilirsiniz. En modern akıllı telefon modellerinde iOS, 2 gigabayt ve iPad'in üst sürümlerinde - 4 cömert hale geldi. Pratikte, elbette, her şeyin çok üzücü olduğu, desteklenen en genç cihaz modellerine odaklanmalısınız. Daha da kötüsü, VM Tracker'da uygulamanın bellek durumuna baktığınızda, LMDB'nin bellek eşlemeli bellek olduğunu iddia eden tek şirket olmadığını göreceksiniz. İyi parçalar, sistem ayırıcılar, kaynak dosyaları, görüntü çerçeveleri ve diğer daha küçük yırtıcılar tarafından yenilip tüketilir.
Buluttaki deneylerin sonuçlarına dayanarak, LMDB tarafından ayrılan belleğin aşağıdaki uzlaşma değerlerine ulaştık: 384 bit cihazlar için 32 megabayt ve 768 bit cihazlar için 64. Bu hacim kullanıldıktan sonra, herhangi bir değiştirme işlemi kodla tamamlanmaya başlar. MDB_MAP_FULL. Bu tür hataları izlememizde gözlemliyoruz, ancak bu aşamada ihmal edilecek kadar küçükler.
Depolama tarafından aşırı bellek tüketiminin bariz olmayan bir nedeni, uzun ömürlü işlemler olabilir. Bu iki olgunun birbiriyle nasıl ilişkili olduğunu anlamak için, geri kalan iki LMDB balinasını ele almak bize yardımcı olacaktır.
3.2. 2 numaralı balina. B+-ağacı
Bir anahtar/değer deposunun üstündeki tabloları öykünmek için API'sinde aşağıdaki işlemler bulunmalıdır:
- Yeni bir eleman ekleme.
- Belirli bir anahtarla bir öğe arayın.
- Bir elemanın silinmesi.
- Sıralama düzenlerinde anahtar aralıkları üzerinde yineleyin.
Dört işlemi de kolayca uygulayabilen en basit veri yapısı ikili arama ağacıdır. Düğümlerinin her biri, alt anahtarların tüm alt kümesini iki alt ağaca bölen bir anahtardır. Solda, ebeveynden daha küçük olanlar ve sağda - daha büyük olanlar var. Sıralı bir anahtar seti elde etmek, klasik ağaç geçişlerinden biriyle elde edilir.
İkili ağaçların, bir disk veri yapısı olarak etkili olmalarını engelleyen iki temel dezavantajı vardır. İlk olarak, dengelerinin derecesi tahmin edilemez. Farklı dalların yüksekliğinin büyük ölçüde değişebildiği ağaçların elde edilmesinde önemli bir risk vardır ve bu da, beklenenle karşılaştırıldığında aramanın algoritmik karmaşıklığını önemli ölçüde kötüleştirir. İkincisi, düğümler arasındaki çapraz bağların bolluğu, ikili ağaçları bellekteki konumlarından mahrum eder Yakın düğümler (aralarındaki bağlantılar açısından), sanal bellekte tamamen farklı sayfalarda bulunabilir. Sonuç olarak, bir ağaçtaki birkaç komşu düğümün basit bir geçişi bile karşılaştırılabilir sayıda sayfanın ziyaret edilmesini gerektirebilir. Bellek içi veri yapısı olarak ikili ağaçların verimliliğinden bahsettiğimizde bile bu bir sorundur, çünkü işlemci önbelleğinde sürekli dönen sayfalar ucuz değildir. Düğümle ilgili sayfaları diskten sık sık yükseltmeye gelince, işler gerçekten kötüye gidiyor. .
İkili ağaçların bir evrimi olan B-ağaçları, önceki paragrafta tanımlanan sorunları çözer. İlk olarak, kendi kendini dengelerler. İkinci olarak, düğümlerinin her biri, alt anahtar kümesini 2'ye değil, M sıralı alt kümelere böler ve M sayısı, birkaç yüz hatta binlerce mertebesinde oldukça büyük olabilir.
Böylece:
- Her düğümde çok sayıda önceden sipariş edilmiş anahtar vardır ve ağaçlar çok düşüktür.
- Ağaç, bellekte yerellik özelliğini kazanır, çünkü değere yakın anahtarlar doğal olarak bir veya komşu düğümlerde yan yana bulunur.
- Bir arama işlemi sırasında ağaca inerken geçiş düğümlerinin sayısını azaltır.
- Her biri zaten çok sayıda sıralı anahtar içerdiğinden, aralık sorguları için okunan hedef düğümlerin sayısını azaltır.
LMDB, verileri depolamak için B+ ağacı adı verilen B ağacının bir çeşidini kullanır. Yukarıdaki diyagram, içerdiği üç tür düğümü göstermektedir:
- En üstte kök bulunur. Bir havuz içindeki bir veritabanı kavramından başka bir şey gerçekleştirmez. Tek bir LMDB örneği içinde, eşlenen sanal adres alanını paylaşan birden çok veritabanı oluşturabilirsiniz. Her biri kendi kökünden başlar.
- En alt seviyede yapraklar (yaprak) bulunur. Veritabanında depolanan anahtar/değer çiftlerini içerenler yalnızca ve yalnızca onlar. Bu arada, bu B+-ağaçlarının özelliğidir. Normal bir B-ağacı, değer-parçalarını tüm seviyelerin düğüm noktalarında saklıyorsa, B+-varyasyonu yalnızca en düşük seviyededir. Bu gerçeği düzelttikten sonra, aşağıda LMDB'de kullanılan ağacın alt tipini sadece bir B-ağacı olarak adlandıracağız.
- Kök ile yapraklar arasında 0 veya daha fazla navigasyon (dal) düğümü bulunan teknik seviyeler vardır. Görevleri, sıralanmış anahtar setini yapraklar arasında bölmektir.
Fiziksel olarak, düğümler önceden belirlenmiş bir uzunluktaki bellek bloklarıdır. Boyutları, yukarıda bahsettiğimiz işletim sistemindeki bellek sayfalarının boyutunun katlarıdır. Düğüm yapısı aşağıda gösterilmiştir. Başlık, en bariz olanı örneğin sağlama toplamı olan meta bilgileri içerir. Ardından, verilerin bulunduğu hücrelerin bulunduğu ofsetler hakkında bilgi gelir. Verilerin rolü, gezinme düğümlerinden bahsediyorsak anahtarlar veya yapraklar söz konusu olduğunda tüm anahtar-değer çiftleri olabilir.Çalışmada sayfaların yapısı hakkında daha fazla bilgi edinebilirsiniz. .
Sayfa düğümlerinin dahili içeriğini ele aldıktan sonra, LMDB B ağacını aşağıdaki biçimde basitleştirilmiş bir şekilde daha fazla temsil edeceğiz.
Düğümlü sayfalar diskte sıralı olarak düzenlenir. Daha yüksek numaralı sayfalar dosyanın sonuna doğru yer alır. Sözde meta sayfası (meta sayfası), tüm ağaçların köklerini bulmak için kullanılabilecek ofsetler hakkında bilgi içerir. Bir dosya açıldığında LMDB, geçerli bir meta sayfa aramak için dosyayı sayfa sayfa baştan sona tarar ve bunun aracılığıyla mevcut veritabanlarını bulur.
Artık veri organizasyonunun mantıksal ve fiziksel yapısı hakkında bir fikir sahibi olarak, LMDB'nin üçüncü balinasını düşünmeye devam edebiliriz. Tüm depolama değişikliklerinin işlemsel olarak ve birbirinden ayrı olarak gerçekleşmesi, veritabanına bir bütün olarak çoklu sürüm özelliği kazandırması onun yardımıyla olur.
3.3. Balina #3. yazı üzerine kopyala
Bazı B-ağacı işlemleri, düğümlerinde bir dizi değişiklik yapmayı içerir. Bir örnek, zaten maksimum kapasitesine ulaşmış bir düğüme yeni bir anahtar eklemektir. Bu durumda, öncelikle düğümü ikiye bölmek ve ikinci olarak, ebeveynindeki yeni spin off alt düğüme bir bağlantı eklemek gerekir. Bu prosedür potansiyel olarak çok tehlikelidir. Herhangi bir nedenle (çökme, elektrik kesintisi vb.) dizideki değişikliklerin yalnızca bir kısmı gerçekleşirse, ağaç tutarsız bir durumda kalacaktır.
Bir veritabanını hataya dayanıklı hale getirmenin geleneksel bir çözümü, ek bir disk tabanlı veri yapısı, B-ağacının yanına önceden yazma günlüğü (WAL) olarak da bilinen işlem günlüğü eklemektir. Bu, sonunda, kesinlikle B-ağacının kendisinde değişiklik yapılmadan önce, amaçlanan işlemin yazıldığı bir dosyadır. Bu nedenle, kendi kendine teşhis sırasında veri bozulması tespit edilirse, veritabanı kendini temizlemek için günlüğe başvurur.
LMDB, hata toleransı mekanizması olarak yazma sırasında kopyalama adı verilen farklı bir yöntem seçmiştir. Özü, mevcut bir sayfadaki verileri güncellemek yerine, önce onu tamamen kopyalaması ve zaten kopyada bulunan tüm değişiklikleri yapmasıdır.
Ayrıca, güncellenen verilerin kullanılabilir olması için, üst düğümde kendisiyle ilgili olarak güncel hale gelen düğüme olan bağlantının değiştirilmesi gerekir. Bunun için de modifiye edilmesi gerektiğinden, aynı zamanda önceden kopyalanmıştır. İşlem, köke kadar yinelemeli olarak devam eder. Meta sayfasındaki veriler en son değişen verilerdir.
Güncelleme prosedürü sırasında süreç aniden çökerse, o zaman ya yeni bir meta sayfa oluşturulmayacak ya da sonuna kadar diske yazılmayacak ve sağlama toplamı yanlış olacaktır. Bu iki durumda da yeni sayfalara erişilemez ve eski sayfalar etkilenmez. Bu, LMDB'nin veri tutarlılığını korumak için ileriye dönük günlük yazma ihtiyacını ortadan kaldırır. De facto, yukarıda açıklanan diskteki veri depolama yapısı aynı anda işlevini üstlenir. Açık bir işlem günlüğünün olmaması, yüksek veri okuma hızı sağlayan LMDB'nin özelliklerinden biridir.
Yalnızca eklenen B-ağacı adı verilen sonuçtaki yapı, doğal olarak işlem yalıtımı ve çoklu sürüm sağlar. LMDB'de her açık işlem, kendisiyle ilişkilendirilmiş güncel bir ağaç köküne sahiptir. İşlem tamamlanmadığı sürece ağacın onunla ilişkili sayfaları asla değiştirilmeyecek veya yeni veri sürümleri için yeniden kullanılmayacaktır.Böylece işlem sırasında ilgili veri seti ile tam olarak istediğiniz kadar çalışabilirsiniz. depolama şu anda aktif olarak güncellenmeye devam etse bile işlemin açıldığı saat. Bu, çok sürümlülüğün özüdür ve LMDB'yi sevdiklerimiz için ideal bir veri kaynağı yapar. UICollectionView. Bir işlem açtıktan sonra, hiçbir şey kalmamasından korkarak mevcut verileri bazı bellek içi yapılara aceleyle pompalayarak uygulamanın bellek ayak izini artırmanıza gerek yoktur. Bu özellik, LMDB'yi, böyle bir toplam izolasyonla övünemeyen aynı SQLite'tan ayırır. İkinci işlemde iki işlem açıp bunlardan birinde belirli bir kaydı sildikten sonra, kalan ikinci işlemde aynı kayıt elde edilemez.
Madalyonun diğer yüzü, potansiyel olarak önemli ölçüde daha yüksek sanal bellek tüketimidir. Slayt, veritabanının farklı sürümlerine bakarak 3 açık okuma işlemi ile aynı anda değiştirilirse veritabanı yapısının nasıl görüneceğini gösterir. LMDB, gerçek işlemlerle ilişkili köklerden erişilebilen düğümleri yeniden kullanamayacağından, depolamanın bellekte başka bir dördüncü kök tahsis etmekten ve değiştirilen sayfaları bir kez daha altına klonlamaktan başka seçeneği yoktur.
Burada, bellek eşlemeli dosyalar hakkındaki bölümü hatırlamak gereksiz olmayacaktır. Görünüşe göre ek sanal bellek tüketimi, uygulamanın bellek ayak izine katkıda bulunmadığı için bizi çok rahatsız etmemeli. Ancak aynı zamanda iOS'un bunu tahsis etme konusunda çok cimri olduğu ve ustanın omzundan bir sunucu veya masaüstünde 1 terabayt LMDB bölgesi sağlayamayacağımız ve bu özelliği hiç düşünmediğimiz kaydedildi. Mümkün olduğunda, işlemlerin ömrünü olabildiğince kısa tutmaya çalışmalısınız.
4. Anahtar/değer API'sinin üzerinde bir veri şeması tasarlama
LMDB tarafından sağlanan temel soyutlamalara bakarak API'yi ayrıştırmaya başlayalım: ortam ve veritabanları, anahtarlar ve değerler, işlemler ve imleçler.
Kod listeleri hakkında bir not
LMDB genel API'sindeki tüm işlevler, çalışmalarının sonucunu bir hata kodu biçiminde döndürür, ancak sonraki tüm listelemelerde, kısa ve öz olması adına kontrolü yapılmaz.Uygulamada, havuzla etkileşim için kendi kodumuzu kullandık. C++ sarmalayıcıları , hataların C++ istisnaları olarak gerçekleştiği.
LMDB'yi bir iOS veya macOS projesine bağlamanın en hızlı yolu olarak CocoaPod'umu sunuyorum .
4.1. Temel soyutlamalar
Çevre
Yapı MDB_env LMDB'nin dahili durumunun deposudur. Ön ekli işlevler ailesi mdb_env özelliklerinden bazılarını yapılandırmanıza izin verir. En basit durumda, motorun başlatılması şöyle görünür.
mdb_env_create(env);
mdb_env_set_map_size(*env, 1024 * 1024 * 512)
mdb_env_open(*env, path.UTF8String, MDB_NOTLS, 0664);Mail.ru Cloud uygulamasında sadece iki parametre için varsayılan değerleri değiştirdik.
İlki, depolama dosyasının eşlendiği sanal adres alanının boyutudur. Ne yazık ki, aynı cihazda bile, spesifik değer çalıştırmadan çalıştırmaya önemli ölçüde değişebilir. iOS'un bu özelliğini hesaba katmak için maksimum depolama miktarını dinamik olarak seçiyoruz. Belirli bir değerden başlayarak, fonksiyona kadar art arda yarıya iner. mdb_env_open dışında bir sonuç döndürmez. ENOMEM. Teorik olarak, tersi bir yol vardır - önce motora minimum bellek ayırın ve ardından hatalar alındığında MDB_MAP_FULL, artırın. Ancak çok daha dikenlidir. Bunun nedeni, işlevi kullanarak belleği yeniden eşleştirme prosedürünün mdb_env_set_map_size daha önce motordan alınan tüm varlıkları (imleçler, işlemler, anahtarlar ve değerler) geçersiz kılar. Koddaki bu tür olayların muhasebeleştirilmesi, önemli bir karmaşıklığa yol açacaktır. Bununla birlikte, sanal bellek sizin için çok değerliyse, bu, çok ileri giden çatala bakmak için bir neden olabilir. , beyan edilen özellikler arasında "otomatik anında veritabanı boyutu ayarı" olduğu yer.
Varsayılan değeri bize uymayan ikinci parametre, iplik güvenliğini sağlama mekaniğini düzenler. Ne yazık ki, en azından iOS 10'da, iş parçacığı yerel depolama desteğiyle ilgili sorunlar var. Bu nedenle yukarıdaki örnekte depo bayrağı ile açılmıştır. MDB_NOTLS. Ayrıca, gerekli C++ sarıcı ve bu öznitelikteki değişkenleri kesmek için.
Veritabanları
Veritabanı, yukarıda bahsettiğimiz B ağacının ayrı bir örneğidir. Açılışı, ilk başta biraz garip gelebilecek bir işlem içinde gerçekleşir.
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);Aslında, LMDB'deki bir işlem, belirli bir veritabanı değil, bir depolama varlığıdır. Bu kavram, farklı veritabanlarında bulunan varlıklar üzerinde atomik işlemler gerçekleştirmenizi sağlar. Teorik olarak, bu, tabloları farklı veritabanları biçiminde modelleme olasılığını açar, ancak bir kerede aşağıda ayrıntılı olarak açıklanan diğer yoldan gittim.
Anahtarlar ve değerler
Yapı MDB_val hem anahtar hem de değer kavramını modeller. Deponun semantikleri hakkında hiçbir fikri yok. Onun için farklı olan şey, yalnızca belirli bir boyuttaki bayt dizisidir. Maksimum anahtar boyutu 512 bayttır.
typedef struct MDB_val {
size_t mv_size;
void *mv_data;
} MDB_val;Mağaza, anahtarları artan düzende sıralamak için bir karşılaştırıcı kullanır. Kendiniz ile değiştirmezseniz, bunları sözlüksel sırayla bayt bayt sıralayan varsayılan olan kullanılacaktır.
Işlemler
İşlem cihazı ayrıntılı olarak açıklanmaktadır. , bu yüzden burada ana özelliklerini kısa bir satırda tekrarlayacağım:
- Tüm temel özellikler için destek Anahtar kelimeler: atomiklik, tutarlılık, izolasyon ve güvenilirlik. MacOS ve iOS'ta dayanıklılık açısından MDBX'te düzeltilen bir hata olduğunu not etmeden geçemeyeceğim. Onların daha fazlasını okuyabilirsiniz .
- Çoklu okuma yaklaşımı, "tek yazar / çoklu okuyucu" şemasıyla tanımlanır. Yazarlar birbirlerini engellerler ama okuyucuları engellemezler. Okuyucular yazarları veya birbirlerini engellemez.
- İç içe işlemler için destek.
- Çoklu sürüm desteği.
LMDB'de çoklu sürüm oluşturma o kadar iyidir ki, bunu uygulamalı olarak göstermek istiyorum. Aşağıdaki kod, her işlemin, veritabanının tam olarak açıldığı sırada ilgili olan sürümüyle çalıştığını ve sonraki tüm değişikliklerden tamamen izole edildiğini göstermektedir. Depoyu başlatmak ve ona bir test kaydı eklemek ilgi çekici değildir, bu nedenle bu ritüeller spoiler altında kalır.
Test girişi ekleme
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);İsteğe bağlı olarak, aynı numarayı SQLite ile denemenizi ve ne olduğunu görmenizi öneririm.
Çoklu sürüm, bir iOS geliştiricisinin hayatına çok güzel faydalar sağlar. Bu özelliği kullanarak, ekran formları için veri kaynağı güncelleme oranını kullanıcı deneyimi hususlarına göre kolayca ve doğal bir şekilde ayarlayabilirsiniz. Örneğin, Mail.ru Cloud uygulamasının sistem medya galerisinden otomatik yükleme içeriği gibi bir özelliğini ele alalım. İyi bir bağlantı ile müşteri, sunucuya saniyede birkaç fotoğraf ekleyebilir. Her indirmeden sonra güncellerseniz UICollectionView kullanıcının bulutundaki medya içeriği ile bu işlem sırasında yaklaşık 60 fps'yi ve yumuşak kaydırmayı unutabilirsiniz. Sık ekran güncellemelerini önlemek için, temelde veri değişim oranını bir şekilde sınırlamanız gerekir. UICollectionViewDataSource.
Veritabanı çoklu sürüm oluşturmayı desteklemiyorsa ve yalnızca geçerli geçerli durumla çalışmanıza izin veriyorsa, zamana bağlı bir veri anlık görüntüsü oluşturmak için, bunu ya bir bellek içi veri yapısına ya da geçici bir tabloya kopyalamanız gerekir. Bu yaklaşımlardan herhangi biri çok pahalıdır. Bellek içi depolama durumunda, hem oluşturulmuş nesnelerin depolanmasından kaynaklanan bellek maliyetlerini hem de yedekli ORM dönüşümleriyle ilişkili zaman maliyetlerini elde ederiz. Geçici masaya gelince, bu sadece önemsiz olmayan durumlarda mantıklı olan daha da pahalı bir zevk.
Çok sürümlü LMDB, istikrarlı bir veri kaynağı sağlama sorununu çok zarif bir şekilde çözer. Sadece bir işlem açmak yeterlidir ve işte - biz onu tamamlayana kadar, veri setinin sabitlenmesi garanti edilir. Güncelleme oranının mantığı artık tamamen sunum katmanının ellerinde ve hiçbir önemli kaynak yükü yok.
İmleçler
İmleçler, bir B-ağacından geçerek anahtar-değer çiftleri üzerinde düzenli yineleme için bir mekanizma sağlar. Onlar olmadan, şimdi döneceğimiz veri tabanındaki tabloları etkin bir şekilde modellemek imkansız olurdu.
4.2. Tablo Modelleme
Anahtar sıralama özelliği, temel soyutlamaların üzerinde bir tablo gibi üst düzey bir soyutlama oluşturmanıza olanak tanır. Bu işlemi, kullanıcının tüm dosyaları ve klasörleri hakkındaki bilgilerin önbelleğe alındığı bulut istemcisinin ana tablosu örneğinde ele alalım.
Tablo Şeması
Klasör ağacı olan bir tablonun yapısının keskinleştirilmesi gereken yaygın senaryolardan biri, belirli bir dizinde bulunan tüm öğeleri seçmektir.Bu tür verimli sorgular için iyi bir veri organizasyon modeli, . Anahtar-değer deposunun üstüne uygulamak için, dosya ve klasörlerin anahtarlarını, üst dizine ait olmalarına göre gruplanacak şekilde sıralamak gerekir. Ek olarak, dizinin içeriğini bir Windows kullanıcısına tanıdık bir biçimde görüntülemek için (önce klasörler, sonra dosyalar, her ikisi de alfabetik olarak sıralanır), ilgili ek alanların anahtara dahil edilmesi gerekir.
Aşağıdaki resim, göreve bağlı olarak, anahtarların bir bayt dizisi olarak temsilinin nasıl görünebileceğini gösterir. İlk olarak, ana dizin tanımlayıcısına (kırmızı) sahip baytlar, ardından türe (yeşil) ve zaten kuyruğa isme (mavi) sahip baytlar yerleştirilir.Varsayılan LMDB karşılaştırıcısına göre sözlük sırasına göre sıralanarak, şu şekilde sıralanırlar: gereken yol. Aynı kırmızı ön eke sahip sıralı olarak geçiş yapan tuşlar, herhangi bir ek işlem sonrası işlem gerektirmeden kullanıcı arayüzünde (sağda) görüntülenmeleri gereken sırayla bize bunlarla ilişkili değerleri verir.
Anahtarları ve Değerleri Serileştirme
Dünya çapında nesneleri serileştirmenin birçok yöntemi vardır. Hızdan başka bir gereksinimimiz olmadığı için kendimize mümkün olan en hızlı olanı seçtik - C dil yapısının bir örneği tarafından işgal edilen bir bellek dökümü. Böylece, bir dizin öğesinin anahtarı aşağıdaki yapı ile modellenebilir. NodeKey.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameBuffer[256];
} NodeKey;Kaydetmek NodeKey nesnede depolama ihtiyacı MDB_val işaretçiyi yapının başlangıcındaki adresteki verilere konumlandırın ve fonksiyonla boyutlarını hesaplayın sizeof.
MDB_val serialize(NodeKey * const key) {
return MDB_val {
.mv_size = sizeof(NodeKey),
.mv_data = (void *)key
};
}Veritabanı seçim kriterleri ile ilgili ilk bölümde, önemli bir seçim faktörü olarak CRUD işlemlerinin bir parçası olarak dinamik tahsislerin en aza indirilmesinden bahsetmiştim. fonksiyon kodu serialize LMDB durumunda, veritabanına yeni kayıtlar eklendiğinde bunların nasıl tamamen önlenebileceğini gösterir. Sunucudan gelen bayt dizisi önce yığın yapılarına dönüştürülür ve ardından önemsiz bir şekilde depoya dökülür. LMDB içinde de dinamik ayırma olmadığı göz önüne alındığında, iOS standartlarına göre harika bir durum elde edebilirsiniz - ağdan diske kadar verilerle çalışmak için yalnızca yığın belleği kullanın!
İkili karşılaştırıcı ile anahtar sıralama
Anahtar sıra ilişkisi, karşılaştırıcı adı verilen özel bir işlevle verilir. Motor, içerdikleri baytların semantiği hakkında hiçbir şey bilmediğinden, varsayılan karşılaştırıcının, anahtarları bayt bayt karşılaştırmalarına başvurarak sözlüksel sırayla düzenlemekten başka seçeneği yoktur. Yapıları düzenlemek için kullanmak, bir oyma baltasıyla tıraş olmaya benzer. Ancak basit durumlarda bu yöntemi kabul edilebilir buluyorum. Alternatif aşağıda açıklanmıştır, ancak burada yol boyunca dağılmış birkaç tırmık not edeceğim.
Akılda tutulması gereken ilk şey, ilkel veri türlerinin bellek temsilidir. Bu nedenle, tüm Apple cihazlarında tamsayı değişkenleri şu biçimde saklanır: . Bu, en önemsiz baytın solda olacağı ve bayt bayt karşılaştırmalarını kullanarak tamsayıları sıralayamayacağınız anlamına gelir. Örneğin, bunu 0'dan 511'e kadar bir dizi sayı ile yapmaya çalışmak aşağıdaki sonucu verecektir.
// value (hex dump)
000 (0000)
256 (0001)
001 (0100)
257 (0101)
...
254 (fe00)
510 (fe01)
255 (ff00)
511 (ff01)Bu sorunu çözmek için, tamsayıların bayt karşılaştırıcısına uygun bir biçimde anahtarda saklanması gerekir. Aileden gelen işlevler, gerekli dönüşümü gerçekleştirmeye yardımcı olacaktır. hton* (özellikle htons örnekteki çift baytlık sayılar için).
Programlamada dizeleri temsil etme biçimi, bildiğiniz gibi, bir bütündür. . Dizelerin anlambilimi ve bunları bellekte temsil etmek için kullanılan kodlama, karakter başına birden fazla bayt olabileceğini gösteriyorsa, varsayılan bir karşılaştırıcı kullanma fikrinden hemen vazgeçmek daha iyidir.
Akılda tutulması gereken ikinci şey, yapı alanı derleyicisi. Bunlar nedeniyle, alanlar arasında, elbette bayt sıralamasını bozan, çöp değerleri olan baytlar oluşturulabilir. Çöpü ortadan kaldırmak için, hizalama kurallarını göz önünde bulundurarak alanları kesin olarak tanımlanmış bir sırada bildirmeniz veya yapı bildiriminde özniteliği kullanmanız gerekir. packed.
Harici bir karşılaştırıcı tarafından anahtar siparişi
Temel karşılaştırma mantığı, bir ikili karşılaştırıcı için fazla karmaşık olabilir. Birçok nedenden biri de yapıların içerisinde teknik alanların bulunmasıdır. Bir dizin öğesi için zaten aşina olduğumuz bir anahtar örneğinde bunların oluşumunu açıklayacağım.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameBuffer[256];
} NodeKey;Tüm basitliğine rağmen, vakaların büyük çoğunluğunda çok fazla bellek tüketir. Başlık arabelleği 256 bayttır, ancak ortalama olarak dosya ve klasör adları nadiren 20-30 karakteri geçer.
Bir kaydın boyutunu optimize etmenin standart tekniklerinden biri, onu gerçek boyutuna sığdırmaktır. Özü, tüm değişken uzunluklu alanların içeriğinin yapının sonundaki bir arabellekte saklanması ve uzunluklarının ayrı değişkenlerde saklanmasıdır.Bu yaklaşıma göre, anahtar NodeKey aşağıdaki şekilde dönüştürülür.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeKey;Ayrıca, serileştirme sırasında veri boyutu olarak belirtilmez sizeof tüm yapı ve tüm alanların boyutu sabit uzunluk artı arabelleğin fiilen kullanılan kısmının boyutudur.
MDB_val serialize(NodeKey * const key) {
return MDB_val {
.mv_size = offsetof(NodeKey, nameBuffer) + key->nameLength,
.mv_data = (void *)key
};
}Yeniden düzenleme sonucunda, anahtarların kapladığı alandan önemli ölçüde tasarruf ettik. Ancak teknik alan gereği nameLength, varsayılan ikili karşılaştırıcı artık anahtar karşılaştırma için uygun değildir. Kendi adımızla değiştirmezsek, adın uzunluğu sıralamada adın kendisinden daha öncelikli bir faktör olacaktır.
LMDB, her veritabanının kendi anahtar karşılaştırma işlevine sahip olmasına izin verir. Bu, işlev kullanılarak yapılır. mdb_set_compare kesinlikle açmadan önce. Bariz sebeplerden dolayı, bir veritabanı kullanım ömrü boyunca değiştirilemez. Girişte, karşılaştırıcı ikili biçimde iki anahtar alır ve çıktıda karşılaştırmanın sonucunu döndürür: (-1'den küçük), (1'den büyük) veya eşit (0). için sözde kod NodeKey öyle görünüyor.
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 // ...
}Veritabanındaki tüm anahtarlar aynı türde olduğu sürece, bayt temsillerini anahtarın uygulama yapısının türüne koşulsuz olarak atamak yasaldır. Burada bir nüans var ama biraz daha aşağıda "Kayıtları Okumak" alt bölümünde tartışılacak.
Değer Serileştirme
Saklanan kayıtların anahtarları ile LMDB son derece yoğun çalışır. Herhangi bir uygulama işlemi çerçevesinde birbirleriyle karşılaştırılırlar ve tüm çözümün performansı karşılaştırıcının hızına bağlıdır. İdeal bir dünyada, varsayılan ikili karşılaştırıcı, anahtarları karşılaştırmak için yeterli olmalıdır, ancak gerçekten kendinizinkini kullanmanız gerekiyorsa, içindeki anahtarların serisini kaldırma prosedürü mümkün olduğunca hızlı olmalıdır.
Veritabanı, kaydın (değer) Değer kısmıyla özellikle ilgilenmez. Bir bayt gösteriminden bir nesneye dönüştürülmesi, yalnızca uygulama kodu tarafından, örneğin ekranda görüntülenmesi için zaten gerekli olduğunda gerçekleşir. Bu nispeten nadiren gerçekleştiğinden, bu prosedürün hızı için gereksinimler o kadar kritik değildir ve uygulanmasında rahatlığa odaklanmak için çok daha özgürüz.Örneğin, henüz indirilmemiş dosyalar hakkındaki meta verileri seri hale getirmek için şunu kullanıyoruz: NSKeyedArchiver.
NSData *data = serialize(object);
MDB_val value = {
.mv_size = data.length,
.mv_data = (void *)data.bytes
};Ancak, performansın önemli olduğu zamanlar vardır. Örneğin, kullanıcı bulutunun dosya yapısı hakkındaki meta bilgileri kaydederken, aynı nesne bellek dökümünü kullanırız. Serileştirilmiş temsillerini oluşturma görevinin öne çıkan özelliği, bir dizinin öğelerinin bir sınıf hiyerarşisi tarafından modellenmiş olmasıdır.
C dilinde uygulanması için, mirasçıların belirli alanları ayrı yapılara alınır ve bunların taban ile bağlantısı birleşim tipi bir alan aracılığıyla belirtilir. Birleşmenin gerçek içeriği, type teknik özniteliği aracılığıyla belirtilir.
typedef struct NodeValue {
EntityId localId;
EntityType type;
union {
FileInfo file;
DirectoryInfo directory;
} info;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeValue;Girişleri ekleme ve güncelleme
Serileştirilmiş anahtar ve değer depoya eklenebilir. Bunun için fonksiyon kullanılır. mdb_put.
// key и value имеют тип MDB_val
mdb_put(..., &key, &value, MDB_NOOVERWRITE);Konfigürasyon aşamasında, havuzun aynı anahtarla birden fazla kaydı saklamasına izin verilebilir veya yasaklanabilir. Yıpranma yalnızca koddaki bir hatanın sonucu olarak meydana geliyorsa, bayrağı belirterek buna karşı sigortalayabilirsiniz. NOOVERWRITE.
Kayıtları Okumak
LMDB'deki kayıtları okuma işlevi mdb_get. Anahtar/değer çifti önceden dökülmüş yapılarla temsil ediliyorsa, bu prosedür şöyle görünür.
NodeValue * const readNode(..., NodeKey * const key) {
MDB_val rawKey = serialize(key);
MDB_val rawValue;
mdb_get(..., &rawKey, &rawValue);
return (NodeValue * const)rawValue.mv_data;
}Sunulan liste, bir yapı dökümü yoluyla serileştirmenin, yalnızca yazarken değil, verileri okurken de dinamik ayırmalardan kurtulmanıza nasıl izin verdiğini gösterir. fonksiyondan türetilen mdb_get işaretçi, veritabanının nesnenin bayt temsilini depoladığı sanal bellek adresine tam olarak bakar. Aslında, çok yüksek hızda veri okuma sağlayan neredeyse ücretsiz bir tür ORM alıyoruz. Yaklaşımın tüm güzelliği ile, onunla ilişkili birkaç özelliği hatırlamak gerekir.
- Salt okunur bir işlem için, bir değer yapısına işaretçinin yalnızca işlem kapatılana kadar geçerli kalması garanti edilir. Daha önce belirtildiği gibi, yazma sırasında kopyalama ilkesi sayesinde, nesnenin bulunduğu B ağacının sayfaları, en az bir işlem onlara atıfta bulunduğu sürece değişmeden kalır. Aynı zamanda, onlarla ilişkili son işlem tamamlanır tamamlanmaz, sayfalar yeni veriler için yeniden kullanılabilir. Nesnelerin onları oluşturan işlemden sonra hayatta kalması gerekiyorsa, yine de kopyalanmaları gerekir.
- Bir okuma yazma işlemi için, elde edilen yapı-değerinin işaretçisi yalnızca ilk değiştirme prosedürüne (veri yazma veya silme) kadar geçerli olacaktır.
- Her ne kadar yapı
NodeValuetam teşekküllü değil, kırpılmış ("Anahtarları harici bir karşılaştırıcı ile sipariş etme" alt bölümüne bakın), işaretçi aracılığıyla alanlarına kolayca erişebilirsiniz. Ana şey onu reddetmek değil! - Alınan işaretçi aracılığıyla hiçbir durumda yapıyı değiştiremezsiniz. Tüm değişiklikler yalnızca yöntem aracılığıyla yapılmalıdır.
mdb_put. Ancak, bunu yapmak için tüm arzuya rağmen, bu yapının bulunduğu hafıza alanı salt okunur modda haritalandığı için çalışmayacaktır. - Örneğin, işlevi kullanarak maksimum depolama boyutunu artırmak için bir dosyayı bir işlemin adres alanına yeniden eşleyin
mdb_env_set_map_sizegenel olarak tüm işlemleri ve ilgili varlıkları ve özellikle nesneleri okumak için işaretçileri tamamen geçersiz kılar.
Son olarak bir özellik daha o kadar sinsi ki, özünün ifşası bir noktaya daha sığmıyor. B-ağacıyla ilgili bölümde, sayfalarının bellekteki düzeninin bir şemasını verdim. Bundan, seri hale getirilmiş verilerle arabelleğin başlangıcının adresinin kesinlikle keyfi olabileceği sonucu çıkar. Bu nedenle, yapıda elde edilen onlara işaretçi MDB_val ve bir yapıya bir işaretçiye atama genellikle hizasızdır. Aynı zamanda, bazı yongaların mimarileri (iOS söz konusu olduğunda bu armv7'dir), herhangi bir verinin adresinin bir makine sözcüğü boyutunun katı veya başka bir deyişle sistemin bitliği olmasını gerektirir. (armv7 için bu 32 bittir). Başka bir deyişle, şöyle bir işlem *(int *foo)0x800002 üzerlerinde kaçmaya eşittir ve bir kararla infaza yol açar EXC_ARM_DA_ALIGN. Böyle üzücü bir kaderden kaçınmanın iki yolu vardır.
Birincisi, verileri önceden bilinen hizalanmış bir yapıya kopyalamaktır. Örneğin, özel bir karşılaştırıcıda bu aşağıdaki gibi yansıtılacaktır.
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 // ...
}Alternatif bir yol, derleyiciye bir anahtar ve değere sahip yapıların bir öznitelik kullanılarak hizalanamayabileceğini önceden bildirmektir. aligned(1). ARM'de aynı etki olabilir ve paketlenmiş özniteliği kullanarak. Yapının kapladığı alanın optimizasyonuna da katkı sağladığı düşünüldüğünde bu yöntem bana tercih edilebilir gibi görünse de veri erişim işlemlerinin maliyetini artırmak için.
typedef struct __attribute__((packed)) NodeKey {
uint8_t parentId;
uint8_t type;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeKey;Aralık Sorguları
Bir kayıt grubu üzerinde yineleme yapmak için LMDB bir imleç soyutlaması sağlar. Kullanıcı bulutu meta verilerinin bize zaten aşina olduğu bir tablo örneğini kullanarak onunla nasıl çalışılacağına bakalım.
Bir dizindeki dosyaların listesini görüntülemenin bir parçası olarak, alt dosya ve klasörlerin ilişkili olduğu tüm anahtarları bulmanız gerekir. Önceki alt bölümlerde, anahtarları sıraladık NodeKey böylece önce üst dizin kimliklerine göre sıralanırlar. Bu nedenle, teknik olarak, bir klasörün içeriğini elde etme görevi, imleci belirli bir önek ile bir tuş grubunun üst sınırına yerleştirmek ve ardından alt sınıra doğru yinelemeye indirgenir.
Sıralı arama yaparak "alında" üst sınırını bulabilirsiniz. Bunu yapmak için, imleç, veritabanındaki tüm anahtar listesinin başına yerleştirilir ve ardından, üst dizin tanımlayıcısına sahip anahtar, altında görünene kadar artırılır. Bu yaklaşımın 2 belirgin dezavantajı vardır:
- Aramanın doğrusal karmaşıklığı, bildiğiniz gibi, genel olarak ağaçlarda ve özel olarak bir B-ağacında, logaritmik zamanda yapılabilir.
- Boşuna, istenenden önceki tüm sayfalar dosyadan ana belleğe yükseltilir ki bu son derece pahalıdır.
Neyse ki, LMDB API, imleci başlangıçta konumlandırmak için etkili bir yol sağlar. Bunu yapmak için, değeri aralığın üst sınırında bulunan anahtardan kesinlikle küçük veya ona eşit olacak böyle bir anahtar oluşturmanız gerekir. . Örneğin, yukarıdaki şekildeki listeyle ilgili olarak, alanın bulunduğu bir anahtar yapabiliriz. parentId 2'ye eşit olacak ve geri kalan her şey sıfırlarla dolu. Bu tür kısmen doldurulmuş bir anahtar, işlevin girişine beslenir. mdb_cursor_get işlemi gösteren 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);Anahtar grubunun üst sınırı bulunursa, ya buluşana kadar ya da anahtar başka bir anahtarla buluşana kadar üzerinde yineleniriz. parentIdveya tuşlar hiç bitmeyecek.
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 groupGüzel olan, mdb_cursor_get kullanarak yinelemenin bir parçası olarak, yalnızca anahtarı değil, aynı zamanda değeri de alıyoruz. Seçim koşullarını yerine getirmek için, diğer şeylerin yanı sıra, kaydın değer kısmındaki alanları kontrol etmek gerekirse, ek hareketler olmadan kendileri için oldukça erişilebilirdirler.
4.3. Tablolar arasındaki ilişkileri modelleme
Bugüne kadar, tek tablolu bir veritabanı tasarlamanın ve bunlarla çalışmanın tüm yönlerini dikkate almayı başardık. Bir tablonun, aynı türden anahtar/değer çiftlerinden oluşan sıralanmış kayıtlar kümesi olduğunu söyleyebiliriz. Bir anahtarı bir dikdörtgen olarak ve onunla ilişkili değeri bir kutu olarak görüntülerseniz, veritabanının görsel bir diyagramını elde edersiniz.
Ancak gerçek hayatta bu kadar az kanla geçinmek pek mümkün olmuyor. Genellikle bir veritabanında, ilk olarak, birkaç tabloya sahip olmak ve ikinci olarak, seçimleri birincil anahtardan farklı bir sırada gerçekleştirmek gerekir. Bu son bölüm, bunların yaratılışı ve birbirine bağlanması konularına ayrılmıştır.
Dizin tabloları
Bulut uygulamasının bir "Galeri" bölümü vardır. Tüm buluttaki medya içeriğini tarihe göre sıralanmış olarak görüntüler. Böyle bir seçimin en iyi şekilde uygulanması için, ana tablonun yanında yeni bir anahtar türüyle başka bir tane oluşturmanız gerekir. Birincil sıralama kriteri olarak hareket edecek olan dosyanın oluşturulduğu tarihi içeren bir alan içereceklerdir. Yeni anahtarlar, alttaki tablodaki anahtarlarla aynı verilere atıfta bulunduğundan, bunlara dizin anahtarları adı verilir. Aşağıdaki resimde turuncu renkle vurgulanmıştır.
Aynı veri tabanı içerisinde farklı tabloların anahtarlarını birbirinden ayırmak için hepsine ilave bir teknik alan tableId eklenmiştir. Sıralama için en yüksek önceliği yaparak, anahtarları önce tablolara göre ve zaten tabloların içinde - kendi kurallarımıza göre gruplandıracağız.
Dizin anahtarı, birincil anahtarla aynı verileri ifade eder. Bu özelliğin, birincil anahtarın değer kısmının bir kopyasıyla ilişkilendirilerek doğrudan uygulanması, aynı anda birkaç açıdan yetersizdir:
- Yer kaplayan bir bakış açısından, meta veriler oldukça zengin olabilir.
- Performans açısından, düğüm meta verilerini güncellerken iki anahtarın üzerine yazmanız gerekeceğinden.
- Sonuçta, kod desteği açısından, anahtarlardan birinin verilerini güncellemeyi unutursak, depolamada ince bir veri tutarsızlığı hatası alırız.
Ardından, bu eksikliklerin nasıl giderileceğini ele alacağız.
Tablolar arasındaki ilişkilerin organizasyonu
Model, bir dizin tablosunu ana tabloya bağlamak için çok uygundur. "değer olarak anahtar". Adından da anlaşılacağı gibi, dizin kaydının değer kısmı birincil anahtar değerinin bir kopyasıdır. Bu yaklaşım, birincil kaydın değer kısmının bir kopyasının saklanmasıyla ilgili yukarıda listelenen tüm dezavantajları ortadan kaldırır. Tek ücret indeks anahtarı ile değer almak için veritabanına bir yerine 2 sorgu yapmanız gerektiğidir. Şematik olarak, ortaya çıkan veritabanı şeması aşağıdaki gibidir.
Tablolar arasındaki ilişkileri düzenlemek için başka bir model "gereksiz anahtar". Özü, anahtara sıralama için değil, ilgili anahtarı yeniden oluşturmak için gerekli olan ek nitelikler eklemektir.Bununla birlikte, Mail.ru Cloud uygulamasında kullanımının gerçek örnekleri vardır, ancak, derinlere dalmaktan kaçınmak için. Belirli iOS çerçeveleri bağlamında, hayali ama daha anlaşılır bir örnek vereceğim.
Bulut mobil istemcileri, kullanıcının diğer kişilerle paylaştığı tüm dosya ve klasörleri görüntüleyen bir sayfaya sahiptir. Nispeten az sayıda bu tür dosya olduğundan ve bunlarla ilişkili tanıtım hakkında çok fazla özel bilgi olduğundan (kime erişim verilir, hangi haklarla vb.), Değer kısmıyla onu yüklemek mantıklı olmayacaktır. ana tablodaki kayıt. Ancak, bu tür dosyaları çevrimdışı görüntülemek istiyorsanız, yine de bir yerde saklamanız gerekir. Bunun için ayrı bir tablo oluşturmak doğal bir çözümdür. Aşağıdaki şemada, anahtarının önüne "P" eklenmiştir ve "propname" yer tutucusu, daha spesifik bir değer olan "public info" ile değiştirilebilir.
Yeni tablonun uğruna oluşturulduğu tüm benzersiz meta veriler, kaydın değer bölümüne taşınır. Aynı zamanda, zaten ana tabloda depolanan dosya ve klasörler hakkındaki verileri çoğaltmak istemiyorum. Bunun yerine "node ID" ve "timestamp" alanları şeklinde "P" anahtarına yedekli veriler eklenir. Onlar sayesinde, birincil anahtarı alabileceğiniz bir dizin anahtarı oluşturabilirsiniz ve bununla son olarak düğümün meta verilerini alabilirsiniz.
Çözüm
LMDB uygulamasının sonuçlarını olumlu değerlendiriyoruz. Ardından uygulama donma sayısı %30 azaldı.
Yapılan çalışmaların sonuçları iOS ekibi dışında da yanıt buldu. Şu anda Android uygulamasındaki ana "Dosyalar" bölümlerinden biri de LMDB kullanımına geçti ve diğer bölümler de yolda. Anahtar/değer depolamanın uygulandığı C dili, uygulamayı başlangıçta C++ dilinde çapraz platform etrafında bağlamak için iyi bir yardımcıydı. Ortaya çıkan C++ kitaplığının Objective-C ve Kotlin'deki platform koduyla sorunsuz bağlantısı için bir kod oluşturucu kullanıldı Dropbox'tan, ama bu başka bir hikaye.
Kaynak: habr.com