Blockchain, ze względu na swoją zdecentralizowaną konstrukcję, poświęca efektywność, dlatego zwiększenie prędkości wykonania zawsze było jednym z pilnych problemów do rozwiązania. „Warstwa wykonawcza” blockchaina jest kluczową częścią przetwarzania każdej transakcji i dodawania jej do łańcucha. Aby przyspieszyć zdolności przetwarzania, poprawa w warstwie wykonawczej stała się jednym z kluczowych strategii, a równoległe wykonanie jest istotnym przełomem w tym zakresie.
Tradycyjne blockchainy zazwyczaj przetwarzają transakcje jedna po drugiej, co znacznie ogranicza prędkość transakcji, szczególnie w gęsto zaludnionych sieciach, prowadząc do zatorów. Jednak dzięki równoległemu wykonaniu, wiele transakcji może być przetwarzanych jednocześnie, co znacznie zwiększa efektywność wykonania i zmniejsza obciążenie łańcucha.
Aby lepiej zrozumieć, czym jest równoległość, zaczniemy od przedstawienia wykonania, używając Ethereum w trybie PBS po scaleniu jako przykładu, aby wyjaśnić, czym jest wykonanie oraz pokazać, gdzie wykonanie znajduje się w całym cyklu życia transakcji.
Konkretne etapy wykonania transakcji
Transakcja wchodzi do puli pamięci i jest filtrowana oraz sortowana: to jest etap wstępny po złożeniu transakcji, który obejmuje interakcje między Mempool, Searcher i Builder, kończąc na filtracji i sortowaniu transakcji.
Builder buduje blok (ale nie wykonuje): Builder układa opłacalne transakcje w blok, aby zakończyć pakowanie i sortowanie transakcji.
Proposer weryfikuje i przesyła blok: Po zbudowaniu bloku, Builder wysyła propozycję bloku do Proposera. Proposer weryfikuje strukturę bloku i treść transakcji, a następnie formalnie przesyła blok do sieci, aby rozpocząć wykonanie.
Wykonanie transakcji: Po przesłaniu bloku, węzeł wykonuje transakcje w bloku jedna po drugiej. To jest kluczowy etap aktualizacji stanu, każda transakcja wyzwala wywołanie inteligentnego kontraktu, zmiany salda konta lub zmiany stanu.
Świadkowie świadczą: Weryfikatorzy świadczą o wynikach wykonania bloku i korzeniu stanu, traktując to jako ostateczne potwierdzenie. To zapewnia autentyczność i ważność bloku na poziomie wykonania oraz zapobiega niespójności.
Synchronizacja stanu: Każdy węzeł synchronizuje wyniki wykonania bloku (takie jak saldo konta, aktualizacje stanu kontraktu itp.) do swojego lokalnego stanu, po każdej transakcji węzeł oblicza i przechowuje nowy korzeń stanu, który będzie użyty jako stan początkowy w następnym bloku.
Oczywiście, to tylko synchronizacja stanu transakcji na poziomie bloku; aby zachować najnowszy stan na łańcuchu, w normalnych warunkach węzły synchronizują dane blok po bloku i nieustannie weryfikują bloki i stany. Aby osiągnąć ostateczność w mechanizmie POS, agregator musi złożyć podpisy świadków z każdego Slot w pełny podpis i przekazać go do proponującego następny Slot, a weryfikatorzy muszą po przejściu jednego Epoch potwierdzić stan wszystkich bloków w tym Epoch na podstawie liczby głosów, tworząc tymczasowy punkt kontrolny stanu konsensusu. Gdy dwa kolejne Epoch uzyskują wsparcie większości weryfikatorów, blok i transakcje osiągają ostateczność.
Z perspektywy całego cyklu życia transakcji, wykonanie następuje po weryfikacji przez Proposera struktury bloku i treści transakcji przesłanych przez Buildera. Rzeczywisty proces wykonania wymaga przetwarzania transakcji jedna po drugiej i aktualizacji odpowiednich stanów konta lub kontraktu. Po wykonaniu wszystkich transakcji, Proposer oblicza nowy korzeń stanu (korzeń Merkle), który jest podsumowaniem wyników wykonania wszystkich transakcji w bieżącym bloku i ostatecznego globalnego stanu. Mówiąc prościej, pełny proces wykonania bloku obejmuje szereg obliczeń, które muszą zostać zakończone, aby zmienić Ethereum z poprzedniego stanu na następny stan, od wykonania każdej transakcji po obliczenie korzenia Merkle.
Wykonanie sekwencyjne
W przeciwieństwie do równoległości, istnieje wykonanie sekwencyjne, które jest obecnie bardziej powszechnym sposobem wykonania w blockchainie. Zwykle transakcje są wykonywane w kolejności. Po zakończeniu wykonania transakcji, Ethereum aktualizuje stan konta i powiązane informacje (np. saldo, dane przechowywane w kontraktach) w drzewie stanu kont, generując nowe hashe stanu konta. Po zakończeniu aktualizacji wszystkich drzew stanu konta, powstaje korzeń drzewa stanu, znany jako korzeń Merkle stanu. Po ukończeniu korzeni Merkle stanu, korzeni Merkle transakcji i korzeni Merkle potwierdzeń, nagłówek bloku jest haszowany, generując hasz bloku.
A w tym przypadku, kolejność wykonania transakcji jest kluczowa. Ponieważ drzewo Merkle jest binarnym drzewem wartości hash, różne kolejności prowadzą do różnych wartości korzenia Merkle.
Równoległe wykonanie
W środowisku równoległego wykonania, węzły próbują przetwarzać transakcje w bloku równolegle. Nie wykonują transakcji jedna po drugiej w kolejności, lecz przypisują transakcje do różnych „ścieżek wykonawczych”, aby mogły być wykonywane jednocześnie. Dzięki równoległemu wykonaniu, system może bardziej efektywnie przetwarzać transakcje w bloku, zwiększając przepustowość.
Po zakończeniu wykonania wszystkich transakcji, węzeł podsumowuje wyniki wykonania (tj. aktualizacje stanu wpływające na transakcje), tworząc nowy stan bloku. Ten stan zostanie dodany do blockchaina, reprezentując najnowszy globalny stan na łańcuchu.
Konflikt stanu
Ponieważ równoległość przetwarza transakcje na różnych ścieżkach jednocześnie, jednym z głównych wyzwań równoległości są konflikty stanu. Oznacza to, że mogą występować sytuacje, w których wiele transakcji próbuje odczytać lub zapisać tę samą część danych (stanu) na blockchainie w tym samym czasie. Jeśli te sytuacje nie są odpowiednio obsługiwane, mogą prowadzić do niepewnych wyników wykonania. Ponieważ kolejność aktualizacji stanu jest różna, ostateczne wyniki obliczeń również mogą być różne. Na przykład,
Załóżmy, że są dwie transakcje, transakcja A i transakcja B, które obie próbują zaktualizować saldo tego samego konta:
Transakcja A: Zwiększ saldo konta o 10.
Transakcja B: Zwiększ saldo konta o 20.
Początkowe saldo konta wynosi 100.
Jeśli wykonujemy w sposób szeregowy, rezultatem kolejności wykonania jest określony:
1. Najpierw wykonaj transakcję A, potem transakcję B:
Saldo konta najpierw wzrasta o 10, zmieniając się na 110.
Zwiększ o 20, ostatecznie zmienia się na 130.
2. Najpierw wykonaj transakcję B, a następnie transakcję A:
Saldo konta najpierw wzrasta o 20, zmieniając się na 120.
Następnie wzrasta o 10, ostatecznie zmieniając się na 130.
W obu tych sekwencjach, ostateczne saldo wynosi 130, ponieważ system zapewnia spójność kolejności wykonania transakcji.
Jednak w środowisku równoległego wykonania, transakcja A i transakcja B mogą jednocześnie odczytać początkowe saldo 100 i przeprowadzić swoje obliczenia:
Transakcja A odczytuje saldo 100, oblicza i aktualizuje saldo na 110.
Transakcja B również odczytuje saldo 100, oblicza i aktualizuje saldo na 120.
W tej sytuacji, ze względu na równoległe wykonanie transakcji, ostateczne saldo aktualizuje się tylko do 120, a nie 130, ponieważ operacje transakcji A i B „nakładają się” na wyniki, co prowadzi do konfliktu stanu.
Tego rodzaju problemy z konfliktami stanu często nazywane są „przykrywaniem danych”, czyli kiedy transakcje próbują jednocześnie modyfikować te same dane, mogą wzajemnie przykrywać swoje wyniki obliczeń, co prowadzi do niepoprawnego ostatecznego stanu. Innym rodzajem konfliktu stanu, który może prowadzić do problemów, jest niemożność zapewnienia kolejności wykonania. Ponieważ wiele transakcji kończy operacje w różnych okresach czasu, prowadzi to do różnych kolejności wykonania. Różne kolejności mogą prowadzić do różnych wyników obliczeń, co czyni wyniki niepewnymi.
Aby uniknąć tej niepewności, systemy równoległego wykonania blockchaina zwykle wprowadzają mechanizmy wykrywania konfliktów i wycofywania, lub wcześniej analizują zależności transakcji, aby zapewnić, że będą mogły być wykonywane równolegle bez wpływu na ostateczną spójność stanu.
Optymistyczna równoległość kontra deterministyczna równoległość
Istnieją dwa podejścia do problemu potencjalnych konfliktów stanu: deterministyczna równoległość i optymistyczna równoległość. Obie te formy mają swoje kompromisy pod względem efektywności i złożoności projektowej.
Deterministyczna równoległość wymaga wcześniejszego zadeklarowania dostępu do stanu, weryfikator lub sequencer sprawdza zadeklarowany dostęp do stanu podczas sortowania transakcji. Jeśli wiele transakcji próbuje zapisać ten sam stan, oznacza się je jako konflikt, aby uniknąć równoczesnego wykonania. Różne łańcuchy różnią się szczegółami implementacji wcześniejszego deklarowania dostępu do stanu, ale ogólnie obejmują następujące sposoby:
Poprzez normy kontraktowe: programiści bezpośrednio określają zakres dostępu do stanu w inteligentnym kontrakcie. Na przykład, przelew tokenów ERC-20 wymaga dostępu do pól salda nadawcy i odbiorcy.
Poprzez deklarację zorganizowanych danych transakcyjnych: dodanie specjalnych pól do transakcji w celu oznaczenia dostępu do stanu.
Przez analizę kompilatora: kompilatory języków wysokiego poziomu mogą statycznie analizować kod kontraktu, automatycznie generując zestawy dostępu do stanu.
Poprzez wymuszenie deklaracji w ramach: niektóre frameworki wymagają od programistów jawnego określenia stanu, do którego potrzebują dostępu podczas wywoływania funkcji.
Optymistyczna równoległość najpierw optymistycznie przetwarza transakcje, a gdy występuje konflikt, ponownie wykonuje dotknięte transakcje w kolejności. Aby zminimalizować występowanie konfliktów, kluczowym założeniem w projektowaniu optymistycznej równoległości jest szybkie przewidywanie i hipotetyzowanie stanu za pomocą danych historycznych, analizy statycznej itp. To oznacza, że system, przy braku pełnej weryfikacji, zakłada, że niektóre operacje lub aktualizacje stanu są ważne, starając się unikać czekania na wszystkie procesy weryfikacji, co zwiększa wydajność i przepustowość.
Choć optymistyczna równoległość może starać się unikać wystąpienia konfliktów poprzez szybkie przewidywania i hipotetyzacje stanu, zawsze istnieją pewne nieuniknione wyzwania, szczególnie w przypadku wykonywania kontraktów lub transakcji międzyłańcuchowych. Jeśli konflikty występują często, ponowne wykonanie może znacząco spowolnić wydajność systemu i zwiększyć zużycie zasobów obliczeniowych.
Deterministyczna równoległość również przeprowadza kontrole zależności stanu przed dokonaniem transakcji, aby uniknąć konfliktów, które mogą wystąpić w optymistycznej równoległości, ale wymaga od programistów dokładnego zadeklarowania zależności stanu przed złożeniem transakcji, co zwiększa złożoność realizacji.
Dylemat równoległego EVM
Podejście do konfliktów stanu obejmuje nie tylko różnice między deterministycznymi a optymistycznymi, ale także wymaga rozważenia architektury bazy danych łańcucha w procesie realizacji równoległej. Problemy z konfliktami stanu w EVM opartym na architekturze drzewa Merkle są szczególnie trudne. Drzewo Merkle to struktura haszująca o warstwach, w której po każdej transakcji modyfikującej pewne dane stanu, korzeń haszujący drzewa Merkle również musi być zaktualizowany. Proces aktualizacji jest rekurencyjny, obliczany od liści do korzenia. Ponieważ haszowanie jest nieodwracalne, można obliczyć warstwę górną tylko po zakończeniu zmian na niższych warstwach, co sprawia, że trudno jest zaktualizować je równolegle.
Jeśli dwie transakcje są wykonywane równolegle i uzyskują dostęp do tego samego stanu (np. saldo konta), może to prowadzić do konfliktów w węzłach drzewa Merkle. Rozwiązanie takich konfliktów zazwyczaj wymaga dodatkowych mechanizmów zarządzania transakcjami, aby zapewnić, że w różnych gałęziach uzyskuje się spójne wartości hasha korzenia. To nie jest łatwe do zrealizowania w EVM, ponieważ wymaga podejmowania decyzji między równoległym przetwarzaniem a spójnością stanu.
Rozwiązania równoległe, które nie są EVM
Solana
W przeciwieństwie do globalnego drzewa stanu Ethereum, Solana przyjęła model konta. Każde konto jest niezależną przestrzenią pamięci, przechowywaną w księdze, co unika problemu konfliktów ścieżek.
Solana jest systemem równoległym deterministycznym. W Solanie każda transakcja musi w momencie składania wyraźnie zadeklarować, jakie konta będą używane i jakie są wymagane uprawnienia dostępu (tylko do odczytu lub do odczytu i zapisu). Taki projekt pozwala węzłom blockchaina na wcześniejszą analizę zasobów, które będą potrzebne podczas wykonania każdej transakcji. Ponieważ transakcje mają już jasno określone zależności między kontami przed rozpoczęciem wykonania, węzły mogą ocenić, które transakcje będą uzyskiwać dostęp do tych samych kont, a które transakcje mogą bezpiecznie działać równolegle, co umożliwia inteligentne planowanie, unikanie konfliktów i realizację równoległego harmonogramu.
Ponieważ każda transakcja już przed wykonaniem zadeklarowała, do jakich kont i uprawnień będzie miała dostęp, Solana może sprawdzić, czy istnieją jakiekolwiek zależności między transakcjami (model Sealevel). Jeśli transakcje nie mają wspólnych kont do odczytu lub zapisu, system może przypisać je do różnych procesorów i wykonać równolegle.
Aptos
Projekt równoległego wykonania Aptos znacznie różni się od Ethereum; wprowadza kluczowe innowacje w architekturze i mechanizmach, głównie w modelu konta i przechowywaniu stanu.
Ethereum podczas wykonywania transakcji musi często aktualizować globalne drzewo stanu (MPT). Stan wszystkich kont i kontraktów jest przechowywany w jednym współdzielonym drzewie stanu, a każda transakcja musi uzyskać dostęp do i zaktualizować część tego drzewa stanu. Aptos z kolei dzieli konta na niezależne jednostki stanu, gdzie każdy obiekt jest osobną parą klucz-wartość, a obiekty mogą istnieć niezależnie, nie wpływając na siebie nawzajem, a tylko przy wyraźnych odniesieniach będą ze sobą powiązane. Obiekty nie mają wspólnych ścieżek w drzewie, co eliminuje problemy z rywalizacją o blokady, a tym samym pozwala na całkowicie równoległe wykonanie.
Podstawowa struktura danych Aptos to Jellyfish Merkle Tree. Stan każdego obiektu jest ostatecznie przechowywany w JMT jako niezależna para klucz-wartość. W przeciwieństwie do MPT Ethereum, Jellyfish Merkle Tree ma strukturę pełnego drzewa binarnego, co upraszcza ścieżkę przechowywania i ścieżkę zapytań dla węzłów, znacznie skracając czas weryfikacji. Dodatkowo, położenie każdego konta w drzewie jest stałe, a węzły w drzewie są przechowywane niezależnie, co pozwala na równoległe aktualizacje i wyszukiwania wielu kont.
Aptos to optymistyczna równoległość, która nie wymaga wcześniejszego dostarczenia wszystkich zadeklarowanych zależności kont. W tym celu Aptos wykorzystuje Block-STM, który oszacowuje zależności na podstawie ustalonej kolejności transakcji, aby zredukować liczbę przerwań.
Równoległe EVM
W porównaniu z równoległym EVM, przetwarzanie zależności stanu, wykrywanie konfliktów, zarządzanie gazem i mechanizmy wycofywania są znacznie bardziej skomplikowane. Aby lepiej to zrozumieć, możemy przyjrzeć się, jak niektóre projekty równoległego EVM (takie jak Sui, Monad, Canto) rozwiązują te problemy.
Sui
Sui, podobnie jak Aptos, również używa modelu obiektowego do zarządzania stanem, traktując każdy obiekt (na przykład konto, stan inteligentnego kontraktu) jako niezależny zasób. Te obiekty są rozróżniane za pomocą unikalnych identyfikatorów obiektów. Kiedy transakcje dotyczą różnych obiektów, mogą być przetwarzane równolegle, ponieważ operują na różnych stanach, co nie prowadzi do bezpośrednich konfliktów.
Pomimo że Sui używa modelu obiektowego do zarządzania stanem, aby być kompatybilnym z EVM, architektura Sui przez dodatkową warstwę adaptacyjną lub mechanizm abstrakcji łączy model obiektowy z modelem konta EVM.
W Sui, harmonogram transakcji stosuje strategię optymistycznej równoległości, zakładając, że między transakcjami nie występują konflikty. Jeśli wystąpi konflikt, system używa mechanizmu wycofywania, aby przywrócić stan.
Sui wykorzystuje model obiektowy i technologię izolacji stanu, co skutecznie unika problemów z zależnościami stanu. Każdy obiekt jako niezależny zasób, różne transakcje mogą być wykonywane równolegle, co zwiększa przepustowość i efektywność. Ale ta metoda wiąże się z komplikacjami modelu obiektowego i kosztami mechanizmu wycofywania. Jeśli wystąpią konflikty między transakcjami, konieczne może być wycofanie części stanu, co zwiększa obciążenie systemu i może wpływać na efektywność przetwarzania równoległego. W porównaniu z systemami równoległymi, które nie są EVM (takimi jak Solana), Sui wymaga większych zasobów obliczeniowych i pamięciowych, aby utrzymać efektywną równoległość.
Monad
Podobnie jak Sui, Monad również przyjmuje optymistyczną równoległość. Jednak optymistyczna równoległość Monada przed wykonaniem konkretnej transakcji przewiduje niektóre transakcje mające zależności. Prognozowanie odbywa się głównie przez statyczny analizator kodu Monada. Prognozowanie wymaga dostępu do stanu, a sposób przechowywania stanu w bazie danych Ethereum sprawia, że dostęp do stanu jest bardzo trudny. Aby zwiększyć efektywność równoległego odczytu stanu, Monad również przebudował bazę danych.
Drzewo stanu Monada jest podzielone na partycje, z każdą partycją utrzymującą swoją własną poddrzewo stanu. Podczas aktualizacji wystarczy zmodyfikować odpowiednie fragmenty, nie ma potrzeby odbudowywania całego drzewa stanu. Dzięki tabeli indeksów stanu szybko lokalizuje się stan w partycji, co zmniejsza interakcję między partycjami.
Podsumowanie
Równoległość polega na zwiększeniu efektywności wykonania warstwy wykonawczej poprzez wykonanie wieloma ścieżkami, a aby osiągnąć wielościeżkowe wykonanie, łańcuch musi przeprowadzić szereg działań, takich jak wykrywanie konfliktów i mechanizmy wycofywania, aby zapewnić, że mogą być wykonywane równolegle bez wpływu na ostateczną spójność stanu, oraz wprowadzić pewne ulepszenia do bazy danych.
Oczywiście, poprawa efektywności warstwy wykonawczej nie ogranicza się tylko do równoległości, optymalizacje w etapie wykonania mogą również odbywać się poprzez zmniejszenie potrzeby operacji odczytu i zapisu bazy danych dla jednej transakcji. Całkowite przyspieszenie łańcucha obejmuje szerszy zakres, w tym również poprawę efektywności warstwy konsensusu.
Za każdą technologią kryją się specyficzne ograniczenia. Równoległość jest tylko jednym ze sposobów zwiększenia efektywności, a ostateczna decyzja o zastosowaniu tej technologii wymaga również rozważenia, czy jest przyjazna dla programistów, czy można ją zrealizować bez poświęcania decentralizacji itp. Nakładanie technologii nie zawsze jest korzystne; przynajmniej w przypadku Ethereum, równoległość nie jest tak atrakcyjna. Z perspektywy zwiększenia efektywności, włączenie równoległości nie jest optymalnym rozwiązaniem dla Ethereum, biorąc pod uwagę zarówno prostotę, jak i obecny plan rozwoju Ethereum skoncentrowany na Rollup.