Jul 22, 2015
Command line parameters, environment variables, and configuration files are common ways to change the behavior of software. However, sometimes that is just not enough and an embedded language can be the solution. In this case we will embed Lua using gopher-lua.
Godoc: http://godoc.org/github.com/yuin/gopher-lua
All code in the post can be found at http://github.com/otm/embedding-lua-in-go
Running Lua Code in Go
First lets set up the environment and test that it works, start by install gopher-lua:
go get github.com/yuin/gopher-lua
Secondly let’s create a minimal implementation:
package main
import "github.com/yuin/gopher-lua"
func main() {
L := lua.NewState()
defer L.Close()
if err := L.DoString(`print("Hello World")`); err != nil {
panic(err)
}
}
hello.go
lua.NewState() creates our Lua VM, and it is though L (*lua.LState) we will interact with Lua in the future. Throughout the post L will denote a pointer to lua.LState. L.DoString runs the Lua code in the VM. Running the Go code will yield:
$ go run hello.go
Hello World
To run a Lua file, instead of a string, call lua.DoFile
L := lua.NewState()
defer L.Close()
if err := L.DoFile("hello.lua"); err != nil {
panic(err)
}
Embedding Lua Code as Strings
DoFile and DoString can be called several times, and thus it can be utilized to expose Lua function. In the example bellow sayHello function is first defined, and then called in the second call to DoString
func main() {
L := lua.NewState()
defer L.Close()
if err := L.DoString(`function sayHello() print("Hello Again") end`); err != nil {
panic(err)
}
if err := L.DoString(`sayHello()`); err != nil {
panic(err)
}
}
hello2.go
Calling Go Code from Lua
Exposing Go functions to Lua is essential to create custom a custom API. A Go function should implement the LGFunction type to be callable from Lua.
type LGFunction func(*LState) int
It receives a *lua.LState and returns an integer. The LState is needed for interacting with the Lua VM, most commonly for retrieving function arguments. The returned integer defines how many return values has been pushed to the Lua stack. A complete example looks like this:
func square(L *lua.LState) int { //*
i := L.ToInt(1) // get first (1) function argument and convert to int
ln := lua.LNumber(i * i) // make calculation and cast to LNumber
L.Push(ln) // Push it to the stack
return 1 // Notify that we pushed one value to the stack
}
func main() {
L := lua.NewState()
defer L.Close()
L.SetGlobal("square", L.NewFunction(square)) // Register our function in Lua
if err := L.DoString(`print("4 * 4 = " .. square(4))`); err != nil {
panic(err)
}
}
calling-go.go
The LState defines some convenience functions, in the example above we are using L.ToInt(1) to fetch the first function argument.
Note: Lua isn’t zero-indexed, so the first function argument is fetched with L.ToInt(1), second argument with L.ToInt(2). In Lua, all arrays are 1-indexed, however t[0] is still valid but that would result in the lenght of the array to be off-by-one.
There are a number of To...(n int) functions available. These functions does not throw errors, but will return Go default values if conversion is not possible. To get automatic errors the L.Check...(n int) family of functions can be used; They throw a Lua error if the type check fails. For optional arguments the L.Opt...(n int, default T) functions can be used. Example:
L.GetTop() returns the number of arguments that was used when the function was called. And to fetch an argument without conversion the L.Get(n int) function can be used.
If an argument to a function can be of more then one type the L.CheckTypes(n int, types ...LValueType) function can be used to check and yield an error to the user. Using the L.CheckTypes function equate to checking the type manually and then calling L.TypeError(n int, message string) if there is an error.
// Second argument can be string or function
L.CheckTypes(2, lua.LTString, lua.LTFunction)
switch lv := L.Get(2).(type) {
case LString:
// use as string
case Lfunction:
// use as function
}
Calling Lua from Go
Calling Lua code is done through L.CallByParam, which takes a parameters object, P, and arguments as variadic parameters. The parameters object takes three important parameters:
- Fn - the lua.LFunction to call
- Nret - The number of returned values
- Protect - If protect is
true an error is returned, otherwise a panic will occur.
The following code defines a “concat” function in Lua. Calls the concat function with the arguments “Go” and “Lua” and prints the resulting string to stdout.
// luaCode is the Lua code we want to call from Go
var luaCode = `
function concat(a, b)
return a .. " + " .. b
end
`
func main() {
L := lua.NewState()
defer L.Close()
if err := L.DoString(luaCode); err != nil {
panic(err)
}
// Call the Lua function concat
// Lua analogue:
// str = concat("Go", "Lua")
// print(str)
if err := L.CallByParam(lua.P{
Fn: L.GetGlobal("concat"), // name of Lua function
NRet: 1, // number of returned values
Protect: true, // return err or panic
}, lua.LString("Go"), lua.LString("Lua")); err != nil {
panic(err)
}
// Get the returned value from the stack and cast it to a lua.LString
if str, ok := L.Get(-1).(lua.LString); ok {
fmt.Println(str)
}
// Pop the returned value from the stack
L.Pop(1)
}
calling-lua.go
Good to Know
Gopher-Lua Types
The gopher-lua library operates on a interface called LValue.
type LValue interface {
String() string
Type() LValueType
}
Objects implementing this interface are LNilType, LBool, LNumber, LString, LFunction, LUserData, LState, LTable, and LChannel. Calling the LValue.Type() returns the corresponding LValueType.
const (
LTNil LValueType = iota
LTBool
LTNumber
LTString
LTFunction
LTUserData
LTThread
LTTable
LTChannel
)
Covertion and Check functions
There are some practical functions to convert and check lua.LValue objects.
lua.LVAsBool(v LValue) - Convert to bool, nil and false becomes false. Otherwise true.
lua.LVAsString(v LValue) - Converts LString and LNumber to string. Otherwise empty string.
lua.CanConvToString(v LValue) - True if LString or LNumber. Otherwise false.
lua.LVIsFalse(v LValue) - Returns true if nil or false.
The LTable type
One of the most versatile and used data structures in Lua is LTable (actually it is the only one). The LTable type can be used for emulating namespaces and classes. However, the basic API is quite simple, and the advanced features deserves its own post. See http://godoc.org/github.com/yuin/gopher-lua#LTable for the LTable Go API.
May 31, 2015
Hacking a bash prompt that adapts when entering a git repository.
Disclaimer: This is a 15min hack which might include bugs and can definitely be made more performant.
This bash hack will keep the normal prompt, and only change it when entering a directory that is tracked by git. In a git repository it will display the basename of the directory and branch. The branch name is colored accordingly:
- Red - uncommitted working
- Yellow - your brancgh is ahead
- Green - nothing to commit
- Ochre - all other statuses
Examples
nils@ratchet:~/project$
Normal Directory
[go](master)$
Non Commited
Code
The following code should be included in the .bashrc file
COLOR_RED="\033[0;31m"
COLOR_YELLOW="\033[0;33m"
COLOR_GREEN="\033[0;32m"
COLOR_OCHRE="\033[38;5;95m"
COLOR_BLUE="\033[0;34m"
COLOR_WHITE="\033[0;37m"
COLOR_RESET="\033[0m"
COLOR_RESET2="\e[0m"
function git_color {
local git_status="$(git status 2> /dev/null)"
if [[ ! $git_status =~ "working directory clean" ]]; then
echo -e $COLOR_RED
elif [[ $git_status =~ "Your branch is ahead of" ]]; then
echo -e $COLOR_YELLOW
elif [[ $git_status =~ "nothing to commit" ]]; then
echo -e $COLOR_GREEN
else
echo -e $COLOR_OCHRE
fi
}
function git_branch {
local git_status="$(git status 2> /dev/null)"
local on_branch="On branch ([^${IFS}]*)"
local on_commit="HEAD detached at ([^${IFS}]*)"
if [[ $git_status =~ $on_branch ]]; then
local branch=${BASH_REMATCH[1]}
echo "($branch)"
elif [[ $git_status =~ $on_commit ]]; then
local commit=${BASH_REMATCH[1]}
echo "($commit)"
fi
}
function git_dir {
echo "$(basename `git rev-parse --show-toplevel`)/$(git rev-parse --show-prefix)"
}
PS1='$(git status &> /dev/null || printf "\u@\h:\w\$ ")' # other dir
PS1+='$(git status &> /dev/null && printf "' # if we are in git dir
PS1+="\[$COLOR_RESET\]" # reset color
PS1+="[\$(git_dir)]" # get git dir + path
PS1+="\[\$(git_color)\]" # colors git status
PS1+="\$(git_branch)" # prints current branch
PS1+="\[$BLUE\]\[$COLOR_RESET2\]\\$ " # '#' for root, else '$'
PS1+='")'
export PS1
May 30, 2015
Series: Raft 101
tl;dr In this part we will implement a very simplistic cluster node using the etcd raft implementation. And with the node implementation we will start up a small cluster.
The complete source to this post can be found at http://github.com/otm/raft-part-1, and documentation for the etcd raft at https://godoc.org/github.com/coreos/etcd/raft
Creating a Basic Node
Clusters are built by nodes, so lets start of by defining a node. Initially the node only needs to keep track of the raft and the persistent storage. Below is a minimal implementation of the node type and its constructor function.
import (
"github.com/coreos/etcd/raft"
"github.com/coreos/etcd/raft/raftpb"
"golang.org/x/net/context"
)
const hb = 1
type node struct {
// id is the node id in the cluster
id unint64
// the raft that the cluster node will use
// this includes the WAL
raft raft.Node
// the raft configuration
cfg *raft.Config
// pstore is a fake implementation of a persistent storage
// that will be used side-by-side with the WAL in the raft
pstore map[string]string
}
func newNode(id int, peers []raft.Peer) *node {
n := &node{
id: id,
cfg: &raft.Config{
// ID in the etcd raft
ID: uint64(id),
// ElectionTick controls the time before a new election starts
ElectionTick: 10 * hb,
// HeartbeatTick controls the time between heartbeats
HeartbeatTick: hb,
// Storage contains the log
Storage: raft.NewMemoryStorage(),
MaxSizePerMsg: math.MaxUint16,
MaxInflightMsgs: 256,
},
pstore: make(map[string]string),
}
n.raft = raft.StartNode(n.cfg, peers)
return n
}
With the node comes some responsibilities:
- Read from
Node.Ready() channel and process the updates.
- All persisted log entries must be made available via an implementation of the Storage interface. This can be solved by using the provided MemoryStorage type, if it is repopulated upon restart; or by implementing a disked backed implementation. In this example we will not implement this part.
- Call
Node.Step() when receiving a message from another node.
- Call
Node.Tick() at regular intervals. Internally the raft time is represented by an abstract tick, that controls two important timeouts, the heartbeat and election timeout.
So the state machine main loop will look like this:
func (n *node) run() {
n.ticker = time.Tick(time.Second)
for {
select {
case <-n.ticker:
// Point (4) above
n.raft.Tick()
case rd := <-n.raft.Ready():
// Point (2) above
case <-n.done:
return
}
}
}
Handling Raft Ready Events
Above a large part of the control loop is left out, that is the processing of updates from the Node.Ready() channel. When receiving a message there are four important tasks:
Write HardState, Entries and Snapshot to persistent storage. Note! When writing to storage it is important to check the Entry Index (i). If previously persisted entries with Index >= i exist, those entries needs to be discarded. For instance this can happen if we get a cluster split with the leader in the minority part; because then the cluster can advance in the other part.
Send all messages to the nodes named in the To field. Note! It is important to not send any messages until:
- the latest HardState has been persisted
- all Entries from previous batch have been persisted (messages from the current batch can be sent and persisted in parallel)
- call
Node.ReportSnapshot() if any message has type MsgSnap and the snapshot has been sent
Apply Snapshot and CommitedEntries to the state machine. If any committed Entry has the type EntryConfChange call Node.ApplyConfChange to actually apply it to the node. The configuration change can be canceled at this point by setting the NodeId field to zero before calling ApplyConfChange. Either way, ApplyConfChange must be called; and the decision to cancel must be based solely on the state machine and not on external information, for instance observed health state of a node.
Call Node.Advance() to signal readiness for the next batch. This can be done any time after step 1 is finished. Note! All updates must be processed in the order they were received by Node.Ready()
The four tasks above can be done in parallel as long as all notices above are fulfilled. In the example below rd is of the type raft.Ready
n.saveToStorage(rd.HardState, rd.Entries, rd.Snapshot) // (1)
n.send(rd.Messages) // (2)
if !raft.IsEmptySnap(rd.Snapshot) {
n.processSnapshot(rd.Snapshot) //(3)
}
for _, entry := range rd.CommittedEntries {
n.process(entry) // (3)
if entry.Type == raftpb.EntryConfChange {
var cc raftpb.ConfChange
cc.Unmarshal(entry.Data)
n.node.ApplyConfChange(cc) // (3)
}
}
n.raft.Advance() // (4)
Below is the raft.Ready type, please note that pb is actually raftpb.
type Ready struct {
// The current volatile state of a Node.
// SoftState will be nil if there is no update.
// It is not required to consume or store SoftState
// It is useful for logging and debugging
*SoftState
// The current state of a Node to be saved to stable storage BEFORE
// Messages are sent.
// HardState will be equal to empty state if there is no update.
pb.HardState
// Entries specifies entries to be saved to stable storage BEFORE
// Messages are sent.
Entries []pb.Entry
// Snapshot specifies the snapshot to be saved to stable storage.
Snapshot pb.Snapshot
// CommittedEntries specifies entries to be committed to a
// store/state-machine. These have previously been committed to stable
// store.
CommittedEntries []pb.Entry
// Messages specifies outbound messages to be sent AFTER Entries are
// committed to stable storage.
// If it contains a MsgSnap message, the application MUST report back to raft
// when the snapshot has been received or has failed by calling ReportSnapshot.
Messages []pb.Message
}
Save To Storage
Saving to storage is not so advanced in a simplistic example like this:
- Append the entries - this is basically the message to be committed
- Set the hard state - this will commit the message
- Apply the snapshot - this overwrites the storage with the given snapshot
func (n *node) saveToStorage(hardState raftpb.HardState, entries []raftpb.Entry, snapshot raftpb.Snapshot) {
n.store.Append(entries)
if !raft.IsEmptyHardState(hardState) {
n.store.SetHardState(hardState)
}
if !raft.IsEmptySnap(snapshot) {
n.store.ApplySnapshot(snapshot)
}
}
Send
For now the RPC will be simulated with a global map which holds the nodes. With the send function there is also a matching receive function. Note, the receive() function calls raft.Step(), and that is crucial to advance the state machine.
func (n *node) send(messages []raftpb.Message) {
for _, m := range messages {
// Inspect the message (just for fun)
log.Println(raft.DescribeMessage(m, nil))
// send message to other node
nodes[m.To].receive(n.ctx, m)
}
}
func (n *node) receive(ctx context.Context, message raftpb.Message) {
n.raft.Step(ctx, message)
}
Process Raft Entry
If entry.Type of the raftpb.Entry is raftpb.EntryNormal the message should be processed. The message will be encoded in entry.Data. The protocol below is very simple, and is a string on the form key:value
func (n *node) process(entry raftpb.Entry) {
if entry.Type == raftpb.EntryNormal && entry.Data != nil {
log.Println("normal message:", string(entry.Data))
parts := bytes.SplitN(entry.Data, []byte(":"), 2)
n.pstore[string(parts[0])] = string(parts[1])
}
}
Process Snapshot
For now processSnapshot will only be a dummy implementation. But basically it should only overwrite the the current persistent storage.
func (n *node) processSnapshot(snapshot raftpb.Snapshot) {
log.Printf("Applying snapshot on %v is not implemenetd yet")
}
Advance the Raft
At this point the only thing left to do is calling Node.Advance(), this signals that the node is ready for the next batch. Please note that all updates must be processed in the order they were received from Node.Ready. In our example it looks like this:
n.raft.Advance()
Using the Raft
Finally it is time to start up a couple of nodes and connect them to a cluster. Below the nodes are started with predefined peers. Lastly Node.Campaign is called to start an election campaign; it is not necessary but it saves some time, as we do not need to wait for the election timeout. Note! At this point we do not have a resilient cluster, because if a node is lost there is no way to reach a majority consensus.
nodes[1] = newNode(1, []raft.Peer{{ID: 1}, {ID: 2}})
go nodes[1].run()
nodes[2] = newNode(2, []raft.Peer{{ID: 1}, {ID: 2}})
go nodes[2].run()
nodes[1].raft.Campaign(nodes[1].ctx)
However, all nodes in the cluster can not be known in advance. Below a node is created and added to a running cluster. It is created without any peers and a configuration change is proposed to the cluster. When the configuration change has been committed, the cluster is fault tolerant.
nodes[3] = newNode(3, []raft.Peer{})
go nodes[3].run()
nodes[2].raft.ProposeConfChange(nodes[2].ctx, raftpb.ConfChange{
ID: 3,
Type: raftpb.ConfChangeAddNode,
NodeID: 3,
Context: []byte(""),
})
Next up is writing data to the cluster, that is also done by proposing a change to the cluster. Each of the writes are done to different nodes in the cluster.
nodes[1].node.Propose(nodes[1].ctx, []byte("key1:value1"))
nodes[2].node.Propose(nodes[2].ctx, []byte("key2:value2"))
nodes[3].node.Propose(nodes[3].ctx, []byte("key3:value3"))
Dumping the data on the nodes reveals if they have been synchronized properly.
for i, node := range nodes {
fmt.Printf("** Node %v **\n", i)
for k, v := range node.pstore {
fmt.Printf("%v = %v", k, v)
}
fmt.Printf("*************\n")
}
If a node is added to the cluster, data will be replicated to the newly added node by replaying the log.
May 27, 2015
Series: Raft 101
The Raft consensus algorithm provides an understandable, easy to use, and generic way to distribute a state machine in a cluster. The Raft is a successor, or an alternative, to an algorithm called Paxos.
A node in the cluster can have three states: follower, candidate, or leader. Consensus in the cluster is maintained by the leader, which is responsible for log replication. To become the leader a node will change its status from follower to candidate.
Leader Election
The leader in the cluster sends heartbeat messages to the followers. If a follower does not receive a heartbeat within the election timeout it will transition state from follower to candidate. The candidate starts a new election term and increases the term counter, votes for itself and sends a RequestVote message to the cluster members. A member node will vote on the first candidate that sends a RequestVote message, and it will only vote once during a term. At this point there are three scenarios in the cluster:
- The candidate receives a message from a leader with equal or higher term - and transitions from candidate to flower.
- The candidate receives a majority of the votes - and transitions from candidate to leader.
- The candidate’s election times out - and transitions from candidate to follower.
Log Replication
All changes go through the leader, leader gets proposal, creates a log entry (uncommited), then replicates the entry to the followers, when a majority of the followers have written the log entry the leader commits it (the leaders state has now changed), the leader notifies the followers that the entry has been committed. At this point the cluster is in consensus.
Log replication
Once there is a leader the cluster can move forward. All changes go through the leader, however followers can propose a change to the leader. When the leader is updated it creates a log entry, which is uncommited; the leader replicates the log entry to the followers in an AppendEntries message. When a majority of followers has written the log entry, the leader will commit the pending entry; the leader state has now changed and notifies the followers that the entry is committed. At this point the cluster is in consensus and has moved forward.
Cluster Split
Cluster consensus requires at least two nodes; thus three nodes are needed to create a resilient cluster. In case of a cluster split there will be one part that can achieve consensus, and move forward. However, there are two scenarios that are interesting to look into.
Leader in Majority Part
The leader is in the part of the cluster that can reach consensus - That part will continue to work and move forward. In the other part a new leader can not be elected as consensus can not be reached. When the cluster split is resolved the log entries will replicate to the follower that was on the “wrong” side of the split.
Leader in Minority Part
The leader is in the part of the cluster that can not reach consensus - Proposed changes to the original leader will be entered in the log and replicated to the followers; however the change can not be committed and that part of the cluster can not move forward. At the same time, on the other side of the cluster a leader election will start, due to the lack of leader, and the term will increment and a leader will be elected. The increment in election term here is important. Now when there is a leader, and enough nodes for consensus, this part of the cluster can start to move forward.
When the cluster split is resolved there will be two leaders. However, the leader with the lower term will now have uncommitted entries in the log. When it reseives a message from the leader with a higher term it will roll back the log entries and start to commit the log entries from the leader with higher term.
Next part will be a practical introduction to the Raft algorithm in etcd.