W Spanner, TrueTime & Twierdzenie CAP , pisze Eric Brewer:
Jedną subtelną rzeczą dotyczącą Spannera jest to, że uzyskuje on możliwość serializacji z blokad, ale otrzymuje spójność zewnętrzna (podobnie jak linearyzowalność ) z TrueTime [ podkreślenie dodane ].
Jaka jest definicja zewnętrznej spójności , i czym różni się od linearyzowalności ?
Komentarze
- To świetne pytanie i chciałbym, żeby Eric miał tu trochę rozwinięte. Czy można go linearyzować, czy nie? 🙂
Odpowiedź
Zewnętrzna spójność nie ma ustalonego znaczenia. W tym kontekście ma znaczenie pojawiające się w następnym zdaniu dokumentu:
Dla dowolnych dwóch transakcji $ T_1 $ i $ T_2 $ (nawet jeśli po przeciwnych stronach globe): jeśli $ T_2 $ zaczyna zatwierdzać po zakończeniu zatwierdzania $ T_1 $, wówczas znacznik czasu $ T_2 $ jest większy niż znacznik czasu $ T_1 $.
Komentarze
- Im więcej o tym myślę, tym bardziej przypomina mi to linearyzację, ponieważ wszystkie transakcje są uporządkowane. Niestety, czasami te terminy są subtelne. .. Czy ktoś się nie zgadza? To znaczy, transakcje są serializowane i są całkowicie uporządkowane na podstawie czasu zatwierdzenia. Być może subtelność polega na tym, jak 2PC jest zaimplementowane w Spannerze?
- @Bminer Linearyzability to modele spójności, które dotyczy tylko pojedynczych obiektów, gdzie transakcje mogą obejmować wiele o obiekty.
- @LorinHochstein – Ha! To pachnie jak mielone słowa. Cały sens terminologii polega na tym, aby pomóc prawdziwym ludziom zrozumieć, jakie gwarancje otrzymują, zwłaszcza w odniesieniu do transakcji. Linearyzowalność + serializowalność to najsilniejsza gwarancja i myślę, że ' jest tym, do czego dokument Spanner odnosi się przy użyciu terminu " spójności zewnętrznej. " Ale nasuwa się pytanie: czy ktoś naprawdę wie, co " spójność zewnętrzna " znaczy? 🙂
Odpowiedź
Możesz pomyśleć o zewnętrznej spójności z izolacji transakcji (Tx) i punktu widzenia zamówienia . W izolacji Tx mówi się, że spójność zewnętrzna jest równoważna ścisłej izolacji możliwej do serializacji, gdzie „ścisła” jest częścią ograniczenia czasu rzeczywistego (jak w przypadku linearyzacji).
To znowu wszystko oznacza, że dla klienta systemowego Tx skutki uboczne są równoważne systemowi, w którym wszystkie transmisje odbywają się w izolacji, bez współbieżności i gdzie ich kolejność w czasie rzeczywistym, widziana przez klienta, jest zachowana. Co ważniejsze, ta sama kolejność jest widoczna dla każdego innego niepowiązanego klienta.
Przeczytaj więcej o tym rozróżnieniu na tym blogu .
Odpowiedź
Wspominając o " spójności zewnętrznej " , Brewer odwołuje się do B. Liskova. Praktyczne zastosowania zsynchronizowanych zegarów w systemach rozproszonych . Zasady ACM przetwarzania rozproszonego (PODC). Montreal, Kanada, sierpień 1991 r.
Liskov, terminem, odwołuje się do Gifforda D.K. Przechowywanie informacji w zdecentralizowanym systemie komputerowym . Raport techniczny CSL-81-8, Xerox Corporation, marzec 1983
Oto jak Gifford definiuje spójność zewnętrzną:
Zewnętrzne spójność gwarantuje, że transakcja zawsze otrzyma aktualne informacje. Korzystając z pojęć, które właśnie wprowadziliśmy, możemy podać formalną definicję spójności zewnętrznej. Rzeczywista kolejność, w której transakcje są zakończone, definiuje unikalny harmonogram szeregowy. Ten harmonogram szeregowy nosi nazwę zewnętrzny harmonogram . Mówi się, że system zapewnia zewnętrzną spójność, jeśli gwarantuje, że harmonogram, którego będzie używał do przetwarzania zestawu transakcji, jest równoważny z jego zewnętrznym harmonogramem.
Jak wspomina @Oleg, brzmi to jak ścisła serializowalność .