Raft Mutabakat Algoritması (2015)

 (raft.github.io)
3 puan yazan GN⁺ 2023-09-04 | 1 yorum | WhatsApp'ta paylaş
  • Raft, dağıtık sistemlerde birden çok sunucunun aynı kararı vermesini sağlayan mutabakat sorununu daha anlaşılır kılmak için tasarlandı; hata toleransı ve performans açısından Paxos ile eşdeğer olmayı hedefler
  • Raft; lider seçimi, log çoğaltma ve güvenlik gibi alt problemlere bölünerek çoğaltılmış durum makinesi uygulaması için gereken karar noktalarını netleştirir
  • Sunucuların çoğunluğu ayaktaysa ilerleyebilir; çoğunluk kaybolduğunda dursa bile hatalı sonuç üretmeyerek güvenliği korur
  • Sitede tarayıcı tabanlı RaftScope ve The Secret Lives of Data görselleştirmesi, Raft makalesi, TLA+ belirtimi, doğrulama/analiz makaleleri ve sunum materyalleri bir araya getirilmiş
  • Rust, Go, Java, C++, C#, Python gibi çeşitli dillerdeki uygulamalar listelenmiş; her uygulamanın lider seçimi/log çoğaltma, kalıcılık, üyelik değişikliği ve log sıkıştırma desteği farklılık gösterir

Raft’ın hedeflediği mutabakat sorunu

  • Raft, mutabakat algoritmasını daha geniş bir okur kitlesinin anlayabileceği hale getirmek için tasarlandı
  • Hata toleransı ve performansta Paxos ile eşdeğer bir seviyeyi hedefler
  • Temel fark yapısındadır
    • Sorunu görece bağımsız alt problemlere böler
    • Gerçek sistem uygulamaları için gereken bileşenleri ayırarak ele alır
  • Amaç, mutabakat tabanlı sistemlerin daha kolay anlaşılmasını ve daha yüksek kalitede uygulanmasını sağlamaktır

Mutabakat ve çoğaltılmış durum makinesi

  • Mutabakat (consensus), hata toleranslı dağıtık sistemlerin temel problemidir
  • Birden çok sunucu tek bir değer üzerinde anlaşır ve bir kez kararlaştırılan değer nihai durum olur
  • Tipik mutabakat algoritmaları, sunucuların çoğunluğu kullanılabilir olduğunda ilerler
    • 5 sunuculu bir küme, 2 sunucu arızalansa bile çalışmaya devam edebilir
    • Daha fazla sunucu arızalanırsa ilerleme durur
    • Bu durumda bile hatalı sonuç döndürmemek önemlidir
  • Mutabakat genellikle çoğaltılmış durum makinesi oluşturmak için kullanılır
    • Her sunucunun bir durum makinesi ve log’u vardır
    • Durum makinesi, hata toleransı kazandırılmak istenen bir hash tablosu gibi bir bileşen olabilir
    • İstemciler, bazı sunucular arızalansa bile tek bir güvenilir durum makinesiyle etkileşime giriyormuş gibi görebilir
  • Her durum makinesi, kendi log’undaki komutları girdi olarak alır
    • Hash tablosu örneğinde set x to 3 gibi bir komut log’a girer
    • Mutabakat algoritması, sunucu log’larına hangi komutların hangi sırayla konacağını belirler
    • Bir durum makinesi set x to 3 komutunu n’inci komut olarak uyguladıysa, başka bir durum makinesinin aynı konuma farklı bir komut uygulamamasını garanti etmelidir
  • Sonuç olarak tüm durum makineleri aynı komut dizisini işler ve aynı sonuç dizisine ve durum dizisine ulaşır

Raft’ı anlamak için görselleştirmeler

  • Tarayıcıda çalışan Raft kümesi görselleştirmesini doğrudan etkileşimli olarak kullanabilirsiniz
    • Solda 5 sunucu gösterilir
    • Sağda her sunucunun log’u gösterilir
    • Kullanıcı etkileşime girerek Raft’ın işleyişini görebilir
  • RaftScope hâlâ geliştirilmesi gereken birçok noktaya sahip ve Pull Request’ler memnuniyetle karşılanır
  • The Secret Lives of Data Raft’ı farklı biçimde gösteren bir görselleştirmedir
    • Daha yönlendirmelidir ve etkileşimi daha azdır
    • Konuyla ilk kez tanışan okurlar için daha yumuşak bir başlangıç noktası olabilir

Makale, belirtim ve doğrulama materyalleri

Sunumlar ve eğitim materyalleri

  • Raft’a giriş niteliğindeki sunumların listesi de birlikte derlenmiştir
    • John Ousterhout’un CS@Illinois Distinguished Lecture Series sunumu, Ağustos 2016
    • Jin Li’nin Dr. TLA+ Series kapsamında Raft ve TLA+ belirtimi sunumu, Temmuz 2016
    • Diego Ongaro’nun Build Stuff 2015, CoreOS Fest 2015, Sourcegraph meetup, LinkedIn, USENIX ATC 2014, CraftConf 2014, RICON West 2013 sunumları
    • Ben Johnson’ın Strange Loop 2013 sunumu
    • John Ousterhout’un Raft User Study dersi, Mart 2013
  • Üniversiteler ve eğitim programları da Raft’ı derslerde veya programlama ödevi olarak kullanır
    • University of Copenhagen, Czech Technical University in Prague, The University of Hong Kong, University of Virginia, UC San Diego, Technical University of Munich, UIUC gibi birçok program dahildir
    • Bazı programlar Go, Java, Erlang gibi dillerle Raft programlama ödevleri sunar
    • MIT 6.824, Raft ders notlarını içerir ve Jon Gjengset’in eğitmenlere ve öğrencilere yönelik Raft yazılarına da yönlendirir
  • Ek dersler, sitenin deposunda Pull Request veya issue ile güncellenebilir

Soru kanalları ve uygulama listesi

  • Raft ve uygulamalarıyla ilgili sorular için uygun yer olarak raft-dev Google group gösterilir
  • Bazı uygulamaların kendi mailing list’leri olduğundan her bir README’nin kontrol edilmesi gerekir
  • Açık kaynak kodu bulunan Raft uygulamaları listesi de sunulur
    • Popüler veya yakın zamanda güncellenmiş uygulamalar tablonun üst kısmına yerleştirilmiştir
    • Bilgiler zamanla eskiyebileceğinden Pull Request veya issue ile güncellenebilir
  • Tablo, uygulama bazında Stars, ad, başlıca yazar, dil, lisans ve özellik desteğini karşılaştırır
    • Özellik maddeleri lider seçimi ve log çoğaltma, kalıcılık, üyelik değişikliği ve log sıkıştırmadır
  • Üst sıralardaki uygulama örnekleri şunlardır
    • TiKV: Rust, Apache-2.0, 16,751★; lider seçimi/log çoğaltma, kalıcılık, üyelik değişikliği ve log sıkıştırmanın tamamını destekler
    • RethinkDB: C++, Apache-2.0, 27,000★; başlıca özelliklerin tamamını destekler
    • Seastar Raft: C++20, AGPL, 15,624★; başlıca özelliklerin tamamını destekler
    • hashicorp/raft: Go, MPL-2.0, 9,048★; başlıca özelliklerin tamamını destekler
    • hazelcast-raft: Java, Apache-2.0, 6,579★; başlıca özelliklerin tamamını destekler
  • Liste Rust, Go, Java, C++, C, Erlang, Python, Scala, C#, JavaScript, Haskell, OCaml, Kotlin, Zig, TypeScript, Elixir, F#, Shell gibi çeşitli dillerde uygulamalar içerir

İlgili okumalar

1 yorum

 
GN⁺ 2023-09-04
Hacker News yorumları

  • Jepsen’in yaratıcısının dağıtık sistemleri öğrenmek için hazırladığı çalışma tezgâhı Maelstrom, Raft’ın basit bir model denetimli uygulamasını ve uygulama eğitimini oldukça iyi içeriyor: https://github.com/jepsen-io/maelstrom/
    Raft basit bir algoritma, ama orijinal makalede oyuncak uygulamalarda sıkça atlanan pek çok doğruluk ayrıntısı var.
    Gerçek donanımdaki bellek/disk bozulmalarını ve gri arızaları, sıkı gecikme süresi SLA’larını, esnek quorum’ları ve dinamik küme üyeliğini de hesaba katınca üretim uygulaması uzun ve yorucu bir işe dönüşüyor.
    Yalnızca etcd ve hashicorp/raft’ın commit geçmişine bakmak bile, en çok doğrulanmış açık kaynak Raft uygulamalarında bile düzenli olarak doğruluk hatalarının ortaya çıktığını gösteriyor.
    TigerBeetle ekibi, kusurlu donanım ve soyutlanmamış sistem modeli altında dağıtık sistemlerin gerçekliğini ayrıntılı biçimde ele alıyor; ayrıca Paxos’tan daha eski olmasına rağmen Raft’a daha çok benziyor gibi görünen Viewstamped Replication’ı neden seçtiklerini de açıklıyor: https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/DE...

    • “Viewstamped Replication Paxos’tan daha eski olsa da Raft’a daha çok benziyor gibi görünüyor” kısmıyla ilgili olarak, Heidi Howard ve Richard Mortier’nin Paxos vs Raft makalesi, çoklu mutabakat Paxos’u ile Raft’ı birbirine çok yakın görünecek şekilde yan yana düzenliyor: https://doi.org/10.1145/3380787.3393681
      Uygulama tarafındaki kaygılar açısından ne sonuç doğurduğunu pek bilmiyorum, ama makalenin kendisi mükemmel; tavsiye ederim.
      Sunum da var, ama ileri geri referanslarla bakmak için yazılı metnin daha iyi olduğunu düşünüyorum: https://www.youtube.com/watch?v=0K6kt39wyH0
    • Viewstamped Replication makalesi şaşırtıcı derecede okunması kolaydı.
      Mutabakat algoritmalarını daha önce hiç görmemiş olmama rağmen birkaç kez okuduktan sonra bir ölçüde takip edebildim: https://dspace.mit.edu/bitstream/handle/1721.1/71763/MIT-CSA...
    • Heterojen ağ topolojilerini ve bazı üyelerin lider yapılınca gerçekten berbat olduğunu da unutmamak gerek.

  • Yakın zamanda Raft’ın lider seçimini ve log replikasyonunu uygulamayı denedim; snapshot/checkpoint aşamasına kadar gelemedim ama şimdiye kadar yaptığım projeler arasında en zorlarından biriydi.
    Raft makalesi okunması kolay ve sezgiyi iyi veriyor.
    Doğrudan uygulamasanız bile etcd, Consul, CockroachDB, TiDB gibi Raft tabanlı yazılımları zaten kullanıyor olma ihtimaliniz yüksek.
    Uygularken yararlı bulduğum kaynakları burada topladım: https://github.com/eatonphil/goraft#references
    Diego Ongaro’nun doktora tezi ve TLA+ belirtimi de dahil.
    “Raft makalesindeki Figure 2 yeterlidir” denir, ama TLA+ belirtimiyle karşılaştırınca çok daha muğlak olduğu için bunun doğru olmadığını düşünüyorum.

    • Görünüşte harika, ama gerçekten kapsamlı bir test suite’i yoksa çok sayıda ince hata olması kaçınılmaz.
      MIT dağıtık sistemler dersindeki Raft testleri ile bağlamayı öneririm: https://pdos.csail.mit.edu/6.824/labs/lab-raft.html
      En azından lider seçimi ve log replikasyonu tarafı, az miktarda refactoring ile mümkün görünüyor.
    • Lisans düzeyindeki ağ programlama dersinde Raft uygulamamız gerekiyordu; makalenin okunmasının kolay olduğu konusunda aynı deneyimi yaşadım.
      Özellikle dağıtık algoritmalarla ilk kez karşılaşanlara gerçekten tavsiye edilir.
      Uygulama kalitesi harika olmayabilir ama ilgilenenler için koydum: https://github.com/skowalak/fastapi-raft/
    • Figure 2 harika, ama Raft’ı uygulamak için makalenin tamamının gerektiğine katılıyorum.
      Uygulama sırasında gereken birkaç somut ayrıntı daha makalenin içinde var.

  • Mutabakat algoritmaları ilginizi çekiyorsa, dağıtık sistemler teorisi dersinde kullandığımız Reasoning about Knowledge adlı kitap da bakmaya değer: https://mitpress.mit.edu/9780262562003/reasoning-about-knowl...
    Modal mantığı öğrenmek için biraz yatırım yapmak gerekiyor, ama o kısmı aşınca Raft ya da Paxos’un neden çalıştığına dair ispatlar çok sezgisel ve basit hale geliyor.
    İspatın karmaşıklığını, ispata kullanılan mantıksal yapının içine iten bir yaklaşım; mutabakata bakışımı değiştirdi.

  • “Raft Consensus Algorithm Failure”, Théodore Géricault, 1819: https://classicprogrammerpaintings.com/post/6141087496359280...

    • Raft’ın TLA+ ispatı olduğuna göre “hatasız” olması gerekir; şaka olduğunu biliyorum ama gerçekten hata olup olmadığını merak ediyorum.

  • Görselleştirmenin ne gösterdiğini anlamıyorsanız, bir düğüme tıklayıp arıza oluşturabildiğinize bakmanız yeterli
    Özellikle şu anda lider olan, tüm paketleri gönderip alan düğümde denemek iyi olur
    İlk kaydırıcının yanındaki küçük duraklatma simgesine basıp tekrar saate çevirirseniz simülasyon devam eder
    Sağdaki elektronik tablonun ne olduğunu hâlâ bilmiyorum; hep boş olduğu için bozukmuş gibi görünüyor
    Şimdiye kadar bulduğum tıklanabilir öğeler iki kaydırıcı, saat/duraklatma simgesi ve tek tek sunucular

    • Sağdaki tablo her replikanın günlük durumunu gösteriyor
      Lidere tıklayıp request seçerseniz komut göndermeyi simüle edebilirsiniz
      Bir replikayı çevrimdışı bırakırsanız geride kaldığını, geri geldiğinde de arayı kapattığını görebilirsiniz

  • Birkaç yıl önce ciddi yük altında sağlam bir Chubby benzeri sistemin sürekli kritik olduğu bir ortamdaydım; o zaman başarısızlık kabul edilemiyorsa ZooKeeper kullanırdık
    Ama bugün insanların etcd, Consul gibi Raft tabanlı seçeneklerin üzerine yıllardır çok ağır işler bindirdiğini biliyorum
    Bunlardan birinin artık varsayılan tercih hâline gelip gelmediğini merak ediyorum
    Raft’ın kavramsal netliği ve zarafeti performansa ve güvenilirliğe dönüşecek gibi geliyor, ama bu alandaki sezgilerim eskidi
    2023’te Google’a ya da GCP’ye bağlı olmayan insanların yüksek öneme sahip sistemlerde varsayılan en iyi pratik olarak ne kullandığını merak ediyorum
    TikV tarafında yapılmış üretim seviyesinde bir Rust Raft uygulaması varmış gibi hatırlıyorum; sağlam ve yüksek performanslı bir kilit sunucusu Rust’a oldukça uygun bir alan gibi görünüyor, gerçekten kullanılıp kullanılmadığını da merak ediyorum

  • “Raft nedir?” sorusunun cevabı buysa, okuduktan sonra hâlâ bilmiyorum
    “Raft, anlaşılması kolay olacak şekilde tasarlanmış bir mutabakat algoritmasıdır. Hata toleransı ve performans açısından Paxos ile denktir. Farkı, görece bağımsız alt problemlere ayrılmış olması ve pratik sistemler için gereken ana kısımları temiz biçimde ele almasıdır. Raft’ın mutabakatı daha geniş bir okur kitlesine sunmasını ve bu kitlenin bugünkünden daha çeşitli, yüksek kaliteli mutabakat tabanlı sistemler geliştirebilmesini umuyoruz”
    Bu tarz şeyler yalnızca bunlara özgü bir sorun değil, ama kendi çalışmalarını düzgün açıklamak için daha fazla zaman harcamamalarını üzücü buluyorum

    • Bu açıklama aslında iyi bir açıklama da olabilir
      Çünkü ne anlama geldiğini bilmeyen okurları otomatik olarak eliyor
      Dağıtık sistemler kurarken çeşitli mutabakat algoritmalarını karşılaştıran biri için basit ve net bir açıklama; öyle değilse zaten ilgili bir algoritma olmama ihtimali yüksek
      Genel olarak mutabakat algoritmaları, birden çok fiziksel cihaz üzerinde veri deposu replikaları olduğunda ve cihazların ya da bağlantıların bir kısmı bir şekilde arızalandığında ne yapılacağını belirleme problemini çözmeye çalışır
      “Mutabakat” denmesinin nedeni, arıza durumunda makinelerin bir veri parçası hakkında hangi kararı verecekleri konusunda uzlaşmak zorunda olmalarıdır
      Örneğin üç sunucu aynı SQL veritabanını replike ediyor ve (A) - (B) - (C) biçimindeyse, C ile diğer ikisi arasındaki ağ bağlantısı koparsa A ve B bunu bilip B’yi birincil düğüme yükseltebilir
      Ama C ne olduğunu bilmez ve bazı yazmaları almaya devam edebilir
      Bağlantı geri geldiğinde A, B ve C artık ne yapacaklarına karar vermek zorundadır
      B ve C birbirinden farklı yazma kümelerini bağımsız olarak aldığı için, sunucuların verileri nasıl işleyecekleri konusunda mutabakata varması gerekir
      Raft, Paxos vb.’nin tutarlı ve performanslı bir şekilde çözmeye çalıştığı problem tam olarak budur
    • Bir sonraki paragraf olan “Durun, mutabakat nedir?” kısmına kadar okuyup okumadığınızı merak ediyorum
      Bazı kavramlar, hiç arka plan bilgisi olmayan birine tek paragrafta tanıtılamayacak kadar büyüktür
      Yine de bağlantı verilen yazının okumaya devam edildiğinde harika bir giriş kaynağı olduğunu düşünüyorum

  • Bir mutabakat protokolü araştırmacısı olarak, son 10 yıldaki blokzincir araştırmaları sayesinde mutabakatın çok daha anlaşılır hâle geldiğini düşünüyorum
    Raft ise özellikle incelikli kısımlar da dahil edildiğinde buna kıyasla Yunanca gibi okunuyor ve uygulanıyor
    Bugün mutabakat protokollerini ilk kez öğrenen birine Bitcoin’den başlayıp Paxos, Tendermint, Simplex’e geçmesini söyler, Raft’ı tamamen atlattırırdım
    Simplex benim yazdığım bir makale; PBFT’nin basitleştirilmiş bir sürümü

    • Mutabakat protokolü araştırmacısı değilim, ama blokzincir çok sayıda ek unsur, karmaşıklık ve maliyet getiriyor gibi görünüyor
      Raft görece basit görünüyor
      Blokzincirin, “lider seç ve günlüğü replike et”ten daha kolay bakım yapılabilir ve hata yapması daha zor olacak ne sunduğunu merak ediyorum

  • Bu siteyi seviyorum
    Dağıtık sistemler dersinde Raft’ı öğrenip uygularken bu sayfa gerçekten faydalı olmuştu
    Makalenin kendisi de epey okunabilir

    • Dağıtık sistemler dersi veriyorum ve bu siteyi referans materyallerden biri olarak kullanıyorum
      Raft’ı bu kadar anlaşılır hâle getirdiğiniz için teşekkürler

  • Değişikliklerin mutlaka lider üzerinden geçmesini gerektirmeyen bir mutabakat algoritması olup olmadığını merak ediyorum
    Birçok dağıtık sistemde girdi işlemeyi de dağıtmak istersiniz

    • Yüksek hata toleransını önceleyen ve bunun için lider sayısını ya da sorgu verisinin kopyasını almak için gereken asgari düğüm sayısını artıran algoritmalar vardır
      Bunlardan biri Chord’dur: https://en.m.wikipedia.org/wiki/Chord_(peer-to-peer)
      Chord, düğümlerin değerleri tutarlı hashing ile paylaştığı bir P2P halkasıdır
      Ağ, “finger table” denen bir şeyi kullanır; özünde replikasyon bilgisini tablo biçiminde saklar
      Bu tablodaki bilgi yanlış ya da eski olabilir; erişilen peer, değeri bulana ya da bulunamadığı anlaşılana kadar başka bir peer’a, genellikle bir sonraki düğüme veya ardıl düğüme gitmenizi söyleyebilir
      Bu algoritmanın “lider” olmadan da kullanılabilmesinin nedeni, sadece bir düğüme gidip tüm düğümleri doğrusal biçimde tarayan bir yöntemle de çalışabilmesidir
      Sorguları hızlandırmak için kullanılan finger table zorunlu değildir
    • Literatürde lidersiz protokoller vardır: EPaxos, Caesar, Tempo vb.
      Bu sistemlerde genellikle her işlem için bir “lider” vardır, ancak normal çalışmada bu rol için rekabet edilmez
      İşlem koordinatörü kendini ilan eder; seçim yalnızca koordinatör herhangi bir nedenle başarısız olduğunda yapılır
      Belirli bir veri ya da anahtar için aynı anda birden fazla lider de bulunabilir
      Cassandra şu anda bu aileden lidersiz bir protokol olan Accord’u geliştiriyor
      Aslında Cassandra, LWT için hâlihazırda lidersiz bir protokol kullanıyor
      Bu, klasik tekil mutabakat Paxos’un optimize edilmiş bir varyantıdır; ancak aynı anahtar için rakip işlemler eşzamanlı ilan edilirse ek yük oldukça yüksek olur
    • Bir lider seçip değişiklikleri lider üzerinden göndermek sistemi basitleştirir; çekişme olduğunda iş hacmi ve öngörülebilirliği iyileştirir
      İşlemler birbirinden bağımsız konulara yayılıyorsa liderleri shard’lara bölerek yükü dağıtabilirsiniz
      Bu, anahtar uzayı aralıklarını farklı liderlere atayıp her düğümün uygun liderlik payına sahip olacağı şekilde seçimleri ayarlama yöntemidir
      Lidersiz ilerlemek istiyorsanız her yazmayı fiilen bir seçim gibi kurgulayabilirsiniz
      Geçici işlem ya da işlem büyükse, işlem isteğini tüm düğümlere broadcast edip kabul yeter sayısını aldığında kazanarak commit etmek gibi
      Ancak birden fazla düğüm neredeyse aynı anda işlem denediğinde mutabakata varmak uzun sürebilir
      Çok sayıda düğüm varsa ve hepsinin aynı konuya yönelik bekleyen işlemleri bulunuyorsa, bir lider seçip tüm işlemleri lider üzerinden göndermek, her işlem için ayrı ayrı mutabakat kurmaktan çok daha hızlıdır
    • Paxos hiçbir düğümü diğerlerinden üstün tutmaz
      Ancak amaç iş hacmini artırmak için dağıtmaksa, Paxos’un gerektirdiği yeter sayı yerine tek bir liderin yeterli olduğu bir yöntem daha verimli olabilir
      Bu bir tahmin
      Paxos’ta da çağrılar her seferinde aynı yere giderse daha verimli olur
      Çünkü çekişmeyi ve yeniden oylamaları vb. önleyebilirsiniz
    • Shard başına Paxos ve shardmaster kullanan bir yaklaşım da vardır
      Özünde her shard’ın kendi Paxos mutabakatı bulunur