עצי Prolly וניהול גרסאות של נתונים לפי תוכן

המאמר המקורי באנגלית

שלום לכולם, ברוכים השבים ל־טיפה של ידע!

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

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

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

אינדקסים מסודרים ועצים מבוססי כתובות תוכן

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

• חיפוש ועדכון מהירים: הפתרון הקלאסי הוא עץ B או B+. אלה עצי חיפוש מסודרים ששומרים על איזון הנתונים ומאפשרים חיפוש, הוספה ומחיקה בסיבוכיות O(log n). הם הבסיס לכמעט כל מסד נתונים יחסי, כגון PostgreSQL ו־MySQL.
• שלמות נתונים ומניעת כפילות: גיבוב קריפטוגרפי של צומת כולל את תוכנו והפניות לבניו. גיבובי שורש שווים הם ראיה חזקה לשוויון נתונים בקידוד קנוני תחת הנחות העמידות להתנגשויות של הגיבוב, לא ודאות מתמטית ולא הוכחה שהנתונים הגיעו ממחבר מהימן.

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

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

עץ Prolly נכנס לתמונה: כיצד חלוקה הסתברותית למקטעים עוזרת

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

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

הקסם של שינויים מקומיים

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

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

כך מקבלים:

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

הארכיטקטורה של מפת עץ Prolly

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

Root: [ k3 -> H_A | k7 -> H_B ]
           |                  |
A: [ k2 -> H_12 | k3 -> H_3 ] B: [ k5 -> H_45 | k7 -> H_67 ]
         |          |                 |           |
Leaves: [k1,k2]    [k3]             [k4,k5]       [k6,k7]

H_* are symbolic content addresses, not measured or complete hashes.
Each index entry pairs a child's maximum key with that child's hash.

בארכיטקטורה הזו:

• צומתי עלים ברמה 0 מכילים זוגות מפתח־ערך ממוינים. מנגנון חלוקה דטרמיניסטי מבוסס תוכן קובע את גבולותיהם; גישת הגיבוב המתגלגל שלעיל היא אפשרות תכנון אחת.
• צומתי אינדקס, ברמה 1 ומעלה: מכילים רשומות אינדקס. כל רשומה מורכבת מהמפתח הגבוה ביותר בצומת בן ומהגיבוב הקריפטוגרפי של אותו צומת.
• אחסון מבוסס כתובות תוכן: כל צומת נכתב למנוע אחסון מבוסס תוכן, כגון מאגר בלוקים של IPFS, מאגר מפתח־ערך או אף קבצים רגילים, כאשר הגיבוב הקריפטוגרפי שלו הוא המפתח.

המחשה פשוטה ב־JavaScript של חלוקת Prolly למקטעים

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

// Teaching example: per-record content boundary, not a rolling hash or full tree.
const crypto = require('crypto');

// Target chunk size indicator.
// Under roughly uniform hashes, this pattern has probability about 1 in 4.
const CHUNK_PATTERN_MOD = 4; 

function getHash(dataString) {
    return crypto.createHash('sha256').update(dataString).digest('hex');
}

function chunkData(sortedKeyValuePairs) {
    const chunks = [];
    let currentChunk = [];

    for (const kv of sortedKeyValuePairs) {
        currentChunk.push(kv);
        
        // Serialize the key-value pair to hash it
        const serialized = JSON.stringify(kv);
        const hash = getHash(serialized);
        
        // Convert the first eight hex digits of the hash to an integer
        const hashValue = parseInt(hash.substring(0, 8), 16);
        
        // Probabilistic boundary check
        if (hashValue % CHUNK_PATTERN_MOD === 0) {
            chunks.push(currentChunk);
            currentChunk = [];
        }
    }
    
    // Don't forget the leftover items!
    if (currentChunk.length > 0) {
        chunks.push(currentChunk);
    }
    
    return chunks;
}

// Sample sorted dataset
const dataset = [
    { key: "user_01", val: "Alice" },
    { key: "user_02", val: "Bob" },
    { key: "user_03", val: "Charlie" },
    { key: "user_04", val: "David" },
    { key: "user_05", val: "Eve" },
    { key: "user_06", val: "Frank" },
    { key: "user_07", val: "Grace" },
];

console.log(chunkData(dataset));

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

למה זה חשוב לכם?

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

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

1. מסדי נתונים מבוזרים ותקשורת עמית לעמית

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

2. ניהול גרסאות לנתונים בסגנון Git באמצעות Dolt

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

3. סנכרון מסדי נתונים בקצה

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

סיכום: העתיד מבוסס כתובות תוכן

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

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

להמשך קריאה, עיינו ב־פרויקט Noms ובהיסטוריית התכנון שלו וב־Dolt. Noms מספק הקשר היסטורי מועיל; בדקו את מצב התחזוקה הנוכחי לפני אימוץ פרויקט. המקור לא זיהה את ספריית Prolly שהוצגה כחדשה, ולכן לא נוסף קישור מומצא למאגר.

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

עד הפעם הבאה, תכנות מהנה!