teorama ng C.A.P

4.1 Consistency tungkol sa Brewera

Upang magsimula, si Eric Brewer ay hindi, at hindi kailanman inaangkin na, isang dalubhasa sa database. Siya ay kabilang sa komunidad ng mga distributed system, at ang kanyang sikat na pahayag, kung saan lumitaw ang CAP "theorem", ay ibinigay sa conference na "Principles of Distributed Computing". (Sa pamamagitan ng paraan, sampung taon mamaya, noong 2010, muli siyang nagbigay ng inanyayahang pahayag sa parehong kumperensya, at sa pahayag na ito ay nagbigay siya, lalo na, ng ilang mga halimbawa ng mga ipinamamahaging sistema, ang pag-unlad kung saan isinasaalang-alang ang " theorem" ng CAP.) Sa lugar na ito ay may sariling interpretasyon ng mga terminong ginamit sa larangan ng mga database.

Sa partikular, ang terminong "kaagad na pagkakapare-pareho" ay nangangahulugan na pagkatapos na matanggap ng user ang abiso mula sa system tungkol sa matagumpay na pagkumpleto ng ilang operasyon sa pag-update ng data, ang resulta ng operasyong ito ay agad na makikita ng lahat ng mga tagamasid.

Nangangahulugan ang pagiging pare-pareho sa kalaunan na kung walang mga bagong operasyon sa pag-update ng data ang pumapasok sa system sa loob ng sapat na mahabang panahon, maaari itong asahan na ang mga resulta ng lahat ng nakaraang operasyon sa pag-update ng data ay kakalat sa lahat ng mga node ng system, at lahat ng data ng replika ay pare-pareho (malamang, dapat itong maunawaan bilang "lahat ng mga replika ay magkakaroon ng parehong estado".

Sa ganitong pakiramdam ng pagkakapare-pareho sa isip, ang "theorem" ng Brewer ay maaaring ituring na lubos na nauunawaan at halata: sa anumang distributed system na may nakabahaging data, alinman lamang sa dalawang katangian ng consistency, availability, at partition tolerance ng network ang maaaring sabay na matiyak. Kaugnay nito, pinaghahambing pa nga ng Brewer ang hanay ng mga katangian ng ACID sa kanyang iminungkahing hanay ng mga katangian ng BASE (Basically Available, Soft-state, Eventual consistency - availability sa karamihan ng mga kaso; unstable state; final consistency). Ngunit ang pagsalungat na ito, sa palagay ko, ay hindi makatwiran, dahil sa unang kaso ay pinag-uusapan natin ang mga lohikal na katangian ng mga transaksyon, at sa pangalawa - tungkol sa mga pisikal na katangian ng mga ipinamamahaging sistema.

4.2 Katibayan ng "teorem"

Marami ang naniniwala na ang "theorem" ni Brewer ay pormal nang napatunayan. Sa katunayan, ang papel nina Seth Gilbert at Nancy Lynch ay nagpapakilala ng ilang (halos) pormal na mga kahulugan kung saan ang konteksto ang "teorama" ay talagang nagiging isang teorama at napatunayan. Gayunpaman, tingnan natin kung paano tinutukoy ang tatlong katangian ng isang distributed system, kung saan, ayon sa "theorem" ni Brewer, dalawang katangian lamang ang maaaring sabay na suportahan.

Ang pagkakapare-pareho ay tinatawag na atomic, o linearizable consistency (atomic, o linearizable consistency), na isang pag-aari ng system, lahat ng indibidwal na data object ay atomic (linearizable). Sa turn, ang isang atomic na bagay ay isang bagay na may ilang mga operasyon, tulad na ang tawag ng operasyon at ang pagtanggap ng data ng tugon ay nangyayari na parang kaagad, i.e. hindi tinatanggap ng bagay ang tawag ng susunod na operasyon hanggang sa ganap na nakumpleto ang nakaraang operasyon. Ang pagkakasunud-sunod kung saan ang mga operasyon ay natanggap ay dapat na tulad na kung ang isang read-type na operasyon ay dumating pagkatapos ng ilang write-type na operasyon ay ginanap, pagkatapos ay ang read operation ay dapat na ibalik ang halaga na isinulat nito o ilang mamaya write operation.

Palaging available ang isang distributed system kung dapat sagutin ang bawat kahilingang natanggap ng isang hindi nabigong node. Ang katatagan ng system sa network partition ay na-modelo bilang pagpapanatili ng viability ng system kung sakaling mawala ang isang di-makatwirang bilang ng mga mensahe na ipinadala mula sa isang node patungo sa isa pa.

Batay sa mga kahulugang ito, binabalangkas nina Hilbert at Lynch ang sumusunod na theorem (walang orasan sa asynchronous na modelo ng network, at ang mga node ay dapat gumawa lamang ng mga desisyon batay sa mga natanggap na mensahe at lokal na kalkulasyon):

Sa isang asynchronous na modelo ng network, hindi posibleng magpatupad ng read/write data object na ginagarantiyahan ang availability at atomic consistency na mga katangian para sa lahat ng wastong pagpapatupad (kabilang ang mga nawawalang mensahe).

Ang teorama na ito ay talagang pormal na pinatunayan ng pamamaraang "sa pamamagitan ng kontradiksyon". Ang artikulo ay nagpatuloy upang tapusin na:

Sa isang asynchronous na modelo ng network, hindi posibleng magpatupad ng read/write data object na ginagarantiyahan ang mga katangian ng pagiging naa-access para sa lahat ng wastong pagpapatupad at atomic consistency para sa mga valid na pagpapatupad kung saan hindi nawawala ang mga mensahe.

Bilang karagdagan, ang katotohanan ng pangunahing teorama ay pinatunayan para sa isang bahagyang kasabay na modelo ng network, kung saan ang bawat node ay may isang orasan, ang oras na ipinapakita kung saan tumataas sa parehong rate, ngunit kung saan ay hindi naka-synchronize, i.e. maaaring magpakita ng iba't ibang oras sa parehong tunay na sandali. Ipinakita na para sa kasong ito ang isang katulad na kahihinatnan ay hindi nagmula, at, samakatuwid, para sa bahagyang kasabay na mga network ay may higit pang mga posibilidad para sa pag-aayos ng mga ipinamamahaging sistema na may "magandang" mga katangian.

Oo, sa isang kahulugan (hindi kinakailangang pareho sa nilalayon ng Brewer) sina Gilbert at Lynch ay maaaring ituring na napatunayan na imposibleng sabay-sabay na matiyak ang mga katangian ng atomic consistency, availability, at partition tolerance ng isang network sa iisang distributed system. Ngunit ano ang kinalaman nito sa mga transaksyon sa database sa pangkalahatan at partikular sa mga transaksyon sa ACID?

4.3 Mga transaksyon sa ACID

Narito ang isinulat ni Julian Browne tungkol dito sa kanyang tala sa talakayan ng "teorama" ng CAP:

Sa kanilang patunay, ginamit nina Hilbert at Lynch ang terminong atomicity sa halip na consistency, na mas may katuturan mula sa teknikal na pananaw dahil, mahigpit na pagsasalita, ang consistency sa kahulugan ng ACID ay tumutukoy sa mga ideal na katangian ng mga transaksyon sa database at nangangahulugan na walang data na maging paulit-ulit kung nilalabag nila ang ilang paunang itinatag na mga paghihigpit. Ngunit kung ipagpalagay natin na ang isang paunang itinatag na limitasyon ng mga ipinamamahaging sistema ay ang pagbabawal ng pagkakaroon ng maraming magkakaibang mga halaga para sa parehong elemento ng data, kung gayon, sa aking opinyon, ang kapintasan na ito sa abstraction ng pagkakapare-pareho ay maaaring isaalang-alang. hindi gaanong mahalaga (bilang karagdagan, kung ginamit ni Brewer ang terminong atomicity, kung gayon ang AAP theorem ay lilitaw, na ang pangalan ay magiging lubhang hindi maginhawang bigkasin).

Ito ay nakasulat na hindi masyadong seryoso, ngunit matapat. At, sa katunayan, ang pangangailangan ng atomic consistency ay hindi dapat ihalo sa mga kinakailangan ng transactional consistency sa kahulugan ng ACID. Ang mga hadlang sa integridad ng database ay lohikal, kung gugustuhin mo, ang mga kinakailangan sa negosyo. Nagmula ang mga ito sa logic ng domain ng application. Ang pangangailangan ng atomic consistency ay ibang-iba. Ito ay isang kinakailangan sa pagpapatupad na nabibilang sa kategoryang tradisyonal na tinutukoy sa industriya ng database bilang pisikal na pagkakapare-pareho (halimbawa, kapag nagsasagawa ng anumang pagpapatakbo ng pagbabago ng index, ang lahat ng mga bloke ng kaukulang B+ tree ay dapat maglaman ng mga wastong halaga at maiugnay ng mga wastong sanggunian ).

At narito ang seryosong isinulat ng mga kinatawan ng komunidad ng database na sina Daniel Abadi at Alexander Thomson sa kanilang tala:

... ang pangangailangan para sa pagkakaroon ng mga scalable transactional system ay nagiging kritikal, at ito ay karaniwang natutugunan sa pamamagitan ng pagtitiklop at awtomatikong pag-redirect ng mga kahilingan kung sakaling mabigo ang isa sa mga node. Samakatuwid, inaasahan ng mga developer ng application na ang mga garantiya ng pagkakapare-pareho ng mga ACID system (orihinal na binubuo ng lokal na suporta para sa mga invariant na tinukoy ng user) ay palalawakin upang matiyak ang matatag na pagkakapare-pareho (na ang lahat ng mga replika ng parehong data sa anumang naibigay na oras ay magiging magkaparehong mga kopya, ibig sabihin, sa ang pagkakapare-pareho ng kasong ito ay ipinahiwatig sa kahulugan ng CAP/PACELC.

Sa madaling salita, ang pagkakapare-pareho ng Brewer ay walang kinalaman sa pagkakapare-pareho sa kahulugan ng ACID, ngunit nasa mga system na nakatuon sa pagbibigay ng mataas na kakayahang magamit sa pamamagitan ng pagtitiklop ng data na kanais-nais na mapanatili ang malakas na pagkakapare-pareho ng replika. Ito ay hindi isang ACID property, ngunit isang teknikal (pisikal) na tampok ng massively parallel DBMS na nagpapadali sa pagbuo ng application.

Ayon kay Michael Stonebreaker, ang susi sa pagbuo ng isang mataas na kalidad na modernong DBMS ay ang tamang pagpili ng mga teknikal na kompromiso. Kapag pumipili ng isang tiyak na solusyon sa engineering, maraming mga kadahilanan ang dapat isaalang-alang - ang mga kinakailangan ng mga gumagamit sa hinaharap, ang posibilidad ng iba't ibang mga sitwasyon ng pagkabigo, atbp., at hindi dogmatikong ginagabayan ng anumang pangkalahatang teoretikal na mga alituntunin (kabilang ang CAP "theorem").

Naniniwala ang Stonebreaker na sa larangan ng mga transactional parallel database system, ang pag-abandona sa pagkakapare-pareho ng Brewer sa pabor sa pagsuporta sa mataas na kakayahang magamit at pagpapaubaya sa partition ng network ay isang hindi magandang trade-off dahil (a) ang replica consistency ay isang napaka-kapaki-pakinabang na feature ng system; (b) ang transactional massively parallel DBMS ay hindi nangangailangan ng mga cluster na may napakalaking bilang ng mga node, kaya ang network split na sitwasyon ay hindi malamang; (c) ang sistema ay madaling maging hindi magagamit, hindi dahil sa isang network partition, ngunit, halimbawa, dahil sa pagkakaroon ng mga regular na nagaganap na mga error sa software.

Kaya, ang mataas na aktibidad ng mga kinatawan ng kampo ng NoSQL (basahin ang NoACID), na madalas na tumutukoy sa "theorem" ng Brewer, ay hindi konektado sa teoretikal na imposibilidad ng pagbuo ng massively parallel transactional DBMS na sumusuporta sa mga transaksyon sa ACID, ngunit sa katotohanan na ang mga pinasimple na sistema na hindi lamang sumusuporta sa mga transaksyon sa ACID, kundi pati na rin ang pagkakapare-pareho ng kopya, ay ginawa nang mas madali at mas mabilis. Dahil sa kanilang simplistic na organisasyon, sila ay may kakayahan sa napakabilis na pagproseso ng data, at para sa ilang mga aplikasyon ito ay mas mahalaga kaysa sa lahat ng mga kaginhawaan na likas sa teknolohiya ng database.

Tingnan natin kung paano tumugon ang komunidad ng database sa hamon na ito.