50 Yıl Sonra, Two-Phase Locking Hâlâ En İyisi mi?

 (concurrencyfreaks.blogspot.com)
1 puan yazan GN⁺ 2023-10-01 | 1 yorum | WhatsApp'ta paylaş
  • 1976'da yayımlanan Two-Phase Locking(2PL), serializability'den daha güçlü olan Opacity'yi sağlasa da, aradan yaklaşık 50 yıl geçmesine rağmen okuma ölçeklenebilirliği ve ilerleme garantisi açısından hâlâ sınırları var
  • Birden çok kayıt içeren işlemleri basit kilit alma-bırakma kurallarıyla ele alırken güçlü yalıtım seviyesi sunduğu için ticari işlemsel veritabanlarında ve eşzamanlı veri yapılarında hâlâ yaygın biçimde kullanılıyor
  • Geleneksel 2PL'de karşılıklı dışlama kilitleri nedeniyle okumalar kendi aralarında da çakışabiliyor; reader-writer lock kullanılsa bile ikili arama ağacının kökü gibi okumaların yoğunlaştığı noktalarda read-indicator çekişmesi ortaya çıkıyor
  • 2PLSF, her reader'ın işaretini cache line'lara dağıtarak okuma kilidi alma sırasındaki çekişmeyi azaltıyor ve merkezi atomik sayacın fetch_and_add() işlemini yalnızca çakışan transaction'lara uyguluyor
  • No-Wait, Deadlock-detection ve Wait-Or-Die gibi 2PL türevleri live-lock veya ölçeklenebilirlik sorunlarını sürdürürken, 2PLSF hem okuma ölçeklenebilirliğini hem de starvation-free transaction sağlamayı hedefleyen bir iyileştirme sunuyor

2PL neden hâlâ önemli?

  • Two-Phase Locking(2PL), serializability sağlayan ilk genel amaçlı eşzamanlılık denetimlerinden biridir ve pratikte daha güçlü bir yalıtım seviyesi olan Opacity sunar
  • 2PL, Jim Gray ve arkadaşlarının makalesi ile 1976'da yayımlandı; fikrin kendisi daha da eski olabileceğinden neredeyse 50 yıllık bir teknik olarak ele alınıyor
  • Genel amaçlı eşzamanlılık denetimi, nesneler, kayıtlar ve tuple'lar gibi birden çok veri öğesi üzerinde all-or-nothing anlamı taşıyan transaction'ları mümkün kılan algoritmaları ifade eder
  • 2PL'nin avantajı sadeliği ve güçlü yalıtımıdır
    • Bir kaydı okumadan veya yazmadan önce, önce o kaydı koruyan kilit alınır
    • Transaction bitene kadar alınan kilitler tutulur; böylece tutarlı bir bakış oluşturulabilir

Basit kuralların yarattığı yalıtım

  • 2PL'de transaction sırasında her erişimde bir kilit alınır ve artık erişim kalmadığının bilindiği transaction sonunda tüm kilitler bırakılır
  • Bitiş anında erişilen verilerin tüm kilitleri elde tutulduğu için, ilgili transaction için bir linearization point oluşur
  • 50 yıl önce birçok veritabanı araştırmacısı, kayıt erişimi biter bitmez kilidin serbest bırakılabileceğini düşünüyordu; ancak bu tür eşzamanlılık denetimi serializable değildir
  • Bilinen ticari transaction veritabanları 2PL veya T/O, MVCC kombinasyonları kullanır
  • Eşzamanlı veri yapıları alanında linearizability fiilî standart gibidir ve birden çok düğüme tutarlı yazmak için genellikle yazma erişimlerinde 2PL benzeri bir yaklaşım gerekir
    • İstisna lock-free veri yapılarıdır, ancak doğru bir lock-free uygulama yazmanın zor olduğu vurgulanır

2PL'nin darboğazı: okuma ölçeklenebilirliği ve live-lock

  • 2PL'nin en büyük zayıflıkları okuma ölçeklenebilirliğinin düşüklüğü ve live-lock ilerleme garantisidir
  • Klasik 2PL, karşılıklı dışlama kilitleri etrafında tasarlandığı için iki iş parçacığı aynı kaydı yalnızca okusa bile çakışabilir; bunlardan biri ya da ikisi abort edilip yeniden başlatılabilir
  • Reader-writer lock'a geçildiğinde okumalar arası çakışma azalır, ancak kilit maliyeti ve bellek kullanımı artar
    • Karşılıklı dışlama kilidi, kilitli/serbest durumunu gösteren 1 bit ile uygulanabilir
    • Reader-writer lock ise bu bitin yanında, o anda okuma modunda kilidi tutan reader sayısını sayan bir sayaç gerektirir
    • Örneğin 7 bitlik sayaç en fazla 128 iş parçacığını ifade edebilir ve her kilit 1 bayt yer kaplayabilir
    • Veritabanında milyarlarca kayıt varsa, yalnızca kilitler için bile milyarlarca bayt gerekebilir
  • Daha büyük sorun ise sayaç çekişmesidir
    • Read-non-disjoint iş yüklerinde çok sayıda okuma aynı veri üzerinde yoğunlaşır
    • İkili arama ağacının kök düğümü, tüm işlemlerin alt düğümlere inmeden önce okumak zorunda olduğu tipik bir örnektir
    • 2PL'de köke her erişimde kilit almak gerekir ve reader-writer lock kullanılsa bile kök düğüm kilidinde ciddi çekişme oluşur

Mevcut yaklaşımlar ve ölçeklenebilir read-indicator

  • TLRW, Dave Dice ve Nir Shavit'in SPAA 2010'da sunduğu bir yaklaşımdır; reader-writer lock kullanarak karşılıklı dışlama kilitlerinden daha yüksek performans elde etse de iyimser eşzamanlılık denetimi kadar hızlı değildir
  • TLRW'ye benzer şekilde, her okuma erişiminin reader-writer lock içindeki tek bir değişken üzerinde çekiştiği bir uygulama Rank-based Relaxed AVL ikili arama ağacına uygulandığında, gerek yazma gerek okuma transaction'larının ölçeklenmesi büyük ölçüde düzleşir
  • Read-indicator çekişmesi, ölçeklenebilir bir read-indicator ile hafifletilebilir
    • Tercih edilen yöntem, her reader'ın gelişini ve ayrılışını ayrı bir cache line üzerinde işaretlediği bir reader-writer lock'tur
    • Böylece okuma kilidi alırken çekişme ortadan kalkar
    • Yazma kilidi almak isteyen iş parçacığı ise buna izin verilip verilmediğini görmek için tüm cache line'ları taramak zorunda kaldığından, yazma kilidi edinme maliyeti artar
  • NUMA Aware reader-writer locks, bu tekniği kullanan reader-writer lock algoritmalarını ele alır
    • Üç reader-writer lock algoritmasından ikisi yüksek ölçeklenebilirlik sağlasa da starvation-free değildir

2PLSF'nin reader-writer lock tasarımı

  • Two-Phase Locking Starvation-Free(2PLSF), okuma kilidi alımında iyi ölçeklenen ve ek özellikler sunan bir reader-writer lock ile uygulanmış bir eşzamanlılık denetimidir
  • 2PLSF'nin reader-writer lock'u, read-lock için iş parçacığı başına 1 bit ayırır
    • Bu bitler kendi cache line'larına yerleştirilir
    • Komşu kilitlerin read-indicator bitleriyle birlikte konumlandırılır
  • NUMA-aware reader-writer lock makalesinde olduğu gibi maliyet yazma kilidi alımına kaydırılır
    • Yazma kilidi birden çok cache line'ı taramak zorundadır
    • Bu sihirli bir çözüm değil, bir trade-offtur
  • Bu trade-off'un yararlı olmasının nedeni, çoğu iş yükünün read-heavy olması ve write-intensive iş yüklerinin bile kayıt arama aşaması gibi bölümlerde önemli miktarda zamanı okuma erişimlerine harcamasıdır
  • Geliştirilmiş reader-writer lock kullanıldığında 2PL, read-non-disjoint iş yüklerinde de ölçeklenebilir hâle gelebilir; ancak live-lock sorununun ayrıca çözülmesi gerekir

2PL türevlerinin bıraktığı ilerleme garantisi sorunları

  • Klasik 2PL'de çekişmenin nasıl ele alındığına göre No-Wait, Deadlock-detection ve Wait-Or-Die gibi başlıca türevler bulunur

  • No-Wait

    • Çakışma olduğunda ya kendi transaction'ı ya da karşı transaction abort edilir ve yeniden denenir
    • Yeniden deneme hemen yapılabilir ya da üstel backoff ile sonraya bırakılabilir
    • A kaydından sonra B'yi değiştirmek isteyen transaction ile B'den sonra A'yı değiştirmek isteyen transaction sürekli çakışırsa, ikisi de commit edemeden abort-restart döngüsüne girebilir; bu da live-lock progress anlamına gelir

  • Deadlock-detection

    • Kilitte bekleyen iş parçacıklarının listesi tutulur ve döngüler yani deadlock'lar tespit edilir
    • Reader-writer lock'ta her reader'ın kendi listesine sahip olması gerekir; ayrıca her listeyi koruyan bir karşılıklı dışlama kilidi de gerekir
    • Read-lock modunda kilit alınırken tüm reader listelerinin taranması gerektiğinden maliyet yükselir
    • Kuramsal olarak starvation-free olabilir, ancak starvation-free lock gerektirmesi ve kamuya açık yüksek ölçeklenebilir starvation-free reader-writer lock bulunmaması nedeniyle bu hedefle çelişir
    • Her reader için ayrı liste tutmak bellek kullanımını da artırabilir

  • Wait-Or-Die

    • Tüm transaction'lara bir sıra verilir ve kilit çakışmasında transaction zaman damgası ile kilit sahibinin zaman damgası karşılaştırılarak bekleme ya da abort kararı verilir
    • Karşılıklı dışlama kilitlerinde sahip bilgisi, kilidin içinde benzersiz iş parçacığı tanımlayıcısı olarak saklanabildiği için bu yaklaşım iyi çalışır
    • Reader-writer lock'ta aynı yöntemi kullanmak için her reader için thread-id gerekir
    • 256 iş parçacığını desteklemek için her reader-writer lock başına 8 bit × 256 = 256 bayt gerekir

Merkezi atomik sayaç darboğazı ve 2PLSF'nin farkı

  • Wait-Or-Die'ın daha büyük engeli, tüm transaction'ların benzersiz bir transaction ID'ye sahip olmak zorunda olmasıdır
    • Örneğin merkezi bir atomik değişkenden fetch_and_add() ile numara alınarak sıra üretilebilir
  • Modern CPU'ların çoğunda, çekişmeli bir atomik değişken üzerinde saniyede 40 milyondan fazla fetch_and_add() yapmak zordur
    • Bu sayı, Visa'nın günde yaklaşık 660 milyon transaction'ıyla karşılaştırıldığında büyük görünebilir
    • Ancak in-memory DBMS'ler veya eşzamanlı veri yapıları için yeterince büyük olmayabilir
    • Bir test makinesinde saniyede 20 milyon fetch_and_add() değerini aşmak zordu
  • Bu fetch_and_add() yalnızca yazma transaction'ları için değil, okuma transaction'ları dâhil tüm transaction'lar için gerektiğinden ölçeklenebilirliği sınırlar
  • TL2, okuma transaction'larının atomik fetch_and_add() yapmadan iyimser okuma gerçekleştirdiği bir yaklaşımdır
    • Okuma transaction'ları açısından yüz milyonlarca tps'e kadar ölçeklenebilir
    • Buna karşılık Wait-Or-Die tabanlı 2PL, 40M tps/sec sınırını aşamaz
  • 2PLSF yalnızca çakışmaya giren transaction'ları sıralar
    • Merkezi atomik değişkende fetch_and_add() yapan transaction sayısı azalır
    • Çakışmayan transaction'lar 40M tps platosuna takılmaz
    • Örneğin çakışmasız 200M tps çalışırken, yalnızca çakışan 40M tps fetch_and_add() sınırına bağlı kalabilir
    • Algoritma starvation-freedom sağlar

Kaynaklar ve nihai değerlendirme

  • 2PLSF algoritmasının kendisi burada ayrıntılı biçimde ele alınmasa da, starvation-free bir algoritma için görece basit olduğu değerlendiriliyor
  • Başvuru kaynakları olarak makale ve kaynak kod sunuluyor
  • 2PLSF ayrıca ACM makalesi ile de bağlantılı; Pedro Ramalhete, Andreia ve Pascal Felber'in geliştirdiği bir algoritma olarak özetleniyor
  • 2PLSF'nin hedefi, 2PL'nin en başından beri sahip olması gereken özelliklere yaklaşmak
    • Okumaların çakıştığı read-non-disjoint durumlarda bile iyi ölçeklenir
    • Blocking progress'in en güçlü biçimi olan starvation-free transaction sağlar
    • Bazı çakışma durumlarında da ölçeklenebilir kalabilir
  • 2PLSF kusursuz değil, ancak çakışma çözümü açısından TL2'den daha iyi olduğu değerlendiriliyor; mevcut 2PL ile farkı ise kazma ile hilti arasındaki farka benzetiliyor

İlgili okumalar

1 yorum

 
GN⁺ 2023-10-01
Hacker News yorumları
  • Bu konuda yeniyim ama ilginç buluyorum; dağıtması kolay bir tutarlılık çözümü olsa iyi olurdu.
    Dağıtık mikroservis mimarisinde birden fazla veri deposunu senkronize etmek ya da “tutarlı” tutmak için sektördeki en iyi uygulamanın ne olduğunu merak ediyorum.
    Birkaç gün önce tutarsızlık sorununu “settled timestamp” ile çözmeye çalıştım; hata raporu gelmeden zaman geçerse bunu geçerli bir kaydetme/commit olarak gören çok sürümlü bir yaklaşıma yakın. İki aşamalı commit’te ikinci aşamanın zaman olması gibi.
    Başka sunucuların saatlerini izleyip güncellenmezse o sunucunun settled timestamp’ine güvenmeme şeklinde çalışıyor; her güncellemede yanıt beklemek yerine yalnızca bir sonraki timestamp aralığını beklemek gerektiğinden, tutarlılığı çok sayıda sunucuya ölçeklemeyi amaçlıyordum.
    Rastgele güncellemeler gönderip alan 10 thread ile belirlenimsizliği test eden çok thread’li ve çok işlemli bir Python kodu yazdım: https://replit.com/@Chronological/InconsistencySimulation#ma...
    Bu simülasyonda okuma, tüm sunucuların bildirdiği timestamp’lerin minimumu; 10 saniye sonra her thread’e sayaç değerini sorduğunuzda bazen hepsi aynı değeri veriyor ama oldukça sık split-brain durumuna düşüyor.
    Dağıtık sistemlerde wall clock timestamp’lerinin sıralamayı belirlemek için uygun olmadığını, mantıksal saatler veya vektör saatler kullanmak gerektiğini biliyorum.
    Herhangi bir anda simülasyonun herkesin aynı sayıyı raporlamasını sağlayabilsem iyi olurdu. Bloomlang, eventual consistency’de geç gelen değerlerin sonucu etkileyip linearizable olmama sorununu çözmeye çalışıyor.
    Özellikle tutarlılığı koruyarak ölçeklenmekle ilgileniyorum, ama bu oldukça zor bir problem gibi görünüyor.
    • Sektördeki en iyi uygulama, dağıtık mikroservis mimarisi kullanmamaktır.
    • Dağıtık sistemlerin temel fikri, her düğümün yeniden oynattığı merkezi bir yazma sırası günlüğüne sahip olmaktır.
      Birden fazla sistem merkezi günlüğe sıralı olarak yazar ve günlük, istekleri bir anahtar-değer deposu gibi alır. Bu günlük tüm düğümlere kopyalanır; düğümler de günlüğü okuyup istenen karmaşık mantığı çalıştırır.
    • Gerçekten hem (a) dağıtık veri deposuna hem de (b) senkron tutarlılığa ihtiyacınız olup olmadığını yeniden değerlendirmeniz iyi olur. İkisinden birinden vazgeçmek bile işleri çok daha basitleştirir.
    • 5 yıl içinde TigerBeetle DB’nin tutarlı, yüksek işlem hacimli ve hataya dayanıklı dağıtık veritabanları için sektör standardı olacağını düşünüyorum.
    • Raft protokolüne bakın. Genelde protokol katmanında doğrudan entegre etmeye çalışmak yerine, seri hale getirilebilir olması gereken koordinasyon/veri için Raft uygulayan etcd gibi tutarlı bir depo kullanmak standart yaklaşımdır.
      Kubernetes etcd kullandığı için, güçlü tutarlılığa sahip bir anahtar-değer deposu olarak oldukça iyi ölçeklenir.
      “Birden fazla veri deposu” dediğiniz için heterojen veriler olduğunu ve CockroachDB gibi seçeneklerin uygun olmadığını varsayıyorum.
      Yeniyseniz bunu kendiniz yapmak risklidir. https://aphyr.com/ testler için bir tür referans niteliğinde ve eğitim açısından da harikadır. Dağıtık sistemleri Jepsen ile test edebilirsiniz, ancak Kyle’ın sağlam olduğunu gösterdiği veri depolarını kullanmak daha iyidir.
  • Bu yeni yaklaşımın Serializable Snapshot Isolation (SSI) ile nasıl karşılaştırıldığını merak ediyorum: https://wiki.postgresql.org/wiki/SSI
    Bu tekniklere çok aşina değilim, ama veritabanlarını çalışırken SSI bana geleceğin “daha iyi” iki aşamalı kilitlemesi gibi tanıtılmıştı. SSI’ın 2PLSF’den nasıl farklı olduğunu ve burada neden bahsedilmediğini merak ediyorum.
    • Yeni bir platform için bellek modeli oluşturuyorum; neredeyse tamamını copy-on-write, snapshot ve SSI etrafında tasarlıyorum.
      Ama dağıtık etkiler söz konusu olduğunda hâlâ kilitlere, iki aşamalı transaction’lara vb. ihtiyaç var. Şahsen bunları birbirinin alternatifi olmaktan çok birbirini tamamlayan özellikler olarak görüyorum.
  • Kilitleme algoritmaları harika, ancak uygulamadan önce gerçekten çok sayıda thread’in aynı kaynak için yarışması gerekip gerekmediğini bir adım geri çekilip düşünmek önemli.
    Bellek içi veri yapıları için bu doğal olabilir, ama harici bir veritabanı veya başka paylaşılan harici kaynaklarla uğraşıyorsanız daha iyi bir yol olabilir.
    Çoğu zaman istekleri batch işleyerek harici kaynağa daha düşük eşzamanlılık ve daha büyük payload’larla erişebilirsiniz. O kaynak batch’leri iyi işliyorsa gerekli eşzamanlılık ve kilitleme çok azalır.
    Örneğin Postgres kullanıyorsanız bağlantı sayısı azalır ve karmaşıklığı artıran PgBouncer’ı eklemeniz gerekmeyebilir.
    Ancak istekleri batch’lemek çoğu programlama diline pek uymaz. Go’nun kanalları veya Elixir’in process’leri gibi yüksek eşzamanlılık için optimize edilmiş diller bunu iyi yapabilir; ama her şeyi thread’lerle ele alan dillerde acı verici olabilir.
  • Yazarın 2PL’nin baştan böyle olması gerektiğini savunduğu 2PLSF makalesi: https://zenodo.org/record/7886718
  • HN’de paylaşılan tüm linklerin HTTPS linki olmasını şart koşan yeni bir politikaya gerçekten ihtiyacımız var.
    • Neden öyle olmalı? HTTP ile de gayet iyi çalışan eski ve yararlı birçok site var. HTTPS desteklediği halde HTTP linki paylaşılan durumlardan bahsediyorsanız katılıyorum.
    • Yalnızca salt okunur şekilde etkileşim kurduğumuz bir sitede HTTPS yerine HTTP linkini ziyaret etmenin ne gibi sonuçları olduğunu merak ediyorum. Bu bir güvenlik sorunu mu, yoksa gizlilik sorunu mu?
    • Firefox’u HTTPS-Only Mode ile çalıştırabilirsiniz: https://support.mozilla.org/en-US/kb/https-only-prefs
      HTTPS’ye yükseltilemeyen sitelerde uyarı çıkar; ikisini de destekleyen siteler ise doğrudan HTTPS sürümüne gider.
    • Eşzamanlılık algoritmalarıyla ilgili bir yazıyı okuduktan sonra aklınıza gelen şey bu alakasız gözlem mi oldu?
      Ayrıca HTTP linki iyi bir eşzamanlılık algoritması hakkındaysa yine de okurum.
    • Hâlâ birkaç yalnızca HTTP web sitesi var.
  • Wait-Or-Die’da transaction ID almak için gerçekten fetch_and_add gerekiyor mu? En başta bir transaction ID gerekip gerekmediğinden de şüpheliyim.

Amaç, etkin işlemler arasında rastgele ama tutarlı bir sıra koymak gibi görünüyor; böylece bir çakışma olduğunda kimin bekleyeceği ve kimin öldürüleceği konusunda birbirleriyle anlaşabiliyorlar. O zaman thread ID kullanılamaz mı?
Rastgele bir sayı da mümkün olabilir. Eşitliği “ölüm” olarak ele alırsanız, en kötü durumda iki işlem de gereksiz yere durdurulur ve yeni bir rastgele sayıyla yeniden dener
Bahsedilmemiş ama uzun süren işlemlerin kısa işlemler yüzünden aç kalmaması için daha eski işlemlere öncelik vermek istiyor gibi. Örneğin uzun bir işlem ortalama üç kısa işlemle çakışıyorsa ve her çakışmada kazanan fiilen rastgeleyse, uzun işlemin üçünde de kazanıp commit etme olasılığı yalnızca 1/8’dir
Ancak aç kalmayı önlemek için her seferinde daha eski işleme öncelik vermek gerekmez; çoğu durumda yeterlidir. Özellikle de yalnızca çok az daha eskiyse
Bu yüzden thread’ler arasındaki saat sapması veya başka tür hatalar olsa bile timestamp ya da cycle counter benzeri bir şey iyi çalışabilir. Eşitlikler thread ID ile bozulabilir ya da yine iki taraf da durdurulabilir

  • Thread ID yerine ULID kullanırdım: https://github.com/ulid/spec
    Bu duruma ve başka birçok duruma iyi uyuyor
  • İki aşamalı yöntem ile Paxos’u karşılaştırmak için bir çerçeve sunan harika bir makale: https://lamport.azurewebsites.net/video/consensus-on-transac...
    • Adlar çakışıyor ama iki aşamalı kilitleme, iki aşamalı commit’ten farklıdır
      İki aşamalı commit, Paxos ile karşılaştırılabilecek bir şeydir ve ikisi de mutabakat protokolleri kategorisine girer
      İki aşamalı kilitleme ise bir eşzamanlılık kontrol mekanizmasıdır
  • Sonsuza dek sürer ve asla kusursuz da değildir
    İlk kilit mesajı kaybolduğunda sorun, kaybolanın yanıt mesajı olmadığını nasıl bileceğinizdir
    Basit durumlarda GitHub veya Dropbox gibi sadece devam edip çakışmayı daha sonra ele alabilirsiniz. Bir veritabanıysa bol şans; bir bankaysa daha da fazla
  • Relaxed AVL tree’nin son görselini tam anlayamıyorum. Sağ uçta, yani %100 okuma durumunda TL2 algoritmasının thread sayısıyla doğrusal ölçeklenmesi gerekiyormuş gibi geliyor
    Salt okunur işlemlerde TL2, global sürümü örnekledikten sonra tüm okumalar için yerel sürümün örneklenen sürümden küçük ya da ona eşit olduğunu kontrol etse yeterli
    O halde grafiğin neden doğrusalın altında kaldığını ve TL2’nin neden diğer STM uygulamaları kadar hızlı olmadığını anlamak zor
    • TL2 için öyle bir grafik göremiyorum. Bunun yerine TLRW grafiği görünüyor; TLRW reader lock kullandığı için ölçeklenebilirlik sınırı var
  • Rastgeleleştirilmiş bir kuyruk eklemek sorunu basitçe çözebilir
    Örneğin normalde 1000 iş ve 10–100 donanım thread’i olduğunu varsayalım
    1000 işten oluşan sıralı tek bir liste yapıp, her thread için bunun bir kopyasını oluşturur ve her seferinde kopyanın sırasını rastgeleleştirirsiniz
    Böylece her thread kendi listesini okuyup işi çalıştırdıktan sonra, bloklamayan çok thread’li bir kuyruk olarak uygulanmış tek bir listeye abone olabilir
    En kötü durumda bazı thread’ler belirli bir işi tekrar tekrar yapabilir
    Bu yöntemle atomik işlemler 1000 kata kadar ölçeklenebilir