Контроль сумісності на основі часових позначок

В інформатиці алгоритм керування кон'юнктурою на основі часових позначок є методом неблокуючий контроль сумісності. Він використовується в деяких базах даних для безпечного опрацювання транзакцій, використовуючи мітки часу.

Розробка

Припущення

• Кожне значення позначки часу є унікальним і точно відображає мить у часі.
• Немає двох часових позначок, які не можуть бути однаковим.
• Часові позначки з високим значенням виникають пізніше, ніж часові позначки з нижчим значенням.

Створення часової мітки

Для створення часових позначок було використано ряд різних способів

• Використовуйте значення годинника системи на початку транзакції, як часову позначку.
• Використовуйте захищений потоком спільний лічильник, який збільшується на початку транзакції, як часову позначку.
• Поєднання перерахованих вище двох методів.

Формальний опис

Кожна транзакція ($T_{i}$) є упорядкованим списком дій ($A_{ix}$). Перед тим, як транзакція виконає свою першу дію ($A_{i1}$), вона позначається поточною часовою позначкою або будь-якою іншою послідовністю строго повністю впорядкованим: $TS(T_{i})=NOW()$. Кожній транзакції також надається спочатку порожній набір транзакцій, від яких вона залежить, $DEP(T_{i})=[]$, і спочатку порожній набір старих об'єктів, який він оновив, $OLD(T_{i})=[]$. Кожному об'єкт $(O_{j})$ у базі даних надаються два поля часових позначок, які не використовуються, крім для контролю одночасності: $RTS(O_{j})$ — час, коли значення об'єкта востаннє було використано транзакцією, $WTS(O_{j})$ — час, коли значення об'єкта востаннє оновлено транзакцією.

Для всіх $T_{i}$:

Для кожної дії $A_{ix}$:

Якщо $A_{ix}$ бажає використовувати значення $O_{j}$:

Якщо $WTS(O_{j})>TS(T_{i})$ то скасувати (останній потік перезаписує значення),

В іншому випадку оновіть набір залежностей $DEP(T_{i}).\mathrm {add} (WTS(O_{j}))$ та набір $RTS(O_{j})=\max(RTS(O_{j}),TS(T_{i}))$;

Якщо $A_{ix}$ хоче оновити значення $O_{j}$:

Якщо $RTS(O_{j})>TS(T_{i})$ то перервати (останній потік вже покладається на старе значення),

Якщо $WTS(O_{j})>TS(T_{i})$ то пропустити (Правила запису Томаса),

Інакше збережіть попередні значення, $OLD(T_{i}).\mathrm {add} (O_{j},WTS(O_{j}))$, встановіть $WTS(O_{j})=TS(T_{i})$, та оновити значення $O_{j}$,

Поки є транзакція в $DEP(T_{i})$, яка не закінчилася: почекати

Якщо в $DEP(T_{i})$ є транзакція, яка перервала, тоді скасувати

Інакше: здійснити.

До скасування:

Для кожного $(\mathrm {old} O_{j},\mathrm {old} WTS(O_{j}))$ in $OLD(T_{i})$

Якщо $WTS(O_{j})$ дорівнює $TS(T_{i})$ тоді відновіть $O_{j}=\mathrm {old} O_{j}$ and $WTS(O_{j})=\mathrm {old} WTS(O_{j})$

Неформальний опис

Щоразу, коли починається транзакція, вона отримує часову позначку. Ця часова марка вказує на порядок здійснення транзакції щодо інших транзакцій. Отже, враховуючи дві транзакції, які впливають на один і той же об'єкт, операція транзакції з попередньою часовою позначкою повинна виконуватися до початку операції з пізнішою часовою міткою. Однак якщо операція з помилковою транзакцією реально представлена спочатку, то вона переривається, і транзакція повинна бути перезапущена. Кожен об'єкт у базі даних має часову позначку читання, яка оновлюється кожного разу, коли дані об'єкта читаються, та часову позначку запису , яка оновлюється щоразу, коли дані об'єкта змінюються.

Якщо транзакція хоче прочитати об'єкт,

• але транзакція розпочалася перед об'єктом запис часової позначки, це означає, що щось змінило дані об'єкта після початку транзакції. У цьому випадку транзакцію скасовують і її потрібно перезапустити.
• і транзакція розпочалася після об'єкта тимчасової мітки запису, це означає, що безпечно читати об'єкт. У цьому випадку, якщо часова мітка транзакції стоїть після об'єкта часова мітка читання , часова мітка читання встановлюється як часова мітка транзакції.

Якщо транзакція хоче записати на об'єкт,

• але транзакція розпочалася перед об'єктом читати часову позначку, це означає, що щось подивилося на об'єкт, і ми припускаємо, що він взяв копію даних об'єкта. Таким чином, ми не можемо записати в об'єкт так, як це зробить будь-які скопійовані дані недійсними, тому транзакція перервана і повинна бути перезапущена.
• і транзакція розпочалася до позначки часу запису об'єкта, це означає, що щось змінило об'єкт з моменту початку транзакції У цьому випадку ми використовуємо правило написання Томаса і просто пропускаємо нашу операцію запису і продовжуємо як звичайну транзакцію, яку не потрібно переривати або перезавантажувати
• в іншому випадку транзакція записується в об'єкт, а запис часової позначки об'єкта встановлюється як часова мітка транзакції.

Відновлення

Для пояснення термінів відшкодування, уникання каскадних абортів і строгого див. Розклад (інформатика).

Зверніть увагу, що впорядкування часових міток у його базовій формі не призводить до відновлення історії. Розглянемо для прикладу наступну історію транзакцій $T_{1}$ і $T_{2}$:

$W_{1}(x)\;R_{2}(x)\;W_{2}(y)\;C_{2}\;R_{1}(z)\;C_{1}$

Це може бути створено планувальником TO, але не підлягає відновленню, оскільки $T_{2}$ виконує зобов'язання, навіть незважаючи на те, що він читав з незареєстрованої транзакції. Щоб переконатися, що вона створює історію, що підлягає відновленню, планувальник може зберігати перелік інших транзакцій, які кожна транзакція «читала з», і не дозволяти транзакції здійснюватись до того, як цей список складався з лише здійснених транзакцій. Щоб уникнути каскадних переривань роботи, планувальник може тегувати дані, записані невідправленими транзакціями, «брудними», і ніколи не дозволяти операції зчитування такого елементу даних, перш ніж вона була позначена тегом. Щоб отримати сувору історію, планувальник не повинен допускати жодних операцій з брудними предметами.

Проблеми впровадження

Дозвіл часової мітки

Це мінімальний час, що минув між двома сусідніми часовими позначками. Якщо роздільна здатність часової позначки занадто велика (груба), збільшується можливість рівних двох та більше часових позначок, що дозволяє деяким транзакціям здійснюватись із правильного порядку. Наприклад, якщо припустити, що у нас є система, яка може створити сто унікальних часових позначок в секунду, і враховуючи дві події, які трапляються на відстані 2 мілісекунд, їм, ймовірно, буде надана однакова мітка часу, навіть якщо вони насправді відбувалися в різний час.

Блокування часової мітки

Незважаючи на те, що ця техніка є незаблокованою, оскільки Об'єкт не заблокований від одночасного доступу протягом тривалості транзакції, акт запису кожної часової позначки проти Об'єкта вимагає надзвичайно короткої тривалості блокування на Об'єкт або його проксі.

Див. також

• Мультиверсійний контроль одночасності
• Позначка часу (обчислення)