Consistency və consensus

Fəsil 8 nəyin pozula biləcəyini göstərdi: paketlər itir, saatlar yalan danışır, proseslər dayanır. İndi sual budur: bu şəraitdə hansı zəmanətləri qurmaq mümkündür? Tək bir nümunə götürək: istifadəçi username seçir və sistem onun unikal olduğunu təmin etməlidir. Tək database-də bu, unique index-dir. Üç datacenter-də, hər biri öz replica-sı ilə, eyni anda iki nəfər eyni adı istəyəndə kim qalib gəlir? Cavab vermək üçün node-lar razılığa gəlməlidir və buna consensus deyilir.

Fəsil 7-dəki transaction-lar kimi, bu fəsildə də yanaşma eynidir: ümumi məqsədli abstraksiyalar tapmaq ki, application onların üzərində qurulsun və alt qatdakı xaosu görməsin. Ən güclü belə abstraksiya linearizability-dir. Əvvəlcə onu, sonra ordering-i, sonda isə consensus-un özünü nəzərdən keçirəcəyik.

Consistency zəmanətləri

Replicated database-lərin çoxu eventual consistency verir: yazmağı dayandırsanız, bir müddət sonra bütün replica-lar eyni dəyəri qaytaracaq. Bu, çox zəif zəmanətdir: "bir müddət" nə qədərdir, deyilmir, və yazma davam edərkən oxumanın nə qaytaracağı haqqında heç nə deyilmir.

Daha güclü modellər performans və fault tolerance qiymətinə gəlir, amma kodu sadələşdirir. Onları Fəsil 7-dəki isolation səviyyələri ilə qarışdırmamaq lazımdır: isolation paralel transaction-lar haqqındadır, consistency isə replica-ların vəziyyəti haqqında.

Linearizability

Linearizability-nin ideyası sadədir: sistem elə davranmalıdır ki, sanki data-nın yalnız bir kopyası var və bütün əməliyyatlar atomikdir. Bu, recency guarantee-dir: yazma tamamlanan kimi, bütün sonrakı oxumalar yeni dəyəri görməlidir, hansı replica-dan oxunmasından asılı olmayaraq.

Futbol matçının nəticəsi nümunəsi: Alisa finalın nəticəsini saytda görüb Boba deyir. Bob bir saniyə sonra eyni saytı yeniləyir və köhnə nəticəni görür, çünki onun sorğusu geridə qalmış replica-ya düşüb. Alisa oxumasını Bobdan əvvəl bitirib, ona görə linearizable sistemdə Bob ən azı Alisanın gördüyünü görməli idi. Formal şəkildə: hər əməliyyatın başlanğıcı və sonu var; linearizability tələb edir ki, hər əməliyyatın bu interval daxilində atomik olaraq icra olunduğu bir an tapılsın və bütün əməliyyatların bu anlarına görə sıralanması "tək kopya" modelinə uyğun gəlsin.

Serializability ilə fərq vacibdir: serializability transaction-ların hansısa ardıcıl sıraya uyğun icrasıdır, sıranın real vaxtla əlaqəsi tələb olunmur. Linearizability isə tək obyekt üzərində real vaxta bağlı zəmanətdir, transaction-ları bir neçə obyektə birləşdirmir. Serializable snapshot isolation linearizable deyil, çünki snapshot-dan oxuyur. Hər ikisini verən sistemə strict serializability deyilir.

Linearizability nə vaxt lazımdır?

• Lock və leader election: lock-u alan hər node əmin olmalıdır ki, yalnız o alıb. Linearizable compare-and-set lazımdır; ZooKeeper və etcd bunu verir.
• Unikallıq constraint-ləri: username, fayl adı, hesab balansının mənfiyə düşməməsi, anbarda sonuncu məhsul. Hamısı "kim birinci oldu" sualıdır və linearizable sıra tələb edir.
• Kanallar arası vaxt asılılığı: istifadəçi şəkli storage-ə yükləyir, web server queue-ya "şəkli kiçilt" mesajı göndərir, resizer storage-dən oxuyur. Queue storage-dən sürətlidirsə, resizer köhnə versiyanı və ya heç nə görür. Storage linearizable olsaydı, problem olmazdı; deyilsə, çarə mesajda data-nın özünü göndərməkdir.

İmplementasiya

Fəsil 5-dəki replication üsullarına görə:

Leaderless üçün nüans: w + r > n quorum-u ilə belə, bir yazma iki replica-ya fərqli vaxtda çatarkən bir oxuyucu yeni, sonrakı oxuyucu köhnə dəyəri görə bilər. Oxuyanın read repair-i sinxron etməsi və yazanın yazmadan əvvəl quorum-dan oxuması ilə düzəltmək olar, amma bu, performansı aşağı salır.

Qiyməti: CAP və gecikmə

İki datacenter arasında şəbəkə kəsilsə, hər datacenter-dəki client-lər nə edir? Single-leader-də leader olmayan datacenter ya yazmaları qəbul etmir, ya da linearizability pozulur. Multi-leader-də hər datacenter işləyir, amma linearizable deyil. Bu dilemma CAP teoremi kimi tanınır, lakin "Consistency, Availability, Partition tolerance: ikisini seç" formulası yanlışdır: şəbəkə partition-ı seçim deyil, baş verən hadisədir. Düzgün ifadə: partition baş verəndə ya linearizable, ya available ol. Partition yoxdursa, hər ikisi mümkündür. Üstəlik CAP yalnız bir consistency modelini və bir xəta növünü nəzərə alır; şəbəkə gecikməsi və node çökməsi haqqında heç nə demir.

Daha dərin səbəb də var: linearizability-dən imtina etmək çox vaxt availability yox, performans üçündür. Hətta tək kompüterin CPU nüvələri linearizable deyil: bir nüvənin yazdığı dəyər cache-dən digər nüvəyə dərhal çatmır, çünki bu, hər yazmanı yavaşladardı. Sübut olunub ki, linearizable oxuma və yazmanın cavab vaxtı ən azı şəbəkə gecikməsinin qeyri-müəyyənliyinə mütənasibdir. Sürət lazımdırsa, zəif model seçilir.

Ordering zəmanətləri

Linearizability bütün əməliyyatların tək sırada icrası deməkdir. Sıranın əsas məqsədi causality-ni qorumaqdır: sual cavabdan əvvəl, yazma onu oxuyan oxumadan əvvəl, sətrin yaradılması onun update-indən əvvəl gəlməlidir.

Causal order partial order-dir: iki əməliyyat bir-birindən asılı deyilsə, onların sırası yoxdur, onlar concurrent-dir. Linearizability isə total order-dir: hər cüt əməliyyat müqayisə oluna bilər. Buna görə linearizability causality-ni ehtiva edir, amma əksi doğru deyil. Vacib nəticə: çox sistem üçün causal consistency kifayətdir və o, linearizability-dən fərqli olaraq şəbəkə partition-ında da işləyə bilər.

Sequence number-lar və Lamport timestamp-ləri

Causality-ni izləmək üçün hər əməliyyata nömrə vermək olar. Single-leader sistemdə leader log-un özü ardıcıl nömrə verir. Leader olmayanda isə Lamport timestamp işlədilir: hər node (counter, nodeId) cütü saxlayır, hər əməliyyatda counter artır, hər mesajda cari counter göndərilir və alan tərəf öz counter-ini max(öz, gələn) + 1 edir. Nəticə: əgər A causally B-dən əvvəldirsə, A-nın timestamp-i kiçikdir. Timestamp-lər total order verir və saat sinxronlaşması tələb etmir.

Amma bu, unikallıq problemini həll etmir. İki node eyni username-i eyni anda qeyd edir; sonradan timestamp-lərə baxıb kimin qalib olduğunu demək olar, amma sorğu anında node bilmir ki, başqa node-da daha kiçik timestamp-lə eyni sorğu var-varmı. Bunu bilmək üçün bütün node-larla danışmaq lazımdır və biri cavab vermirsə, sistem dayanır. Fərq budur: sıranın sonradan məlum olması kifayət deyil, sıra final olmalıdır.

Total order broadcast

Bu, total order broadcast adlanan abstraksiyaya gətirir: node-lar arasında mesaj göndərmə protokolu ki, iki xüsusiyyəti var: heç bir mesaj itmir, hər node bütün mesajları eyni sırada alır. Mesaj çatdırılandan sonra onun sırası dəyişmir, bu, "final"lığı verir. Bunun üzərində state machine replication qurulur: hər replica eyni yazmaları eyni sırada tətbiq edirsə, hamısı eyni vəziyyətə gəlir. Fəsil 7-dəki serializable transaction-lar da belə alınır: hər transaction mesajdır, hər node onları deterministik icra edir.

Total order broadcast-dan linearizable compare-and-set qurmaq olar: "username X-i istəyirəm" mesajını broadcast et, log-u oxu, sənin mesajından əvvəl eyni username-lə mesaj varsa, uduzdun. Əksinə də mümkündür: linearizable increment-and-get register ilə hər mesaja ardıcıl nömrə vermək. Deməli, bu iki məsələ ekvivalentdir və hər ikisi consensus-a bərabərdir.

Distributed transaction-lar və atomic commit

Çox node-u əhatə edən transaction-da bütün node-lar ya commit, ya abort etməlidir. Bu, atomic commit problemidir və Fəsil 7-dəki tək node commit-indən fərqlidir: orada commit bir disk yazması idi, burada bir node commit edib digəri abort edərsə, atomicity pozulur.

Two-phase commit

2PC bunu coordinator ilə həll edir. Birinci fazada coordinator hər iştirakçıya prepare göndərir; iştirakçı transaction-ı tam yoxlayıb, disk-ə yazıb "bəli" cavab verir və bu cavabla söz verir ki, sonradan nə olursa olsun commit edə biləcək. İkinci fazada bütün cavablar "bəli"dirsə, coordinator qərarını öz log-una yazır, bu, geri dönüşü olmayan nöqtədir, sonra hamıya commit göndərir. Bir "xeyr" varsa, hamıya abort.

Zəif nöqtə coordinator-dur. İştirakçı "bəli" deyib, sonra coordinator çöküb: iştirakçı nə commit, nə abort edə bilər, çünki coordinator-un qərarını bilmir; digərlərindən soruşsa belə, onlar da bilməyə bilər. Transaction in doubt vəziyyətində qalır, lock-ları saxlayır və coordinator qayıdana qədər gözləyir. Coordinator-un log-u itibsə, bu transaction-lar əbədi ilişir və operator onları əl ilə həll edir. Three-phase commit bu bloklanmanı aradan qaldırmağa çalışır, amma unbounded gecikməli şəbəkədə işləmir.

XA standartı heterojen sistemlər, məsələn database və message broker, arasında 2PC-dir. Application prosesi coordinator rolunu oynayır və onun çökməsi hər iştirakçıda in-doubt transaction-lar və saxlanılan lock-lar deməkdir: bütün sistemin bir hissəsi coordinator qayıdana qədər dayanır. Database-daxili distributed transaction-lar isə, məsələn partitioned database-in öz 2PC-si, çox vaxt daha yaxşı işləyir, çünki protokol bir məhsulun daxilində optimallaşdırılıb.

Fault-tolerant consensus

Consensus-un formal tərifi: bir neçə node dəyər təklif edir və alqoritm onlardan birini seçir. Dörd xüsusiyyət tələb olunur:

• Uniform agreement: heç bir iki node fərqli qərar vermir.
• Integrity: heç bir node iki dəfə qərar vermir.
• Validity: seçilən dəyər hansısa node tərəfindən təklif olunub.
• Termination: çökməyən hər node nəhayət qərar verir.

İlk üçü safety, sonuncu liveness-dir. 2PC termination-ı pozur: coordinator çökəndə heç kim qərar vermir. Fault-tolerant consensus isə node-ların çoxluğu sağ olduğu müddətdə irəliləməlidir. Paxos, Raft, Zab və Viewstamped Replication bu problemi həll edir və əslində hamısı total order broadcast implementasiya edir: hər mesaj üçün ayrıca consensus etmək əvəzinə, mesajların sırası üçün bir dəfə razılaşırlar.

Praktikada bu alqoritmlər leader seçir, amma leader-in unikallığını Fəsil 8-dəki fencing token-ə bənzər epoch number ilə təmin edir: hər seçkidə epoch artır, hər qərar quorum-un təsdiqini tələb edir və quorum bu epoch-dan böyük epoch bilmədiyini yoxlayır. Deməli iki qərar var: leader seçmək və leader-in təklifini qəbul etmək, və hər ikisinin quorum-ları kəsişməlidir. Bu, 2PC-dən fərqdir: orada hər iştirakçının "bəli"si lazım idi, burada çoxluq kifayətdir, və in-doubt vəziyyət yoxdur, çünki yeni leader köhnənin işini davam etdirə bilir.

Məhdudiyyətlər də var. Hər qərar quorum-a synchronous replication tələb edir, ona görə gecikmə artır. Node-ların sayı sabit olmalıdır, dinamik membership əlavə mürəkkəblik gətirir. Leader-in ölümünü timeout ilə aşkarlamaq lazımdır və gecikməsi dəyişkən şəbəkədə yalançı seçkilər performansı öldürür. Nəhayət, bəzi alqoritmlər tək bir etibarsız link-ə həssasdır və sonsuz seçki dövrünə düşə bilər.

Membership və koordinasiya xidmətləri

ZooKeeper və etcd bu alqoritmləri paketləyib "koordinasiya xidməti" kimi təqdim edir. Onlar az miqdarda data-nı yaddaşda saxlayır, total order broadcast ilə replicate edir və bunun üzərində bir neçə faydalı xüsusiyyət verir: linearizable compare-and-set, əməliyyatların total ordering-i və hər əməliyyata artan nömrə, yəni hazır fencing token; client session-ları və heartbeat ilə failure detection; dəyişikliklərə abunə olub notification almaq.

Tipik istifadə: hər partition üçün leader seçmək, job scheduler-də işi node-lara bölmək, yeni node əlavə olunanda partition-ları yenidən balanslaşdırmaq. Bu data az dəyişir, bu səbəbdən consensus-un yavaşlığı problem deyil; application-ın öz data-sı isə koordinasiya xidmətindən keçmir. Service discovery üçün isə linearizability şərt deyil: köhnə DNS cavabı adətən problem yaratmır. Membership service isə hansı node-ların sağ olduğunu consensus ilə müəyyən edir: Fəsil 8-də dediyimiz kimi, node-un sağ olub-olmadığını heç kim dəqiq bilmir, amma hamının eyni cavaba razılaşması sistemin işləməsi üçün kifayətdir.

Bütün fəsil bir nəticəyə gəlir: unikallıq, lock, atomic commit, total order broadcast, linearizable register, hamısı ekvivalent problemlərdir və hamısı consensus-dur. Consensus baha başa gəlir, ona görə ağıllı dizayn onu az yerdə, az data üçün işlədir. Növbəti fəsillər bunun əksini göstərir: Fəsil 10 və 11-dəki derived data sistemləri consensus-suz, eventual consistency ilə necə güclü nəticə verir.

Tapşırıqlar

1. Üç replica-lı key-value store-da w = 2, r = 2, n = 3 quorum-u var. Bir yazmanın iki replica-ya fərqli anlarda çatdığı ssenaridə iki oxuyucunun linearizability-ni pozan nəticə görə biləcəyini timeline diaqramı ilə göstərin. Hansı əlavə addım bunu düzəldir?
2. Üç node-da Lamport timestamp alqoritmini pseudo-code ilə yazın və beş mesajlıq nümunə üzərində işlədin. Sonra göstərin ki, iki concurrent "username X-i al" sorğusunda timestamp-lər qalibi sonradan müəyyən edir, amma sorğu anında rədd cavabı vermək üçün kifayət etmir.
3. Komandanız sifariş sistemində database və message broker arasında XA transaction işlətməyi düşünür. Coordinator çöküb 30 dəqiqə qayıtmayanda database-də nə baş verir? Fəsil 12-ni gözləmədən, 2PC-siz eyni atomicity-ni verən alternativ dizayn təklif edin və onun hansı zəmanəti zəiflətdiyini yazın.