CAP teoremi

All lectures for TR purposes
Seviye , Ders
Mevcut

4.1 Brewera hakkında tutarlılık

Öncelikle, Eric Brewer bir veri tabanı uzmanı değildir ve öyle olduğunu da asla iddia etmemiştir. Dağıtılmış sistemler topluluğuna mensuptur ve CAP "teoreminin" yer aldığı ünlü konuşması "Dağıtılmış Hesaplama İlkeleri" konferansında verilmiştir. (Bu arada, on yıl sonra, 2010'da, aynı konferansta tekrar davetli bir konuşma yaptı ve bu konuşmada, özellikle, geliştirilmesi dikkate alınan bir dizi dağıtık sistem örneği verdi. teoremi"dir.) Bu alanda veritabanları alanında kullanılan terimler kendi yorumlarına sahiptir.

Özellikle, "anında tutarlılık" terimi , kullanıcı sistemden bazı veri güncelleme işlemlerinin başarıyla tamamlandığı hakkında bildirim aldıktan sonra, bu işlemin sonucunun tüm gözlemciler tarafından anında görülebileceği anlamına gelir.

Nihai tutarlılık , sisteme yeterince uzun bir süre boyunca hiçbir yeni veri güncelleme işlemi girmezse, önceki tüm veri güncelleme işlemlerinin sonuçlarının sonunda sistemin tüm düğümlerine yayılmasının beklenebileceği ve tüm kopya verilerinin tutarlı (görünüşe göre bu, "tüm kopyaların aynı duruma sahip olacağı" şeklinde anlaşılmalıdır.

Bu tutarlılık duygusu göz önünde bulundurulduğunda, Brewer'ın "teoremi" oldukça anlaşılır ve açık olarak kabul edilebilir: paylaşılan verilere sahip herhangi bir dağıtılmış sistemde, ağın yalnızca herhangi iki özelliği olan tutarlılık, kullanılabilirlik ve bölüm toleransı aynı anda sağlanabilir. Bu bağlamda Brewer, ASİT özellikleri kümesini önerdiği BASE özellikleri grubuyla bile karşılaştırır (Temelde Kullanılabilir, Yumuşak durum, Nihai tutarlılık - çoğu durumda kullanılabilirlik; kararsız durum; son tutarlılık). Ancak bu muhalefet, bence haksız, çünkü ilk durumda işlemlerin mantıksal özelliklerinden ve ikincisinde - dağıtılmış sistemlerin fiziksel özelliklerinden bahsediyoruz.

4.2 "teoremin" kanıtı

Birçoğu Brewer'ın "teoreminin" resmen kanıtlandığına inanıyor. Aslında, Seth Gilbert ve Nancy Lynch'in makalesi, "teoremin" gerçekten bir teorem haline geldiği ve kanıtlandığı bağlamda bazı (neredeyse) resmi tanımlar getiriyor. Bununla birlikte, Brewer "teoremine" göre aynı anda yalnızca iki özelliği desteklenebilen dağıtılmış bir sistemin bu üç özelliğinin nasıl belirlendiğini görelim.

Tutarlılık , sistemin bir özelliği olan atomik veya doğrusallaştırılabilir tutarlılık (atomik veya doğrusallaştırılabilir tutarlılık) olarak adlandırılır ve tüm bireysel veri nesneleri atomiktir (doğrusallaştırılabilir). Buna karşılık, bir atomik nesne, birkaç işlemi olan bir nesnedir, öyle ki işlem çağrısı ve yanıt verilerinin alınması anında gerçekleşir, yani. önceki işlem tamamen tamamlanana kadar nesne bir sonraki işlemin çağrısını kabul etmez. İşlemlerin alınma sırası öyle olmalıdır ki, bir okuma türü işlemi, bir tür yazma işlemi gerçekleştirildikten sonra gelirse, okuma işlemi, bu veya daha sonraki bir yazma işlemi tarafından yazılan değeri döndürmelidir.

Başarısız olmayan bir düğüm tarafından alınan her talebin yanıtlanması gerekiyorsa, dağıtılmış bir sistem her zaman kullanılabilir. Sistemin ağ bölümlerine dayanıklılığı, bir düğümden diğerine gönderilen rastgele sayıda mesajın kaybı durumunda sistemin yaşayabilirliğinin korunması olarak modellenmiştir.

Bu tanımlara dayanarak, Hilbert ve Lynch aşağıdaki teoremi formüle eder (eşzamansız ağ modelinde saat yoktur ve düğümler yalnızca alınan mesajlar ve yerel hesaplamalar temelinde kararlar vermelidir):

Eşzamansız bir ağ modelinde, tüm geçerli yürütmeler için (mesajları kaybedenler dahil) kullanılabilirliği ve atomik tutarlılık özelliklerini garanti eden bir okuma/yazma veri nesnesi uygulamak mümkün değildir.

Bu teorem, "çelişki yoluyla" yöntemiyle gerçekten oldukça basit bir şekilde resmen kanıtlanmıştır. Makale şu sonuca varmak için devam ediyor:

Eşzamansız bir ağ modelinde, tüm geçerli yürütmeler için erişilebilirlik özelliklerini ve mesajların kaybolmadığı geçerli yürütmeler için atomik tutarlılığı garanti eden bir okuma/yazma veri nesnesi uygulamak mümkün değildir.

Ek olarak, ana teoremin doğruluğu, her düğümün bir saate sahip olduğu, zamanın aynı oranda arttığı, ancak senkronize olmayan, yani. aynı gerçek anda farklı zamanlar gösterebilir. Bu durum için benzer bir sonucun elde edilmediği gösterilmiştir ve bu nedenle kısmen senkronize ağlar için "iyi" özelliklere sahip dağıtılmış sistemleri organize etmek için daha fazla olasılık vardır.

Evet, bir anlamda (Brewer'ın amaçladığı gibi olmayabilir) Gilbert ve Lynch'in, tek bir dağıtılmış sistemdeki bir ağın atomik tutarlılığı, kullanılabilirliği ve bölüm toleransı özelliklerini aynı anda sağlamanın imkansız olduğunu kanıtlamış olduğu düşünülebilir. Ancak bunun genel olarak veritabanı işlemleriyle ve özel olarak ACID işlemleriyle ne ilgisi var?

4.3 ASİT işlemleri

Julian Browne, CAP "teoremi" tartışmasına ilişkin notunda bu konuda şunları yazıyor:

Kanıtlarında Hilbert ve Lynch tutarlılık yerine atomiklik terimini kullanırlar ki bu teknik açıdan daha anlamlıdır çünkü tam anlamıyla ASİT anlamındaki tutarlılık, veritabanı işlemlerinin ideal özelliklerini ifade eder ve hiçbir verinin olmayacağı anlamına gelir. önceden belirlenmiş bazı kısıtlamaları ihlal ederlerse ısrarcı olurlar. Ancak, dağıtılmış sistemlerin önceden belirlenmiş bir sınırlamasının, aynı veri öğesi için birkaç farklı değerin varlığının yasaklanması olduğunu varsayarsak, o zaman bence tutarlılık soyutlamasındaki bu kusur düşünülebilir. önemsiz (ek olarak, Brewer atomiklik terimini kullanırsa, adını telaffuz etmesi son derece elverişsiz olacak olan AAP teoremi görünecektir).

Bu çok ciddi değil, dürüstçe yazılmıştır. Ve aslında, atomik tutarlılık gerekliliği, ASİT anlamında işlemsel tutarlılık gereklilikleri ile karıştırılmamalıdır. Veritabanı bütünlüğü kısıtlamaları mantıklıdır, isterseniz iş gereksinimleridir. Uygulama etki alanı mantığından gelirler. Atomik tutarlılık gerekliliği çok farklı türdendir. Bu, veritabanı endüstrisinde geleneksel olarak fiziksel tutarlılık olarak adlandırılan kategoriye giren bir uygulama gereksinimidir (örneğin, herhangi bir dizin değiştirme işlemi gerçekleştirirken, karşılık gelen B+ ağacının tüm blokları geçerli değerler içermeli ve geçerli referanslarla bağlanmalıdır. ).

Ve veritabanı topluluğu Daniel Abadi ve Alexander Thomson'ın temsilcileri notlarında oldukça ciddi bir şekilde şunları yazıyorlar:

... ölçeklenebilir işlem sistemlerinin kullanılabilirliği gereksinimi giderek daha kritik hale geliyor ve bu genellikle düğümlerden birinin arızalanması durumunda isteklerin çoğaltılması ve otomatik olarak yeniden yönlendirilmesi yoluyla karşılanıyor. Bu nedenle, uygulama geliştiricileri, ACID sistemlerinin (başlangıçta kullanıcı tanımlı değişmezler için yerel destekten oluşan) tutarlılık garantilerinin, güçlü bir tutarlılık sağlamak için genişletilmesini beklemektedir (herhangi bir zamanda aynı verilerin tüm kopyalarının aynı kopyalar olması, örn. bu durumda tutarlılık, CAP/PACELC anlamında ima edilir.

Başka bir deyişle, Brewer tutarlılığının ACID anlamında tutarlılıkla hiçbir ilgisi yoktur, ancak veri çoğaltma yoluyla yüksek kullanılabilirlik sağlamaya odaklanan sistemlerde, güçlü çoğaltma tutarlılığının sürdürülmesi arzu edilir. Bu bir ACID özelliği değil, uygulama geliştirmeyi kolaylaştıran büyük ölçüde paralel DBMS'nin teknik (fiziksel) bir özelliğidir.

Michael Stonebreaker'a göre, yüksek kaliteli modern bir DBMS oluşturmanın anahtarı, teknik tavizlerin doğru seçimidir. Spesifik bir mühendislik çözümü seçerken, birçok faktör dikkate alınmalıdır - gelecekteki kullanıcıların gereksinimleri, çeşitli arıza durumlarının olasılığı vb.

Stonebreaker, işlemsel paralel veritabanı sistemleri alanında, yüksek kullanılabilirlik ve ağ bölümü toleransını desteklemek adına Brewer'ın tutarlılığından vazgeçmenin zayıf bir değiş tokuş olduğuna inanıyor çünkü (a) çoğaltma tutarlılığı, sistemin çok yararlı bir özelliğidir; (b) işlemsel büyük ölçüde paralel DBMS, çok sayıda düğüme sahip kümelere ihtiyaç duymaz, bu nedenle ağ bölünmesi durumları pek olası değildir; (c) sistem, bir ağ bölümü nedeniyle değil, örneğin düzenli olarak meydana gelen yazılım hatalarının varlığı nedeniyle kolayca kullanılamaz hale gelebilir.

Bu nedenle, genellikle Brewer'ın "teoremine" atıfta bulunan NoSQL kampının (NoACID'yi okuyun) temsilcilerinin yüksek etkinliği, ACID işlemlerini destekleyen büyük ölçüde paralel işlemsel DBMS oluşturmanın teorik imkansızlığıyla değil, basitleştirilmiş sistemlerle bağlantılıdır. sadece ACID işlemlerini değil, aynı zamanda replika tutarlılığı da destekleyen, daha kolay ve daha hızlı oluşturulur. Basit organizasyonları nedeniyle, çok hızlı veri işleme yeteneğine sahiptirler ve bazı uygulamalar için bu, veritabanı teknolojisinin doğasında bulunan tüm kolaylıklardan daha önemlidir.

Veritabanı topluluğunun bu zorluğa nasıl yanıt verdiğini görelim.

Yorumlar
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION