בסתיו 2019, אירוע המיוחל התרחש בצוות Mail.ru Cloud iOS. מסד הנתונים הראשי לאחסון מתמשך של מצב יישומים הפך אקזוטי מאוד עבור העולם הנייד מסד נתונים ממופה זיכרון ברק (LMDB). מתחת לגזרה אנו מציעים לכם סקירה מפורטת שלו בארבעה חלקים. ראשית, בואו נדבר על הסיבות לבחירה כל כך לא טריוויאלית וקשה. לאחר מכן נעבור לשקול את שלושת עמודי התווך שבלב ארכיטקטורת LMDB: קבצים ממופי זיכרון, B+-tree, גישת העתק-על-כתיבה להטמעת טרנזקציונליות וריבוי גרסאות. לסיום, לקינוח - החלק הפרקטי. בו נבחן כיצד לתכנן וליישם סכימת מסד נתונים עם מספר טבלאות, כולל אינדקס אחת, על גבי ה-API של מפתח-ערך ברמה נמוכה.

תוכן

1. מוטיבציה ליישום
2. מיצוב LMDB
3. שלושה עמודים של LMDB
   3.1. לוויתן מס' 1. קבצים ממופי זיכרון
   3.2. לוויתן מס' 2. B+-עץ
   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 אלף קבצים בענן, אז כדי לסנכרן אותו יש צורך ליצור מחדש ולהרוס שני עצים עם מיליון צמתים. אבל כל צומת הוא מצרף המכיל גרף של אובייקטי משנה. לאור זה, תוצאות הפרופיל היו צפויות. התברר שגם בלי לקחת בחשבון את אלגוריתם המיזוג, עצם הליך היצירה וההשמדה של מספר עצום של חפצים קטנים עולה אגורה לא קטנה.המצב מחמיר בשל העובדה שפעולת הסנכרון הבסיסית כלולה במספר רב. של סקריפטים של משתמשים. כתוצאה מכך, אנו מתקנים את הקריטריון החשוב השני בבחירת מסד נתונים - היכולת ליישם פעולות CRUD ללא הקצאה דינמית של אובייקטים.

דרישות אחרות מסורתיות יותר וכל הרשימה שלהן היא כדלקמן.

1. בטיחות חוטים.
2. ריבוי עיבודים. מוכתב על ידי הרצון להשתמש באותו מופע מסד נתונים כדי לסנכרן מצב לא רק בין שרשורים, אלא גם בין האפליקציה הראשית והרחבות iOS.
3. היכולת לייצג ישויות מאוחסנות כאובייקטים שאינם ניתנים לשינוי
4. אין הקצאות דינמיות בתוך פעולות CRUD.
5. תמיכה בעסקאות עבור נכסים בסיסיים ACID: אטומיות, עקביות, בידוד ואמינות.
6. מהירות על המקרים הפופולריים ביותר.

עם סט דרישות זה, SQLite הייתה ונשארה בחירה טובה. אולם, במסגרת מחקר החלופות, נתקלתי בספר "תחילת העבודה עם LevelDB". בהנהגתה, נכתב בנצ'מרק המשווה את מהירות העבודה עם מסדי נתונים שונים בתרחישי ענן אמיתיים. התוצאה עלתה על הציפיות הפרועות ביותר שלנו. במקרים הפופולריים ביותר - קבלת סמן על רשימה ממוינת של כל הקבצים ורשימה ממוינת של כל הקבצים עבור ספרייה נתונה - התברר כי LMDB מהיר פי 10 מ- SQLite. הבחירה הפכה ברורה.

2. מיצוב LMDB

LMDB היא ספרייה קטנה מאוד (רק 10K שורות) המיישמת את השכבה הבסיסית הנמוכה ביותר של מסדי נתונים - אחסון.

התרשים שלמעלה מראה שהשוואת LMDB עם SQLite, שגם מיישמת רמות גבוהות יותר, בדרך כלל אינה נכונה יותר מאשר SQLite עם Core Data. זה יהיה הוגן יותר לצטט את אותם מנועי אחסון כמתחרים שווים - BerkeleyDB, LevelDB, Sophia, RocksDB וכו'. ישנם אפילו פיתוחים שבהם LMDB פועל כרכיב מנוע אחסון עבור SQLite. הניסוי הראשון כזה היה ב-2012 נערך מאת LMDB הווארד צ'ו. ממצאים התברר כל כך מסקרן שיוזמתו נקלטה על ידי חובבי OSS, ומצאה את המשכה באדם LumoSQL. בינואר 2020, מחבר הפרויקט הזה היה Den Shearer הוצג זה ב- LinuxConfAu.

LMDB משמש בעיקר כמנוע לבסיסי נתונים של יישומים. הספרייה חייבת את המראה שלה למפתחים OpenLDAP, שהיו מאוד לא מרוצים מ-BerkeleyDB כבסיס לפרויקט שלהם. החל מספריה צנועה btree, הווארד צ'ו הצליח ליצור את אחת האלטרנטיבות הפופולריות ביותר של זמננו. הוא הקדיש את הדוח המגניב שלו לסיפור הזה, כמו גם למבנה הפנימי של LMDB. "מסד הנתונים הממופות בזיכרון ברק". דוגמה טובה לכיבוש מתקן אחסון הייתה משותפת לליאוניד יוריב (aka yleo) מ-Positive Technologies בדוח שלו ב-Highload 2015 "מנוע ה-LMDB הוא אלוף מיוחד". בו הוא מדבר על LMDB בהקשר של משימה דומה של יישום ReOpenLDAP, ו-LevelDB כבר היה נתון לביקורת השוואתית. כתוצאה מהיישום, ל-Positive Technologies אפילו היה מזלג בפיתוח פעיל MDBX עם תכונות טעימות מאוד, אופטימיזציות ו תיקוני באגים.

LMDB משמש לעתים קרובות כאחסון כפי שהוא. לדוגמה, דפדפן Mozilla Firefox בחר זה עבור מספר צרכים, והחל מגרסה 9, Xcode מועדף SQLite שלה לאחסון אינדקסים.

המנוע הטביע את חותמו גם בעולם פיתוח המובייל. עקבות השימוש בו יכולים להיות למצוא בלקוח iOS עבור טלגרם. לינקדאין הרחיקה לכת עוד יותר ובחרה ב-LMDB כאחסון ברירת המחדל עבור מסגרת מטמון הנתונים תוצרת הבית שלה Rocket Data, שעליה סיפר במאמרו ב-2016.

LMDB נלחמת בהצלחה על מקום בשמש בנישה שהשאירה BerkeleyDB לאחר שהגיעה לשליטתה של אורקל. הספרייה אהובה על המהירות והאמינות שלה, אפילו בהשוואה לעמיתיה. כידוע, אין ארוחות צהריים חינם, ואני רוצה להדגיש את הפשרה שתצטרכו להתמודד איתה בבחירה בין LMDB ל-SQLite. התרשים לעיל מדגים בבירור כיצד מושגת מהירות מוגברת. ראשית, אנחנו לא משלמים עבור שכבות נוספות של הפשטה על גבי אחסון הדיסק. ברור שארכיטקטורה טובה עדיין לא יכולה בלעדיהם, והם יופיעו בהכרח בקוד היישום, אבל הם יהיו הרבה יותר עדינים. הם לא יכילו תכונות שאינן נדרשות על ידי יישום ספציפי, למשל, תמיכה בשאילתות בשפת SQL. שנית, ניתן ליישם בצורה אופטימלית מיפוי של פעולות יישומים בבקשות לאחסון דיסק. אם SQLite בעבודתי מבוסס על הצרכים הסטטיסטיים הממוצעים של אפליקציה ממוצעת, אז אתה, כמפתח אפליקציות, מודע היטב לתרחישי עומס העבודה העיקריים. עבור פתרון פרודוקטיבי יותר, תצטרך לשלם תג מחיר מוגדל הן עבור פיתוח הפתרון הראשוני והן עבור התמיכה שלו לאחר מכן.

3. שלושה עמודים של למ.ד.ב

לאחר שהסתכלנו על ה-LMDB ממעוף הציפור, הגיע הזמן להעמיק. שלושת הסעיפים הבאים יוקדשו לניתוח העמודים העיקריים עליהם נשענת ארכיטקטורת האחסון:

1. קבצים ממופי זיכרון כמנגנון לעבודה עם דיסק וסנכרון מבני נתונים פנימיים.
2. B+-tree כארגון של מבנה הנתונים המאוחסנים.
3. העתק-על-כתיבה כגישה לספק מאפייני עסקאות ACID ו-multiversion.

3.1. לוויתן מס' 1. קבצים ממופי זיכרון

קבצים ממופי זיכרון הם אלמנט ארכיטקטוני חשוב עד כדי כך שהם אפילו מופיעים בשם המאגר. בעיות של שמירה במטמון וסנכרון של גישה למידע מאוחסן נותרות לחלוטין למערכת ההפעלה. LMDB אינו מכיל מטמונים בתוך עצמו. זוהי החלטה מודעת של המחבר, שכן קריאת נתונים ישירות מקבצים ממופים מאפשרת לך לחתוך הרבה פינות ביישום המנוע. להלן רשימה רחוקה מלהיות מלאה של כמה מהם.

1. שמירה על עקביות הנתונים באחסון כאשר עובדים איתו ממספר תהליכים הופכת לאחריות מערכת ההפעלה. בסעיף הבא, מכניקה זו נידונה בפירוט ועם תמונות.
2. היעדר מטמונים מבטל לחלוטין את LMDB מהתקורה הקשורה להקצאות דינמיות. קריאת נתונים בפועל פירושה הגדרת מצביע לכתובת הנכונה בזיכרון הוירטואלי ותו לא. זה נשמע כמו מדע בדיוני, אבל בקוד מקור האחסון כל הקריאות ל-calloc מתרכזות בפונקציית תצורת האחסון.
3. היעדר מטמונים פירושו גם היעדר מנעולים הקשורים לסנכרון הגישה שלהם. קוראים, שיכול להיות מספר שרירותי של קוראים בו-זמנית, לא נתקלים באף מוטקס בדרכם אל הנתונים. בשל כך, למהירות הקריאה יש מדרגיות ליניארית אידיאלית המבוססת על מספר המעבדים. ב-LMDB, רק פעולות שינוי מסונכרנות. יכול להיות רק כותב אחד בכל פעם.
4. מינימום של לוגיקה של מטמון וסנכרון מבטל את הסוג המורכב ביותר של שגיאות הקשורות לעבודה בסביבה מרובה הליכי. היו שני מחקרי מסד נתונים מעניינים בכנס Usenix OSDI 2014: "כל מערכות הקבצים אינן נוצרות שוות: על המורכבות של יצירת יישומים עקביים לקרוס" и "עינוי מאגרי מידע בשביל הכיף והרווח". מהם תוכלו ללקט מידע הן על האמינות חסרת התקדים של LMDB והן על ההטמעה הכמעט ללא רבב של מאפייני עסקאות ACID, שעדיפה על זו של SQLite.
5. המינימליזם של LMDB מאפשר לייצוג המכונה של הקוד שלו להיות ממוקם לחלוטין במטמון L1 של המעבד עם מאפייני המהירות הנובעים מכך.

לרוע המזל, ב-iOS, עם קבצים ממופים לזיכרון, הכל לא נטול עננים כמו שהיינו רוצים. כדי לדבר על החסרונות הקשורים אליהם בצורה מודעת יותר, יש צורך לזכור את העקרונות הכלליים של יישום מנגנון זה במערכות הפעלה.

מידע כללי על קבצים ממופי זיכרון

עם כל אפליקציה שפועלת, מערכת ההפעלה משייכת ישות הנקראת תהליך. לכל תהליך מוקצה מגוון רציף של כתובות בו הוא מציב את כל מה שצריך כדי לפעול. בכתובות הנמוכות ביותר יש קטעים עם קוד ונתונים ומשאבים מקודדים. לאחר מכן מגיע בלוק הולך וגדל של מרחב כתובות דינמי, המוכר לנו היטב תחת השם heap. הוא מכיל את הכתובות של ישויות המופיעות במהלך הפעלת התוכנית. בחלק העליון נמצא אזור הזיכרון המשמש את מחסנית האפליקציות. הוא גדל או מתכווץ; במילים אחרות, לגודלו יש גם אופי דינמי. כדי למנוע מהמחסנית והערימה לדחוף ולהפריע זה לזה, הם ממוקמים בקצוות שונים של מרחב הכתובות. יש חור בין שני החלקים הדינמיים בחלק העליון והתחתון. מערכת ההפעלה משתמשת בכתובות בחלק האמצעי הזה כדי לשייך מגוון של ישויות לתהליך. בפרט, הוא יכול לשייך קבוצה רציפה מסוימת של כתובות לקובץ בדיסק. קובץ כזה נקרא Memory-mapped.​

שטח הכתובות המוקצה לתהליך הוא עצום. תיאורטית, מספר הכתובות מוגבל רק על ידי גודל המצביע, אשר נקבע על ידי קיבולת הסיביות של המערכת. אם הזיכרון הפיזי היה ממופה אליו 1 ל-1, אז התהליך הראשון היה זולל את כל זיכרון ה-RAM, ולא היה דיבור על ריבוי משימות.

עם זאת, מניסיוננו אנו יודעים שמערכות הפעלה מודרניות יכולות לבצע בו זמנית כמה תהליכים שתרצה. זה אפשרי בשל העובדה שהם רק מקצים הרבה זיכרון לתהליכים על הנייר, אבל למעשה הם מעמיסים לזיכרון הפיזי הראשי רק את החלק המבוקש כאן ועכשיו. לכן, הזיכרון הקשור לתהליך נקרא וירטואלי.

מערכת ההפעלה מארגנת זיכרון וירטואלי ופיזי לדפים בגודל מסוים. ברגע שדף מסוים של זיכרון וירטואלי מבוקש, מערכת ההפעלה טוענת אותו לזיכרון הפיזי ומתאימה אותם בטבלה מיוחדת. אם אין חריצים פנויים, אחד מהדפים שנטענו קודם לכן מועתק לדיסק, והמבוקש תופס את מקומו. הליך זה, אליו נחזור עוד מעט, נקרא החלפה. האיור שלהלן ממחיש את התהליך המתואר. עליו נטען עמוד A עם כתובת 0 והוצב בדף הזיכרון הראשי עם כתובת 4. עובדה זו באה לידי ביטוי בטבלת ההתכתבויות בתא מספר 0.​

הסיפור זהה לחלוטין עם קבצים שמופו לזיכרון. באופן הגיוני, הם כביכול ממוקמים באופן רציף וכל כולו במרחב הכתובות הווירטואלי. עם זאת, הם נכנסים לזיכרון הפיזי עמוד אחר עמוד ורק לפי בקשה. שינוי של דפים כאלה מסונכרן עם הקובץ בדיסק. בדרך זו, ניתן לבצע קלט/פלט של קבצים פשוט על ידי עבודה עם בתים בזיכרון - כל השינויים יועברו אוטומטית על ידי ליבת מערכת ההפעלה לקובץ המקור.​
​
התמונה למטה מדגימה כיצד LMDB מסנכרן את מצבו בעת עבודה עם מסד הנתונים מתהליכים שונים. על ידי מיפוי הזיכרון הוירטואלי של תהליכים שונים לאותו קובץ, אנו מחייבים למעשה את מערכת ההפעלה לסנכרן באופן טרנזיטיבי בלוקים מסוימים של מרחבי הכתובות שלהם זה עם זה, היכן שמסתכלת LMDB.​
​

ניואנס חשוב הוא ש-LMDB, כברירת מחדל, משנה את קובץ הנתונים באמצעות מנגנון קריאת המערכת לכתיבה, ומציג את הקובץ עצמו במצב קריאה בלבד. לגישה זו שתי השלכות חשובות.

התוצאה הראשונה משותפת לכל מערכות ההפעלה. המהות שלו היא להוסיף הגנה מפני נזק לא מכוון למסד הנתונים על ידי קוד שגוי. כפי שאתה יודע, הוראות ההפעלה של תהליך חופשיות לגשת לנתונים מכל מקום במרחב הכתובות שלו. יחד עם זאת, כפי שרק זכרנו, הצגת קובץ במצב קריאה-כתיבה פירושה שכל הוראה יכולה גם לשנות אותו. אם היא עושה זאת בטעות, מנסה, למשל, למעשה להחליף אלמנט מערך באינדקס לא קיים, אז היא יכולה לשנות בטעות את הקובץ הממופה לכתובת זו, מה שיוביל לפגיעה במסד הנתונים. אם הקובץ מוצג במצב קריאה בלבד, אז ניסיון לשנות את מרחב הכתובות המתאים יוביל לסיום חירום של התוכנית עם אות SIGSEGV, והקובץ יישאר שלם.

התוצאה השנייה כבר ספציפית ל-iOS. לא המחבר ולא כל מקורות אחרים מזכירים את זה במפורש, אבל בלעדיו LMDB לא יתאים להפעלה על מערכת הפעלה ניידת זו. הסעיף הבא מוקדש לשיקולו.

פרטים ספציפיים של קבצים ממופי זיכרון ב-iOS

היה דיווח נפלא ב-WWDC ב-2018 "צלילה עמוקה בזיכרון iOS". זה אומר לנו שב-iOS, כל הדפים שנמצאים בזיכרון הפיזי הם אחד מ-3 סוגים: מלוכלך, דחוס ונקי.

זיכרון נקי הוא אוסף של דפים שניתן לפרוק ללא כאב מהזיכרון הפיזי. ניתן לטעון מחדש את הנתונים שהם מכילים לפי הצורך מהמקורות המקוריים שלו. קבצים ממופי זיכרון לקריאה בלבד נכנסים לקטגוריה זו. iOS לא חוששת לפרוק את הדפים הממופים לקובץ מהזיכרון בכל עת, מכיוון שהם מובטחים להיות מסונכרנים עם הקובץ בדיסק.
​
כל הדפים שהשתנו מגיעים בסופו של דבר לזיכרון מלוכלך, לא משנה היכן הם היו ממוקמים במקור. בפרט, קבצים ממופי זיכרון ששונו על ידי כתיבה לזיכרון הווירטואלי המשויך אליהם יסווגו בצורה זו. פתיחת LMDB עם דגל MDB_WRITEMAP, לאחר ביצוע שינויים בו, תוכל לאמת זאת באופן אישי.​

ברגע שאפליקציה מתחילה לתפוס יותר מדי זיכרון פיזי, iOS מעביר אותה לדחיסת דפים מלוכלכת. הזיכרון הכולל שנכבש על ידי דפים מלוכלכים ודחוסים מהווה את מה שמכונה טביעת הזיכרון של האפליקציה. ברגע שהוא מגיע לערך סף מסוים, הדמון של מערכת הרוצח OOM מגיע אחרי התהליך ומסיים אותו בכוח. זוהי המוזרות של iOS בהשוואה למערכות הפעלה שולחניות. לעומת זאת, צמצום טביעת הרגל של הזיכרון על ידי החלפת עמודים מזיכרון פיזי לדיסק אינו מסופק ב-iOS. ניתן רק לנחש את הסיבות. אולי ההליך של העברה אינטנסיבית של דפים לדיסק ובחזרה גוזל מדי אנרגיה עבור מכשירים ניידים, או ש-iOS חוסך את המשאב של שכתוב תאים על כונני SSD, או שאולי המעצבים לא היו מרוצים מהביצועים הכוללים של המערכת, שבה הכל נמצא מחליפים כל הזמן. כך או כך, העובדה נשארת עובדה.

החדשות הטובות, שכבר הוזכרו קודם לכן, הן ש-LMDB כברירת מחדל אינה משתמשת במנגנון mmap לעדכון קבצים. המשמעות היא שהנתונים המוצגים מסווגים על ידי iOS כזיכרון נקי ואינם תורמים לטביעת הרגל של הזיכרון. אתה יכול לאמת זאת באמצעות כלי Xcode בשם VM Tracker. צילום המסך למטה מציג את מצב הזיכרון הוירטואלי של iOS של אפליקציית הענן במהלך הפעולה. בהתחלה, 2 מופעי LMDB אותחלו בו. הראשון הורשה להציג את הקובץ שלו על 1GiB של זיכרון וירטואלי, השני - 512MiB. למרות העובדה ששני המאגרים תופסים כמות מסוימת של זיכרון תושב, אף אחד מהם לא תורם גודל מלוכלך.

ועכשיו הגיע הזמן לחדשות רעות. הודות למנגנון ההחלפה במערכות הפעלה שולחניות של 64 סיביות, כל תהליך יכול לתפוס שטח כתובות וירטואלי ככל שהשטח הפנוי בדיסק הקשיח להחלפה הפוטנציאלית שלו מאפשר. החלפת החלפה בדחיסה ב-iOS מפחיתה באופן קיצוני את המקסימום התיאורטי. כעת כל התהליכים החיים חייבים להשתלב בזיכרון הראשי (לקרוא RAM), וכל אלה שאינם מתאימים חייבים להיאלץ להסתיים. זה מצוין כמו באמור לעיל להגיש תלונה, ו ב תיעוד רשמי. כתוצאה מכך, iOS מגבילה מאוד את כמות הזיכרון הזמינה להקצאה באמצעות mmap. כאן כאן אתה יכול להסתכל על הגבולות האמפיריים של כמות הזיכרון שניתן להקצות למכשירים שונים באמצעות שיחת מערכת זו. בדגמי הסמארטפונים המודרניים ביותר, iOS הפכה לנדיבה ב-2 גיגה-בייט, ובגרסאות מובילות של האייפד - ב-4. בפועל, כמובן, צריך להתמקד בדגמי המכשירים הנתמכים הנמוכים ביותר, שם הכל עצוב מאוד. גרוע מכך, על ידי התבוננות במצב הזיכרון של האפליקציה ב-VM Tracker, תגלו ש-LMDB רחוקה מלהיות היחידה שטוענת שהיא ממופה זיכרון. נתחים טובים נאכלים על ידי מקצי מערכת, קבצי משאבים, מסגרות תמונה וטורפים קטנים אחרים.

בהתבסס על תוצאות ניסויים בענן, הגענו לערכי הפשרה הבאים עבור הזיכרון שהוקצה על ידי LMDB: 384 מגה בייט למכשירי 32 סיביות ו-768 עבור התקני 64 סיביות. לאחר שנפח זה מנוצל, כל פעולות השינוי מתחילות להסתיים בקוד MDB_MAP_FULL. אנו רואים טעויות כאלה במעקב שלנו, אבל הן קטנות מספיק כדי שבשלב זה ניתן להזניח אותן.

סיבה לא ברורה לצריכת זיכרון מוגזמת על ידי האחסון יכולה להיות עסקאות ארוכות חיים. כדי להבין כיצד שתי התופעות הללו קשורות, ניעזר בהתחשב בשני עמודי התווך הנותרים של LMDB.

3.2. לוויתן מס' 2. B+-עץ

כדי לחקות טבלאות על גבי אחסון ערך מפתח, הפעולות הבאות חייבות להיות נוכחות ב-API שלו:

1. הכנסת אלמנט חדש.
2. חפש אלמנט עם מפתח נתון.
3. הסרת אלמנט.
4. חזור על מרווחי מפתחות לפי סדר מיון.

מבנה הנתונים הפשוט ביותר שיכול ליישם בקלות את כל ארבע הפעולות הוא עץ חיפוש בינארי. כל אחד מהצמתים שלו מייצג מפתח המחלק את כל המשנה של מפתחות הצאצא לשני תתי עצים. השמאלי מכיל את אלה שקטנים מההורה, והימין מכיל את אלה שגדולים יותר. השגת ערכת מפתחות מסודרת מושגת באמצעות אחת ממעברי העצים הקלאסיים

לעצים בינאריים יש שני פגמים בסיסיים שמונעים מהם להיות יעילים כמבנה נתונים מבוסס דיסק. ראשית, מידת האיזון שלהם אינה ניתנת לחיזוי. קיים סיכון ניכר בהשגת עצים בהם גבהים של ענפים שונים יכולים להיות שונים מאוד, מה שמחמיר משמעותית את המורכבות האלגוריתמית של החיפוש לעומת הצפוי. שנית, שפע הקישורים הצולבים בין צמתים מונע מעצים בינאריים מקומיות בזיכרון, צמתים קרובים (מבחינת הקשרים ביניהם) יכולים להיות ממוקמים בדפים שונים לחלוטין בזיכרון הוירטואלי. כתוצאה מכך, אפילו מעבר פשוט של מספר צמתים סמוכים בעץ עשויה לדרוש ביקור במספר דומה של דפים. זו בעיה גם כשמדברים על האפקטיביות של עצים בינאריים כמבנה נתונים בזיכרון, שכן סיבוב מתמיד של דפים במטמון המעבד אינו תענוג זול. כאשר מדובר באחזור תכוף של דפים הקשורים לצמתים מהדיסק, המצב הופך לחלוטין מְצַעֵר.

עצי B, בהיותם אבולוציה של עצים בינאריים, פותרים את הבעיות שזוהו בפסקה הקודמת. ראשית, הם מאוזנים בעצמם. שנית, כל אחד מהצמתים שלהם מפצל את קבוצת מפתחות הצאצא לא ל-2, אלא לקבוצות משנה מסודרות, והמספר M יכול להיות גדול למדי, בסדר גודל של כמה מאות, או אפילו אלפים.

בְּכָך:

1. כל צומת מכיל מספר רב של מפתחות שכבר הוזמנו והעצים קצרים מאוד.
2. העץ רוכש את המאפיין של מיקום המיקום בזיכרון, מכיוון שמפתחות קרובים בערכם ממוקמים באופן טבעי זה ליד זה באותם צמתים או צמתים שכנים.
3. מספר צמתי המעבר בעת ירידה מעץ במהלך פעולת חיפוש מצטמצם.
4. מספר צמתי היעד הנקראים במהלך שאילתות טווח מצטמצם, מכיוון שכל אחד מהם כבר מכיל מספר רב של מפתחות מסודרים.

LMDB משתמש בווריאציה של עץ B המכונה עץ B+ כדי לאחסן נתונים. התרשים שלמעלה מציג את שלושת סוגי הצמתים הקיימים בו:

1. בחלק העליון נמצא השורש. זה מממש לא יותר מאשר הרעיון של מסד נתונים בתוך מחסן. בתוך מופע LMDB אחד, אתה יכול ליצור מספר מסדי נתונים שחולקים מרחב כתובות וירטואלי ממופה. כל אחד מהם מתחיל מהשורש שלו.
2. ברמה הנמוכה ביותר נמצאים העלים. הם ורק הם מכילים את צמדי המפתח-ערך המאוחסנים במסד הנתונים. אגב, זו המוזרות של עצי B+. אם עץ B רגיל מאחסן חלקי ערך בצמתים בכל הרמות, אזי הווריאציה B+ נמצאת רק בנמוכה ביותר. לאחר שתיקנו עובדה זו, עוד נקרא לתת-הסוג של העץ המשמש ב-LMDB פשוט B-עץ.
3. בין השורש והעלים יש 0 רמות טכניות או יותר עם צמתי ניווט (ענף). המשימה שלהם היא לחלק את סט המפתחות הממוין בין העלים.

מבחינה פיזית, צמתים הם גושי זיכרון באורך קבוע מראש. הגודל שלהם הוא כפול מגודלם של דפי זיכרון במערכת ההפעלה, שעליה דנו למעלה. מבנה הצומת מוצג להלן. הכותרת מכילה מטא מידע, שהברור שבהם הוא למשל ה-checksum. לאחר מכן מגיע מידע על ההיסטים שבהם נמצאים התאים עם הנתונים. הנתונים יכולים להיות מפתחות, אם אנחנו מדברים על צמתי ניווט, או צמדי מפתח-ערך שלמים במקרה של עלים.​ תוכל לקרוא עוד על מבנה הדפים בעבודה "הערכה של חנויות מפתח-ערך עם ביצועים גבוהים".

לאחר שעסקנו בתוכן הפנימי של צמתי עמודים, נציג עוד יותר את עץ B-LMDB בצורה פשוטה בטופס הבא.

דפים עם צמתים ממוקמים ברצף בדיסק. עמודים בעלי מספר גבוה יותר ממוקמים לקראת סוף הקובץ. מה שנקרא מטא דף מכיל מידע על הקיזוזים שבאמצעותם ניתן למצוא את השורשים של כל העצים. בעת פתיחת קובץ, LMDB סורקת את הקובץ עמוד אחר עמוד מקצה להתחלה בחיפוש אחר מטא עמוד חוקי ודרכו מוצאת מסדי נתונים קיימים.

כעת, לאחר שיש לנו מושג על המבנה ההגיוני והפיזי של ארגון הנתונים, אנו יכולים לעבור לשקול את העמוד השלישי של LMDB. בעזרתו כל שינויי האחסון מתרחשים בעסקאות ובמנותק זה מזה, מה שמעניק למסד הנתונים בכללותו את המאפיין של ריבוי גרסאות.

3.3. לוויתן מס' 3. העתק-על-כתיבה

חלק מפעולות עץ B כוללות ביצוע סדרה של שינויים בצמתים שלו. דוגמה אחת היא הוספת מפתח חדש לצומת שכבר הגיע לקיבולת המקסימלית שלו. במקרה זה, יש צורך, ראשית, לפצל את הצומת לשניים, ושנית, להוסיף קישור לצומת הצאצא החדש בהורה שלו. הליך זה עלול להיות מסוכן מאוד. אם מסיבה כלשהי (התרסקות, הפסקת חשמל וכו') יתרחשו רק חלק מהשינויים מהסדרה, אז העץ יישאר במצב לא עקבי.

אחד הפתרונות המסורתיים להפיכת מסד נתונים סובלני לתקלות הוא הוספת מבנה נתונים נוסף בדיסק ליד עץ B - יומן טרנזקציות, הידוע גם בשם יומן כתיבה קדימה (WAL). זהו קובץ שבסופו הפעולה המיועדת נכתבת בקפדנות לפני שינוי ה-B-tree עצמו. לפיכך, אם מזוהה פגיעה בנתונים במהלך אבחון עצמי, מסד הנתונים מתייעץ ביומן כדי לעשות סדר.

LMDB בחרה בשיטה אחרת כמנגנון סובלנות תקלות, הנקראת העתקה-על-כתיבה. המהות שלו היא שבמקום לעדכן נתונים בעמוד קיים, הוא קודם כל מעתיק אותו במלואו ומבצע את כל השינויים בעותק.

לאחר מכן, על מנת שהנתונים המעודכנים יהיו זמינים, יש צורך לשנות את הקישור לצומת שהפך לעדכני בצומת האב שלו. מכיוון שגם זה צריך להיות שונה בשביל זה, זה גם מועתק מראש. התהליך ממשיך באופן רקורסיבי עד לשורש. הדבר האחרון שיש לשנות הוא הנתונים בדף המטא.​

אם לפתע במהלך הליך העדכון התהליך קורס, או שדף מטא חדש לא ייווצר, או שהוא לא ייכתב לדיסק לחלוטין, וסכום הבדיקה שלו יהיה שגוי. בכל אחד משני המקרים הללו, לא יהיה ניתן להגיע לדפים חדשים, אך ישנים לא יושפעו. זה מבטל את הצורך של LMDB לכתוב יומן קדימה כדי לשמור על עקביות הנתונים. דה פקטו, מבנה אחסון הנתונים בדיסק שתואר לעיל מקבל בו זמנית את תפקידו. היעדר יומן עסקאות מפורש הוא אחת התכונות של LMDB המספק מהירות קריאת נתונים גבוהה

העיצוב המתקבל, הנקרא append-only B-tree, מספק באופן טבעי בידוד עסקאות וניהול ריבוי גרסאות. ב-LMDB, כל עסקה פתוחה משויכת לשורש העץ הרלוונטי כרגע. עד השלמת העסקה, דפי העץ המשויכים אליה לעולם לא ישונו או יעשו בהם שימוש חוזר עבור גרסאות חדשות של הנתונים, כך תוכלו לעבוד כמה זמן שתרצו בדיוק עם סט הנתונים שהיה רלוונטי באותה עת העסקה נפתחה, גם אם האחסון ממשיך להתעדכן באופן פעיל בשלב זה. זוהי המהות של multiversion, מה שהופך את 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 הוא המאגר של המצב הפנימי של ה-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 יש בעיות עם תמיכה באחסון מקומי. מסיבה זו, בדוגמה למעלה, המאגר נפתח עם הדגל MDB_NOTLS. בנוסף לזה, זה היה גם הכרחי מזלג עטיפת C++ lmdbxxלחתוך משתנים עם תכונה זו ובתוכה.

מאגרי מידע

מסד הנתונים הוא מופע B-tree נפרד, עליו דנו למעלה. הפתיחה שלו מתרחשת בתוך עסקה, מה שעלול להיראות קצת מוזר בהתחלה.

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

באמצעות השוואה, החנות ממיינת את המפתחות בסדר עולה. אם לא תחליף אותו בעצמך, ייעשה שימוש ברירת המחדל, הממיין אותם בייט-byte לפי סדר לקסיקוגרפי.​

עסקות

מבנה העסקה מתואר בפירוט ב הפרק הקודם, אז כאן אחזור בקצרה על המאפיינים העיקריים שלהם:

1. תומך בכל המאפיינים הבסיסיים ACID: אטומיות, עקביות, בידוד ואמינות. אני לא יכול שלא לציין שיש באג מבחינת עמידות ב-macOS ו-iOS שתוקן ב-MDBX. אתה יכול לקרוא עוד בהם README.
2. הגישה לריבוי שרשורים מתוארת על ידי ערכת "סופר יחיד / מספר קוראים". סופרים חוסמים זה את זה, אבל לא חוסמים קוראים. הקוראים אינם חוסמים סופרים או אחד את השני.
3. תמיכה בעסקאות מקוננות.
4. תמיכה בריבוי גרסאות.

Multiversion ב-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 ולראות מה קורה.

Multiversion מביאה הטבות נחמדות מאוד לחייו של מפתח iOS. באמצעות מאפיין זה, תוכל להתאים בקלות ובאופן טבעי את קצב העדכון של מקור הנתונים עבור טפסי מסך, בהתבסס על שיקולי חווית משתמש. לדוגמה, ניקח תכונה של אפליקציית Mail.ru Cloud כגון טעינה אוטומטית של תוכן מגלריית המדיה של המערכת. עם חיבור טוב, הלקוח יכול להוסיף מספר תמונות בשנייה לשרת. אם תעדכן אחרי כל הורדה UICollectionView עם תוכן מדיה בענן של המשתמש, אתה יכול לשכוח מ-60 פריימים לשנייה וגלילה חלקה במהלך תהליך זה. כדי למנוע עדכוני מסך תכופים, אתה צריך איכשהו להגביל את הקצב שבו הנתונים משתנים בבסיס UICollectionViewDataSource.

אם מסד הנתונים אינו תומך בריבוי גרסאות ומאפשר לך לעבוד רק עם המצב הנוכחי, אז כדי ליצור תמונת מצב יציבה בזמן של הנתונים, עליך להעתיק אותו למבנה נתונים בזיכרון כלשהו או לטבלה זמנית. כל אחת מהגישות הללו היא יקרה מאוד. במקרה של אחסון בזיכרון, אנו מקבלים עלויות הן בזיכרון, הנגרמות מאחסון אובייקטים בנויים, והן בזמן, הקשורות לטרנספורמציות ORM מיותרות. באשר לשולחן הזמני, זהו תענוג יקר עוד יותר, הגיוני רק במקרים לא טריוויאליים.

פתרון המולטיורסיה של LMDB פותר את הבעיה של שמירה על מקור נתונים יציב בצורה מאוד אלגנטית. מספיק רק לפתוח עסקה והרי - עד שנשלים אותה, ערכת הנתונים מובטחת מתוקנת. ההיגיון למהירות העדכון שלו נמצא כעת לחלוטין בידי שכבת המצגת, ללא תקורה של משאבים משמעותיים.

סמנים

סמנים מספקים מנגנון לאיטרציה מסודרת על צמדי מפתח-ערך באמצעות חציית עץ B. בלעדיהם, אי אפשר יהיה ליצור מודל יעיל של הטבלאות במסד הנתונים, אליו אנו פונים כעת.

4.2. דוגמנות שולחן

המאפיין של סדר מפתח מאפשר לך לבנות הפשטה ברמה גבוהה כגון טבלה על גבי הפשטות בסיסיות. הבה נשקול תהליך זה באמצעות הדוגמה של הטבלה הראשית של לקוח ענן, השומר מידע על כל הקבצים והתיקיות של המשתמש.

סכימת טבלה

אחד התרחישים הנפוצים שעבורם יש להתאים מבנה טבלה עם עץ תיקיות הוא הבחירה של כל האלמנטים הנמצאים בתוך ספרייה נתונה. מודל ארגון נתונים טוב לשאילתות יעילות מסוג זה הוא רשימת סמיכות. כדי ליישם אותו על גבי אחסון ערך מפתח, יש צורך למיין את המפתחות של הקבצים והתיקיות בצורה כזו שהם מקובצים על סמך החברות שלהם בספריית האב. בנוסף, על מנת להציג את תוכן הספרייה בצורה המוכרת למשתמש Windows (תחילה תיקיות, ולאחר מכן קבצים, שניהם ממוינים בסדר אלפביתי), יש צורך לכלול את השדות הנוספים המתאימים במפתח.

התמונה למטה מראה כיצד, בהתבסס על המשימה שעל הפרק, ייצוג של מפתחות בצורה של מערך בתים עשוי להיראות. הבתים עם המזהה של ספריית האב (אדום) ממוקמים תחילה, לאחר מכן עם הסוג (ירוק) ובזנב עם השם (כחול). בהיותם ממוינים לפי ברירת המחדל של השוואת LMDB בסדר לקסיקוגרפי, הם מסודרים ב- אופן נדרש. מעבר מפתחות ברצף עם אותה קידומת אדומה נותנת לנו את הערכים המשויכים להם בסדר שבו הם אמורים להיות מוצגים בממשק המשתמש (בצד ימין), ללא צורך בעיבוד נוסף נוסף.

סידור מפתחות וערכים

בעולם הומצאו שיטות רבות להסדרת חפצים. מכיוון שלא הייתה לנו דרישה אחרת מלבד מהירות, בחרנו לעצמנו את המהיר ביותר האפשרי - dump של הזיכרון שנכבש על ידי מופע של מבנה שפת 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 // ...
}​

כל עוד כל המפתחות במסד הנתונים הם מאותו סוג, הטלת ייצוג הביטים שלהם ללא תנאי לסוג מבנה מפתח האפליקציה היא חוקית. יש כאן ניואנס אחד, אבל הוא יידון להלן בסעיף המשנה "קריאת רשומות".

סידור ערכים

LMDB עובד בצורה אינטנסיבית במיוחד עם המפתחות של רשומות מאוחסנות. ההשוואה ביניהם מתרחשת במסגרת כל פעולה יישומית, וביצועי הפתרון כולו תלויים במהירות המשווה. בעולם אידיאלי, ברירת המחדל של ההשוואה הבינארית אמורה להספיק כדי להשוות מפתחות, אבל אם היית צריך להשתמש במפתחות משלך, אז ההליך לביטול הסדרת מפתחות בו צריך להיות מהיר ככל האפשר.

בסיס הנתונים אינו מתעניין במיוחד בחלק הערך של הרשומה (ערך). ההמרה שלו מייצוג בתים לאובייקט מתרחשת רק כאשר הוא כבר נדרש על ידי קוד האפליקציה, למשל, להציג אותו על המסך. מכיוון שזה קורה לעתים רחוקות יחסית, דרישות המהירות עבור הליך זה אינן כל כך קריטיות, וביישום שלו אנו הרבה יותר חופשיים להתמקד בנוחות. לדוגמה, כדי להעלות מטא נתונים בסידרה על קבצים שטרם הורדו, אנו משתמשים 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;​
}

הרשימה המוצגת מראה כיצד סדרה באמצעות dump מבנה מאפשרת לך להיפטר מהקצאות דינמיות לא רק בעת כתיבה, אלא בעת קריאת נתונים. נגזר מהפונקציה 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. ישנן שתי דרכים להימנע מגורל עצוב שכזה.

הראשון מסתכם בהעתקה ראשונית של נתונים למבנה מיושר ברור. לדוגמה, ב-comparator מותאם אישית זה יבוא לידי ביטוי באופן הבא.

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. לשווא, כל העמודים הקודמים לזה שמחפשים מוסרים מהקובץ לזיכרון הראשי, שהוא יקר ביותר.

למרבה המזל, ה-API של LMDB מספק דרך יעילה למקם את הסמן בהתחלה. לשם כך, עליך ליצור מפתח שהערך שלו כמובן קטן או שווה למפתח שנמצא בגבול העליון של המרווח. לדוגמה, ביחס לרשימה באיור למעלה, נוכל ליצור מפתח שבו השדה 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 ספציפיות, אתן דוגמה פיקטיבית, אבל ברורה יותר

ללקוחות ניידים בענן יש עמוד המציג את כל הקבצים והתיקיות שהמשתמש שיתף עם אנשים אחרים. מכיוון שיש מעט יחסית קבצים כאלה, ויש הרבה סוגים שונים של מידע ספציפי על פרסום הקשור אליהם (למי ניתנת גישה, באילו זכויות וכו'), לא יהיה זה רציונלי להכביד על החלק הערכי של הקובץ. רשום איתו בטבלה הראשית. עם זאת, אם אתה רוצה להציג קבצים כאלה במצב לא מקוון, אתה עדיין צריך לאחסן אותם במקום כלשהו. פתרון טבעי הוא ליצור עבורו שולחן נפרד. בתרשים שלהלן, המפתח שלו הוא "P", וניתן להחליף את מציין המיקום "propname" בערך הספציפי יותר "מידע ציבורי".​

כל המטא-נתונים הייחודיים, לצורך האחסון בהם נוצרה הטבלה החדשה, ממוקמים בחלק הערך של הרשומה. יחד עם זאת, אינך רוצה לשכפל את הנתונים על קבצים ותיקיות שכבר מאוחסנים בטבלה הראשית. במקום זאת, נתונים מיותרים מתווספים למפתח "P" בצורה של השדות "מזהה צומת" ו"חותמת זמן". הודות להם, אתה יכול לבנות מפתח אינדקס, שממנו אתה יכול לקבל מפתח ראשי, שממנו, לבסוף, אתה יכול לקבל מטא נתונים של צומת.

מסקנה

אנו מעריכים את תוצאות היישום של LMDB באופן חיובי. לאחריו ירד מספר הקפאת האפליקציות ב-30%.

תוצאות העבודה שנעשו הדהדו מעבר לצוות iOS. נכון לעכשיו, אחד מקטעי ה"קבצים" הראשיים באפליקציית אנדרואיד עבר גם הוא לשימוש ב-LMDB, וחלקים נוספים בדרך. שפת ה-C, שבה מיושם מאגר ה-key-value, הייתה עזרה טובה ליצירת מסגרת יישומים סביבה חוצת פלטפורמות ב-C++. נעשה שימוש במחולל קוד כדי לחבר בצורה חלקה את ספריית C++ שהתקבלה עם קוד פלטפורמה ב-Objective-C וב-Kotlin ג'יני מ-Dropbox, אבל זה סיפור אחר לגמרי.

מקור: www.habr.com