Lua Library to Implement Simplified Consensus Algorithms (Raft Light Type)

Lua library implementing simplified Raft consensus for embedded systems, featuring leader election, state replication, and configurable timers.

Brief Introduction

Lua Library to Implement Simplified Consensus Algorithms (Raft Light Type) (lua)
DESCRIPTION:
This library implements a simplified distributed consensus algorithm inspired by Raft, suitable for embedded or distributed systems with limited resources. It provides mechanisms for leader election, state replication, and log management, all with a simple and configurable interface.

ADDITIONAL NOTES:
The implementation is designed to be modular and easily integrable into embedded systems or lightweight servers. Communication between nodes is abstracted and can be adapted to various media (sockets, serial, radio). The library does not implement all Raft optimizations but provides a solid base for custom developments.

EXPLANATIONS:
- The node maintains an internal state with current term, command log, and role state (follower, candidate, leader).
- Leader election occurs via randomized timeouts to avoid collisions and vote requests to all other nodes.
- The leader periodically sends heartbeats (empty AppendEntries) to maintain control and replicate commands.
- Communication is based on serialized JSON messages for simplicity and readability.
- Timers are fundamental to manage election timeouts and heartbeat intervals, configurable to adapt to different network latencies.
- The library exposes functions to initialize the node, handle incoming messages, and send commands to replicate.

Example Code: lua

-- Lua library for simplified consensus algorithm like Raft light
-- Author: Senior Software Engineer
-- Description: implements leader election, log replication, and node state management

local socket = require("socket") -- LuaSocket for communication
local json = require("json") -- JSON library for serialization

local Raft = {}

-- Role constants
local ROLE_FOLLOWER = "follower"
local ROLE_CANDIDATE = "candidate"
local ROLE_LEADER = "leader"

-- Default configuration
local DEFAULT_ELECTION_TIMEOUT_MIN = 1500 -- ms
local DEFAULT_ELECTION_TIMEOUT_MAX = 3000 -- ms
local DEFAULT_HEARTBEAT_INTERVAL = 500 -- ms

-- Helper function to generate random timeout between min and max
local function random_timeout(min, max)
    return math.random(min, max)
end

-- Raft Node
local Node = {}
Node.__index = Node

function Node:new(config)
    -- Node configuration
    local o = {
        id = config.id, -- local node ID
        peers = config.peers, -- table {id -> {host, port}}
        currentTerm = 0,
        votedFor = nil,
        log = {}, -- array of commands {term, command}
        commitIndex = 0,
        lastApplied = 0,
        state = ROLE_FOLLOWER,
        votesReceived = {},
        electionTimeout = random_timeout(DEFAULT_ELECTION_TIMEOUT_MIN, DEFAULT_ELECTION_TIMEOUT_MAX),
        heartbeatInterval = DEFAULT_HEARTBEAT_INTERVAL,
        electionTimer = nil,
        heartbeatTimer = nil,
        socket = nil,
        lastHeartbeat = socket.gettime(),
        callbacks = {
            onCommit = config.onCommit or function() end,
            sendMessage = config.sendMessage or function() end
        }
    }
    setmetatable(o, self)
    return o
end

-- Initialize UDP socket for communication
function Node:initSocket()
    local udp = socket.udp()
    udp:settimeout(0) -- non-blocking
    udp:setsockname("*", self.peers[self.id].port)
    self.socket = udp
end

-- Send JSON message to peer
function Node:send(toId, message)
    local peer = self.peers[toId]
    if not peer then return end
    local msgStr = json.encode(message)
    self.socket:sendto(msgStr, peer.host, peer.port)
end

-- Broadcast message to all peers except self
function Node:broadcast(message)
    for peerId, _ in pairs(self.peers) do
        if peerId ~= self.id then
            self:send(peerId, message)
        end
    end
end

-- Reset election timer
function Node:resetElectionTimer()
    self.electionTimeout = random_timeout(DEFAULT_ELECTION_TIMEOUT_MIN, DEFAULT_ELECTION_TIMEOUT_MAX)
    self.electionTimer = socket.gettime() + self.electionTimeout / 1000
end

-- Reset heartbeat timer
function Node:resetHeartbeatTimer()
    self.heartbeatTimer = socket.gettime() + self.heartbeatInterval / 1000
end

-- Handle RequestVote RPC message
function Node:onRequestVote(msg, fromId)
    local granted = false
    if msg.term < self.currentTerm then
        granted = false
    else
        if msg.term > self.currentTerm then
            self.currentTerm = msg.term
            self.votedFor = nil
            self.state = ROLE_FOLLOWER
        end
        if (self.votedFor == nil or self.votedFor == fromId) and
           (msg.lastLogTerm > (self.log[#self.log] and self.log[#self.log].term or 0) or
           (msg.lastLogTerm == (self.log[#self.log] and self.log[#self.log].term or 0) and msg.lastLogIndex >= #self.log)) then
            granted = true
            self.votedFor = fromId
            self:resetElectionTimer()
        end
    end
    local reply = {
        type = "RequestVoteResponse",
        term = self.currentTerm,
        voteGranted = granted
    }
    self:send(fromId, reply)
end

-- Handle AppendEntries RPC message (heartbeat or replication)
function Node:onAppendEntries(msg, fromId)
    if msg.term < self.currentTerm then
        local reply = {type = "AppendEntriesResponse", term = self.currentTerm, success = false}
        self:send(fromId, reply)
        return
    end
    self.currentTerm = msg.term
    self.state = ROLE_FOLLOWER
    self.votedFor = nil
    self:resetElectionTimer()

    -- Check log matching
    local prevLogIndex = msg.prevLogIndex
    local prevLogTerm = msg.prevLogTerm
    if prevLogIndex > 0 then
        if not self.log[prevLogIndex] or self.log[prevLogIndex].term ~= prevLogTerm then
            local reply = {type = "AppendEntriesResponse", term = self.currentTerm, success = false}
            self:send(fromId, reply)
            return
        end
    end

    -- Append new entries
    for i, entry in ipairs(msg.entries) do
        local idx = prevLogIndex + i
        if self.log[idx] and self.log[idx].term ~= entry.term then
            -- truncate divergent log
            for j = #self.log, idx, -1 do
                table.remove(self.log, j)
            end
        end
        if not self.log[idx] then
            self.log[idx] = entry
        end
    end

    -- Update commitIndex
    if msg.leaderCommit > self.commitIndex then
        self.commitIndex = math.min(msg.leaderCommit, #self.log)
        self:applyLogEntries()
    end

    local reply = {type = "AppendEntriesResponse", term = self.currentTerm, success = true}
    self:send(fromId, reply)
end

-- Apply log commands up to commitIndex
function Node:applyLogEntries()
    while self.lastApplied < self.commitIndex do
        self.lastApplied = self.lastApplied + 1
        local entry = self.log[self.lastApplied]
        if entry then
            self.callbacks.onCommit(entry.command)
        end
    end
end

-- Start election
function Node:startElection()
    self.state = ROLE_CANDIDATE
    self.currentTerm = self.currentTerm + 1
    self.votedFor = self.id
    self.votesReceived = {[self.id] = true}
    self:resetElectionTimer()

    local lastLogIndex = #self.log
    local lastLogTerm = (lastLogIndex > 0) and self.log[lastLogIndex].term or 0

    local msg = {
        type = "RequestVote",
        term = self.currentTerm,
        candidateId = self.id,
        lastLogIndex = lastLogIndex,
        lastLogTerm = lastLogTerm
    }
    self:broadcast(msg)
end

-- Handle incoming messages
function Node:handleMessage(msgStr, fromHost, fromPort)
    local msg = json.decode(msgStr)
    if not msg or not msg.type then return end

    local fromId = nil
    for id, peer in pairs(self.peers) do
        if peer.host == fromHost and peer.port == fromPort then
            fromId = id
            break
        end
    end
    if not fromId then return end

    if msg.type == "RequestVote" then
        self:onRequestVote(msg, fromId)
    elseif msg.type == "RequestVoteResponse" then
        if self.state == ROLE_CANDIDATE and msg.term == self.currentTerm and msg.voteGranted then
            self.votesReceived[fromId] = true
            local votesCount = 0
            for _ in pairs(self.votesReceived) do votesCount = votesCount + 1 end
            if votesCount > (#self.peers // 2) then
                self.state = ROLE_LEADER
                self:resetHeartbeatTimer()
            end
        elseif msg.term > self.currentTerm then
            self.currentTerm = msg.term
            self.state = ROLE_FOLLOWER
            self.votedFor = nil
            self:resetElectionTimer()
        end
    elseif msg.type == "AppendEntries" then
        self:onAppendEntries(msg, fromId)
    elseif msg.type == "AppendEntriesResponse" then
        -- For simplicity, advanced replication is not handled
        if msg.term > self.currentTerm then
            self.currentTerm = msg.term
            self.state = ROLE_FOLLOWER
            self.votedFor = nil
            self:resetElectionTimer()
        end
    end
end

-- Function to be called periodically to handle timers and send heartbeat
function Node:tick()
    local now = socket.gettime()

    -- Receive messages
    while true do
        local msgStr, ip, port = self.socket:receivefrom()
        if not msgStr then break end
        self:handleMessage(msgStr, ip, port)
    end

    -- Handle election timeout
    if self.state ~= ROLE_LEADER and now >= self.electionTimer then
        self:startElection()
    end

    -- Handle heartbeat
    if self.state == ROLE_LEADER and now >= self.heartbeatTimer then
        local msg = {
            type = "AppendEntries",
            term = self.currentTerm,
            leaderId = self.id,
            prevLogIndex = #self.log,
            prevLogTerm = (#self.log > 0) and self.log[#self.log].term or 0,
            entries = {}, -- empty heartbeat
            leaderCommit = self.commitIndex
        }
        self:broadcast(msg)
        self:resetHeartbeatTimer()
    end
end

-- Append command to log (leader only)
function Node:appendCommand(command)
    if self.state ~= ROLE_LEADER then
        return false, "Not leader"
    end
    local entry = {term = self.currentTerm, command = command}
    table.insert(self.log, entry)
    -- For simplicity immediate commit
    self.commitIndex = #self.log
    self:applyLogEntries()
    return true
end

-- Public API
Raft.Node = Node

return Raft
×
×
×
Do you want to regenerate the answer?
×
Export chat
Choose export format
Generazione PDF in corso…
Allegati
×
You are about to close the chat and switch to the image generator. If you are not logged in, you will lose our chat. Do you confirm?
You are viewing a shared chat in temporary mode. It will not be saved.
×
Saved prompts
×
Private note
×
Label
×
Search all chats
×
Your insights
Analyzing…
×
AI Preferences
Assistant name 30
Answer length
AI model
Structured answers
Include examples
Use emojis
Guide me, don't solve Hints and questions instead of a ready answer
More settings →
×
Share this chat
Anyone opening this link can view the chat or add it to their profile as their own chat.
Note: the chat attachments will be shared too. Anyone who adds it will receive a copy of the files in their own folder.
Shared chat
Someone shared a chat with you. Do you want to just view it or add it to your chats?
Note: the chat attachments will be shared too. Anyone who adds it will receive a copy of the files in their own folder.
×

Saved messages

Loading...

×

Chat History

example-programs · CHAT HISTORY

Loading...

AI Preferences

×
  • BasicQuick and essential answers for study
  • MediumHigher quality for study and programming
  • AdvancedComplex reasoning and detailed analysis
Explain Steps

Complete Example

-- Example usage of the Raft library
-- This example creates two nodes that communicate locally via UDP
-- and demonstrates leader election and heartbeat messages.

local Raft = require("raft") -- assuming the provided code is saved as raft.lua
local socket = require("socket")
local json = require("json")

-- Define two nodes with local UDP ports
local peers = {
    [1] = {host = "127.0.0.1", port = 5001},
    [2] = {host = "127.0.0.1", port = 5002}
}

-- Callback to print committed commands
local function onCommit(command)
    print("Committed command:", command)
end

-- Callback to send messages (not used here, socket send is done internally)
local function sendMessage() end

-- Create two nodes
local node1 = Raft.Node:new({id = 1, peers = peers, onCommit = onCommit, sendMessage = sendMessage})
local node2 = Raft.Node:new({id = 2, peers = peers, onCommit = onCommit, sendMessage = sendMessage})

-- Initialize sockets
node1:initSocket()
node2:initSocket()

-- Reset timers
node1:resetElectionTimer()
node2:resetElectionTimer()

-- Simple event loop to run nodes and simulate network
local function runNodes(nodes, durationSeconds)
    local startTime = socket.gettime()
    while socket.gettime() - startTime < durationSeconds do
        for _, node in ipairs(nodes) do
            node:tick()
        end
        socket.sleep(0.1) -- sleep 100ms
    end
end

print("Starting nodes...")
runNodes({node1, node2}, 10) -- run for 10 seconds

-- Try to append a command to leader
local success, err = node1:appendCommand("set x=1")
if not success then
    print("Node1 appendCommand failed:", err)
else
    print("Node1 appended command successfully")
end

runNodes({node1, node2}, 5) -- run more to propagate command

-- Original Raft library code follows:

-- Lua library for simplified consensus algorithm like Raft light
-- Author: Senior Software Engineer
-- Description: implements leader election, log replication, and node state management

local socket = require("socket") -- LuaSocket for communication
local json = require("json") -- JSON library for serialization

local Raft = {}

-- Role constants
local ROLE_FOLLOWER = "follower"
local ROLE_CANDIDATE = "candidate"
local ROLE_LEADER = "leader"

-- Default configuration
local DEFAULT_ELECTION_TIMEOUT_MIN = 1500 -- ms
local DEFAULT_ELECTION_TIMEOUT_MAX = 3000 -- ms
local DEFAULT_HEARTBEAT_INTERVAL = 500 -- ms

-- Helper function to generate random timeout between min and max
local function random_timeout(min, max)
    return math.random(min, max)
end

-- Raft Node
local Node = {}
Node.__index = Node

function Node:new(config)
    -- Node configuration
    local o = {
        id = config.id, -- local node ID
        peers = config.peers, -- table {id -> {host, port}}
        currentTerm = 0,
        votedFor = nil,
        log = {}, -- array of commands {term, command}
        commitIndex = 0,
        lastApplied = 0,
        state = ROLE_FOLLOWER,
        votesReceived = {},
        electionTimeout = random_timeout(DEFAULT_ELECTION_TIMEOUT_MIN, DEFAULT_ELECTION_TIMEOUT_MAX),
        heartbeatInterval = DEFAULT_HEARTBEAT_INTERVAL,
        electionTimer = nil,
        heartbeatTimer = nil,
        socket = nil,
        lastHeartbeat = socket.gettime(),
        callbacks = {
            onCommit = config.onCommit or function() end,
            sendMessage = config.sendMessage or function() end
        }
    }
    setmetatable(o, self)
    return o
end

-- Initialize UDP socket for communication
function Node:initSocket()
    local udp = socket.udp()
    udp:settimeout(0) -- non-blocking
    udp:setsockname("*", self.peers[self.id].port)
    self.socket = udp
end

-- Send JSON message to peer
function Node:send(toId, message)
    local peer = self.peers[toId]
    if not peer then return end
    local msgStr = json.encode(message)
    self.socket:sendto(msgStr, peer.host, peer.port)
end

-- Broadcast message to all peers except self
function Node:broadcast(message)
    for peerId, _ in pairs(self.peers) do
        if peerId ~= self.id then
            self:send(peerId, message)
        end
    end
end

-- Reset election timer
function Node:resetElectionTimer()
    self.electionTimeout = random_timeout(DEFAULT_ELECTION_TIMEOUT_MIN, DEFAULT_ELECTION_TIMEOUT_MAX)
    self.electionTimer = socket.gettime() + self.electionTimeout / 1000
end

-- Reset heartbeat timer
function Node:resetHeartbeatTimer()
    self.heartbeatTimer = socket.gettime() + self.heartbeatInterval / 1000
end

-- Handle RequestVote RPC message
function Node:onRequestVote(msg, fromId)
    local granted = false
    if msg.term < self.currentTerm then
        granted = false
    else
        if msg.term > self.currentTerm then
            self.currentTerm = msg.term
            self.votedFor = nil
            self.state = ROLE_FOLLOWER
        end
        if (self.votedFor == nil or self.votedFor == fromId) and
           (msg.lastLogTerm > (self.log[#self.log] and self.log[#self.log].term or 0) or
           (msg.lastLogTerm == (self.log[#self.log] and self.log[#self.log].term or 0) and msg.lastLogIndex >= #self.log)) then
            granted = true
            self.votedFor = fromId
            self:resetElectionTimer()
        end
    end
    local reply = {
        type = "RequestVoteResponse",
        term = self.currentTerm,
        voteGranted = granted
    }
    self:send(fromId, reply)
end

-- Handle AppendEntries RPC message (heartbeat or replication)
function Node:onAppendEntries(msg, fromId)
    if msg.term < self.currentTerm then
        local reply = {type = "AppendEntriesResponse", term = self.currentTerm, success = false}
        self:send(fromId, reply)
        return
    end
    self.currentTerm = msg.term
    self.state = ROLE_FOLLOWER
    self.votedFor = nil
    self:resetElectionTimer()

    -- Check log matching
    local prevLogIndex = msg.prevLogIndex
    local prevLogTerm = msg.prevLogTerm
    if prevLogIndex > 0 then
        if not self.log[prevLogIndex] or self.log[prevLogIndex].term ~= prevLogTerm then
            local reply = {type = "AppendEntriesResponse", term = self.currentTerm, success = false}
            self:send(fromId, reply)
            return
        end
    end

    -- Append new entries
    for i, entry in ipairs(msg.entries) do
        local idx = prevLogIndex + i
        if self.log[idx] and self.log[idx].term ~= entry.term then
            -- truncate divergent log
            for j = #self.log, idx, -1 do
                table.remove(self.log, j)
            end
        end
        if not self.log[idx] then
            self.log[idx] = entry
        end
    end

    -- Update commitIndex
    if msg.leaderCommit > self.commitIndex then
        self.commitIndex = math.min(msg.leaderCommit, #self.log)
        self:applyLogEntries()
    end

    local reply = {type = "AppendEntriesResponse", term = self.currentTerm, success = true}
    self:send(fromId, reply)
end

-- Apply log commands up to commitIndex
function Node:applyLogEntries()
    while self.lastApplied < self.commitIndex do
        self.lastApplied = self.lastApplied + 1
        local entry = self.log[self.lastApplied]
        if entry then
            self.callbacks.onCommit(entry.command)
        end
    end
end

-- Start election
function Node:startElection()
    self.state = ROLE_CANDIDATE
    self.currentTerm = self.currentTerm + 1
    self.votedFor = self.id
    self.votesReceived = {[self.id] = true}
    self:resetElectionTimer()

    local lastLogIndex = #self.log
    local lastLogTerm = (lastLogIndex > 0) and self.log[lastLogIndex].term or 0

    local msg = {
        type = "RequestVote",
        term = self.currentTerm,
        candidateId = self.id,
        lastLogIndex = lastLogIndex,
        lastLogTerm = lastLogTerm
    }
    self:broadcast(msg)
end

-- Handle incoming messages
function Node:handleMessage(msgStr, fromHost, fromPort)
    local msg = json.decode(msgStr)
    if not msg or not msg.type then return end

    local fromId = nil
    for id, peer in pairs(self.peers) do
        if peer.host == fromHost and peer.port == fromPort then
            fromId = id
            break
        end
    end
    if not fromId then return end

    if msg.type == "RequestVote" then
        self:onRequestVote(msg, fromId)
    elseif msg.type == "RequestVoteResponse" then
        if self.state == ROLE_CANDIDATE and msg.term == self.currentTerm and msg.voteGranted then
            self.votesReceived[fromId] = true
            local votesCount = 0
            for _ in pairs(self.votesReceived) do votesCount = votesCount + 1 end
            if votesCount > (#self.peers // 2) then
                self.state = ROLE_LEADER
                self:resetHeartbeatTimer()
            end
        elseif msg.term > self.currentTerm then
            self.currentTerm = msg.term
            self.state = ROLE_FOLLOWER
            self.votedFor = nil
            self:resetElectionTimer()
        end
    elseif msg.type == "AppendEntries" then
        self:onAppendEntries(msg, fromId)
    elseif msg.type == "AppendEntriesResponse" then
        -- For simplicity, advanced replication is not handled
        if msg.term > self.currentTerm then
            self.currentTerm = msg.term
            self.state = ROLE_FOLLOWER
            self.votedFor = nil
            self:resetElectionTimer()
        end
    end
end

-- Function to be called periodically to handle timers and send heartbeat
function Node:tick()
    local now = socket.gettime()

    -- Receive messages
    while true do
        local msgStr, ip, port = self.socket:receivefrom()
        if not msgStr then break end
        self:handleMessage(msgStr, ip, port)
    end

    -- Handle election timeout
    if self.state ~= ROLE_LEADER and now >= self.electionTimer then
        self:startElection()
    end

    -- Handle heartbeat
    if self.state == ROLE_LEADER and now >= self.heartbeatTimer then
        local msg = {
            type = "AppendEntries",
            term = self.currentTerm,
            leaderId = self.id,
            prevLogIndex = #self.log,
            prevLogTerm = (#self.log > 0) and self.log[#self.log].term or 0,
            entries = {}, -- empty heartbeat
            leaderCommit = self.commitIndex
        }
        self:broadcast(msg)
        self:resetHeartbeatTimer()
    end
end

-- Append command to log (leader only)
function Node:appendCommand(command)
    if self.state ~= ROLE_LEADER then
        return false, "Not leader"
    end
    local entry = {term = self.currentTerm, command = command}
    table.insert(self.log, entry)
    -- For simplicity immediate commit
    self.commitIndex = #self.log
    self:applyLogEntries()
    return true
end

-- Public API
Raft.Node = Node

return Raft

What do you need?

Node: represents a single node in the cluster with state (follower, candidate, leader), log, and current term.

Messaging: asynchronous management of messages between nodes (RequestVote, AppendEntries) via configurable callbacks.

Timer: management of timeouts for election and heartbeat with configurable scheduling functions.

Network configuration: definition of IP addresses and ports of nodes for communication via UDP/TCP sockets.

Arduino wiring/pinout: not directly applicable, but can be integrated with ESP8266/ESP32 modules for WiFi communication (e.g., GPIO pins for status LEDs, buttons for reset).

Software dependencies: LuaSocket for network communication, LuaTimer or equivalent for timer management, JSON.lua for message serialization.

Configuration: Lua configuration file to define cluster parameters (number of nodes, local node ID, election timeout, heartbeat interval).

Similar Topics