Модель даних

etcd розроблений для надійного зберігання даних, які рідко оновлюються, та забезпечення надійних запитів на спостереження. etcd надає попередні версії пар ключ-значення для підтримки недорогих знімків та історії подій спостереження (“запити подорожей у часі”). Постійна, багатоверсійна, модель даних з контролем паралельності добре підходить для цих випадків використання.

etcd зберігає дані у багатоверсійному постійному сховищі ключ-значення. Постійне сховище ключ-значення зберігає попередню версію пари ключ-значення, коли її значення замінюється новими даними. Сховище ключ-значення фактично є незмінним; його операції не оновлюють структуру на місці, а завжди створюють нову оновлену структуру. Усі минулі версії ключів залишаються доступними та спостережуваними після модифікації. Щоб запобігти нескінченному зростанню сховища даних з часом та зберіганню старих версій, сховище може бути стиснуте для видалення найстаріших версій замінених даних.

Логічний вигляд

Логічний вигляд сховища — це плоский двійковий простір ключів. Простір ключів має лексично відсортований індекс за байтовими рядками ключів, тому запити діапазонів є недорогими.

Простір ключів підтримує кілька ревізій. Коли створюється сховище, початкова ревізія дорівнює 1. Кожна атомарна операція зміни (наприклад, транзакційна операція може містити кілька операцій) створює нову ревізію у просторі ключів. Усі дані, що зберігаються у попередніх ревізіях, залишаються незмінними. Старі версії ключів все ще можуть бути доступні за їх попередніми ревізіями. Так само ревізії також індексуються; запити діапазонів за ревізіями зі спостерігачами є ефективними. Якщо сховище стиснуте для економії місця, ревізії до стиснутої ревізії будуть видалені. Ревізії монотонно зростають протягом усього життя кластера.

Життя ключа охоплює покоління, від створення до видалення. Кожен ключ може мати одне або кілька поколінь. Створення ключа збільшує версію цього ключа, починаючи з 1, якщо ключ не існує у поточній ревізії. Видалення ключа створює надгробок (tombstone) ключа, завершуючи поточне покоління ключа, скидаючи його версію до 0. Кожна модифікація ключа збільшує його версію; таким чином, версії монотонно зростають у межах покоління ключа. Після стиснення будь-яке покоління, що закінчилося до ревізії стиснення, буде видалено, а значення, встановлені до ревізії стиснення, за винятком останнього, будуть видалені.

Фізичний вигляд

etcd зберігає фізичні дані як пари ключ-значення у постійному b+дереві. Кожна ревізія стану сховища містить лише дельту від попередньої ревізії для ефективності. Одна ревізія може відповідати кільком ключам у дереві.

Ключем пари ключ-значення є 3-кортеж (major, sub, type). Major – це ревізія сховища, до якої належить ключ. Sub розрізняє ключі в межах однієї ревізії. Type - необовʼязковий суфікс для спеціального значення (наприклад, t, якщо значення містить надгробок). Значення пари ключ-значення містить модифікацію з попередньої ревізії, тобто одну дельту від попередньої ревізії. b+-дерево впорядковано за ключем у лексичному байтовому порядку. Діапазонний пошук за дельтами ревізій є швидким; це дозволяє швидко знаходити модифікації з однієї конкретної ревізії в іншу. Ущільнення видаляє застарілі пари «ключ-значення».

etcd також зберігає вторинний індекс btree у памʼяті для прискорення запитів діапазону за ключами. Ключі в індексі btree — це ключі сховища, доступні користувачеві. Значення є вказівником на модифікацію постійного b+дерева. Ущільнення видаляє мертві вказівники.

Загалом, etcd отримує інформацію про ревізію з btree, а потім використовує ревізію як ключ для отримання значення з b+tree (як показано нижче).