Programming

Introduction to Go Modules

This post is also available in other languages:

The upcoming version 1.11 of the Go programming language will bring experimental support for modules, a new dependency management system for Go. A few days ago, I wrote a quick post about it. Since that post went live, things changed a bit and as we’re now very close to the new release, I thought it would be a good time for another post with a more hands-on approach. So here’s what we’ll do: we’ll create a new package and then we’ll make a few releases to see how that would work.

Creating a Module

So first things first. Let’s create our package. We’ll call it “testmod”. An important detail here: **this directory should be **outside your $GOPATH because by default, the modules support is disabled inside it. Go modules is a first step in potentially eliminating $GOPATH entirely at some point.

$ mkdir testmod
$ cd testmod

Our package is very simple:

package testmod

<span class="hljs-keyword">import</span> <span class="hljs-string">"fmt"</span> 

<span class="hljs-comment">// Hi returns a friendly greeting</span>
func Hi(name string) string {
   <span class="hljs-keyword">return</span> fmt.Sprintf(<span class="hljs-string">"Hi, %s"</span>, name)
}Code language: JavaScript (javascript)

The package is done but it is still not a module. Let’s change that.

$ go mod init github.com/robteix/testmod
<span class="hljs-attr">go</span>: creating <span class="hljs-keyword">new</span> go.mod: <span class="hljs-built_in">module</span> github.com/robteix/testmodCode language: JavaScript (javascript)

This creates a new file named go.mod in the package directory with the following contents:

<span class="hljs-built_in">module</span> github.com/robteix/testmodCode language: JavaScript (javascript)

Not a lot here, but this effectively turns our package into a module. We can now push this code to a repository:

$ git init 
$ git add * 
$ git commit -am <span class="hljs-string">"First commit"</span> 
$ git push -u origin masterCode language: JavaScript (javascript)

Until now, anyone willing to use this package would go get it:

$ go <span class="hljs-keyword">get</span> github.com/robteix/testmodCode language: JavaScript (javascript)

And this would fetch the latest code in master. This still works, but we should probably stop doing that now that we have a Better Way™. Fetching master is inherently dangerous as we can never know for sure that the package authors didn’t make change that will break our usage. That’s what modules aims at fixing.

Quick Intro to Module Versioning

Go modules are versioned, and there are some particularities with regards to certain versions. You will need to familiarize yourself with the concepts behind semantic versioning.

More importantly, Go will use repository tags when looking for versions, and some versions are different of others: e.g. versions 2 and greater should have a different import path than versions 0 and 1 (we’ll get to that.) As well, by default Go will fetch the latest tagged version available in a repository. This is an important gotcha as you may be used to working with the master branch. What you need to keep in mind for now is that to make a release of our package, we need to tag our repository with the version. So let’s do that.

Making our first release

Now that our package is ready, we can release it to the world. We do this by using version tags. Let’s release our version 1.0.0:

$ git tag v1.0.0
$ git push --tags

This creates a tag on my Github repository marking the current commit as being the release 1.0.0.

Go doesn’t enforce that in any way, but a good idea is to also create a new branch (“v1”) so that we can push bug fixes to.

$ git checkout -b v1
$ git push -u origin v1

Now we can work on master without having to worry about breaking our release.

Using our module

Now we’re ready to use the module. We’ll create a simple program that will use our new package:

package main

<span class="hljs-keyword">import</span> (
 	<span class="hljs-string">"fmt"</span>

 	<span class="hljs-string">"github.com/robteix/testmod"</span>
)

func main() {
 	fmt.Println(testmod.Hi(<span class="hljs-string">"roberto"</span>))
}Code language: JavaScript (javascript)

Until now, you would do a go get github.com/robteix/testmod to download the package, but with modules, this gets more interesting. First we need to enable modules in our new program.

$ go mod init mod

As you’d expect from what we’ve seen above, this will have created a new go.mod file with the module name in it:

<span class="hljs-built_in">module</span> modCode language: JavaScript (javascript)

Things get much more interesting when we try to build our new program:

$ go build
go: finding github.com/robteix/testmod v1.0.0
go: downloading github.com/robteix/testmod v1.0.0

As we can see, the go command automatically goes and fetches the packages imported by the program. If we check our go.mod file, we see that things have changed:

<span class="hljs-built_in">module</span> mod
<span class="hljs-built_in">require</span> github.com/robteix/testmod v1<span class="hljs-number">.0</span><span class="hljs-number">.0</span>Code language: JavaScript (javascript)

And we now have a new file too, named go.sum, which contains hashes of the packages, to ensure that we have the correct version and files.

github.com/robteix/testmod v1.0.0 h1:9EdH0EArQ/rkpss9Tj8gUnwx3w5p0jkzJrd5tRAhxnA=
github.com/robteix/testmod v1.0.0/go.mod h1:UVhi5McON9ZLc5kl5iN2bTXlL6ylcxE9VInV71RrlO8=

Making a bugfix release

Now let’s say we realized a problem with our package: the greeting is missing ponctuation! People are mad because our friendly greeting is not friendly enough. So we’ll fix it and release a new version:

<span class="hljs-comment">// Hi returns a friendly greeting</span>
func Hi(name string) string {
-       <span class="hljs-keyword">return</span> fmt.Sprintf(<span class="hljs-string">"Hi, %s"</span>, name)
+       <span class="hljs-keyword">return</span> fmt.Sprintf(<span class="hljs-string">"Hi, %s!"</span>, name)
}Code language: JavaScript (javascript)

We made this change in the v1 branch because it’s not relevant for what we’ll do for v2 later, but in real life, maybe you’d do it in master and then back-port it. Either way, we need to have the fix in our v1 branch and mark it as a new release.

$ git commit -m <span class="hljs-string">"Emphasize our friendliness"</span> testmod.go
$ git tag v1<span class="hljs-number">.0</span><span class="hljs-number">.1</span>
$ git push --tags origin v1Code language: JavaScript (javascript)

Updating modules

By default, Go will not update modules without being asked. This is a Good Thing™ as we want predictability in our builds. If Go modules were automatically updated every time a new version came out, we’d be back in the uncivilized age pre-Go1.11. No, we need to tell Go to update a modules for us.

We do this by using our good old friend go get:

  • run go get -u to use the latest minor or patch releases (i.e. it would update from 1.0.0 to, say, 1.0.1 or, if available, 1.1.0)
  • run go get -u=patch to use the latest patch releases (i.e., would update to 1.0.1 but not to 1.1.0)
  • run go get package@version to update to a specific version (say, github.com/robteix/[email protected])

In the list above, there doesn’t seem to be a way to update to the latest major version. There’s a good reason for that, as we’ll see in a bit.

Since our program was using version 1.0.0 of our package and we just created version 1.0.1, any of the following commands will update us to 1.0.1:

$ go <span class="hljs-keyword">get</span> -u
$ go <span class="hljs-keyword">get</span> -u=patch
$ go <span class="hljs-keyword">get</span> github.com/robteix/[email protected]Code language: JavaScript (javascript)

After running, say, go get -u our go.mod is changed to:

<span class="hljs-built_in">module</span> mod
<span class="hljs-built_in">require</span> github.com/robteix/testmod v1<span class="hljs-number">.0</span><span class="hljs-number">.1</span>Code language: JavaScript (javascript)

Major versions

According to semantic version semantics, a major version is different than minors. Major versions can break backwards compatibility. From the point of view of Go modules, a major version is a different package completely. This may sound bizarre at first, but it makes sense: two versions of a library that are not compatible with each other are two different libraries.

Let’s make a major change in our package, shall we? Over time, we realized our API was too simple, too limited for the use cases of our users, so we need to change the Hi() function to take a new parameter for the greeting language:

package testmod

import (
 	<span class="hljs-string">"errors"</span>
 	<span class="hljs-string">"fmt"</span> 
) 

<span class="hljs-comment">// Hi returns a friendly greeting in language lang</span>
func Hi(name, lang string) (string, error) {
 	<span class="hljs-keyword">switch</span> lang {
 	<span class="hljs-keyword">case</span> <span class="hljs-string">"en"</span>:
 		<span class="hljs-keyword">return</span> fmt.Sprintf(<span class="hljs-string">"Hi, %s!"</span>, name), nil
 	<span class="hljs-keyword">case</span> <span class="hljs-string">"pt"</span>:
 		<span class="hljs-keyword">return</span> fmt.Sprintf(<span class="hljs-string">"Oi, %s!"</span>, name), nil
 	<span class="hljs-keyword">case</span> <span class="hljs-string">"es"</span>:
 		<span class="hljs-keyword">return</span> fmt.Sprintf(<span class="hljs-string">"¡Hola, %s!"</span>, name), nil
 	<span class="hljs-keyword">case</span> <span class="hljs-string">"fr"</span>:
 		<span class="hljs-keyword">return</span> fmt.Sprintf(<span class="hljs-string">"Bonjour, %s!"</span>, name), nil
 	<span class="hljs-keyword">default</span>:
 		<span class="hljs-keyword">return</span> <span class="hljs-string">""</span>, errors.<span class="hljs-keyword">New</span>(<span class="hljs-string">"unknown language"</span>)
 	}
}Code language: PHP (php)

Existing software using our API will break because they (a) don’t pass a language parameter and (b) don’t expect an error return. Our new API is no longer compatible with version 1.x so it’s time to bump the version to 2.0.0.

I mentioned before that some versions have some peculiarities, and this is the case now. **Versions 2 **and over should change the import path. They are different libraries now.

We do this by appending a new version path to the end of our module name.

<span class="hljs-built_in">module</span> github.com/robteix/testmod/v2Code language: JavaScript (javascript)

The rest is the same as before, we push it, tag it as v2.0.0 (and optionally create a v2 branch.)

$ git commit testmod.go -m <span class="hljs-string">"Change Hi to allow multilang"</span>
$ git checkout -b v2 <span class="hljs-comment"># optional but recommended</span>
$ <span class="hljs-keyword">echo</span> <span class="hljs-string">"module github.com/robteix/testmod/v2"</span> > go.mod
$ git commit go.mod -m <span class="hljs-string">"Bump version to v2"</span>
$ git tag v2<span class="hljs-number">.0</span><span class="hljs-number">.0</span>
$ git push --tags origin v2 <span class="hljs-comment"># or master if we don't have a branch</span>Code language: PHP (php)

Updating to a major version

Even though we have released a new incompatible version of our library, existing software will not break, because it will continue to use the existing version 1.0.1. go get -u will not get version 2.0.0.

At some point, however, I, as the library user, may want to upgrade to version 2.0.0 because maybe I was one of those users who needed multi-language support.

I do it but modifying my program accordingly:

package main

<span class="hljs-keyword">import</span> (
 	<span class="hljs-string">"fmt"</span>
 	<span class="hljs-string">"github.com/robteix/testmod/v2"</span> 
)

func main() {
 	g, <span class="hljs-attr">err</span> := testmod.Hi(<span class="hljs-string">"Roberto"</span>, <span class="hljs-string">"pt"</span>)
 	<span class="hljs-keyword">if</span> err != nil {
 		panic(err)
 	}
 	fmt.Println(g)
}Code language: JavaScript (javascript)

And then when I run go build, it will go and fetch version 2.0.0 for me. Notice how even though the import path ends with “v2”, Go will still refer to the module by its proper name (“testmod”).

As I mentioned before, the major version is for all intents and purposes a completely different package. Go modules does not link the two at all. That means we can use two incompatible versions in the same binary:

package main
<span class="hljs-keyword">import</span> (
 	<span class="hljs-string">"fmt"</span>
 	<span class="hljs-string">"github.com/robteix/testmod"</span>
 	testmodML <span class="hljs-string">"github.com/robteix/testmod/v2"</span>
)

func main() {
 	fmt.Println(testmod.Hi(<span class="hljs-string">"Roberto"</span>))
 	g, <span class="hljs-attr">err</span> := testmodML.Hi(<span class="hljs-string">"Roberto"</span>, <span class="hljs-string">"pt"</span>)
 	<span class="hljs-keyword">if</span> err != nil {
 		panic(err)
 	}
 	fmt.Println(g)
}Code language: JavaScript (javascript)

This eliminates a common problem with dependency management: when dependencies depend on different versions of the same library.

Tidying it up

Going back to the previous version that uses only testmod 2.0.0, if we check the contents of go.mod now, we’ll notice something:

<span class="hljs-built_in">module</span> mod
<span class="hljs-built_in">require</span> github.com/robteix/testmod v1<span class="hljs-number">.0</span><span class="hljs-number">.1</span>
<span class="hljs-built_in">require</span> github.com/robteix/testmod/v2 v2<span class="hljs-number">.0</span><span class="hljs-number">.0</span>Code language: JavaScript (javascript)

By default, Go does not remove a dependency from go.mod unless you ask it to. If you have dependencies that you no longer use and want to clean up, you can use the new tidy command:

$ go mod tidy

Now we’re left with only the dependencies that are really being used.

Vendoring

Go modules ignores the vendor/ directory by default. The idea is to eventually do away with vendoring[^0]. But if we still want to add vendored dependencies to our version control, we can still do it:

$ go mod vendor

This will create a vendor/ directory under the root of your project containing the source code for all of your dependencies.

Still, go build will ignore the contents of this directory by default. If you want to build dependencies from the vendor/ directory, you’ll need to ask for it.

$ go build -mod vendor

I expect many developers willing to use vendoring will run go build normally on their development machines and use -mod vendor in their CI.

Again, Go modules is moving away from the idea of vendoring and towards using a Go module proxy for those who don’t want to depend on the upstream version control services directly.

There are ways to guarantee that go will not reach the network at all (e.g. GOPROXY=off) but these are the subject for a future blog post.

Conclusion

This post may seem a bit daunting, but I tried to explain a lot of things together. The reality is that now Go modules is basically transparent. We import package like always in our code and the go command will take care of the rest.

When we build something, the dependencies will be fetched automatically. It also eliminates the need to use $GOPATH which was a roadblock for new Go developers who had trouble understanding why things had to go into a specific directory.

Vendoring is (unofficially) being deprecated in favour of using proxies.[^0] I may do a separate post about the Go module proxy. (Update: it’s live.) [^0]: I think this came out a bit too strong and people left with the impression that vendoring is being removed right now. It isn’t. Vendoring still works, albeit slightly different than before. There seems to be a desire to replace vendoring with something better, which may or may not be a proxy. But for now this is just it: a desire for a better solution. Vendoring is not going away until a good replacement is found (if ever.)

Playing With Go Modules

Update: much of this article has been rendered obsolete by changes made to Go modules since. Check this more recent post that’s up to date.

Had some free time in my hands, so I decided to check out the new Go modules. For those unaware, the next Go release (1.11) will include a new functionality that aims at addressing package management called “modules”. It will still be marked as experimental, so things may very well change a lot.

Here’s how it works. Let’s say we create a new package:

rselbach@wile ~/code $ mkdir foobar
rselbach@wile ~/code $ cd foobar/

Our foobar.go will be very simple:

package foobar

import (
"fmt"
"io"

"github.com/pkg/errors"
)

func WriteGreet(w io.Writer, name string) error {
if _, err := fmt.Fprintln(w, "Hello", name); err != nil {
return errors.Wrapf(err, "Could not greet %s", name)
}

return nil
}

Notice we’re using Dave Cheney’s excellent errors package. Until now, go get would fetch whatever it found on that package’s repository. If Dave ever decided to change something drastic in the package, our code would probably break without us even knowing about it until too late.

That’s where Go modules come into play, as it will help us (1) formalize the dependency and (2) lock a particular version of it to our code. First we need to turn on the support for modules in our package. We do this by using the new go mod command and giving out module a name:

$ go mod -init -module github.com/rselbach/foobar
go: creating new go.mod: module github.com/rselbach/foobar

After that, you will notice that a new file called go.mod will be created in our package root. For now, it only contains the module name we gave it above:

module github.com/rselbach/foobar

But it does more than that, for now the go command is aware that we are in a module-aware package and will behave accordingly. See what happens when we first try to build this:

$ go build
go: finding github.com/pkg/errors v0.8.0
go: downloading github.com/pkg/errors v0.8.0

It sees that we are using an external package and then it goes out, finds the latest version of it, downloads it, and adds it to our go.mod file:

module github.com/rselbach/foobar

require github.com/pkg/errors v0.8.0

From now one, whenever someone uses our package, Go will also download version 0.8.0 of Dave’s errors package. If version 0.9.0 completely breaks compatibility, it will not break our code for it will continue to be compiled with correct version.

If we change go.mod to require version 0.7.0, our next go build will fetch it as well:

$ go build
go: finding github.com/pkg/errors v0.7.0
go: downloading github.com/pkg/errors v0.7.0

If you’re wondering where the packages are, they’re stored under $GOPATH/src/mod:

$ ls -l ~/go/src/mod/github.com/pkg/
total 0
dr-xr-xr-x 13 rselbach staff 416 20 Jul 07:44 [email protected]
dr-xr-xr-x 14 rselbach staff 448 20 Jul 07:40 [email protected]

What about vendoring?

Good thing you asked. This is where I don’t like Go modules’ approach. It specifically aims at doing away with vendoring. Versioning is obviously taken care of by the modules functionality itself while disponibility is supposed to be taken care of by something like caching proxies.

I don’t see it. First of all, not everybody is Google. Maintaining cache proxies is extra work that many organizations don’t have the resources for. Also, what about when we’re working from home? Or on the commute? Sure, a VPN solves this, but then it’s one more thing we need to maintain.

That doesn’t mean you can’t vendor with Go modules. It’s simply not the default way it works. Let’s see how it works though. Let’s say we want to vendor our dependencies:

$ go mod -vendor
rselbach@wile ~/code/foobar $ ls -la
total 24
drwxr-xr-x 6 rselbach staff 192 20 Jul 08:01 .
drwxr-xr-x 33 rselbach staff 1056 20 Jul 07:14 ..
-rw-r--r-- 1 rselbach staff 252 20 Jul 07:22 foobar.go
-rw-r--r-- 1 rselbach staff 72 20 Jul 07:43 go.mod
-rw-r--r-- 1 rselbach staff 322 20 Jul 07:44 go.sum
drwxr-xr-x 4 rselbach staff 128 20 Jul 08:01 vendor

Notice how go mod now has created a vendor directory in our module root. Inside it you’ll find the source code for the modules we are using. It also contains a file with a list of packages and versions:

$ cat vendor/modules.txt
# github.com/pkg/errors v0.7.0
github.com/pkg/errors

We can now add this to our repository. But it’s not all done. Surprisingly, when modules support is enabled, the go command will ignore our vendor directory completely. In order to actually use our vendor directory, we need to explicitely tell go build to use it

go build -v -getmode=vendor

This essentially emulates the behaviour of previous version of Go.

An LRU in Go (Part 2)

So we created a concurrency-safe LRU in the last post, but it was too slow when used concurrently because of all the locking.

Reducing the amount of time spent waiting on locks is actually not trivial, but not undoable. You can use things like the sync/atomic package to cleverly change pointers back and forth with basically no locking needed. However, our situation is more complicated than that: we use two separate data structures that need to be updated atomically (the list itself and the index.) I don’t know that we can do that with no mutexes.

We can, however, easily lessen the amount of time spent waiting on mutexes by using sharding.

You see, right now we have a single list.List to hold the data and a map for the index. This means that when one goroutine is trying to add, say, {"foo": "bar"}, it has to wait until another finishes updating {"bar" : "baz" } because even though the two keys are not related at all, the lock needs to protect the entire list and index.

A quick and easy way to go around this is to split the data structures into shards. Each shard has its own data structures:

type shard struct {
cap int
len int32

sync.Mutex // protects the index and list
idx map[interface{}]*list.Element // the index for our list
l *list.List // the actual list holding the data
}

And so now, our LRU looks a bit different:

type LRU struct {
    cap int // the max number of items to hold
    nshards int // number of shards
    shardMask int64 // mask used to select correct shard for key
    shards []*shard
}

The methods in LRU are now also much simpler as all they do is call an equivalent method in a given shard:

func (l *LRU) Add(key, val interface{}) {
    l.shard(key).add(key, val)
}

So now it’s time to figure out how to select the correct shard for a given key. In order to prevent two different values of the same key to be stored in two different shards, we need a given key to always return the same shard. We do this by passing a byte representation of the key through the Fowler–Noll–Vo hash function to generate a hash as an int32 number. We do a logical AND between this hash and a shard mask.

The hard part is actually getting a byte representation of a key. It would be trivial if the key was of a fixed type (say, int or string) but we actually use interface{}, which gives us a bit more work to do. The shard() function actually is a large type switch that tries to find the quickest way possible to find the byte representation of any given type.

For instance, if the type is int, we do:

const il = strconv.IntSize / 8
func intBytes(i int) []byte {
    b := make([]byte, il)
    b[0] = byte(i)
    b[1] = byte(i >> 8)
    b[2] = byte(i >> 16)
    b[3] = byte(i >> 24)
    if il == 8 {
        b[4] = byte(i >> 32)
        b[5] = byte(i >> 40)
        b[6] = byte(i >> 48)
        b[7] = byte(i >> 56)
    }
    return b
}

We do similar things to all of the known types. We also check for custom types that provide a String() string method (i.e. implement the Stringer interface.) This should allow for getting the byte representation for the vast majority of types people are likely to want to use as a key. If, however, the type is unknown and is not a Stringer (nor has a Bytes() []byte method), then we fall back to using gob.Encoder, which will work but is very slow to make it realistic usable.

So what does all of this does for us? Now we never lock the entire LRU when doing operations, instead locking only small portions of it when needed, this results in my less time spent waiting for mutexes on average.

We can play around with how many shards we want depending on how much data we store, but we can potentially have thousands of very small shards to provide very fine locking. Of course, since dealing with sharding does have a small overhead, at some point it is not worth adding more.

The following benchmarks were done with 10000 shards and without concurrency —

BenchmarkAdd/mostly_new-4 1000000    1006 ns/op
BenchmarkAdd/mostly_existing-4 10000000  236 ns/op
BenchmarkGet/mostly_found-4 5000000  571 ns/op
BenchmarkGet/mostly_not_found-4 10000000     289 ns/op
BenchmarkRemove/mostly_found-4 3000000   396 ns/op
BenchmarkRemove/mostly_not_found-4 10000000  299 ns/op

And this with 10000 shards with concurrent access —

BenchmarkAddParallel/mostly_new-4 2000000    719 ns/op
BenchmarkAddParallel/mostly_existing-4 10000000  388 ns/op
BenchmarkGetParallel/mostly_found-4 10000000     147 ns/op
BenchmarkGetParallel/mostly_not_found-4 20000000     126 ns/op
BenchmarkRemoveParallel/mostly_found-4 10000000  142 ns/op
BenchmarkRemoveParallel/mostly_not_found-4 20000000  338 ns/op

Still, each shard still locks completely at every access, we might do better than that.

Source code on Github.

An LRU in Go (Part 1)

In my job, I often catch myself having to implement a way to keep data in memory so I can use them at a later time. Sometimes this is for caching purposes, sometimes it’s to keep track of what I’ve sent some other service earlier so I can create a diff or something. Reasons are plenty.

I noticed that I keep writing versions of the same thing over and over and when we’re doing that, maybe it’s time to try and create a more generic solution. So let’s start simple, shall we? What we want is to implement a least-recently-used list (LRU) with no fuss.

Naïve LRU

We start with a simple and very naïve implementation (see the full implementation on Github.)

type LRU struct {
    cap int                           // the max number of items to hold
    idx map[interface{}]*list.Element // the index for our list
    l   *list.List                    // the actual list holding the data
}

We don’t have much there, we have a doubly-linked list l to hold the data and a map to serve as an index. In true Go fashion, we create an initializer —

func New(cap int) *LRU {
    l := &LRU{
        cap: cap,
        l:   list.New(),
        idx: make(map[interface{}]*list.Element, cap+1),
    }
    return l
}

This is nice. Package users will initialize the list with something like l := lru.New(1000) and joy will spread thoughout the land. But I strongly believe the empty value of a struct should also be usable, which is not the case here :

var l LRU
l.Add("hello", "world")

This will panic because neither l nor idx are initialized. My go-to solution for this is to always provide a simples unexported initialization function that is run at the beginning of each exported method and makes sure the initialization is done.

func (l *LRU) lazyInit() {
    if l.l == nil {
        l.l = list.New()
        l.idx = make(map[interface{}]*list.Element, l.cap+1)
    }
}

Now, let’s see how we’d add a new item to the list —

func (l *LRU) Add(k, v interface{}) {
    l.lazyInit()

    // first let's see if we already have this key
    if le, ok := l.idx[k]; ok {
        // update the entry and move it to the front
        le.Value.(*entry).val = v
        l.l.MoveToFront(le)
        return
    }
    l.idx[k] = l.l.PushFront(&entry{key: k, val: v})

    if l.cap > 0 && l.l.Len() > l.cap {
        l.removeOldest()
    }
    return
}

We call lazyInit to make sure everything is initialized than we check whether the key already is in our list. If it is, we only need to update the value and move it to the front of the list as it’s now become the most-recently-used.

If, however, the key was not already in our index, then we need to create a new entry and push it to the list. By the way, this is the first time we see entry, which is an unexported type that we actually store in our list.

type entry struct {
    key, val interface{}
}

Finally, we check whether by adding the new element, we just passed the capacity of the list (if cap is less than 1, we treat as there being no limit to capacity, by the way). If we are over capacity, we go ahead and delete the oldest element in the list.

This is a naïve implementation, but it’s also very fast.

BenchmarkAdd/mostly_new-4                2000000            742 ns/op
BenchmarkAdd/mostly_existing-4          10000000            153 ns/op
BenchmarkGet/mostly_found-4             10000000            222 ns/op
BenchmarkGet/mostly_not_found-4         20000000            143 ns/op
BenchmarkRemove/mostly_found-4          10000000            246 ns/op
BenchmarkRemove/mostly_not_found-4      20000000            142 ns/op

Getting and removing elements is in the same ballpark as accessing a built-in Go map. Getting an existing item adds a bit of overhead on top of accessing the map because it also needs to move the element to the front of the list, but that’s a very fast pointer operation so it’s not that bad.

Adding has to check for an existing item as well as adding/moving the list element, so it’s relatively slower, but still good enough for my immediate needs.

There is a big problem though. This implementation is not at all safe for concurrent use. Sure, package users could protect it with a sync.Mutex but we may want to hide the complexity from them.

The (once again naïve) solution is to protect the list and map accesses with a sync.Mutex of our own.

Concurrent-safe Naïve LRU

Not much needs to be changed to make our naïve implementation safe for concurrent use (full implementation on Github.). We add a mutex —

type LRU struct {
    cap int // the max number of items to hold

    sync.Mutex                               // protects the idem and list
    idx        map[interface{}]*list.Element // the index for our list
    l          *list.List                    // the actual list holding the data
}

And at the top of every exported entrypoint we do something like —

func (l *LRU) Add(k, v interface{}) {
    l.Lock()
    defer l.Unlock()
    l.lazyInit()

Et voilà, we’re safe for concurrent use. But let’s see what the benchmarks tell us.

BenchmarkAdd/mostly_new-4            2000000           819 ns/op
BenchmarkAdd/mostly_existing-4      10000000           200 ns/op
BenchmarkGet/mostly_found-4         10000000           277 ns/op
BenchmarkGet/mostly_not_found-4     10000000           219 ns/op
BenchmarkRemove/mostly_found-4       5000000           325 ns/op
BenchmarkRemove/mostly_not_found-4  10000000           220 ns/op

Overall the code is slightly slower due to the (for now minimal) overhead of the mutex operations. However, although we are safe for concurrent use, we’re not really taking advantage of it, the entire code is completely sequential. An Add will prevent anyone from getting an item. Even a call to Len() locks everyone out.

This will be clear if we modify the tests to run in parallel.

BenchmarkAddParallel/mostly_new-4            1000000          1040 ns/op
BenchmarkAddParallel/mostly_existing-4       5000000           433 ns/op
BenchmarkGetParallel/mostly_found-4          5000000           293 ns/op
BenchmarkGetParallel/mostly_not_found-4     10000000           289 ns/op
BenchmarkRemoveParallel/mostly_found-4       5000000           305 ns/op
BenchmarkRemoveParallel/mostly_not_found-4  10000000           291 ns/op

On average, the calls will take longer because most of the times they’ll have to wait for another operation to finish and free the mutex.

In the next post, we’ll try and cut on the locking considerably.

How to use FileServer with Gorilla’s Subrouter

I’ve just spent much more time than I ever wanted to get this right, so here’s how I did it for future reference.

I have a function that returns an http.Handler, kind of like this:

func Handler(prefix string) http.Handler {
    r := mux.NewRouter().PathPrefix(prefix).Subrouter()
    r.HandleFunc("/foo/", fooHandler).Methods("GET")
    r.HandleFunc("/bar/", barHandler).Methods("GET")
    return r
}

The prefix could be something like “/api/” or “/ui” or whatever, so this http.Handler will serve /api/foo and /api/bar, for example. So far so good.

Now, I also want to serve some static files under the prefix’s “root” (again, something like “/api/”.) My initial thinking was something like this:

r.Handle("/", http.StripPrefix(prefix, http.Dir("./somedir")))

It works fine for anything under the root of “./somedir” but it failed with a 404 error for anything under different subdirectories. I found some answers online, but they never seemed to use a subrouter and thus didn’t work for me at all.

I finally figured it out:

r.PathPrefix("/").Handler(http.StripPrefix(prefix, http.FileServer(http.Dir("./somedir"))))

It wasn’t obvious to me at all.