{"id":372,"date":"2015-11-02T07:40:53","date_gmt":"2015-11-02T06:40:53","guid":{"rendered":"https:\/\/sii.pl\/blog\/?p=372"},"modified":"2025-05-07T11:11:29","modified_gmt":"2025-05-07T09:11:29","slug":"twierdzenie-cap-u-progu-doroslosci","status":"publish","type":"post","link":"https:\/\/sii.pl\/blog\/twierdzenie-cap-u-progu-doroslosci\/","title":{"rendered":"Twierdzenie CAP u progu doros\u0142o\u015bci"},"content":{"rendered":"\n

Wi\u0119kszo\u015b\u0107 os\u00f3b pracuj\u0105cych w bran\u017cy IT s\u0142ysza\u0142a zapewne o twierdzeniu CAP (CAP theorem), kt\u00f3re Eric Brewer og\u0142osi\u0142 w 1999. Od tego czasu sta\u0142o si\u0119 ono standardem my\u015blenia o architekturze aplikacji rozproszonych. Niedawno natkn\u0105\u0142em si\u0119 na interesuj\u0105cy artyku\u0142<\/a>\u00a0CAP theorem revisited autorstwa urodzonego w Wielkiej Brytanii fizyka i informatyka Marka Burgessa, w kt\u00f3rym przygl\u0105da si\u0119 on ponownie twierdzeniu CAP, dowodzi braku jego matematycznych podstaw i proponuje ca\u0142kiem interesuj\u0105c\u0105\u00a0alternatyw\u0119. Lektura artyku\u0142u Burgessa sk\u0142oni\u0142a mnie te\u017c do przeczytania kilku innych opracowa\u0144, kt\u00f3re odnosz\u0105 si\u0119 do CAP ze wsp\u00f3\u0142czesnej perspektywy.<\/p>\n\n\n\n

Burgess uwa\u017ca, \u017ce twierdzenie CAP jest po prostu b\u0142\u0119dne. Swoj\u0105 argumentacj\u0119 rozpoczyna od stwierdzenia, \u017ce w zwi\u0105zku z brakiem matematycznego dowodu (istnieje wszak\u017ce szczeg\u00f3\u0142owe wyja\u015bnienie<\/a> autorstwa Setcha Gilberta i Nancy Lynch) nie jest ono twierdzeniem, a raczej domys\u0142em. Autor u\u017cywa r\u00f3wnie\u017c teorii wzgl\u0119dno\u015bci by dowie\u015b\u0107, \u017ce zignorowanie przez CAP up\u0142ywaj\u0105cego czasu czyni je b\u0142\u0119dnym. Ostatecznie, zamiast trzyma\u0107 si\u0119 CAP, proponuje alternatywne rozwi\u0105zanie, Promise Theory, k\u0142ad\u0105ce nacisk na autonomi\u0119 ka\u017cdego agenta (czy te\u017c w\u0119z\u0142a) i jego odpowiedzialno\u015b\u0107 za wy\u0142\u0105cznie swoje dzia\u0142ania.<\/p>\n\n\n\n

Wspomniany artyku\u0142 Gilberta i Lynch jest pr\u00f3b\u0105 nakre\u015blenia bardziej precyzyjnych ram dla CAP. Autorzy dostarczaj\u0105 znacznie bardziej precyzyjnych definicji dla wszystkich trzech komponent\u00f3w, a tak\u017ce uwzgl\u0119dniaj\u0105 up\u0142yw czasu oraz asynchroniczno\u015b\u0107 po\u0142\u0105cze\u0144 sieciowych. Artyku\u0142 dostarcza wielu ciekawych informacji, jednak\u017ce r\u00f3wnie\u017c mu brakuje matematycznego dowodu. Burgess twierdzi, \u017ce brak tego\u017c jest jedn\u0105 z g\u0142\u00f3wnych s\u0142abo\u015bci CAP.<\/p>\n\n\n\n

Wg szczeg\u00f3lnej teorii wzgl\u0119dno\u015bci Einsteina dwa zdarzenia, kt\u00f3re maj\u0105 miejsce w dw\u00f3ch r\u00f3\u017cnych miejscach nie mog\u0105 by\u0107 jednoczesne. Ich jednoczesno\u015b\u0107 albo kolejno\u015b\u0107 zale\u017cy od po\u0142o\u017cenia obserwatora i kierunku jego ruchu. Je\u015bli zastosujemy wzgl\u0119dno\u015b\u0107 jednoczesno\u015bci do CAP to oka\u017ce si\u0119, \u017ce w rozproszonym systemie (kt\u00f3rego elementy s\u0105 rozrzucone w przestrzeni z samej jego natury) nie mo\u017cemy m\u00f3wi\u0107 o jednoczesno\u015bci, a co za tym idzie sp\u00f3jno\u015bci, z absolutnego punktu widzenia.<\/p>\n\n\n\n

Z tej perspektywy Burgess pr\u00f3buje zdefiniowa\u0107 trzy komponenty CAP mo\u017cliwie najprecyzyjniej. W pierwszej kolejno\u015bci pr\u00f3buje uwzgl\u0119dni\u0107 up\u0142ywaj\u0105cy czas. Dost\u0119pno\u015b\u0107 staje si\u0119 mo\u017cliwo\u015bci\u0105 obiecania, \u017ce odpowied\u017a na ka\u017cde odebrane \u017c\u0105danie zostanie odes\u0142ana przed up\u0142ywem okre\u015blonego czasu \u2013 jest to jedyna prosta definicja wg Burgessa. Sp\u00f3jno\u015b\u0107, jako \u017ce zale\u017cy od dotrzymania obietnic przez inne w\u0119z\u0142y systemu, nie jest czym\u015b, co mo\u017ce zosta\u0107 lekkomy\u015blnie obiecane. Wed\u0142ug autora jedynie sp\u00f3jno\u015b\u0107 ostateczna (eventual consistency) mo\u017ce zosta\u0107 obiecana, albowiem nie jest mo\u017cliwe zapewnienie natychmiastowej sp\u00f3jno\u015bci w dzia\u0142aj\u0105cym systemie \u2013 potrzebny jest czas na osi\u0105gni\u0119cie przez niego r\u00f3wnowagi.<\/p>\n\n\n\n

Najbardziej niejasna okazuje si\u0119 jednak definicja odporno\u015bci na awarie sieci (partition tolerance). Jest ona mo\u017cliwa do sformu\u0142owania, ale definicja (obietnica dostarczenia prawid\u0142owej odpowiedzi przed up\u0142ywem okre\u015blonego czasu nawet, je\u015bli odpowied\u017a jest zale\u017cna od informacji znajduj\u0105cych si\u0119 w niedost\u0119pnej cz\u0119\u015bci sieci) wydaje si\u0119 by\u0107 niepraktyczna i wymaga\u0142aby sporo pracy w celu przygotowania odpowiedzi, kt\u00f3ra by\u0142aby prawid\u0142owa tylko dla fragmentu systemu dzia\u0142aj\u0105cego w obr\u0119bie tej samej dost\u0119pnej cz\u0119\u015bci sieci.<\/p>\n\n\n\n

Twierdzenie CAP widziane z tej perspektywy wydaje si\u0119 faktycznie by\u0107 b\u0142\u0119dne bardzo trudno bowiem okre\u015bli\u0107 jasne granice jego sk\u0142adowych. Burgess zwraca te\u017c uwag\u0119 na to, \u017ce CAP ca\u0142kowicie ignoruje ko\u0144cowego u\u017cytkownika informacji i uwa\u017ca, \u017ce ten czynnik ma w tej chwili zasadniczy wp\u0142yw na oderwanie twierdzenia od otaczaj\u0105cej rzeczywisto\u015bci. W celu przybli\u017cenia swojej koncepcji autor przywo\u0142uje przyk\u0142ad gita i continuous deployment. U\u017cywaj\u0105c gita tworzymy wiele niesp\u00f3jnych \u015brodowisk, ga\u0142\u0119zi, kt\u00f3re mog\u0105 (ale nie musz\u0105) zosta\u0107 ze sob\u0105 w pewnym momencie po\u0142\u0105czone. Je\u015bli dodamy do tego continuous deployment, to ujrzymy proces stopniowego przenoszenia zmian (z lokalnego \u015brodowiska programisty przez \u015brodowisko testowe a\u017c po produkcj\u0119). \u0141\u0105czenie ga\u0142\u0119zi prowadzi do ponownego osi\u0105gni\u0119cia r\u00f3wnowagi przez system, ale jest to proces, kt\u00f3ry trwa pewien czas. Co wi\u0119cej nie powinien by\u0107 przeprowadzany za ka\u017cdym razem, gdy pojawi si\u0119 zmiana powoduj\u0105ca naruszenie sp\u00f3jno\u015bci \u2013 w przeciwnym wypadku bardzo szybko doprowadziliby\u015bmy ca\u0142\u0105 aplikacj\u0119 do niestabilno\u015bci wdra\u017caj\u0105c ka\u017cd\u0105 pojedyncz\u0105 zmian\u0119 na produkcj\u0119.<\/p>\n\n\n\n

Trzymaj\u0105c si\u0119 dalej analogii z gitem nale\u017cy uzna\u0107, \u017ce proces osi\u0105gania r\u00f3wnowagi przez system powinien by\u0107 zainicjowany z wewn\u0105trz, a nie narzucony z zewn\u0105trz. Ga\u0142\u0105\u017a istniej\u0105ca w repozytorium jest utrzymywana w zgodno\u015bci poprzez pobieranie informacji o zmianach z zewn\u0105trz, a nie przez odbieraniu komunikat\u00f3w z centralnego w\u0119z\u0142a odpowiedzialnego za nadz\u00f3r na sp\u00f3jno\u015bci\u0105 ca\u0142ego systemu. Zadaniem lokalnego w\u0119z\u0142a (w tym wypadku programisty) jest zadecydowanie kiedy powinien on zweryfikowa\u0107 swoj\u0105 sp\u00f3jno\u015b\u0107 z pozosta\u0142ymi w\u0119z\u0142ami; niekt\u00f3re zmiany mog\u0105 nie mie\u0107 znaczenia albo mog\u0105 zosta\u0107 zintegrowane p\u00f3\u017aniej.<\/p>\n\n\n\n

Burgess uwa\u017ca, \u017ce systemy opieraj\u0105ce si\u0119 na wysy\u0142aniu komunikat\u00f3w (w kt\u00f3rych istnieje jeden wszystkowiedz\u0105cy w\u0119ze\u0142 odpowiedzialny za utrzymanie sp\u00f3jno\u015bci) nie s\u0105 w stanie okre\u015bli\u0107 czy ca\u0142y system jest sp\u00f3jny. Z kolei w systemach kt\u00f3rych sk\u0142adowe s\u0105 autonomiczne ka\u017cdy w\u0119ze\u0142 odpowiada za swoj\u0105 w\u0142asn\u0105 sp\u00f3jno\u015b\u0107 i jako jedyny mo\u017ce okre\u015bli\u0107 czy jest sp\u00f3jny. Ta w\u0142a\u015bnie my\u015bl wydaje si\u0119 by\u0107 kluczowym wnioskiem autora.<\/p>\n\n\n\n

Trzymanie si\u0119 koncepcji Burgessa przy projektowaniu system\u00f3w rozproszonych mo\u017ce bardzo u\u0142atwi\u0107 nam prac\u0119. Zamiast tworzy\u0107 scentralizowane aplikacje, kt\u00f3rych bardzo istotn\u0105 s\u0142abo\u015bci\u0105 jest uzale\u017cnienie od mo\u017cliwo\u015bci odebrania komunikat\u00f3w z g\u0142\u00f3wnego w\u0119z\u0142a (b\u0105d\u017a klastra w\u0119z\u0142\u00f3w) powinni\u015bmy skupi\u0107 si\u0119 na niezale\u017cno\u015bci poszczeg\u00f3lnych w\u0119z\u0142\u00f3w i pozwoli\u0107 na osi\u0105ganie przez nie r\u00f3wnowagi przez wzajemn\u0105 komunikacj\u0119. Nawet je\u015bli taki system nie b\u0119dzie przez ca\u0142y czas sp\u00f3jny, to osi\u0105gnie on ostatecznie r\u00f3wnowag\u0119 zachowuj\u0105c jednocze\u015bnie wysok\u0105 dost\u0119pno\u015b\u0107.<\/p>\n\n\n\n

Dalsze zg\u0142\u0119bianie Promise Theory i wsp\u00f3\u0142czesnych zastrze\u017ce\u0144 wobec CAP warto zacz\u0105\u0107 od artyku\u0142u Burgessa<\/a> i przejrzenia listy \u017ar\u00f3de\u0142 na jego ko\u0144cu. Szczeg\u00f3lnie godne uwagi wydaj\u0105 si\u0119 by\u0107 artyku\u0142 Brewera<\/a> na temat CAP napisany dwana\u015bcie lat po og\u0142oszeniu twierdzenia i proponowana przez Abadiego alternatywa b\u0105d\u017a rozszerzenie CAP \u2013 PACELC<\/a>.<\/p>\n\n\n\n

(See English version: CAP theorem revisited<\/a>)<\/p>\n\n\n

\n \n
\n \n
\n
\n \n\n
<\/div>\n <\/div>\n
\n \n\n
<\/div>\n <\/div>\n
\n \n\n
<\/div>\n <\/div>\n
\n \n\n
<\/div>\n <\/div>\n
\n \n\n
<\/div>\n <\/div>\n <\/div>\n \n
\n
\n \n\n
<\/div>\n <\/div>\n
\n \n\n
<\/div>\n <\/div>\n
\n \n\n
<\/div>\n <\/div>\n
\n \n\n
<\/div>\n <\/div>\n
\n \n\n
<\/div>\n <\/div>\n <\/div>\n<\/div>\n \n\n
\n 5\/5 ( votes: 2) <\/div>\n <\/div>\n","protected":false},"excerpt":{"rendered":"

Wi\u0119kszo\u015b\u0107 os\u00f3b pracuj\u0105cych w bran\u017cy IT s\u0142ysza\u0142a zapewne o twierdzeniu CAP (CAP theorem), kt\u00f3re Eric Brewer og\u0142osi\u0142 w 1999. Od … Continued<\/a><\/p>\n","protected":false},"author":32,"featured_media":377,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"_editorskit_title_hidden":false,"_editorskit_reading_time":3,"_editorskit_is_block_options_detached":false,"_editorskit_block_options_position":"{}","inline_featured_image":false,"footnotes":""},"categories":[1314],"tags":[560,61],"class_list":["post-372","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-development-na-twardo","tag-architektura-it","tag-systemy-rozproszone"],"acf":[],"aioseo_notices":[],"republish_history":[],"featured_media_url":"https:\/\/sii.pl\/blog\/wp-content\/uploads\/2015\/10\/eric_brewer.jpg","category_names":["Development na twardo"],"_links":{"self":[{"href":"https:\/\/sii.pl\/blog\/wp-json\/wp\/v2\/posts\/372"}],"collection":[{"href":"https:\/\/sii.pl\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sii.pl\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sii.pl\/blog\/wp-json\/wp\/v2\/users\/32"}],"replies":[{"embeddable":true,"href":"https:\/\/sii.pl\/blog\/wp-json\/wp\/v2\/comments?post=372"}],"version-history":[{"count":2,"href":"https:\/\/sii.pl\/blog\/wp-json\/wp\/v2\/posts\/372\/revisions"}],"predecessor-version":[{"id":22813,"href":"https:\/\/sii.pl\/blog\/wp-json\/wp\/v2\/posts\/372\/revisions\/22813"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/sii.pl\/blog\/wp-json\/wp\/v2\/media\/377"}],"wp:attachment":[{"href":"https:\/\/sii.pl\/blog\/wp-json\/wp\/v2\/media?parent=372"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sii.pl\/blog\/wp-json\/wp\/v2\/categories?post=372"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sii.pl\/blog\/wp-json\/wp\/v2\/tags?post=372"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}