HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Raft algorithm: What's the meaning of concept `index`?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
meaningthewhatconceptraftalgorithmindex

Problem

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

Solution

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.

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.

Context

StackExchange Computer Science Q#97542, answer score: 5

Revisions (0)

No revisions yet.