در پاییز 2019، یک رویداد مورد انتظار در تیم Mail.ru Cloud iOS رخ داد. پایگاه داده اصلی برای ذخیره سازی مداوم وضعیت برنامه برای دنیای تلفن همراه کاملاً عجیب و غریب شده است پایگاه داده نقشه برداری از حافظه لایتنینگ (LMDB). در زیر برش، توجه شما به بررسی مفصل آن در چهار قسمت دعوت می شود. ابتدا اجازه دهید در مورد دلایل چنین انتخاب غیر پیش پا افتاده و دشواری صحبت کنیم. سپس بیایید به بررسی سه نهنگ در قلب معماری LMDB بپردازیم: فایل‌های دارای نقشه حافظه، درخت B +، رویکرد کپی روی نوشتن برای پیاده‌سازی تراکنشی و چند نسخه‌سازی. در نهایت، برای دسر - بخش عملی. در آن، ما به نحوه طراحی و پیاده‌سازی یک طرحواره پایه با چندین جدول، از جمله یک شاخص، در بالای API کلیدی سطح پایین نگاه خواهیم کرد.

مقدار

1. انگیزه پیاده سازی
2. تعیین موقعیت LMDB
3. سه نهنگ LMDB
   3.1. نهنگ شماره 1. فایل های دارای نقشه حافظه
   3.2. نهنگ شماره 2. B+-tree
   3.3. نهنگ شماره 3. کپی روی نوشتن
4. طراحی یک طرح داده در بالای API کلید-مقدار
   4.1. انتزاعات اساسی
   4.2. مدل سازی جدول
   4.3. مدل سازی روابط بین جداول

1. انگیزه اجرا

یک بار در سال، در سال 2015، ما مراقب بودیم که یک معیار اندازه گیری کنیم که چقدر رابط برنامه ما تاخیر دارد. ما فقط این کار را نکردیم. ما شکایات بیشتری در مورد این واقعیت داریم که گاهی اوقات برنامه به اقدامات کاربر پاسخ نمی دهد: دکمه ها فشار داده نمی شوند، لیست ها پیمایش نمی کنند و غیره. درباره مکانیک اندازه گیری ها گفت در AvitoTech، بنابراین در اینجا فقط ترتیب اعداد را می دهم.

نتایج اندازه گیری برای ما تبدیل به دوش آب سرد شد. معلوم شد که مشکلات ناشی از یخ زدگی بسیار بیشتر از سایرین است. اگر قبل از درک این واقعیت، شاخص فنی اصلی کیفیت بدون تصادف بود، پس از تمرکز جابجا شد بدون انجماد

ساختن داشبورد با یخ زدگی و خرج کردن کمی и کیفیت با تجزیه و تحلیل علل آنها، دشمن اصلی مشخص شد - اجرای منطق تجاری سنگین در موضوع اصلی برنامه. یک واکنش طبیعی به این رسوایی، میل شدیدی بود که آن را در جریان کار فرو برد. برای حل سیستماتیک این مشکل، ما به معماری چند رشته ای مبتنی بر بازیگران سبک وزن متوسل شدیم. من اقتباس های او را به دنیای iOS اختصاص دادم دو رشته در توییتر جمعی و مقاله در Habré. به عنوان بخشی از داستان فعلی، می‌خواهم بر جنبه‌هایی از تصمیمی که بر انتخاب پایگاه داده تأثیر گذاشت تأکید کنم.

مدل کنشگر سازماندهی سیستم فرض می کند که چند رشته ای به ذات دوم آن تبدیل می شود. اشیاء مدل در آن دوست دارند از مرزهای رشته عبور کنند. و این کار را نه گاهی و در بعضی جاها، بلکه تقریباً مدام و در همه جا انجام می دهند.

پایگاه داده یکی از اجزای اصلی در نمودار ارائه شده است. وظیفه اصلی آن پیاده سازی یک الگوی کلان است پایگاه داده مشترک. اگر در دنیای سازمانی برای سازماندهی همگام سازی داده ها بین سرویس ها استفاده می شود، در مورد معماری بازیگر، داده ها بین رشته ها استفاده می شود. بنابراین، ما به چنین پایگاه داده ای نیاز داشتیم که کار با آن در یک محیط چند رشته ای حتی حداقل مشکلات را ایجاد نمی کند. به ویژه، این بدان معنی است که اشیاء به دست آمده از آن باید حداقل از نظر نخ ایمن باشند، و در حالت ایده آل به هیچ وجه قابل تغییر نباشند. همانطور که می دانید، دومی را می توان به طور همزمان از چندین رشته بدون استفاده از هر نوع قفلی استفاده کرد که تأثیر مفیدی بر عملکرد دارد.

دومین عامل مهمی که بر انتخاب پایگاه داده تأثیر گذاشت، API ابری ما بود. از رویکرد git برای همگام سازی الهام گرفته شده است. مثل او که ما هدف گرفتیم اولین API آفلاین، که برای مشتریان ابری بسیار مناسب به نظر می رسد. فرض بر این بود که آنها فقط یک بار وضعیت کامل ابر را پمپ می کنند و سپس در اکثر موارد همگام سازی از طریق تغییرات چرخشی اتفاق می افتد. افسوس، این امکان هنوز فقط در منطقه نظری است و در عمل، مشتریان نحوه کار با پچ ها را یاد نگرفته اند. دلایل عینی متعددی برای این امر وجود دارد که برای تأخیر در معرفی آنها از پرانتز صرف نظر می کنیم. اکنون نتایج آموزنده این درس در مورد اینکه چه اتفاقی می افتد زمانی که API می گوید "A" و مصرف کننده آن "B" را نمی گوید، بسیار جالب تر است.

بنابراین، اگر git را تصور کنید که هنگام اجرای دستور pull، به جای اعمال وصله‌ها در یک عکس فوری محلی، وضعیت کامل آن را با سرور کامل مقایسه می‌کند، ایده نسبتاً دقیقی از نحوه همگام‌سازی خواهید داشت. در کلاینت های ابری رخ می دهد. به راحتی می توان حدس زد که برای اجرای آن لازم است دو درخت DOM در حافظه با اطلاعات متا در مورد تمام فایل های سرور و محلی اختصاص داده شود. به نظر می رسد که اگر یک کاربر 500 هزار فایل را در فضای ابری ذخیره کند، برای همگام سازی آن، باید دو درخت را با 1 میلیون گره دوباره ایجاد و نابود کرد. اما هر گره یک انباشته است که شامل نموداری از موضوعات فرعی است. در این راستا، نتایج حاصل از نمایه سازی انتظار می رفت. مشخص شد که حتی بدون در نظر گرفتن الگوریتم ادغام، فرآیند ایجاد و سپس از بین بردن تعداد زیادی از اشیاء کوچک یک پنی هزینه دارد. وضعیت با این واقعیت بدتر می شود که عملیات همگام سازی اولیه در تعداد زیادی گنجانده شده است. از اسکریپت های کاربر در نتیجه، دومین معیار مهم در انتخاب پایگاه داده را برطرف می کنیم - توانایی اجرای عملیات CRUD بدون تخصیص پویا اشیا.

سایر الزامات سنتی تر هستند و لیست کامل آنها به شرح زیر است.

1. ایمنی نخ.
2. چند پردازش. دیکته شده توسط تمایل به استفاده از یک نمونه پایگاه داده برای همگام سازی وضعیت نه تنها بین رشته ها، بلکه بین برنامه اصلی و برنامه های افزودنی iOS.
3. توانایی نمایش موجودیت های ذخیره شده به عنوان اشیاء غیرقابل تغییر.
4. عدم تخصیص پویا در عملیات CRUD.
5. پشتیبانی تراکنش برای ویژگی های اساسی ACIDکلمات کلیدی: اتمی، قوام، انزوا و قابلیت اطمینان.
6. سرعت در محبوب ترین موارد.

با این مجموعه الزامات، SQLite انتخاب خوبی بود و هنوز هم است. با این حال، به عنوان بخشی از مطالعه جایگزین ها، به کتابی برخوردم "شروع به کار با LevelDB". تحت رهبری او، معیاری نوشته شد که سرعت کار را با پایگاه داده های مختلف در سناریوهای ابری واقعی مقایسه می کند. نتیجه فراتر از وحشیانه ترین انتظارات بود. در محبوب‌ترین موارد - دریافت مکان‌نما در فهرست مرتب‌شده همه فایل‌ها و فهرست مرتب‌شده همه فایل‌ها برای یک فهرست مشخص - LMDB 10 برابر سریع‌تر از SQLite است. انتخاب آشکار شد.

2. موقعیت یابی LMDB

LMDB یک کتابخانه بسیار کوچک (فقط 10 هزار خط) است که پایین ترین لایه بنیادی پایگاه داده - ذخیره سازی را پیاده سازی می کند.

نمودار بالا نشان می دهد که مقایسه LMDB با SQLite، که حتی سطوح بالاتر را نیز پیاده سازی می کند، به طور کلی درست تر از SQLite با Core Data نیست. منصفانه تر است که موتورهای ذخیره سازی مشابه را به عنوان رقبای برابر ذکر کنیم - BerkeleyDB، LevelDB، Sophia، RocksDB، و غیره. حتی پیشرفت هایی وجود دارد که LMDB به عنوان یک جزء موتور ذخیره سازی برای SQLite عمل می کند. اولین آزمایش از این دست در سال 2012 انجام شد صرف کرد نویسنده LMDB هوارد چو. یافته ها به قدری جالب بود که ابتکار او توسط علاقه مندان OSS مورد توجه قرار گرفت و ادامه آن در مواجهه با LumoSQL. در ژانویه 2020 نویسنده این پروژه دن شیرر است ارایه شده آن را در LinuxConfAu.

کاربرد اصلی LMDB به عنوان موتوری برای پایگاه های داده برنامه ها است. کتابخانه ظاهر خود را مدیون توسعه دهندگان است اوپنالدپ، که به شدت از BerkeleyDB به عنوان اساس پروژه خود ناراضی بودند. دور شدن از کتابخانه محقر btreeهاوارد چو توانست یکی از محبوب ترین جایگزین های زمان ما را ایجاد کند. او گزارش بسیار جالب خود را به این داستان و همچنین ساختار داخلی LMDB اختصاص داده است. پایگاه داده نقشه برداری از حافظه لایتنینگ. لئونید یوریف (معروف به yleo) از Positive Technologies در سخنرانی خود در Highload 2015 "موتور LMDB یک قهرمان ویژه است". در آن، او در مورد LMDB در زمینه یک کار مشابه یعنی پیاده سازی ReOpenLDAP صحبت می کند و LevelDB قبلاً مورد انتقاد مقایسه ای قرار گرفته است. در نتیجه پیاده سازی، Positive Technologies حتی یک چنگال فعال در حال توسعه به دست آورد MDBX با امکانات بسیار خوشمزه، بهینه سازی و رفع اشکال.

LMDB اغلب به عنوان یک ذخیره سازی نیز استفاده می شود. به عنوان مثال، مرورگر موزیلا فایرفاکس انتخاب کرد آن را برای تعدادی از نیازها، و، با شروع از نسخه 9، Xcode ارجح SQLite آن برای ذخیره ایندکس ها.

این موتور همچنین در دنیای توسعه موبایل جای گرفت. ردپای استفاده از آن می تواند باشد پیدا کردن در کلاینت iOS برای تلگرام. لینکدین یک قدم جلوتر رفت و LMDB را به عنوان ذخیره‌سازی پیش‌فرض برای چارچوب ذخیره‌سازی داده‌های داخلی خود، Rocket Data، انتخاب کرد. گفت در مقاله ای در سال 2016

LMDB با موفقیت در حال مبارزه برای یک مکان در خورشید در طاقچه ای است که توسط BerkeleyDB پس از انتقال تحت کنترل اوراکل باقی مانده است. این کتابخانه به دلیل سرعت و قابلیت اطمینان آن، حتی در مقایسه با نوع خود، مورد علاقه است. همانطور که می دانید، هیچ ناهار رایگان وجود ندارد، و من می خواهم بر مبادله ای تأکید کنم که هنگام انتخاب بین LMDB و SQLite باید با آن روبرو شوید. نمودار بالا به وضوح نشان می دهد که چگونه سرعت افزایش یافته به دست می آید. اول، ما برای لایه های اضافی انتزاع در بالای فضای ذخیره سازی دیسک هزینه ای پرداخت نمی کنیم. البته در یک معماری خوب باز هم نمی توانید بدون آنها کار کنید و به ناچار در کد برنامه ظاهر می شوند اما بسیار نازکتر خواهند بود. آنها ویژگی هایی ندارند که توسط یک برنامه خاص مورد نیاز نیست، به عنوان مثال، پشتیبانی از پرس و جو در زبان SQL. ثانیا، پیاده سازی بهینه نگاشت عملیات برنامه به درخواست های ذخیره سازی دیسک امکان پذیر می شود. اگر SQLite در کار من از نیازهای متوسط ​​یک برنامه متوسط ​​ناشی می شود، پس شما به عنوان یک توسعه دهنده برنامه به خوبی از سناریوهای بارگذاری اصلی آگاه هستید. برای یک راه حل مولدتر، باید برای توسعه راه حل اولیه و پشتیبانی بعدی آن، قیمت افزایش یافته ای بپردازید.

3. سه نهنگ LMDB

پس از نگاه کردن به LMDB از دید پرنده، وقت آن است که به عمق بیشتری بروید. سه بخش بعدی به تجزیه و تحلیل نهنگ های اصلی که معماری ذخیره سازی بر آنها استوار است اختصاص داده می شود:

1. فایل های نگاشت حافظه به عنوان مکانیزمی برای کار با دیسک و همگام سازی ساختارهای داده داخلی.
2. B+-tree به عنوان سازمانی از ساختار داده های ذخیره شده.
3. کپی روی نوشتن به عنوان رویکردی برای ارائه ویژگی های تراکنشی ACID و چند نسخه.

3.1. نهنگ شماره 1. فایل های دارای نقشه حافظه

فایل های نگاشت حافظه آنقدر عنصر مهم معماری هستند که حتی در نام مخزن نیز ظاهر می شوند. مسائل مربوط به ذخیره و همگام سازی دسترسی به اطلاعات ذخیره شده کاملاً در اختیار سیستم عامل است. LMDB حاوی هیچ کشی درون خود نیست. این یک تصمیم آگاهانه توسط نویسنده است، زیرا خواندن داده ها به طور مستقیم از فایل های نقشه برداری به شما امکان می دهد تا گوشه های زیادی را در اجرای موتور برش دهید. در زیر لیستی از برخی از آنها بسیار دور از دسترس است.

1. حفظ ثبات داده ها در ذخیره سازی هنگام کار با آن از چندین فرآیند به عهده سیستم عامل می شود. در قسمت بعدی به تفصیل و با تصاویر به این مکانیک پرداخته شده است.
2. عدم وجود حافظه پنهان LMDB را به طور کامل از سربار مربوط به تخصیص پویا رها می کند. خواندن داده ها در عمل به معنای تنظیم نشانگر به آدرس صحیح در حافظه مجازی است و نه بیشتر. به نظر می رسد فانتزی است، اما در منبع مخزن، همه تماس های calloc در تابع پیکربندی مخزن متمرکز می شوند.
3. عدم وجود حافظه پنهان همچنین به معنای عدم وجود قفل های مرتبط با همگام سازی برای دسترسی به آنها است. خواننده هایی که تعداد دلخواه آنها می تواند همزمان وجود داشته باشد، در مسیر رسیدن به داده ها با یک mutex واحد مواجه نمی شوند. به همین دلیل سرعت خواندن از نظر تعداد CPU دارای مقیاس پذیری خطی ایده آلی است. در LMDB، فقط عملیات تغییر همگام سازی می شود. در هر زمان فقط یک نویسنده می تواند وجود داشته باشد.
4. حداقل منطق ذخیره سازی و همگام سازی کد را از نوع بسیار پیچیده ای از خطاهای مرتبط با کار در یک محیط چند رشته ای نجات می دهد. دو مطالعه جالب پایگاه داده در کنفرانس Usenix OSDI 2014 وجود داشت: «همه سیستم‌های فایل یکسان ایجاد نمی‌شوند: در پیچیدگی ایجاد برنامه‌های سازگار با خرابی» и شکنجه پایگاه های داده برای سرگرمی و سود. از آنها می توانید اطلاعاتی در مورد قابلیت اطمینان بی سابقه LMDB و اجرای تقریباً بی عیب و نقص ویژگی های ACID تراکنش ها به دست آورید که در همان SQLite از آن پیشی می گیرد.
5. مینیمالیسم LMDB اجازه می دهد تا نمایش ماشین کد آن به طور کامل در حافظه نهان L1 پردازنده با ویژگی های سرعت حاصله قرار گیرد.

متأسفانه، در iOS، فایل‌های دارای نقشه حافظه آنقدر که ما می‌خواهیم گلگون نیستند. برای صحبت در مورد معایب مرتبط با آنها آگاهانه تر، لازم است اصول کلی برای پیاده سازی این مکانیسم در سیستم عامل ها را یادآوری کنیم.

اطلاعات کلی در مورد فایل های حافظه دار

با هر برنامه اجرایی، سیستم عامل موجودی به نام فرآیند را مرتبط می کند. به هر فرآیند یک محدوده پیوسته از آدرس ها اختصاص داده می شود که در آن هر چیزی را که برای کار نیاز دارد قرار می دهد. پایین ترین آدرس ها شامل بخش هایی با کد و داده ها و منابع سخت کد شده است. بعد بلوک رو به رشد فضای آدرس پویا می آید که برای ما به عنوان پشته شناخته می شود. این شامل آدرس های موجودیت هایی است که در طول عملیات برنامه ظاهر می شوند. در بالا ناحیه حافظه مورد استفاده پشته برنامه قرار دارد. یا رشد می کند یا کوچک می شود، به عبارت دیگر اندازه آن نیز ماهیتی پویا دارد. به طوری که پشته و هیپ با یکدیگر فشار نیاورند و با یکدیگر تداخل نداشته باشند، در انتهای مختلف فضای آدرس از هم جدا می شوند.یک سوراخ بین دو بخش پویا در بالا و پایین وجود دارد. آدرس‌های این بخش میانی توسط سیستم عامل برای ارتباط با فرآیندی از موجودیت‌های مختلف استفاده می‌شود. به طور خاص، می تواند مجموعه ای پیوسته از آدرس ها را به یک فایل روی دیسک نگاشت کند. به چنین فایلی فایل نگاشت حافظه می گویند

فضای آدرس اختصاص داده شده به یک فرآیند بسیار زیاد است. از نظر تئوری، تعداد آدرس‌ها فقط با اندازه اشاره‌گر محدود می‌شود که با بیتی بودن سیستم تعیین می‌شود. اگر حافظه فیزیکی 1-in-1 به آن اختصاص داده می شد، اولین فرآیند کل RAM را از بین می برد و هیچ بحثی در مورد انجام چند وظیفه ای وجود نداشت.

با این حال، ما به تجربه می دانیم که سیستم عامل های مدرن می توانند هر تعداد فرآیند را که بخواهید همزمان اجرا کنند. این به دلیل این واقعیت است که آنها حافظه زیادی را فقط روی کاغذ به پردازش ها اختصاص می دهند ، اما در واقع فقط بخشی را که در اینجا و اکنون مورد تقاضا است در حافظه فیزیکی اصلی بارگذاری می کنند. بنابراین حافظه مرتبط با فرآیند مجازی نامیده می شود.

سیستم عامل حافظه مجازی و فیزیکی را در صفحاتی با اندازه مشخص سازماندهی می کند. به محض اینکه صفحه خاصی از حافظه مجازی مورد تقاضا باشد، سیستم عامل آن را در حافظه فیزیکی بارگذاری می کند و مکاتبات بین آنها را در یک جدول خاص قرار می دهد. اگر اسلات رایگان وجود نداشته باشد، یکی از صفحات بارگذاری شده قبلی روی دیسک کپی می شود و صفحه درخواست شده جای آن را می گیرد. این روش که به زودی به آن باز خواهیم گشت، مبادله نامیده می شود. شکل زیر روند توصیف شده را نشان می دهد. روی آن، صفحه A با آدرس 0 بارگذاری شد و در صفحه حافظه اصلی با آدرس 4 قرار گرفت. این واقعیت در جدول مطابقت در سلول شماره 0 منعکس شد.

در مورد فایل‌های دارای نقشه حافظه، داستان دقیقاً مشابه است. به طور منطقی، آنها ظاهراً به طور مداوم و به طور کامل در فضای آدرس مجازی قرار می گیرند. با این حال، آنها صفحه به صفحه و فقط در صورت تقاضا وارد حافظه فیزیکی می شوند. اصلاح چنین صفحاتی با فایل روی دیسک هماهنگ می شود. بنابراین، می توانید فایل I/O را انجام دهید، به سادگی با بایت ها در حافظه کار کنید - تمام تغییرات به طور خودکار توسط هسته سیستم عامل به فایل اصلی منتقل می شود.
​
تصویر زیر نشان می دهد که LMDB چگونه حالت خود را هنگام کار با پایگاه داده از فرآیندهای مختلف هماهنگ می کند. با نگاشت حافظه مجازی فرآیندهای مختلف بر روی یک فایل، ما عملاً سیستم عامل را موظف می‌کنیم تا بلوک‌های خاصی از فضاهای آدرس خود را به صورت گذرا با یکدیگر همگام‌سازی کند، جایی که LMDB به نظر می‌رسد.
​

نکته مهم این است که LMDB فایل داده را به طور پیش فرض از طریق مکانیسم فراخوانی سیستم نوشتن تغییر می دهد و خود فایل در حالت فقط خواندنی نمایش داده می شود. این رویکرد دو مفهوم مهم دارد.

اولین پیامد در همه سیستم عامل ها مشترک است. ماهیت آن افزودن محافظت در برابر آسیب ناخواسته به پایگاه داده توسط کد نادرست است. همانطور که می دانید، دستورالعمل های اجرایی یک فرآیند برای دسترسی به داده ها از هر نقطه از فضای آدرس آن آزاد است. در عین حال، همانطور که به یاد آوردیم، نمایش یک فایل در حالت خواندن و نوشتن به این معنی است که هر دستورالعملی می تواند علاوه بر این، آن را نیز تغییر دهد. اگر او به اشتباه این کار را انجام دهد، برای مثال، سعی کند در واقع یک عنصر آرایه را در یک شاخص غیر موجود بازنویسی کند، به این ترتیب می تواند به طور تصادفی فایل نگاشت شده به این آدرس را تغییر دهد که منجر به خراب شدن پایگاه داده می شود. اگر فایل در حالت فقط خواندنی نمایش داده شود، تلاش برای تغییر فضای آدرس مربوط به آن منجر به خرابی برنامه با سیگنال می شود. SIGSEGV، و فایل دست نخورده باقی می ماند.

پیامد دوم در حال حاضر مختص iOS است. نه نویسنده و نه هیچ منبع دیگری به صراحت به آن اشاره نمی کنند، اما بدون آن، LMDB برای اجرا بر روی این سیستم عامل تلفن همراه نامناسب خواهد بود. بخش بعدی به بررسی آن اختصاص دارد.

مشخصات فایل های حافظه دار در iOS

در سال 2018، یک گزارش فوق العاده در WWDC وجود داشت حافظه iOS Deep Dive. این نشان می دهد که در iOS همه صفحاتی که در حافظه فیزیکی قرار دارند به یکی از 3 نوع تعلق دارند: کثیف، فشرده و تمیز.

حافظه پاک مجموعه‌ای از صفحات است که می‌توان آن‌ها را با خیال راحت از حافظه فیزیکی خارج کرد. داده های آنها را می توان در صورت نیاز از منابع اصلی خود بارگیری کرد. فایل های دارای نقشه حافظه فقط خواندنی در این دسته قرار می گیرند. iOS ترسی ندارد که صفحات نگاشت شده به یک فایل را در هر زمان از حافظه بارگیری کند، زیرا تضمین می شود که با فایل روی دیسک همگام شوند.
​
همه صفحات اصلاح شده بدون توجه به جایی که در ابتدا قرار دارند وارد حافظه کثیف می شوند. به طور خاص، فایل‌های نگاشت حافظه که با نوشتن در حافظه مجازی مرتبط با آنها اصلاح می‌شوند نیز به این روش طبقه‌بندی می‌شوند. باز کردن LMDB با پرچم MDB_WRITEMAP، پس از ایجاد تغییرات در آن، خودتان می توانید ببینید.

به محض اینکه یک برنامه شروع به اشغال حافظه فیزیکی بیش از حد می کند، iOS صفحات کثیف آن را فشرده می کند. مجموعه حافظه اشغال شده توسط صفحات کثیف و فشرده به اصطلاح ردپای حافظه اپلیکیشن است. هنگامی که به یک مقدار آستانه خاص رسید، دیمون سیستم کشنده OOM بعد از فرآیند می آید و به زور آن را خاتمه می دهد. این ویژگی iOS در مقایسه با سیستم عامل های دسکتاپ است. در مقابل، کاهش ردپای حافظه با جابجایی صفحات از حافظه فیزیکی به دیسک در iOS ارائه نشده است، فقط می توان دلایل آن را حدس زد. شاید روش انتقال شدید صفحات به دیسک و برگشت برای دستگاه های تلفن همراه بیش از حد انرژی مصرف می کند، یا iOS منابع بازنویسی سلول ها را روی دیسک های SSD ذخیره می کند، یا شاید طراحان از عملکرد کلی سیستم راضی نبودند، جایی که همه چیز در آن وجود دارد. مدام تعویض می شود هرچه باشد، واقعیت همچنان پابرجاست.

خبر خوب که قبلاً ذکر شد این است که LMDB به طور پیش فرض از مکانیزم mmap برای به روز رسانی فایل ها استفاده نمی کند. نتیجه این است که داده های ارائه شده توسط iOS به عنوان حافظه تمیز طبقه بندی می شوند و به ردپای حافظه کمکی نمی کنند. این را می توان با استفاده از ابزار Xcode به نام VM Tracker تأیید کرد. اسکرین شات زیر وضعیت حافظه مجازی اپلیکیشن iOS Cloud را در حین کار نشان می دهد. در ابتدا، 2 نمونه LMDB در آن مقداردهی اولیه شد. اولی اجازه داشت فایل خود را به 1 گیگابایت حافظه مجازی نقشه برداری کند، دومی - 512 مگابایت. علیرغم این واقعیت که هر دو حافظه مقدار مشخصی از حافظه ساکن را اشغال می کنند، هیچ یک از آنها به اندازه کثیف کمک نمی کند.

حالا نوبت به خبرهای بد رسیده است. به لطف مکانیزم swap در سیستم‌عامل‌های دسکتاپ ۶۴ بیتی، هر فرآیند می‌تواند به همان اندازه فضای آدرس مجازی را اشغال کند که فضای آزاد روی هارد دیسک برای تعویض بالقوه آن اجازه می‌دهد. جایگزینی swap با فشرده سازی در iOS حداکثر تئوری را به شدت کاهش می دهد. در حال حاضر تمام فرآیندهای زنده باید در حافظه اصلی (خواندن RAM) قرار بگیرند و همه آنهایی که مناسب نیستند در معرض خاتمه اجباری هستند. همانطور که در بالا ذکر شده است گزارش، و در اسناد رسمی. در نتیجه، iOS مقدار حافظه موجود برای تخصیص از طریق mmap را به شدت محدود می کند. اینجا اینجا شما می توانید به محدودیت های تجربی در مورد مقدار حافظه ای که می تواند در دستگاه های مختلف با استفاده از این فراخوانی سیستم تخصیص داده شود نگاه کنید. در مدرن‌ترین مدل‌های گوشی‌های هوشمند، iOS 2 گیگابایت سخاوتمندانه شده است، و در نسخه‌های برتر iPad - 4. در عمل، البته، باید روی جوان‌ترین مدل‌های دستگاه‌های پشتیبانی‌شده تمرکز کنید، جایی که همه چیز بسیار غم‌انگیز است. حتی بدتر از آن، با نگاه کردن به وضعیت حافظه برنامه در VM Tracker، متوجه خواهید شد که LMDB تنها چیزی است که ادعا می کند حافظه نقشه برداری شده با حافظه است. تکه های خوب توسط تخصیص دهنده های سیستم، فایل های منابع، چارچوب های تصویر و سایر شکارچیان کوچکتر خورده می شوند.

بر اساس نتایج آزمایش‌ها در Cloud، به مقادیر مصالحه‌ای حافظه اختصاص‌یافته توسط LMDB رسیدیم: ۳۸۴ مگابایت برای دستگاه‌های ۳۲ بیتی و ۷۶۸ برای دستگاه‌های ۶۴ بیتی. پس از اتمام این حجم، هرگونه عملیات اصلاحی با کد شروع می شود MDB_MAP_FULL. ما چنین خطاهایی را در نظارت خود مشاهده می کنیم، اما آنقدر کوچک هستند که در این مرحله نادیده گرفته شوند.

یک دلیل غیر واضح برای مصرف بیش از حد حافظه توسط ذخیره سازی می تواند تراکنش های طولانی مدت باشد. برای درک چگونگی ارتباط این دو پدیده، به ما کمک می کند تا دو نهنگ LMDB باقی مانده را در نظر بگیریم.

3.2. نهنگ شماره 2. B+-tree

برای شبیه‌سازی جداول بالای یک ذخیره‌سازی کلید-مقدار، عملیات زیر باید در API آن وجود داشته باشد:

1. درج یک عنصر جدید
2. یک عنصر را با یک کلید مشخص جستجو کنید.
3. حذف یک عنصر
4. در فواصل کلیدی به ترتیب مرتب سازی آنها تکرار کنید.

ساده ترین ساختار داده ای که می تواند به راحتی هر چهار عملیات را پیاده سازی کند، درخت جستجوی باینری است. هر یک از گره های آن کلیدی است که کل زیر مجموعه کلیدهای فرزند را به دو زیر درخت تقسیم می کند. در سمت چپ آنهایی هستند که کوچکتر از والدین هستند و در سمت راست - آنهایی که بزرگتر هستند. به دست آوردن مجموعه ای از کلیدهای مرتب شده از طریق یکی از پیمایش های درختی کلاسیک به دست می آید

درخت های باینری دو اشکال اساسی دارند که مانع از کارآمدی آنها به عنوان یک ساختار داده دیسک می شود. اولاً، درجه تعادل آنها غیرقابل پیش بینی است. خطر قابل توجهی برای به دست آوردن درختانی وجود دارد که در آنها ارتفاع شاخه های مختلف می تواند بسیار متفاوت باشد، که به طور قابل توجهی پیچیدگی الگوریتمی جستجو را در مقایسه با آنچه انتظار می رود بدتر می کند. ثانیاً، فراوانی پیوندهای متقابل بین گره ها، درخت های باینری را از محلی بودن در حافظه محروم می کند. در نتیجه، حتی یک پیمایش ساده از چندین گره همسایه در یک درخت ممکن است نیاز به بازدید از تعداد قابل مقایسه ای از صفحات داشته باشد. این یک مشکل است حتی زمانی که ما در مورد کارایی درختان باینری به عنوان یک ساختار داده در حافظه صحبت می کنیم، زیرا چرخش مداوم صفحات در حافظه پنهان پردازنده ارزان نیست. وقتی صحبت از بالا بردن مکرر صفحات مرتبط با گره از دیسک می شود، اوضاع واقعاً بد می شود. اسفناک.

درختان B که تکاملی از درختان دوتایی هستند، مشکلاتی را که در پاراگراف قبل مشخص شد حل می کنند. اولاً آنها خود متعادل هستند. ثانیاً، هر یک از گره های آنها مجموعه کلیدهای فرزند را نه به 2، بلکه به زیر مجموعه های مرتب شده M تقسیم می کند، و عدد M می تواند بسیار بزرگ باشد، به ترتیب چند صد یا حتی هزاران.

در نتیجه:

1. هر گره دارای تعداد زیادی کلید از قبل سفارش شده است و درختان بسیار کم هستند.
2. درخت خاصیت محلی بودن را در حافظه به دست می آورد، زیرا کلیدهایی که از نظر ارزش نزدیک هستند به طور طبیعی در کنار یکدیگر در یک یا گره های همسایه قرار دارند.
3. تعداد گره های حمل و نقل را هنگام پایین آمدن از درخت در طول عملیات جستجو کاهش می دهد.
4. تعداد گره های هدف خوانده شده برای پرس و جوهای محدوده را کاهش می دهد، زیرا هر یک از آنها قبلاً دارای تعداد زیادی کلید مرتب شده است.

LMDB از گونه ای از درخت B به نام درخت B+ برای ذخیره داده ها استفاده می کند. نمودار بالا سه نوع گره را نشان می دهد که شامل:

1. در بالا ریشه است. این چیزی بیش از مفهوم یک پایگاه داده در یک مخزن تحقق نمی یابد. در یک نمونه LMDB، می توانید چندین پایگاه داده ایجاد کنید که فضای آدرس مجازی نگاشت شده را به اشتراک بگذارند. هر کدام از آنها از ریشه خود شروع می شود.
2. در پایین ترین سطح، برگ ها (برگ) قرار دارند. آنها و تنها آنها هستند که شامل جفت های کلید-مقدار ذخیره شده در پایگاه داده هستند. به هر حال، این ویژگی درختان B+ است. اگر یک درخت B معمولی قطعات مقدار را در گره های همه سطوح ذخیره کند، آنگاه تغییر B+ فقط در پایین ترین سطح است. پس از رفع این واقعیت، در موارد زیر، زیرنوع درخت مورد استفاده در LMDB را به سادگی یک درخت B می نامیم.
3. بین ریشه و برگ، 0 یا بیشتر سطح فنی با گره های ناوبری (شاخه) وجود دارد. وظیفه آنها این است که مجموعه کلیدهای مرتب شده را بین برگها تقسیم کنند.

از نظر فیزیکی، گره ها بلوک های حافظه با طول از پیش تعیین شده هستند. اندازه آنها مضربی از اندازه صفحات حافظه در سیستم عامل است که در بالا در مورد آن صحبت کردیم. ساختار گره در زیر نشان داده شده است. هدر حاوی متا اطلاعات است که واضح ترین آنها، برای مثال، چک جمع است. در مرحله بعدی اطلاعات مربوط به افست ها آمده است، که سلول های دارای داده در امتداد آنها قرار دارند. نقش داده‌ها می‌تواند کلید باشد، اگر در مورد گره‌های ناوبری صحبت می‌کنیم، یا کل جفت کلید-مقدار در مورد برگ‌ها. می‌توانید در مورد ساختار صفحات در کار بیشتر بخوانید "ارزیابی فروشگاه های کلیدی-ارزش با کارایی بالا".

پس از پرداختن به محتوای داخلی گره های صفحه، درخت LMDB B را به شکلی ساده به شکل زیر نشان خواهیم داد.

صفحات دارای گره به صورت متوالی بر روی دیسک مرتب می شوند. صفحات با تعداد بیشتر در انتهای فایل قرار دارند. به اصطلاح صفحه متا (صفحه متا) حاوی اطلاعاتی در مورد افست است که می توان از آن برای یافتن ریشه همه درختان استفاده کرد. هنگامی که یک فایل باز می شود، LMDB فایل را صفحه به صفحه از انتها به ابتدا در جستجوی یک متا صفحه معتبر اسکن می کند و پایگاه داده های موجود را از طریق آن پیدا می کند.

حال با داشتن ایده ای از ساختار منطقی و فیزیکی سازماندهی داده ها، می توانیم نهنگ سوم LMDB را در نظر بگیریم. با کمک آن است که تمام تغییرات ذخیره سازی به صورت تراکنشی و جدا از یکدیگر رخ می دهد و به پایگاه داده به عنوان یک کل ویژگی چند نسخه ای را نیز می دهد.

3.3. نهنگ شماره 3. کپی روی نوشتن

برخی از عملیات B-tree شامل ایجاد یک سری تغییرات در گره های آن است. یک مثال اضافه کردن یک کلید جدید به گره ای است که قبلاً به حداکثر ظرفیت خود رسیده است. در این صورت لازم است اولاً گره به دو قسمت تقسیم شود و ثانیاً پیوندی به گره فرزند اسپون آف جدید در والد آن اضافه شود. این روش به طور بالقوه بسیار خطرناک است. اگر به دلایلی (خراش، قطع برق و غیره) تنها بخشی از تغییرات سری اتفاق بیفتد، درخت در حالت ناسازگار باقی می ماند.

یکی از راه حل های سنتی برای ایجاد یک پایگاه داده مقاوم در برابر خطا، اضافه کردن یک ساختار داده مبتنی بر دیسک اضافی، گزارش تراکنش، که به عنوان ثبت پیش از نوشتن (WAL) نیز شناخته می شود، در کنار درخت B است. این فایلی است که در انتهای آن، دقیقاً قبل از اصلاح خود درخت B، عملیات مورد نظر نوشته شده است. بنابراین، اگر خرابی داده ها در حین تشخیص خود تشخیص داده شود، پایگاه داده برای پاکسازی خود با گزارش مشورت می کند.

LMDB روش متفاوتی را به عنوان مکانیزم تحمل خطا انتخاب کرده است که به آن کپی در نوشتن می گویند. ماهیت آن این است که به جای به روز رسانی داده ها در یک صفحه موجود، ابتدا آن را به طور کامل کپی می کند و تمام تغییرات را از قبل در نسخه انجام می دهد.

علاوه بر این، برای اینکه داده های به روز شده در دسترس باشند، لازم است پیوند را به گره ای که در گره والد در رابطه با آن به روز شده است تغییر دهید. از آنجایی که برای این کار نیز باید اصلاح شود، از قبل کپی شده است. این فرآیند به صورت بازگشتی تا ریشه ادامه می یابد. داده های صفحه متا آخرین موردی است که تغییر می کند

اگر به طور ناگهانی فرآیند در حین به روز رسانی از کار بیفتد، در این صورت یا یک متا صفحه جدید ایجاد نمی شود و یا تا انتها روی دیسک نوشته نمی شود و چک جمع آن نادرست است. در هر یک از این دو حالت، صفحات جدید غیر قابل دسترس بوده و صفحات قدیمی تحت تاثیر قرار نمی گیرند. این امر نیاز LMDB را برای نوشتن گزارش پیش رو برای حفظ ثبات داده ها از بین می برد. در واقع، ساختار ذخیره سازی داده ها روی دیسک، که در بالا توضیح داده شد، به طور همزمان عملکرد خود را بر عهده می گیرد. عدم وجود گزارش تراکنش صریح یکی از ویژگی های LMDB است که سرعت خواندن اطلاعات بالایی را فراهم می کند.

ساختار به‌دست‌آمده، به نام درخت B-فقط، به طور طبیعی جداسازی تراکنش و چند نسخه‌سازی را فراهم می‌کند. در LMDB، هر تراکنش باز دارای یک ریشه درختی به روز مرتبط با آن است. تا زمانی که تراکنش کامل نشده باشد، صفحات درخت مرتبط با آن هرگز تغییر نخواهند کرد یا برای نسخه‌های جدید داده‌ها استفاده مجدد نخواهند شد. زمانی که تراکنش باز شد، حتی اگر ذخیره سازی همچنان فعالانه به روز شود. این ماهیت چند نسخه ای است و LMDB را به یک منبع داده ایده آل برای عزیزانمان تبدیل می کند UICollectionView. پس از باز کردن یک تراکنش، نیازی به افزایش ردپای حافظه برنامه ندارید، و عجولانه داده های فعلی را به داخل برخی از ساختارهای حافظه پمپ می کنید، از ترس اینکه چیزی باقی بمانید. این ویژگی LMDB را از همان SQLite متمایز می کند، که نمی تواند از چنین انزوا کاملی ببالد. با بازکردن دو تراکنش در تراکنش های اخیر و حذف یک رکورد خاص در یکی از آنها، دیگر نمی توان همان رکورد را در دومین تراکنش باقی مانده به دست آورد.

روی دیگر سکه مصرف بالقوه قابل توجهی بالاتر از حافظه مجازی است. این اسلاید نشان می دهد که اگر ساختار پایگاه داده به طور همزمان با 3 تراکنش خواندن باز که به نسخه های مختلف پایگاه داده نگاه می کنند، اصلاح شود، چگونه خواهد بود. از آنجایی که LMDB نمی‌تواند از گره‌هایی که از ریشه‌های مرتبط با تراکنش‌های واقعی قابل دسترسی هستند استفاده مجدد کند، ذخیره‌سازی چاره‌ای ندارد جز اینکه ریشه چهارم دیگری را در حافظه تخصیص دهد و یک بار دیگر صفحات تغییر یافته را در زیر آن شبیه‌سازی کند.

در اینجا فراخوانی بخش فایل های دارای نقشه حافظه اضافی نخواهد بود. به نظر می رسد مصرف اضافی حافظه مجازی نباید زیاد ما را آزار دهد، زیرا به ردپای حافظه اپلیکیشن کمکی نمی کند. اما در عین حال به این نکته اشاره شد که iOS در تخصیص آن بسیار خسیس است و نمی توانیم یک منطقه LMDB 1 ترابایتی را روی سرور یا دسکتاپ از روی شانه استاد تهیه کنیم و اصلاً به این ویژگی فکر نکنیم. در صورت امکان، باید سعی کنید طول عمر تراکنش ها را تا حد امکان کوتاه نگه دارید.

4. طراحی یک طرح داده در بالای API کلید-مقدار

بیایید تجزیه API را با نگاهی به انتزاعات اساسی ارائه شده توسط LMDB آغاز کنیم: محیط و پایگاه داده، کلیدها و مقادیر، تراکنش ها و مکان نماها.

یادداشتی در مورد لیست کدها

همه توابع در API عمومی LMDB نتیجه کار خود را به شکل یک کد خطا برمی‌گردانند، اما در همه لیست‌های بعدی، بررسی آن به خاطر مختصر بودن حذف می‌شود. در عمل، ما از کد خودمان برای تعامل با مخزن استفاده می‌کنیم. چنگال بسته بندی های C++ lmdbxx، که در آن خطاها به عنوان استثناهای C++ ظاهر می شوند.

به عنوان سریعترین راه برای اتصال LMDB به پروژه iOS یا macOS، من CocoaPod خود را پیشنهاد می کنم POSLMDB.

4.1. انتزاعات اساسی

محیط

ساختار MDB_env is مخزن وضعیت داخلی LMDB است. خانواده توابع پیشوندی mdb_env به شما اجازه می دهد تا برخی از ویژگی های آن را پیکربندی کنید. در ساده ترین حالت، مقداردهی اولیه موتور به این صورت است.

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، مقادیر پیش فرض را تنها برای دو پارامتر تغییر دادیم.

اولین مورد اندازه فضای آدرس مجازی است که فایل ذخیره سازی به آن نگاشت شده است. متأسفانه، حتی در یک دستگاه، مقدار خاص می تواند به طور قابل توجهی از اجرا به اجرا متفاوت باشد. برای در نظر گرفتن این ویژگی iOS، حداکثر میزان فضای ذخیره سازی را به صورت پویا انتخاب می کنیم. با شروع از یک مقدار مشخص، به طور متوالی نصف می شود تا تابع mdb_env_open نتیجه ای غیر از ENOMEM. در تئوری، یک راه مخالف وجود دارد - ابتدا حداقل حافظه را به موتور اختصاص دهید، و سپس، زمانی که خطا دریافت می شود. MDB_MAP_FULL، آن را افزایش دهید. با این حال، بسیار خاردارتر است. دلیل آن این است که روش نقشه برداری مجدد حافظه با استفاده از تابع mdb_env_set_map_size تمام موجودیت ها (مکان نما، تراکنش ها، کلیدها و مقادیر) دریافت شده از موتور را باطل می کند. در نظر گرفتن چنین چرخشی از رویدادها در کد منجر به پیچیدگی قابل توجه آن می شود. اگر، با این وجود، حافظه مجازی برای شما بسیار عزیز است، پس این ممکن است دلیلی باشد برای نگاه کردن به چنگالی که بسیار جلوتر رفته است. MDBX، جایی که در میان ویژگی های اعلام شده "تنظیم خودکار اندازه پایگاه داده در حین پرواز" وجود دارد.

پارامتر دوم که مقدار پیش فرض آن برای ما مناسب نیست، مکانیک اطمینان از ایمنی نخ را تنظیم می کند. متأسفانه، حداقل در iOS 10، مشکلاتی در زمینه پشتیبانی از حافظه محلی Thread وجود دارد. به همین دلیل، در مثال بالا، مخزن با پرچم باز می شود MDB_NOTLS. علاوه بر این، آن را نیز مورد نیاز است چنگال لفاف C++ lmdbxxبرای برش متغیرها با و در این ویژگی.

پایگاه های داده

پایگاه داده یک نمونه جداگانه از درخت B است که در بالا در مورد آن صحبت کردیم. باز شدن آن در داخل یک تراکنش رخ می دهد که در ابتدا ممکن است کمی عجیب به نظر برسد.

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

در واقع، تراکنش در LMDB یک موجودیت ذخیره سازی است، نه یک پایگاه داده خاص. این مفهوم به شما اجازه می دهد تا عملیات اتمی را بر روی موجودیت های واقع در پایگاه های داده مختلف انجام دهید. در تئوری، این امکان مدل سازی جداول در قالب پایگاه داده های مختلف را باز می کند، اما در یک زمان من به سمت دیگری رفتم که در زیر به تفصیل شرح داده شده است.

کلیدها و مقادیر

ساختار MDB_val مفهوم کلید و مقدار را مدل می کند. مخزن هیچ ایده ای در مورد معنایی آنها ندارد. برای او، چیزی که متفاوت است فقط آرایه ای از بایت ها با اندازه معین است. حداکثر اندازه کلید 512 بایت است.

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

فروشگاه از یک مقایسه کننده برای مرتب کردن کلیدها به ترتیب صعودی استفاده می کند. اگر آن را با خود جایگزین نکنید، از پیش فرض استفاده می شود که آنها را بایت به بایت به ترتیب واژگانی مرتب می کند.

معاملات

دستگاه تراکنش به تفصیل در شرح داده شده است فصل قبل، بنابراین در اینجا ویژگی های اصلی آنها را در یک خط کوتاه تکرار می کنم:

1. پشتیبانی از تمام ویژگی های اساسی ACIDکلمات کلیدی: اتمی، قوام، انزوا و قابلیت اطمینان. نمی توانم توجه نکنم که از نظر دوام در macOS و iOS یک باگ در MDBX برطرف شده است. شما می توانید در آنها بیشتر بخوانید README.
2. رویکرد چند رشته ای با طرح "نویسنده تک / چند خوان" توصیف شده است. نویسندگان یکدیگر را مسدود می کنند، اما خوانندگان را مسدود نمی کنند. خوانندگان نویسندگان یا یکدیگر را مسدود نمی کنند.
3. پشتیبانی از تراکنش های تو در تو
4. پشتیبانی از چند نسخه

Multiversioning در LMDB آنقدر خوب است که می خواهم آن را در عمل نشان دهم. کد زیر نشان می‌دهد که هر تراکنش دقیقاً با نسخه‌ای از پایگاه داده که در زمان باز شدن مربوطه بود کار می‌کند و کاملاً از همه تغییرات بعدی جدا است. راه‌اندازی مخزن و افزودن رکورد آزمایشی به آن هیچ علاقه‌ای ندارد، بنابراین این آیین‌ها در زیر اسپویلر باقی می‌مانند.

افزودن ورودی آزمون

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

به صورت اختیاری، توصیه می‌کنم همین ترفند را با SQLite امتحان کنید و ببینید چه اتفاقی می‌افتد.

Multiversioning مزایای بسیار خوبی برای زندگی یک توسعه دهنده iOS به ارمغان می آورد. با استفاده از این ویژگی، می توانید به راحتی و به طور طبیعی نرخ به روز رسانی منبع داده را برای فرم های صفحه بر اساس ملاحظات تجربه کاربر تنظیم کنید. به عنوان مثال، اجازه دهید چنین ویژگی برنامه Mail.ru Cloud را به عنوان بارگیری خودکار محتوا از گالری رسانه سیستم در نظر بگیریم. با یک اتصال خوب، کلاینت قادر است چندین عکس در ثانیه به سرور اضافه کند. اگر بعد از هر بار دانلود آپدیت کنید UICollectionView با محتوای رسانه ای در فضای ابری کاربر، می توانید 60 فریم در ثانیه و اسکرول نرم را در طول این فرآیند فراموش کنید. برای جلوگیری از به‌روزرسانی‌های مکرر صفحه، باید به نحوی سرعت تغییر داده‌ها را در پایه محدود کنید UICollectionViewDataSource.

اگر پایگاه داده از چند نسخه پشتیبانی نمی کند و به شما امکان می دهد فقط با وضعیت فعلی کار کنید، برای ایجاد یک عکس فوری داده با ثبات زمان، باید آن را در ساختار داده های درون حافظه یا در یک جدول موقت کپی کنید. هر یک از این رویکردها بسیار گران است. در مورد ذخیره سازی در حافظه، هم هزینه های حافظه ناشی از ذخیره سازی اشیاء ساخته شده و هم هزینه های زمانی مرتبط با تبدیل های اضافی ORM را دریافت می کنیم. در مورد میز موقت ، این لذت حتی گران تر است که فقط در موارد غیر پیش پا افتاده منطقی است.

Multiversioning LMDB مشکل حفظ یک منبع داده پایدار را به روشی بسیار زیبا حل می کند. فقط کافی است یک تراکنش و voila را باز کنیم - تا زمانی که آن را کامل نکنیم، مجموعه داده ها تضمین می شود که ثابت شوند. منطق نرخ به روز رسانی آن اکنون کاملاً در دست لایه ارائه است، بدون سربار منابع قابل توجه.

نشانگرها

مکان نماها مکانیزمی را برای تکرار منظم روی جفت های کلید-مقدار با عبور از یک درخت B ارائه می دهند. بدون آنها، مدل سازی موثر جداول در پایگاه داده غیرممکن خواهد بود، که اکنون به آن می پردازیم.

4.2. مدل سازی جدول

ویژگی key ordering به شما امکان می دهد یک انتزاع سطح بالا مانند یک جدول در بالای انتزاعات اولیه بسازید. بیایید این فرآیند را در مثال جدول اصلی کلاینت ابری در نظر بگیریم، که در آن اطلاعات مربوط به تمام فایل‌ها و پوشه‌های کاربر در حافظه پنهان ذخیره می‌شود.

طرح واره جدول

یکی از سناریوهای متداول که برای آن ساختار جدول با درخت پوشه باید تیزتر شود، انتخاب تمام عناصر واقع در یک فهرست مشخص است.یک مدل سازماندهی داده خوب برای پرس و جوهای کارآمد از این نوع است. لیست همجواری. برای پیاده‌سازی آن در بالای ذخیره‌سازی کلید-مقدار، لازم است کلیدهای فایل‌ها و پوشه‌ها را به گونه‌ای مرتب کنیم که بر اساس تعلق به دایرکتوری والد گروه‌بندی شوند. علاوه بر این، برای نمایش محتویات دایرکتوری به شکل آشنا برای یک کاربر ویندوز (اول پوشه ها، سپس فایل ها، هر دو بر اساس حروف الفبا مرتب شده اند)، لازم است که فیلدهای اضافی مربوطه را در کلید قرار دهید.

تصویر زیر نشان می دهد که بر اساس وظیفه، نمایش کلیدها به صورت آرایه ای از بایت ها چگونه ممکن است به نظر برسد. ابتدا بایت ها با شناسه دایرکتوری والد (قرمز) و سپس با نوع (سبز) و از قبل با نام (آبی) در انتهای آن قرار می گیرند. راه مورد نیاز پیمایش متوالی کلیدها با همان پیشوند قرمز، مقادیر مرتبط با آنها را به ترتیبی که باید در رابط کاربری نمایش داده شوند (سمت راست)، بدون نیاز به هیچ گونه پس پردازش اضافی، به ما می دهد.

سریال سازی کلیدها و مقادیر

روش های زیادی برای سریال سازی اشیا در سراسر جهان وجود دارد. از آنجایی که ما هیچ نیاز دیگری به جز سرعت نداشتیم، سریع‌ترین مورد ممکن را برای خود انتخاب کردیم - یک حافظه خالی که توسط نمونه‌ای از ساختار زبان C اشغال می‌شود. بنابراین، کلید یک عنصر دایرکتوری را می‌توان با ساختار زیر مدل‌سازی کرد. NodeKey.

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

نجات دادن NodeKey در ذخیره سازی نیاز در شی MDB_val اشاره گر به داده ها را در آدرس ابتدای ساختار قرار دهید و اندازه آنها را با تابع محاسبه کنید sizeof.

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

در فصل اول در مورد معیارهای انتخاب پایگاه داده، به حداقل رساندن تخصیص پویا به عنوان بخشی از عملیات CRUD به عنوان یک عامل مهم انتخاب اشاره کردم. کد تابع serialize نشان می دهد که چگونه، در مورد LMDB، زمانی که رکوردهای جدید در پایگاه داده درج می شوند، می توان به طور کامل از آنها اجتناب کرد. آرایه بایت های دریافتی از سرور ابتدا به ساختارهای پشته ای تبدیل می شوند و سپس به طور پیش پا افتاده به فضای ذخیره سازی ریخته می شوند. با توجه به اینکه هیچ تخصیص دینامیکی در داخل LMDB وجود ندارد، می‌توانید با استانداردهای iOS وضعیت فوق‌العاده‌ای داشته باشید - فقط از حافظه پشته برای کار با داده‌ها از شبکه تا دیسک استفاده کنید!

ترتیب کلیدها با مقایسه کننده باینری

رابطه ترتیب کلید توسط یک تابع خاص به نام مقایسه کننده داده می شود. از آنجایی که موتور چیزی در مورد معنای بایت های موجود در آنها نمی داند، مقایسه کننده پیش فرض چاره ای ندارد جز اینکه کلیدها را به ترتیب واژگانی ترتیب دهد و به مقایسه بایت به بایت آنها متوسل شود. استفاده از آن برای چیدمان سازه ها شبیه تراشیدن با تبر حکاکی است. هرچند در موارد ساده این روش را قابل قبول می دانم. جایگزین در زیر توضیح داده شده است، اما در اینجا به چند چنگک پراکنده در طول راه اشاره می کنم.

اولین چیزی که باید در نظر داشت، نمایش حافظه انواع داده های اولیه است. بنابراین، در تمام دستگاه های اپل، متغیرهای عدد صحیح در قالب ذخیره می شوند اندیان کوچک. این بدان معنی است که کمترین بایت در سمت چپ خواهد بود و شما نمی توانید اعداد صحیح را با استفاده از مقایسه بایت به بایت آنها مرتب کنید. برای مثال، تلاش برای انجام این کار با مجموعه ای از اعداد از 0 تا 511 به نتیجه زیر می رسد.

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

برای حل این مشکل، اعداد صحیح باید با فرمت مناسب برای مقایسه کننده بایت در کلید ذخیره شوند. کارکردهای خانواده به انجام تحول لازم کمک می کند. hton* (به خصوص htons برای اعداد دو بایتی از مثال).

همانطور که می دانید فرمت نمایش رشته ها در برنامه نویسی یک کل است история. اگر معنای رشته ها، و همچنین رمزگذاری مورد استفاده برای نشان دادن آنها در حافظه، نشان می دهد که ممکن است بیش از یک بایت در هر کاراکتر وجود داشته باشد، بهتر است بلافاصله ایده استفاده از یک مقایسه کننده پیش فرض را کنار بگذارید.

دومین چیزی که باید در نظر داشت این است اصول هم ترازی کامپایلر فیلد ساختار به دلیل آنها، بایت هایی با مقادیر زباله را می توان در حافظه بین فیلدها تشکیل داد، که البته مرتب سازی بایت را قطع می کند. برای حذف زباله، یا باید فیلدها را به ترتیبی کاملاً تعریف شده، با در نظر گرفتن قوانین تراز کردن، اعلام کنید یا از ویژگی در اعلان ساختار استفاده کنید. packed.

سفارش کلید توسط مقایسه کننده خارجی

منطق مقایسه کلیدی ممکن است برای یک مقایسه کننده باینری بسیار پیچیده باشد. یکی از دلایل متعدد وجود زمینه های فنی در داخل سازه ها است. من وقوع آنها را در مثالی از کلیدی که قبلاً برای یک عنصر دایرکتوری برای ما آشنا بود، توضیح خواهم داد.

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

با همه سادگی اش، در اکثر موارد حافظه زیادی مصرف می کند. بافر عنوان 256 بایت است، اگرچه به طور متوسط ​​نام فایل ها و پوشه ها به ندرت بیشتر از 20-30 کاراکتر است.

یکی از تکنیک های استاندارد برای بهینه سازی اندازه یک رکورد، برش دادن آن به اندازه واقعی آن است. ماهیت آن این است که محتویات تمام فیلدهای با طول متغیر در یک بافر در انتهای ساختار و طول آنها در متغیرهای جداگانه ذخیره می شود. مطابق با این رویکرد، کلید NodeKey به شکل زیر تبدیل می شود.

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

علاوه بر این، در طول سریال سازی، به عنوان اندازه داده مشخص نشده است sizeof کل ساختار، و اندازه تمام فیلدها طول ثابت به اضافه اندازه بخش واقعی استفاده شده از بافر است.

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

در نتیجه بازسازی، صرفه جویی قابل توجهی در فضای اشغال شده توسط کلیدها داشتیم. اما با توجه به زمینه فنی nameLength، مقایسه کننده باینری پیش فرض دیگر برای مقایسه کلید مناسب نیست. اگر آن را با نام خود جایگزین نکنیم، طول نام نسبت به خود نام، عامل اولویت بیشتری در مرتب سازی خواهد بود.

LMDB به هر پایگاه داده اجازه می دهد تا عملکرد مقایسه کلید خود را داشته باشد. این کار با استفاده از تابع انجام می شود mdb_set_compare به شدت قبل از باز کردن به دلایل واضح، پایگاه داده را نمی توان در طول عمر خود تغییر داد. در ورودی، مقایسه کننده دو کلید را با فرمت باینری دریافت می کند و در خروجی نتیجه مقایسه را برمی گرداند: کمتر از (-1)، بزرگتر از (1) یا مساوی (0). شبه کد برای NodeKey به نظر می رسد که

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

تا زمانی که همه کلیدها در پایگاه داده از یک نوع هستند، قانونی است که نمایش بایت آنها را بدون قید و شرط به نوع ساختار کاربردی کلید داده شود. در اینجا یک تفاوت وجود دارد، اما کمی پایین تر در زیر بخش "Reading Records" مورد بحث قرار خواهد گرفت.

سریال سازی ارزش

با کلیدهای رکوردهای ذخیره شده، LMDB بسیار فشرده کار می کند. آنها در چارچوب هر عملیات کاربردی با یکدیگر مقایسه می شوند و عملکرد کل راه حل به سرعت مقایسه کننده بستگی دارد. در یک دنیای ایده‌آل، مقایسه‌کننده باینری پیش‌فرض باید برای مقایسه کلیدها کافی باشد، اما اگر واقعاً مجبور بودید از کلیدهای خود استفاده کنید، پس روال غیر سریال‌سازی کلیدها در آن باید تا حد امکان سریع باشد.

پایگاه داده علاقه خاصی به بخش Value از رکورد (مقدار) ندارد. تبدیل آن از نمایش بایت به یک شی تنها زمانی اتفاق می افتد که کد برنامه از قبل به آن نیاز داشته باشد، به عنوان مثال، آن را روی صفحه نمایش دهد. از آنجایی که این اتفاق نسبتاً به ندرت رخ می دهد، الزامات سرعت این رویه چندان حیاتی نیست، و در اجرای آن ما بسیار آزادتر هستیم که روی راحتی تمرکز کنیم. به عنوان مثال، برای سریال سازی ابرداده در مورد فایل هایی که هنوز دانلود نشده اند، از استفاده می کنیم. NSKeyedArchiver.

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

با این حال، مواقعی وجود دارد که عملکرد مهم است. به عنوان مثال، هنگام ذخیره اطلاعات متا در مورد ساختار فایل ابر کاربر، از همان dump حافظه شی استفاده می کنیم. نقطه برجسته وظیفه تولید نمایش سریالی آنها این واقعیت است که عناصر یک دایرکتوری توسط یک سلسله مراتب کلاس مدل می شوند.

برای اجرای آن در زبان C، فیلدهای خاص وراث در ساختارهای جداگانه بیرون می‌آیند و ارتباط آنها با پایه یک از طریق فیلدی از نوع اتحادیه مشخص می‌شود. محتوای واقعی اتحادیه از طریق ویژگی فنی نوع مشخص می شود.

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

افزودن و به روز رسانی سوابق

کلید سریال و مقدار را می توان به فروشگاه اضافه کرد. برای این کار از تابع استفاده می شود mdb_put.

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

در مرحله پیکربندی، مخزن می‌تواند اجازه یا ممنوعیت ذخیره چندین رکورد با یک کلید را داشته باشد. اگر تکثیر کلیدها ممنوع است، هنگام درج یک رکورد، می‌توانید تعیین کنید که آیا به‌روزرسانی رکورد موجود مجاز است یا خیر. اگر خرابی فقط در نتیجه یک خطا در کد رخ دهد، می توانید با مشخص کردن پرچم در برابر آن بیمه شوید. NOOVERWRITE.

خواندن سوابق

تابع خواندن رکوردها در LMDB است mdb_get. اگر جفت کلید-مقدار با ساختارهایی که قبلاً تخلیه شده اند نشان داده شود، این رویه به این شکل است.

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

فهرست ارائه‌شده نشان می‌دهد که چگونه سریال‌سازی از طریق روگرفت ساختارها به شما امکان می‌دهد نه تنها هنگام نوشتن، بلکه هنگام خواندن داده‌ها از شر تخصیص پویا خلاص شوید. برگرفته از تابع mdb_get اشاره گر دقیقا به آدرس حافظه مجازی نگاه می کند که در آن پایگاه داده نمایش بایتی شی را ذخیره می کند. در واقع، ما نوعی ORM را دریافت می کنیم که تقریباً رایگان است و سرعت بسیار بالایی در خواندن داده ها ارائه می دهد. با تمام زیبایی رویکرد، لازم است چندین ویژگی مرتبط با آن را به خاطر بسپارید.

1. برای یک تراکنش فقط خواندنی، یک اشاره گر به یک ساختار ارزش تضمین می شود که فقط تا زمانی که تراکنش بسته شود معتبر باقی می ماند. همانطور که قبلا ذکر شد، صفحات درخت B که شی در آن قرار دارد، به لطف اصل کپی در نوشتن، تا زمانی که حداقل یک تراکنش به آنها اشاره داشته باشد، بدون تغییر باقی می مانند. در عین حال، به محض تکمیل آخرین تراکنش مرتبط با آنها، می توان از صفحات برای داده های جدید مجددا استفاده کرد. اگر لازم است اشیا از معامله ای که آنها را ایجاد کرده است زنده بمانند، هنوز باید کپی شوند.
2. برای یک تراکنش خواندنی، اشاره گر به ساختار-مقدار حاصل فقط تا اولین رویه اصلاح (نوشتن یا حذف داده) معتبر خواهد بود.
3. حتی اگر ساختار NodeValue نه کامل، بلکه بریده شده (به بخش فرعی "سفارش کلیدها توسط مقایسه کننده خارجی" مراجعه کنید)، از طریق اشاره گر، می توانید به راحتی به فیلدهای آن دسترسی داشته باشید. نکته اصلی عدم ارجاع آن است!
4. به هیچ وجه نمی توانید ساختار را از طریق اشاره گر دریافتی تغییر دهید. تمام تغییرات باید فقط از طریق روش انجام شود mdb_put. با این حال، با تمام تمایل به انجام این کار، کار نخواهد کرد، زیرا منطقه حافظه که این ساختار در آن قرار دارد در حالت فقط خواندنی نقشه برداری شده است.
5. برای مثال، یک فایل را به فضای آدرس یک فرآیند مجدداً نقشه برداری کنید تا با استفاده از این تابع، حداکثر اندازه ذخیره سازی را افزایش دهید mdb_env_set_map_size تمام تراکنش ها و موجودیت های مرتبط به طور کلی و اشاره گرها برای خواندن اشیا به طور خاص کاملاً بی اعتبار می شود.

در نهایت، یک ویژگی دیگر آنقدر موذیانه است که افشای ماهیت آن تنها در یک نکته بیشتر نمی گنجد. در فصل درخت B، نموداری از سازماندهی صفحات آن در حافظه ارائه کردم. از آن نتیجه می شود که آدرس ابتدای بافر با داده های سریالی می تواند کاملاً دلخواه باشد. به این دلیل، اشاره گر به آنها، در ساختار به دست آمده است MDB_val و ریخته گری به یک اشاره گر به یک ساختار به طور کلی بدون تراز است. در عین حال، معماری برخی از تراشه ها (در مورد iOS، این armv7 است) ایجاب می کند که آدرس هر داده ای مضربی از اندازه یک کلمه ماشینی یا به عبارت دیگر بیتی بودن سیستم باشد. (برای armv7، این 32 بیت است). به عبارت دیگر، عملیاتی مانند *(int *foo)0x800002 بر آنها معادل فرار است و با حکم به اعدام می انجامد EXC_ARM_DA_ALIGN. دو راه برای جلوگیری از چنین سرنوشت غم انگیزی وجود دارد.

اولین مورد این است که داده ها را از قبل در یک ساختار تراز شده شناخته شده کپی کنید. به عنوان مثال، در یک مقایسه کننده سفارشی، این به صورت زیر منعکس می شود.

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

یک راه جایگزین این است که از قبل به کامپایلر اطلاع داده شود که ساختارهای دارای کلید و مقدار ممکن است با استفاده از یک ویژگی تراز نشوند. aligned(1). در ARM همین اثر می تواند باشد رسیدن و با استفاده از ویژگی packed. با توجه به اینکه به بهینه سازی فضای اشغال شده توسط سازه نیز کمک می کند، این روش به نظر من ارجح است، اگرچه приводит برای افزایش هزینه عملیات دسترسی به داده ها.

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

پرس و جوهای محدوده

برای تکرار بر روی یک گروه از رکوردها، LMDB یک انتزاع مکان نما را فراهم می کند. بیایید نحوه کار با آن را با استفاده از مثال جدولی با ابرداده ابری کاربر که قبلاً برای ما آشناست، بررسی کنیم.

به عنوان بخشی از نمایش فهرستی از فایل‌ها در یک فهرست، باید تمام کلیدهایی را که فایل‌ها و پوشه‌های فرزند با آن‌ها مرتبط هستند، پیدا کنید. در قسمت های فرعی قبلی، کلیدها را مرتب کردیم NodeKey به طوری که ابتدا با شناسه دایرکتوری والد خود مرتب می شوند. بنابراین، از نظر فنی، وظیفه به دست آوردن محتویات یک پوشه به قرار دادن مکان نما بر روی مرز بالایی یک گروه از کلیدها با یک پیشوند مشخص و به دنبال آن تکرار تا مرز پایین کاهش می یابد.

با جستجوی متوالی می توانید کران بالایی "روی پیشانی" را پیدا کنید. برای انجام این کار، مکان نما در ابتدای کل لیست کلیدهای پایگاه داده قرار می گیرد و سپس تا زمانی که کلید با شناسه دایرکتوری والد در زیر آن ظاهر شود، افزایش می یابد. این رویکرد 2 اشکال آشکار دارد:

1. پیچیدگی خطی جستجو، اگرچه همانطور که می دانید در درختان به طور کلی و در درخت B به طور خاص می توان آن را در زمان لگاریتمی انجام داد.
2. بیهوده، تمام صفحات قبل از صفحه مورد نظر از فایل به حافظه اصلی افزایش می یابد که بسیار گران است.

خوشبختانه LMDB API یک راه کارآمد برای قرار دادن مکان نما در ابتدا ارائه می دهد. برای این کار، باید کلیدی را تشکیل دهید که مقدار آن کمتر یا مساوی با کلید واقع در کران بالای بازه شناخته شده است. برای مثال در رابطه با لیست شکل بالا می توانیم کلیدی بسازیم که در آن فیلد parentId برابر 2 خواهد بود و بقیه با صفر پر می شوند. چنین کلید نیمه پر شده به ورودی تابع وارد می شود mdb_cursor_get نشان دهنده عملیات 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);

اگر کران بالای گروه کلیدها پیدا شد، روی آن تکرار می کنیم تا زمانی که با یکدیگر ملاقات کنیم یا کلید با دیگری parentId، یا کلیدها به هیچ وجه تمام نمی شوند

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​​

چه خوب است، به عنوان بخشی از تکرار با استفاده از mdb_cursor_get، ما نه تنها کلید، بلکه مقدار را نیز دریافت می کنیم. اگر برای انجام شرایط انتخاب، لازم است، از جمله موارد دیگر، فیلدها از قسمت مقدار رکورد بررسی شوند، در این صورت آنها کاملاً بدون حرکات اضافی برای خودشان قابل دسترسی هستند.

4.3. مدل سازی روابط بین جداول

ما تا به امروز موفق شده ایم تمامی جنبه های طراحی و کار با پایگاه داده تک جدولی را در نظر بگیریم. می توان گفت که جدول مجموعه ای از رکوردهای مرتب شده است که از جفت های کلید-مقدار از یک نوع تشکیل شده است. اگر یک کلید را به صورت مستطیل و مقدار مربوط به آن را به عنوان یک کادر نمایش دهید، یک نمودار بصری از پایگاه داده دریافت می کنید.

​

با این حال، در زندگی واقعی، به ندرت می توان با این مقدار کم خون گذر کرد. اغلب در یک پایگاه داده لازم است اولاً چندین جدول وجود داشته باشد و ثانیاً انتخاب ها در آنها به ترتیبی متفاوت از کلید اصلی انجام شود. این بخش آخر به مسائل ایجاد و پیوند آنها اختصاص دارد.

جداول فهرست

برنامه ابری دارای بخش "گالری" است. محتوای رسانه ای را از کل فضای ابری، مرتب شده بر اساس تاریخ، نمایش می دهد. برای اجرای بهینه چنین انتخابی، در کنار جدول اصلی، باید یکی دیگر با نوع جدیدی از کلیدها ایجاد کنید. آنها حاوی یک فیلد با تاریخ ایجاد فایل هستند که به عنوان معیار مرتب سازی اولیه عمل می کند. از آنجایی که کلیدهای جدید به همان داده‌هایی اشاره می‌کنند که کلیدهای جدول زیرین هستند، به آنها کلیدهای فهرست می‌گویند. در تصویر زیر با رنگ نارنجی مشخص شده اند.

به منظور جداسازی کلیدهای جداول مختلف از یکدیگر در یک پایگاه داده، یک فیلد فنی اضافی tableId به همه آنها اضافه شده است. با قرار دادن آن در بالاترین اولویت برای مرتب‌سازی، کلیدها را ابتدا بر اساس جداول، و از قبل در داخل جداول - طبق قوانین خودمان گروه‌بندی می‌کنیم.

کلید شاخص به همان داده‌ای اشاره دارد که کلید اصلی است. اجرای ساده این ویژگی با مرتبط کردن یک کپی از قسمت مقدار کلید اولیه، از چند نقطه به طور همزمان، کمتر از حد مطلوب است:

1. از نقطه نظر فضای اشغال شده، ابرداده می تواند بسیار غنی باشد.
2. از نقطه نظر عملکرد، از آنجایی که هنگام به روز رسانی ابرداده گره، باید دو کلید را بازنویسی کنید.
3. از نقطه نظر پشتیبانی از کد، پس از همه، اگر فراموش کنیم که داده ها را برای یکی از کلیدها به روز کنیم، با یک اشکال ظریف ناسازگاری داده ها در ذخیره سازی مواجه خواهیم شد.

در ادامه نحوه رفع این کاستی ها را بررسی خواهیم کرد.

سازماندهی روابط بین جداول

این الگو برای پیوند دادن جدول شاخص با جدول اصلی مناسب است "کلید به عنوان ارزش". همانطور که از نام آن پیداست، قسمت مقدار رکورد شاخص کپی مقدار کلید اولیه است. این رویکرد تمام معایب ذکر شده در بالا مربوط به ذخیره یک کپی از مقدار-بخش رکورد اولیه را حذف می کند. تنها هزینه این است که برای بدست آوردن مقدار توسط کلید شاخص، باید به جای یک پرس و جو، 2 پرس و جو در پایگاه داده ایجاد کنید. از نظر شماتیک، طرح پایگاه داده حاصل به شرح زیر است.

الگوی دیگر برای سازماندهی روابط بین جداول است "کلید اضافی". ماهیت آن افزودن ویژگی‌های اضافی به کلید است که نه برای مرتب‌سازی، بلکه برای ایجاد مجدد کلید مرتبط مورد نیاز است. با این حال، نمونه‌های واقعی استفاده از آن در برنامه Mail.ru Cloud وجود دارد تا از فرو رفتن عمیق در کلید جلوگیری شود. در زمینه چارچوب های خاص iOS، من یک مثال ساختگی، اما قابل درک تر ارائه خواهم داد.

کلاینت‌های Cloud Mobile صفحه‌ای دارند که تمام فایل‌ها و پوشه‌هایی را که کاربر با افراد دیگر به اشتراک گذاشته است، نمایش می‌دهد. از آنجایی که تعداد نسبتاً کمی از این قبیل فایل ها وجود دارد و اطلاعات خاص زیادی در مورد تبلیغات مرتبط با آنها وجود دارد (به چه کسانی دسترسی داده شده است، با چه حقوقی و غیره)، منطقی نیست که آن را با بخش ارزشی سنگین کنیم. ورودی در جدول اصلی با این حال، اگر می‌خواهید چنین فایل‌هایی را به‌صورت آفلاین نمایش دهید، همچنان باید آن‌ها را در جایی ذخیره کنید. یک راه حل طبیعی ایجاد یک جدول جداگانه برای آن است. در نمودار زیر، کلید آن با «P» پیشوند است و مکان‌نمای «propname» را می‌توان با مقدار مشخص‌تر «اطلاعات عمومی» جایگزین کرد.

تمام ابرداده‌های منحصربه‌فرد، که به خاطر آنها جدول جدید ایجاد شده است، به قسمت مقدار رکورد منتقل می‌شوند. در عین حال، نمی‌خواهم اطلاعات مربوط به فایل‌ها و پوشه‌هایی را که قبلاً در جدول اصلی ذخیره شده‌اند، کپی کنم. در عوض، داده‌های اضافی در قالب فیلدهای «شناسه گره» و «مهر زمانی» به کلید «P» اضافه می‌شوند. با تشکر از آنها، می توانید یک کلید شاخص بسازید، که توسط آن می توانید کلید اصلی را دریافت کنید، که در نهایت، می توانید متادیتای گره را دریافت کنید.

نتیجه

ما نتایج اجرای LMDB را مثبت ارزیابی می کنیم. پس از آن، تعداد فریز برنامه ها 30٪ کاهش یافت.

نتایج کار انجام شده پاسخی خارج از تیم iOS پیدا کرده است. در حال حاضر یکی از بخش های اصلی «Files» در اپلیکیشن اندروید نیز به استفاده از LMDB تغییر کاربری داده است و قسمت های دیگری نیز در راه است. زبان C، که در آن ذخیره‌سازی کلید-مقدار پیاده‌سازی می‌شود، کمک خوبی بود تا در ابتدا برنامه را به صورت کراس پلتفرم در زبان C ++ ایجاد کنیم. برای اتصال یکپارچه کتابخانه C ++ حاصل با کد پلت فرم در Objective-C و Kotlin، از یک تولید کننده کد استفاده شد. جنی از Dropbox، اما این داستان دیگری است.

منبع: www.habr.com