Programlama

Çoğaltılan Günlük

Küme düğümleri bir İleri Yazma Günlüğü. Her günlük girişi, kullanıcı isteğiyle birlikte fikir birliği için gereken durumu saklar. Tüm küme düğümlerinin tam olarak aynı İleri Yazma günlüğüne sahip olması için günlük girişleri üzerinde fikir birliği oluşturmak için koordine olurlar. İstekler daha sonra günlüğün ardından sırayla yürütülür. Tüm küme düğümleri her günlük girişinde anlaştıkları için aynı istekleri aynı sırayla yürütürler. Bu, tüm küme düğümlerinin aynı durumu paylaşmasını sağlar.

Her durum değişikliği talebi için iki aşamanın yürütülmesi verimli değildir. Bu nedenle, küme düğümleri başlangıçta bir lider seçer. Lider seçim aşaması, Nesil Saat
ve önceki tüm günlük girişlerini algılar yeter sayı. (Önceki liderin küme düğümlerinin çoğuna kopyalamış olabileceği girişler.) Kararlı bir lider olduğunda, yalnızca lider çoğaltmayı koordine eder. Müşteriler liderle iletişim kurar. Lider, her isteği günlüğe ekler ve tüm takipçilerde çoğaltılmasını sağlar. Bir günlük girişi, takipçilerin çoğuna başarıyla kopyalandığında fikir birliğine varılır. Bu şekilde, istikrarlı bir lider olduğunda, her durum değişikliği operasyonu için fikir birliğine varmak için yalnızca bir aşama yürütmesi gerekir.

Aşağıdaki bölümler, Raft’ın çoğaltılmış bir günlüğü nasıl uyguladığını açıklar.

İstemci isteklerini çoğaltma

Şekil 1: Çoğaltma

Her günlük girişi için lider, bunu yerel İleriye Yazma günlüğüne ekler ve ardından tüm takipçilere gönderir.

lider (sınıf ReplicatedLog…)

  private Long appendAndReplicate(byte[] data) {
      Long lastLogEntryIndex = appendToLocalLog(data);
      replicateOnFollowers(lastLogEntryIndex);
      return lastLogEntryIndex;
  }


  private void replicateOnFollowers(Long entryAtIndex) {
      for (final FollowerHandler follower : followers) {
          replicateOn(follower, entryAtIndex); //send replication requests to followers
      }
  }

Takipçiler, çoğaltma isteğini işler ve günlük girişlerini yerel günlüklerine ekler. Günlük girişlerini başarıyla ekledikten sonra, lidere sahip oldukları en son günlük girişinin dizini ile yanıt verirler. Yanıt aynı zamanda mevcut Nesil Saat sunucunun.

Takipçiler ayrıca girişlerin zaten var olup olmadığını veya çoğaltılmakta olan girişlerin ötesinde girişler olup olmadığını kontrol eder. Zaten mevcut olan girdileri yok sayar. Ancak, farklı nesillere ait girişler varsa, çakışan girişleri kaldırırlar.

takipçi (sınıf ReplicatedLog…)

  void maybeTruncate(ReplicationRequest replicationRequest) {
      replicationRequest.getEntries().stream()
              .filter(entry -> wal.getLastLogIndex() >= entry.getEntryIndex() &&
                      entry.getGeneration() != wal.readAt(entry.getEntryIndex()).getGeneration())
              .forEach(entry -> wal.truncate(entry.getEntryIndex()));
  }

takipçi (sınıf ReplicatedLog…)

  private ReplicationResponse appendEntries(ReplicationRequest replicationRequest) {
      List<WALEntry> entries = replicationRequest.getEntries();
      entries.stream()
              .filter(e -> !wal.exists(e))
              .forEach(e -> wal.writeEntry(e));
      return new ReplicationResponse(SUCCEEDED, serverId(), replicationState.getGeneration(), wal.getLastLogIndex());
  }

Takipçi, istekteki nesil numarası sunucunun bildiği en son nesilden daha düşük olduğunda çoğaltma talebini reddeder. Bu, lideri istifa etmesi ve takipçisi olması konusunda bilgilendirir.

takipçi (sınıf ReplicatedLog…)

  Long currentGeneration = replicationState.getGeneration();
  if (currentGeneration > request.getGeneration()) {
      return new ReplicationResponse(FAILED, serverId(), currentGeneration, wal.getLastLogIndex());
  }

Lider, yanıtlar alındığında her sunucuda çoğaltılan günlük dizinlerinin kaydını tutar. Başarıyla kopyalanan günlük girişlerini izlemek için kullanır. yeter sayı
ve dizini bir commitIndex olarak izler. commitIndex Yüksek Su İşareti günlükte.

lider (sınıf ReplicatedLog…)

  logger.info("Updating matchIndex for " + response.getServerId() + " to " + response.getReplicatedLogIndex());
  updateMatchingLogIndex(response.getServerId(), response.getReplicatedLogIndex());
  var logIndexAtQuorum = computeHighwaterMark(logIndexesAtAllServers(), config.numberOfServers());
  var currentHighWaterMark = replicationState.getHighWaterMark();
  if (logIndexAtQuorum > currentHighWaterMark && logIndexAtQuorum != 0) {
      applyLogEntries(currentHighWaterMark, logIndexAtQuorum);
      replicationState.setHighWaterMark(logIndexAtQuorum);
  }

lider (sınıf ReplicatedLog…)

  Long computeHighwaterMark(List<Long> serverLogIndexes, int noOfServers) {
      serverLogIndexes.sort(Long::compareTo);
      return serverLogIndexes.get(noOfServers / 2);
  }

lider (sınıf ReplicatedLog…)

  private void updateMatchingLogIndex(int serverId, long replicatedLogIndex) {
      FollowerHandler follower = getFollowerHandler(serverId);
      follower.updateLastReplicationIndex(replicatedLogIndex);
  }

lider (sınıf ReplicatedLog…)

  public void updateLastReplicationIndex(long lastReplicatedLogIndex) {
      this.matchIndex = lastReplicatedLogIndex;
  }

Tam çoğaltma

Tüm küme düğümlerinin, bağlantı kesilseler veya çöküp geri gelseler bile, liderden tüm günlük girişlerini almasını sağlamak önemlidir. Raft, tüm küme düğümlerinin liderden tüm günlük girişlerini almasını sağlamak için bir mekanizmaya sahiptir.

Raft’taki her çoğaltma isteğiyle, lider aynı zamanda günlük dizini ve çoğaltılan yeni girdilerin hemen öncesindeki günlük girdilerinin oluşturulmasını da gönderir. Önceki günlük dizini ve terimi yerel günlüğüyle eşleşmezse, takipçiler isteği reddeder. Bu lidere, bazı eski girişler için takipçi günlüğünün senkronize edilmesi gerektiğini gösterir.

takipçi (sınıf ReplicatedLog…)

  if (!wal.isEmpty() && request.getPrevLogIndex() >= wal.getLogStartIndex() &&
           generationAt(request.getPrevLogIndex()) != request.getPrevLogGeneration()) {
      return new ReplicationResponse(FAILED, serverId(), replicationState.getGeneration(), wal.getLastLogIndex());
  }

takipçi (sınıf ReplicatedLog…)

  private Long generationAt(long prevLogIndex) {
      WALEntry walEntry = wal.readAt(prevLogIndex);

      return walEntry.getGeneration();
  }

Böylece lider, matchIndex değerini azaltır ve alt dizinde günlük girişleri göndermeyi dener. Bu, takipçiler çoğaltma isteğini kabul edene kadar devam eder.

lider (sınıf ReplicatedLog…)

  //rejected because of conflicting entries, decrement matchIndex
  FollowerHandler peer = getFollowerHandler(response.getServerId());
  logger.info("decrementing nextIndex for peer " + peer.getId() + " from " + peer.getNextIndex());
  peer.decrementNextIndex();
  replicateOn(peer, peer.getNextIndex());

Önceki günlük dizini ve oluşturma üzerindeki bu kontrol, liderin iki şeyi algılamasını sağlar.

  • Takipçi günlüğünde eksik girişler varsa. Örneğin, takipçi günlüğünde yalnızca bir giriş varsa ve lider üçüncü girişi çoğaltmaya başlarsa, lider ikinci girişi çoğaltana kadar istekler reddedilecektir.
  • Günlükteki önceki girişler farklı bir nesildense, lider günlüğündeki karşılık gelen girişlerden daha yüksek veya daha düşükse. Lider, istekler kabul edilinceye kadar girişleri alt dizinlerden kopyalamayı deneyecektir. Takipçiler, neslin eşleşmediği girişleri keser.

Bu şekilde lider, eksik girişleri veya çakışan girişleri tespit etmek için önceki dizini kullanarak sürekli olarak kendi günlüğünü tüm takipçilere göndermeye çalışır. Bu, tüm küme düğümlerinin, bağlantıları bir süreliğine kesilseler bile, sonunda liderden tüm günlük girişlerini almasını sağlar.

Raft’ın ayrı bir taahhüt mesajı yoktur, ancak normal çoğaltma isteklerinin bir parçası olarak commitIndex’i gönderir. Boş çoğaltma istekleri de sinyal olarak gönderilir. Böylece commitIndex, kalp atışı isteklerinin bir parçası olarak takipçilere gönderilir.

Günlük girişleri, günlük sırasına göre yürütülür

Lider commitIndex’ini güncelledikten sonra, commitIndex’in son değerinden commitIndex’in en son değerine kadar günlük girişlerini sırayla yürütür. İstemci istekleri tamamlanır ve günlük girişleri yürütüldüğünde yanıt istemciye döndürülür.

sınıf ReplicatedLog…

  private void applyLogEntries(Long previousCommitIndex, Long commitIndex) {
      for (long index = previousCommitIndex + 1; index <= commitIndex; index++) {
          WALEntry walEntry = wal.readAt(index);
          var responses = stateMachine.applyEntries(Arrays.asList(walEntry));
          completeActiveProposals(index, responses);
      }
  }

Lider ayrıca, takipçilere gönderdiği kalp atışı istekleriyle birlikte commitIndex’i de gönderir. Takipçiler commitIndex’i günceller ve girişleri aynı şekilde uygular.

sınıf ReplicatedLog…

  private void updateHighWaterMark(ReplicationRequest request) {
      if (request.getHighWaterMark() > replicationState.getHighWaterMark()) {
          var previousHighWaterMark = replicationState.getHighWaterMark();
          replicationState.setHighWaterMark(request.getHighWaterMark());
          applyLogEntries(previousHighWaterMark, request.getHighWaterMark());
      }
  }

Lider Seçimi

Lider seçimi, bir önceki nisapta işlenen log girişlerinin tespit edildiği aşamadır. Her küme düğümü üç durumda çalışır: aday, lider veya takipçi. Küme düğümleri, bir takipçi durumunda başlar ve bir kalp atışı mevcut bir liderden. Takipçi, belirlenen süre içerisinde herhangi bir liderden haber alamazsa aday durumuna geçer ve lider seçimine başlar. Lider seçim algoritması yeni bir Nesil Saat
değer. Raft şu anlama gelir: Nesil Saat olarak terim.

Lider seçim mekanizması ayrıca, seçilen liderin, yeter sayı tarafından şart koşulan güncel günlük girişlerine sahip olmasını sağlar. tarafından yapılan bir optimizasyondur. Sal
öncekinden günlük girişlerini önler yeter sayı
yeni lidere transfer ediliyor.

Eş sunucuların her birine oy talep eden bir mesaj gönderilerek yeni lider seçimi başlatılır.

sınıf ReplicatedLog…

  private void startLeaderElection() {
      replicationState.setGeneration(replicationState.getGeneration() + 1);
      registerSelfVote();
      requestVoteFrom(followers);
  }

Bir sunucu belirli bir zamanda oylandığında Nesil Saat, aynı oy her zaman o nesil için döndürülür. Bu, başarılı bir seçim gerçekleştiğinde, aynı nesil için oy talep eden başka bir sunucunun seçilmemesini sağlar. Oy talebinin işlenmesi şu şekilde gerçekleşir:

sınıf ReplicatedLog…

  VoteResponse handleVoteRequest(VoteRequest voteRequest) {
      //for higher generation request become follower.
      // But we do not know who the leader is yet.
      if (voteRequest.getGeneration() > replicationState.getGeneration()) {
          becomeFollower(LEADER_NOT_KNOWN, voteRequest.getGeneration());
      }

      VoteTracker voteTracker = replicationState.getVoteTracker();
      if (voteRequest.getGeneration() == replicationState.getGeneration() && !replicationState.hasLeader()) {
              if(isUptoDate(voteRequest) && !voteTracker.alreadyVoted()) {
                  voteTracker.registerVote(voteRequest.getServerId());
                  return grantVote();
              }
              if (voteTracker.alreadyVoted()) {
                  return voteTracker.votedFor == voteRequest.getServerId() ?
                          grantVote():rejectVote();

              }
      }
      return rejectVote();
  }

  private boolean isUptoDate(VoteRequest voteRequest) {
      boolean result = voteRequest.getLastLogEntryGeneration() > wal.getLastLogEntryGeneration()
              || (voteRequest.getLastLogEntryGeneration() == wal.getLastLogEntryGeneration() &&
              voteRequest.getLastLogEntryIndex() >= wal.getLastLogIndex());
      return result;
  }

Sunucuların çoğunluğundan oy alan sunucu lider durumuna geçer. Çoğunluk, tartışıldığı gibi belirlenir. yeter sayı. Bir kez seçildikten sonra, lider sürekli olarak bir kalp atışı tüm takipçilere. Takipçiler bir şey almazsa kalp atışı
belirli bir zaman aralığında yeni bir lider seçimi tetiklenir.

Önceki nesilden günlük girişleri

Yukarıdaki bölümde tartışıldığı gibi, konsensüs algoritmalarının ilk aşaması, algoritmanın önceki çalıştırmalarında kopyalanmış olan mevcut değerleri tespit eder. Diğer bir önemli husus ise bu değerlerin liderin en son nesline ait değerler olarak önerilmesidir. İkinci aşama, değerin yalnızca mevcut nesil için değerlerin önerilmesi durumunda taahhüt edildiğine karar verir. Raft, günlükteki mevcut girişler için üretim numaralarını asla güncellemez. Bu nedenle, liderin takipçilerinden bazılarında eksik olan eski nesilden günlük girişleri varsa, bu girişleri yalnızca çoğunluk çoğunluğuna dayalı olarak taahhüt edilmiş olarak işaretleyemez. Bunun nedeni, şu anda kullanılamayan başka bir sunucunun, daha yüksek nesil ile aynı dizinde bir girişe sahip olabilmesidir. Lider, mevcut neslinden bir girişi çoğaltmadan düşerse, yeni lider bu girişlerin üzerine yazabilir. Yani Raft’ta yeni lider, görev süresi boyunca en az bir giriş yapmalıdır. Daha sonra önceki tüm girişleri güvenli bir şekilde gerçekleştirebilir. Raft’ın en pratik uygulamaları, lider seçiminden hemen sonra, liderin müşteri isteklerine hizmet etmeye hazır olduğu düşünülmeden önce, operasyonsuz bir giriş yapmaya çalışır. bkz. [raft-phd] ayrıntılar için bölüm 3.6.1.

Örnek bir lider seçimi

Beş sunucu, atina, bizans, siren, delphi ve ephesus düşünün. ephesus 1. nesil için liderdir. Kendisine, delphi’ye ve atina’ya kopyalanmış girişler vardır.

Şekil 2: Kayıp kalp atışı bir seçimi tetikler

Bu noktada ephesus ve delphi kümenin geri kalanından kopar.

Bizans’ın en az seçim zaman aşımına sahip olması nedeniyle seçim süresini artırarak seçimi tetikliyor. Nesil Saat 2. cyrene’nin nesli 2’den küçüktür ve ayrıca Bizans ile aynı log girişine sahiptir. Yani oyu veriyor. Ancak Atina’nın günlüğünde fazladan bir giriş var. Yani oyu reddediyor.

Bizans 3 oy çoğunluğu elde edemediği için seçimi kaybeder ve tekrar takipçi konumuna geçer.

Şekil 3: Kayıt güncel olmadığı için seçim kaybedildi

atina zaman aşımına uğrar ve bir sonraki seçimi tetikler. artırır Nesil Saat
3’e ve Bizans ve Cyrene’ye oy isteği gönderir. Hem bizans hem de siren, atina’ya göre daha düşük nesil sayısına ve daha az log girişine sahip oldukları için, her ikisi de oyu atina’ya verir. Atina oyların çoğunluğunu aldığında lider olur ve HeartBeats’i Bizans ve Cyrene’ye göndermeye başlar. Bizans ve siren, bir üst nesildeki liderden bir kalp atışı aldığında, nesillerini arttırırlar. Bu, Atina’nın liderliğini doğrular. atina daha sonra kendi kütüğünü bizans ve sirene kopyalar.

Şekil 4: Güncel günlüğe sahip düğüm seçimi kazanır

atina şimdi Entry2’yi 1. nesilden Bizans ve Cyrene’e kopyalıyor. Ancak önceki nesilden bir girdi olduğu için, Entry2 çoğunluk nisabında başarıyla çoğaltıldığında bile commitIndex’i güncellemez.

atina, yerel günlüğüne işlemsiz bir giriş ekler. 3. nesildeki bu yeni giriş başarıyla çoğaltıldıktan sonra, commitIndex’i günceller.

Efes geri gelirse veya ağ bağlantısını geri yükler ve cyrene’ye istek gönderir. Cyrene artık 3. nesil olduğu için istekleri reddeder. ephesus ret yanıtında yeni terimi alır ve takipçi olmak için geri adım atar.

Şekil 7: Liderin geri çekilmesi

İlgili Makaleler

Bir cevap yazın

E-posta hesabınız yayımlanmayacak.

Başa dön tuşu