A Scala Fractal

As a follow up from my previous Fern Fractal written in Go, here the same written in Scala;
The fractal is a Barnsley Fern and is an example of an iterated function system.

import java.awt.{Color, Graphics2D, Dimension}
import swing.{SimpleSwingApplication, Panel, Frame}
import util.Random
class FernFractalFrame(transformFunction: (Double, Double) => (Double, Double), val width: Int, val height: Int, val max: Int) extends Frame {

contents = new Panel {
 preferredSize = new Dimension(width, height)
 opaque = true

override def paint(g: Graphics2D) {
 g.setBackground(new Color(0, 0, 0))
 g.setColor(Color.GREEN)
 g.drawLine(height / 2, width / 2, height / 2, width / 2)
 drawFern((0, 1), max, g)
 }

def paintPoint(p: (Double, Double), g: Graphics2D) = {
 val scale = height / 11
 val y = (height - 25) - (scale * p._2)
 val x = (width / 2) + (scale * p._1)
 g.drawLine(x.toInt, y.toInt, x.toInt, y.toInt)
 }

def drawFern(p: (Double, Double), max: Int, g: Graphics2D) {
 paintPoint(p, g)
 repaint()
 if (max != 0)
 drawFern(transformFunction(p._1, p._2), max - 1, g)
 }
 }
}

object FernFractal extends SimpleSwingApplication {

object TransformFunction extends CFernTransformFunction

class CFernTransformFunction extends ((Double, Double) => (Double, Double)) {

def rnd = Random.nextInt(100)

def transformPoint(p: (Double, Double), a: Double, b: Double, c: Double, d: Double, s: Double): (Double, Double) =
 ((a * p._1) + (b * p._2), ((c * p._1) + (d * p._2) + s))

def apply(x: Double, y: Double) = {
 rnd match {
 case n if n <= 1 => transformPoint((x, y), 0.0, 0.0, 0.0, 0.16, 0.0)
 case n if n <= 7 => transformPoint((x, y), 0.2, -0.26, 0.23, 0.22, 1.6)
 case n if n <= 14 => transformPoint((x, y), -0.15, 0.28, 0.26, 0.24, 0.44)
 case n if n <= 100 => transformPoint((x, y), 0.85, 0.04, -0.04, 0.85, 1.6)
 }
 }
 }

def top = new FernFractalFrame(TransformFunction, 400, 400, 10000)
}

To run this example:

$> scalac FernFractal.scala
$> scala -cp . FernFractal
Advertisements

Go Fern Fractal

I’m so stuck in system level programming in C and Go I almost forget how to do ‘normal’ stuff ;-P Therefore  I gave myself a small Go programming exercise, something with visual feedback. Recently I read this excellent post on how to draw a fractal in Clojure and I thought it would be fun to rewrite this in Go.

The fractal is a Barnsley Fern and is an example of an iterated function system. You take a  function which returns some values and you use the returned values as the input to the same function in the next step, and you keep doing that until eternity or you put a limit on the amount of steps.

With the Barnsley Fern fractal you have four transform function with input x and y. We give it a start point x and y, one of the randomly chosen transform functions will calculate a new x and y. We draw this as a point on an image and than give the new x and y the the next randomly chosen transform function and repeat this 10,000 times.

If you do this with specific parameters you will draw a fern:

And here is the source code:


package main

import (
 "fmt"
 "image"
 "image/draw"
 "image/png"
 "image/color"
 "log"
 "os"
 "math/rand"
)

func main() {
 m := image.NewRGBA(image.Rect(0, 0, 400, 400))
 blue := color.RGBA{0, 0, 0, 255}
 draw.Draw(m, m.Bounds(), &image.Uniform{blue}, image.ZP, draw.Src)
 drawFern(m, 400, 400, 10000)
 f, err := os.OpenFile("fern.png", os.O_CREATE | os.O_WRONLY, 0666)
 if(err != nil) {
 log.Fatal(err)
 }
 if err = png.Encode(f, m); err != nil {
 log.Fatal(err)
 }
 fmt.Println("Done")
}

func drawFern(m *image.RGBA, x float32, y float32, steps int) {
 if steps != 0 {
 x, y = transform(x, y)
 drawPoint(m, x, y)
 drawFern(m, x, y, steps - 1)
 }
}

func drawPoint(m *image.RGBA, x float32, y float32) {
 b := m.Bounds()
 height := float32(b.Max.Y)
 width := float32(b.Max.X )
 scale := float32(height / 11)
 y = (height - 25) - (scale * y)
 x = (width / 2) + (scale * x)
 m.Set(int(x), int(y), color.RGBA{0, 255, 0, 255})
}

func transform(x float32, y float32) (float32, float32) {
 rnd := rand.Intn(101)
 switch {
 case rnd == 1: x, y = transformPoint(x,y, 0.0, 0.0, 0.0, 0.16, 0.0)
 case rnd <= 7: x, y = transformPoint(x,y, 0.2, -0.26, 0.23, 0.22, 0.0)
 case rnd <= 14: x, y = transformPoint(x,y, -0.15, 0.28, 0.26, 0.24, 0.44)
 case rnd <= 100: x, y = transformPoint(x,y, 0.85, 0.04, -0.04, 0.85, 1.6)
 }
 return x, y
}

func transformPoint(x, y, a, b, c ,d , s float32) (float32, float32) {
 return ((a * x) + (b * y)), ((c * x) + (d * y) + s)
}

Moving targets

I’ve been working on SCTP (Stream Control Transmission Protocol) for a while now. Much error and learning involved. One of the things I discovered (or better said; learned the hard way) is that some functions needed by SCTP are deprecated in the last 12 months. My knowledge was based on the excellent Unix Networking Programming book (also known as UNP). And sctp.h in FreeBSD 8.2. However in December 2011 RFC 6458 got published. This document describes the mapping of SCTP into a sockets API.

The functions I used most: sctp_sendmsg() and sctp_recvmsg() are now replaced by sctp_sendv() and sctp_recvv(). (As of FreeBSD 8.3/9.0) But more interestingly the default way to send and receive messages can now be done with recvmsg() and sendmsg(). These two functions, according to UNP (14.5 p390), are the most general of all the I/O functions.

A quick look reveals these methods are in existence for a very long time.

So I’ve started reading RFC 6458, upgraded to FreeBSD 9 and am getting familiar with the sendmsg() and recvmsg() functions.

Olivier

Debugging Go applications on FreeBSD

Go uses a standardised debugging standard called DWARF. Yes, the pun is intended because DWARF was developed alongside ELF (Executable and Linking Format)

The be able to debug you need a debugger wich understands this standard.  The version Go build emits is DWARF3, GDB version 7.x supports this version. The standard debugger (used to compile the system) is version 6 9DWARF2 only), so you need to install a newer one. (/usr/ports/devel/gdb is version 7.x).

Instead of the usual `go run MyBuggyProgram.go`, you need to first build the program:
go build MyBuggyProgram.go

and start it with the debugger:
/usr/local/bin/gdb74 EchoSCTPServer -d $GOROOT

The environment variable GOROOT is optional but is useful if you want to debug the Go code itself, it has to point to a directory where Go is build from source.

Once within the debugger the usual commands are valid:

  • Ctrl+l: clear screen.
  • run: run programme
  • break: set break point
  • next: execute current line and move on the next
  • print (variable): print the value of (variable)
  • step: step into a function while executing

An example debug session:

(gdb) b 33
Note: breakpoint 1 also set at pc 0x400c8b.
Breakpoint 2 at 0x400c8b: file /home/olivier/projects/msc-report-src/echo-go-sctp/server/EchoSCTPServer.go, line 33.
(gdb) run
(gdb) s
net.ListenPacket (net="sctp", addr="localhost:4242", noname=void) at /home/olivier/projects/go-sctp/src/pkg/net/dial.go:213
213 func ListenPacket(net, addr string) (PacketConn, error) {
(gdb) s
214 afnet, a, err := resolveNetAddr("listen", net, addr)
(gdb) n
215 if err != nil {
(gdb) p err
$1 = 0
(gdb) p a
$2 = {IP = {array = "\177", len = 4, cap = 4}, Port = 4242}

More info can be found on the Go blog

Happy debugging 🙂

Olivier

Setting up a development environment for Go

A short blog post on how I’ve setup my development environment so I can develop on Go.

I’ve limited myself to FreeBSD (amd64) and Vim. However most of this setup should also work on other Unix environments and editors (e.g Emacs).

First step: install Go specific vim plugins. The Go source code ships with vim plugins which can be found in $GOROOT/misc/vim. The readme.txt explains the different options to install the plugins. You can soft link to this directory or copy everything straight into your ~/.vim/ directory. These plugins enable syntax highlighting, indentation and documentation lookup.

The second step is to enable you to jump around the code and go to definitions of specific functions. To enable this I use the (rather) well known ctags tools. A version of ctags which support Go can be found here: https://github.com/lyosha/ctags-go.git

Installations is simple, make install (watch out this overwrites previously installed ctags in /usr/local/bin). After this do a `ctags –recurse –sort=yes` at the top of your source tree, this will generater a tags file which can will be used by vim to lookup locations of code definitions. (C-[ : jump to definition, C-t : jump back)

The third step (last) is code completions. This can be done with a plugin called Omni Complete in combination with the Go autocompletion daemon. If your Go environment variables are setup correctly, the following command should do the trick: go get -u github.com/nsf/gocode.  The daemon works in combination with the Go vim plugins. In Vim C-x C-o will open the menu with context sensitive suggestions.

Happy coding!

 

One-to-one or one-to-many? That is the question!

Overview

There are two models of programming in SCTP, one-to-one and one-to-many. The one-to-many comes with all SCTP has to offers, the one-to-one model only a limited set of features can be implemented. However implementing the one-to-one model is very similar to how you would implement the same functionality in TCP. This makes migrating an existing application a relatively painless exercise. If you want to upgrade your existing TCP application to an one-to-many SCTP application significant retooling is needed [1].

Spot the difference

The easiest way to spot the difference between the two is by looking at how the endpoint for communication is created:

One-to-One style

sd = socket(PF_INET, SOCK_STREAM, IPPROTO_SCTP);

SOCK_STREAM stands for stream socket, the data stream is clearly associated with one socket.

One-to-Many style

sd = socket(PF_INET, SOCK_SEQPACKET, IPPROTO_SCTP);

SOCK_SEQPACKET stands for sequenced packet stream. The data stream is sequenced but there is no mention of a socket in the name.

The slightly less obvious way to see the difference is the way the connection between the client and server is set up.

Program Flow

Here is the one-to-one abstraction model:

One to One TCP lookalike

The server creates a passive socket with a listen() followed by an accept() and waits for a connection to come in.  The client creates an active socket and establishes a connection with a connect(). The moment accept() gets a connection request it creates a new socket and allocates a new file descriptor. The association between the two systems gets created explicitly and incoming connections are handled iteratively.

This is the one-to-many model:

One to many, full on SCTP

After the listen() a connection can come in from multiple clients. The association between the systems will be set up implicitly as soon as the client sends a message. As soon as the client closes the association the server releases the association resources too.

So what’s the difference?

Sending data during connection setup

Only the one-to-many is capable of sending data on the third leg of the four-way handshake SCTP does during connection setup [3].  This speeds up data transmission.

Iterative or Concurrent? (another question)

With the one-to-many model multiple associations can transport data over the same socket. The different connections are handled iteratively. With the sctp_peeloff() function an association can be detached in its own separate socket and/or thread. So if you want to you can use a concurrent model.

Connection State

Because of the connectionless nature of the one-to-many mode a lot of the connection state gets handled by the underlying SCTP transport stack and is of no concern for the application.

Conclusion

The one-to-many model has many advantages; it gives you a clear choice on how to handle your connections. It is even possible to combine an iterative server model with a concurrent one. Data can already be sent whilst setting up the association. And last but not least the application has less connection state to maintain.

The one-to-one model on the other hand not only gives you an easy migration path from an existing TCP application it also makes it easy to switch between TCP and SCTP in the same application; the only difference is the socket() call and maybe a setsockopt().

In a following post I will get into more detail on how to implement this. A good book with lots of examples and detailed explanation on how SCTP (and other protocols) work is Unix Network Programming, well worth a read.

References

[1][2] W. R. Stevens, B. Fenner, and A. M. Rudoff, Unix Network Programming: Sockets Networking API v. 1, 3rd ed. Addison Wesley, 2003. p.267, p271

[3] “sctp,” FreeBSD Man Pages. [Online]. Available: http://www.freebsd.org/cgi/man.cgi?query=sctp&manpath=FreeBSD+8.2-RELEASE. [Accessed: 24-Dec-2011].

Zookeeper Single File Leader Election with Retry Logic

In a previous post I explained how to implement leader election as suggested on the Zookeeper website. I posted my solution on the Zookeeper mailing list and got some useful tips. The first one was on how to do leader election. The method suggested is a single file leader election. Works like this:

  1. Try creating ephemeral ZNode
    1. Succes, become leader
    2. Fail, stay inactive
  2. Set watch on ZNode
  3. If ZNode disappears goto 1.

All clients try create the same ephemeral node, which has to be unique, so only one client will be able to create the node. The client who creates the node first becomes the leader, the rest  of the clients stay inactive and wait for the node to disappear before trying to create a node again.

The second suggestion I was given is to keep the connection to Zookeeper in some sort of retry logic. Assuming things will go wrong we have to make sure there is a system in place which can recover from a bad situation.
Here a class diagram of all objects involved:
Class diagram single file leader election
The following sequence diagram explains the flow of the program in case we have a successful election, followed by a signal indicating the node has disappeared.

The ZnodeMonitor implements the Watcher interface which has the process method. As soon as the ZNodeMonitor is set as  the Watcher the Zookeeper can talk back to it in case something changes.

First the client connects to the zookeeper by constructing a RecoverableZookeeper. This happens in the start method, called by the SpeakerServer:

public void start() throws IOException {
    this.zk = new RecoverableZookeeper(connectionString, this);
}

The ZNodeMonitor sets itself as a Watcher (this). This gives Zookeeper the opportunity to call back the ZNodeMonitor as soon as it is connected to the server. It does this by sending a None event type with a SyncConnected state.

@Override
public void process(WatchedEvent watchedEvent) {
    switch (watchedEvent.getType()) {
        case None:
            processNoneEvent(watchedEvent);
            break;
        case NodeDeleted:
            listener.stopSpeaking();
            createZNode();
    }
    try {
        zk.exists(ROOT, this);
    } catch (Exception e) {
        shutdown(e);
    }
}

public void processNoneEvent(WatchedEvent event) {
    switch (event.getState()) {
        case SyncConnected:
            createZNode();
            break;
        case AuthFailed:
        case Disconnected:
        case Expired:
        default:
            listener.stopSpeaking();
            break;
    }
}

Next the client tries to create a ZNode:

public void createZNode() {
    try {
        zk.create(ROOT, listener.getProcessName().getBytes());
        listener.startSpeaking();
    } catch (Exception e) {
        // Something went wrong, lets try set a watch first before
        // we take any action
    }
}

After this (successful or not) it tries setting a watch via the exist() method (also in the process method, see above).

The retry logic is encapsulated in the RecoverableZookeeper. The create() method wraps the original Zookeeper create method in the following retry logic:

public String create(String path, byte[] data) throws KeeperException, InterruptedException {
    RetryCounter retryCounter = retryCounterFactory.create();
    while (true) {
        try {
            return zk.create(path, data, ZooDefs.Ids.OPEN_ACL_UNSAFE, CreateMode.EPHEMERAL);
        } catch (KeeperException e) {
            logger.debug("Error code: " + e.code());
            switch (e.code()) {
                case NODEEXISTS:
                    if (retryCounter.shouldRetry()) {
                        byte[] currentData = zk.getData(path, false, null);
                        if (currentData != null && Arrays.equals(currentData, data)) {
                            return path;
                        }
                        throw e;
                    }
                    throw e;
                case CONNECTIONLOSS:
                case OPERATIONTIMEOUT:
                    if (!retryCounter.shouldRetry()) {
                        break;
                    }
                default:
                    throw e;
            }
        }
        retryCounter.sleepUntilNextRetry();
        retryCounter.useRetry();
}

If the creation of the Znode fails it retries until the reties get exhausted. In case the node already exists it first checks if it created the node itself, otherwise it will throw an exception. In case of a loss of connection or an operation timeout, it keeps retrying.

The complete code is available in my github account. Any questions or suggestions please feel free to send me an email or post a comment. This code also include some simple Ruby scripts to create configuration files and to start and stop multiple Zookeeper servers on a single machine. Handy if you want to test different scenarios.

For a full implementation of retry logic with Zookeeper I recommend the Netflix Zookeeper Library (Curator) which implements all of this and much more and is tested in a large scale environment.