2
$\begingroup$

When reading the description of Raft algorithm from Wikipedia, I noticed there is a special word index.

For web developer, index usually refers to database index.

  • When it comes to Raft algorithm, what does index mean? Is it similar with database index? e.g. B+ tree.

  • What is raft index used for?

Wikipedia: Raft

Log Matching: if two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index.

https://en.wikipedia.org/wiki/Raft_(computer_science)#Safety_rules_in_Raft

$\endgroup$
  • $\begingroup$ Presumably each log entry has an index. $\endgroup$ – Yuval Filmus Sep 20 '18 at 3:34
2
$\begingroup$

TL;DR Just as said by Yuval Filmus, a log index in Raft algorithm is just an integer that tells the position of a log entry in a series of log entries.


Here is a figure that show clearly the meaning of an index of a log entry in Raft algorithm. The figure is taken from the award-winning paper In Search of an Understandable Consensus Algorithm by the creaters of Raft algorithm.

logs in Raft algorithm

This usage of index is in accordance with the most common usage of index as in mathematics and computer programming, which is "a value that identifies and is used to locate a particular element within a data array or table" as said in its entry in dictionary.com. You can also check index notation.

Specifically, a log index in Raft algorithm is used by each server to identify the log entry that is numbered with that index in that server's log. All (indices for) committed log entries will always be consistent across all servers having those entries. Non-consistent (indices for) log entries across servers will be replicated or repaired, depending on the situations.

"For web developer, index usually refers to database index." It looks like that you come with a training in computer databases. As a web developer myself, I would not agree with you readily at all. Indices are used much more frequently to access array elements in everyday programming in just about every programming language. For example, in JavaScript, if there is an array persons=["alice", "bob", "Diego"], then we can use index 1 to access its second element "bob", persons[1]. You will find the same or similar usage that are also abundant in Java, C, C++, C#, Python, Ruby, Go, etc.

If you want to understand Raft algorithm, one of the best introductory material is the video presented by Diego Ongaro.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.