In any kind of stateful distributed system, the problem of mapping a key to a set of machines is pretty common. Even if a distributed system is stateless, you might still want to map a key to the same set of machines for better locality of processing. In its essence, this is very similar to how hash tables work — map a set of k keys to n buckets.

The simplest way to do this is to use modular operations. Hash your key to get a fixed length value, then compute the modulo with n and pick the machine in that slot. For a uniform hash function, this works well if the number of endpoints doesn’t change very frequently and if the cost of re-mapping keys between endpoints is low. If either of those two is not true, this performs very poorly because all of your keys could get remapped if the size of the list changes.

These days, the standard way to limit the number of keys being re-mapped is to use consistent hashing. Most major distributed databases use it in some form or another. Consistent hashing is a special kind of hashing where on an average, K/n keys are remapped whenever the list of endpoints changes (K is the total number of keys). The term consistent hashing first appeared in literature in 1997 in this paper. In consistent hashing, both the keys and the buckets are hashed onto a circle. A key maps to the first bucket that is encountered in the clockwise direction (or counter-clockwise — it doesn’t really matter). Searching for the bucket responsible for a key is pretty simple — pre compute the hash values for all buckets and sort them, hash the key and then run a binary search (in O(log(n))) to find the lowest value that’s higher than the hash of the key. When the buckets are resized, some keys move over to the closest new bucket. On average, the number of keys that need to move is K/n — which is ideal.

One of the biggest drawbacks of consistent hashing is that keys can be imbalanced across buckets. This is mainly because of how resizing is handled. For example, if a bucket is removed, all keys mapped to that bucket move over to the next one (similar for the case where a bucket is added). Ideally, these keys would be distributed equally across all the remaining buckets. To overcome this problem, most implementations divide each physical machine into multiple virtual nodes. Even then, the keys now spread out over as many virtual nodes you assign to a physical machine instead of the ideal state of the load spreading out over all of them. If the number of virtual nodes is not higher than the number of machines, the load can be distributed unevenly.

Rendezvous hashing predates consistent hashing by a year and takes a very different approach to solving these problems, while maintaining the K/n re-mapping invariant. Unfortunately, it’s not as well known as consistent hashing. It’s also known as Highest Random Weight hashing, because of how it’s implemented. Conceptually and practically, it’s much simpler to understand and implement. You hash the key and the machine together and then pick the one with the highest hash value.

type router struct {
  endpoints []*Endpoint
}

func (r *router) Get(key string) *Endpoint {
  var ep *Endpoint
  hashVal := -INF

  for _, e := range r.endpoints {
    h = hash(key, e)
    if h > hashVal {
      ep = e
      hashVal = h
    }
  }
  return ep
}

In case of a uniform hash function, if the buckets change, the keys (on an average, K/n keys) get spread out over all other buckets instead of just one or the number of virtual nodes that were assigned to a machine. The biggest drawback of rendezvous hashing is that it runs in O(n) instead of O(log(n)). However, because you don’t typically have to break each node into multiple virtual nodes, n is typically not large enough for the run-time to be a significant factor.

We actually used this at Twitter in our internal pub/sub platform, EventBus. EventBus was modeled similar to Kafka — there were topics, and topics had subscriptions. A group of clients together consumed a subscription. We called this smallest unit, a stream. Unlike Kafka, EventBus had separate storage and serving layers — so you could scale out the serving layer horizontally. More importantly, any machine could serve a stream. Also, unlike Kafka, we supported a mode where all clients within a subscription could choose to receive a full copy of the stream and implement their own filtering.

Initially, we randomly assigned these streams to different serving machines. This worked fine when the number of streams was in the low hundreds. However, over time, some of our most popular topics (like the one with tweets) gathered streams numbering in the tens of thousands, many with client-side streaming enabled. Because the serving layer kept a local cache of events for each stream and different streams could be reading data at different offsets, every machine started keeping a large amount of data in memory — leading to horrendous GC pressure. We needed an easy way for a group of clients to independently converge on the same serving machine for a particular stream so that an item, once cached, could be sent to multiple clients. We used rendezvous hashing to do this with pretty good results. The clients would select a machine while starting consumption and then periodically rebalance every 5–10 minutes till the throughput across different machines stabilized.

Sometimes, elegant and obscure algorithms tend to outperform conventional wisdom.

Rendezvous Hashing was originally published in i0exception on Medium, where people are continuing the conversation by highlighting and responding to this story.

Benjamin Franklin once said — “Those who give up essential accuracy for temporary speed deserve neither speed nor accuracy”. In the real world, however, you frequently have to trade off one for the other. This tradeoff becomes increasingly appealing as your data volume increases. In this post we’ll discuss some common sampling techniques and ways to get the most out of your data, especially as it relates to product or behavioral user analytics.

Before we look at how to sample, it’s important to understand what the data being sampled looks like. In most cases you’re going to collect events. These are an immutable record of user interactions. Each event typically has a timestamp and a user identifier associated with it. Optionally, you might want to collect some metadata with each event. Typically, once you add instrumentation to your apps or websites (or use a tool that automatically collects everything), these events are generated in response to every user interaction. So, if you’re already generating these events — why sample?

There are two main reasons why you might want to consider looking at a smaller subset of your data for insights — speed and cost. In some cases, you can get faster results if you decide to spend more on computation. However, not all computations are infinitely parallelizable.

How to sample

Whether you decide to sample by dropping data during collection or at query time, how you choose to ignore data matters. It’s important to have the sampling be random — otherwise you’ll run into sampling bias, which makes analysis hard. There are a few ways to do this.

Sample every event

This is the most naive way to sample data, but it works well if you only care about aggregates. Here, the decision to sample is independent of the event or user being tracked. When you run aggregates, you can multiply by the inverse of the sampling factor to get an approximate value. The biggest drawback of this approach is that any kind of analysis that depends on a sequence of events (like a funnel report) is usually incorrect.

Sample high volume events

Not all events are made equal. You are likely to have a few outliers that contribute the most to event volume. Random sampling for these outliers and collecting all other events un-sampled works well in practice. This has the same drawbacks as the previous approach, but the impact is restricted to analysis that spans the outliers.

Sample all users

For user analytics, every event is likely to have an associated user identifier. This represents the individual you are tracking information about. The goal of this approach is to keep all activity for a small sample of users and discard all activity for the others. If the user identifiers you keep data for are selected at random, you can extrapolate the results to get accurate numbers. The good part about this approach is that it works for aggregates as well as for any analysis that depends on a sequence of events, so long as it is per-user.

Sample high volume events by user

Here, we take the good parts of approaches 2 and 3 and combine them. We sample events by user but only restrict the sampling to high volume events. Any analysis that you do on events that don’t involve outliers gets full fidelity whereas anything that’s done across outliers still has accurate numbers as long as the analysis is done per-user. Most major analytics providers let you do this.

Sample by users but always track certain populations

This is basically the same as the previous approach, except you have some way to always track a specific set of users based on some pre-defined criteria. Say, you want to track everything about users who pay you more than $1000 per month — you can do that by always including every event for any of these users. This works well if this sample is relatively small compared to the rest of your user base and you are careful about addressing the edge cases of tracking when someone enters or exits this special population.

User Identity Management

Before we look at where to sample, it’s important to look at one of the biggest challenges with user based sampling. In this day and age, people have multiple devices that they might interact with your application or website on. In addition, users might do the bulk of their activity while logged out and only identify themselves when they have to. This flexibility makes it hard to decide which user identifiers should be in the sample and which shouldn’t — mainly because it’s a chicken and egg problem.

Anonymous and Logged In activity

For most applications and websites, some kind of user identification is required to interact with the product. There are exceptions (as we’ll see later), but for a majority of products, Login acts as the great filter. Once a user logs in, the decision of whether to include it in the sample can mostly be made on the basis of whatever unique identifier your database has for that user. It’s also possible to tie back any of their anonymous activity to the identified user based either on heuristics or actual knowledge (if someone logs in on a device where you previously tracked anonymous activity, there is a good chance that the anonymous activity can be tied to the logged-in user).

However, there are entire verticals where a bulk of your users are going to be anonymous. Travel, e-commerce, search, video etc. see a lot of anonymous activity and users don’t necessarily identify themselves during an interaction with your product.

Users with multiple accounts

The other challenge that some products run into is where users have different identifiers on different platforms. You might use a phone number to identify on the app and an email address to identify on a website. Additionally, you might also allow your users to identify using social media accounts. Tying all these activities back to the same user typically requires some kind of heuristics or best-effort matching and it usually happens long after you’ve been tracking information with these different identifiers.

Where to sample

User identity management plays a big role in determining the utility of your approach to sampling, because once you decide how you want to sample your data, the other important decision you’ll have to make is where to do this.

Broadly speaking, you have 2 choices —

1. collect everything and sample when you run queries.
2. drop data during collection and run queries on the sampled data.

If you’re considering sampling as a way to reduce costs, it’s helpful to understand the 3 types of costs associated with data —

Collection costs are those associated with tracking and processing the data all the way up to the point where you can decide whether to include the event in the sample or not.

Storage costs are what you pay for keeping the data around at rest. These costs compound over time as the data footprint increases.

Query costs are what you pay for processing the sampled data to get meaningful insights.

Here’s what the costs look like based on the approach you take

+----------------------+-------------+----------+----------+
|        Option        |  Collection |  Storage |   Query  |
+----------------------+-------------+----------+----------+
| Sample at query      |  Full       |  Full    |  Sampled |
| Sample at collection |  Full       |  Sampled |  Sampled |
+----------------------+-------------+----------+----------+

Sample at query

This is a little more expensive than the second one because you pay full storage costs and your collection costs might be a little higher depending on how early in your collection process you can determine whether a user falls in the sample or not. However, it has very few drawbacks because you don’t drop any of the data so you can merge user activity as and when you discover connections between anonymous, logged-in and users with multiple accounts. If you can afford to, collect everything.

Sample at collection

If you absolutely must drop data, there are a few ways to try to minimize the impact —

Sampling Technique

Always sample just the high volume events by the user identifier and keep everything around at full fidelity. This reduces the impact of sampling to any analysis that involves the outliers in terms of volume.

Anonymous vs. Logged In users

If your product has low anonymous activity and most users identify themselves before any interaction, you might be able to get by with keeping a copy of all the anonymous data and only sample data for users who have identified themselves. This gives you full visibility into any anonymous activity and at the same time, any analysis that spans anonymous and logged-in usage is correct.

If your product has high anonymous activity and low logged in activity, flip the two — sample all the anonymous data and keep all the logged in activity around for analysis. The drawback of doing this is that analysis spanning anonymous and logged-in usage will be incorrect.

Unfortunately, for most other cases, sampling at collection results in either incomplete or inaccurate data and there’s no real way to counter that.

Conclusion

Sampling plays an important role in improving the speed of analysis and, in some cases, reducing costs. If you can afford to pay the additional processing and storage costs, always sample while running queries. The costs for running queries are typically much higher than the other two, especially as you scan the data multiple times for different kinds of analysis. Keeping a full copy of all the data also lets you use that data for any kind of analysis that involves machine learning or statistical modeling. It also lets you run exploratory analysis on a sample while still retaining the ability to run more important queries on the full dataset.

If you absolutely can’t afford to keep a full copy, try to minimize the impact of sampling by reducing the scope of user identity management challenges on your choice of sampling technique and make sure that you factor in all the corner cases when interpreting the results of your queries.

Sampling — the good, the bad, and the ugly was originally published in i0exception on Medium, where people are continuing the conversation by highlighting and responding to this story.

While the Go programming language specification only states that the iteration order over maps is not guaranteed to be the same across invocations, Go maps in action goes a step further to say that the order is randomized. So, when someone at work asked how I would design a set of integers that returned a random entry on every get , I suggested this neat trick

type intSet map[int]struct{}

func (s intSet) put(v int) {
        s[v] = struct{}{}
}

func (s intSet) get() (int, bool) {
        for k := range s {
                return k, true
        }
        return 0, false
}

Turns out that this approach is incorrect because, while it returns a “random” number on every get, the probability for every element is not the same.

To test this implementation, let’s actually fill up a map with some values and see the distribution over a million runs.

func main() {
        s := make(intSet)
        for i := 0; i < 8; i++ {
                s.put(i)
        }

        counts := make(map[int]int)
        for i := 0; i < 1024*1024; i++ {
                v, ok := s.get()
                if !ok {
                        return
                }
                counts[v]++
        }

        for k, v := range counts {
                fmt.Printf("Value: %v, Count: %v\n", k, v)
        }
}

This is the output you get on running this

code|⇒ ./code
Value: 1, Count: 131026
Value: 7, Count: 130957
Value: 3, Count: 131064
Value: 5, Count: 131288
Value: 2, Count: 131080
Value: 0, Count: 130813
Value: 4, Count: 131137
Value: 6, Count: 131211

That’s good, right? The distribution of each number is roughly equal. Let’s change the numbers a bit and see what happens. For the next run, I added the numbers 0 to 4 instead.

code|⇒ ./code
Value: 1, Count: 131175
Value: 2, Count: 131593
Value: 3, Count: 130904
Value: 0, Count: 654904

While the counts for 1 , 2 and 3 are roughly the same, 0 occurs almost 5 times as often. A truly random distribution would have been around 250000 occurrences of each number.

To explain this anomaly, it’s important to understand how maps are implemented in go. Unsurprisingly, maps are implemented using go. The map.go file in src/runtime contains the common parts of the implementation (there are some optimized map implementations for common types like integers and strings). The comments in map.go help lay out the structure of a map

// A map is just a hash table. The data is arranged
// into an array of buckets. Each bucket contains up to
// 8 key/value pairs. The low-order bits of the hash are
// used to select a bucket. Each bucket contains a few
// high-order bits of each hash to distinguish the entries
// within a single bucket.
//
// If more than 8 keys hash to a bucket, we chain on
// extra buckets.

Let’s take a look at what happens when you’re iterating over a map. If you disassemble the for loop, you’ll see something like this.

TEXT main.intSet.get(SB) /home/aniruddha/code/main.go
  ...
  main.go:10  0x488e56  4889442408   MOVQ AX, 0x8(SP)
  main.go:10  0x488e5b  488d442418   LEAQ 0x18(SP), AX
  main.go:10  0x488e60  4889442410   MOVQ AX, 0x10(SP)
  main.go:10  0x488e65  e8763df8ff   CALL runtime.mapiterinit(SB)
  main.go:10  0x488e6a  488b442418   MOVQ 0x18(SP), AX
  ...
  main.go:11  0x488e93  c3    RET

The call to mapiterinit is what sets up the iterator and then calls the mapiternext function to get the first element in the map. Here’s the part of the code in mapiterinit that actually computes where to start iterating —

r := uintptr(fastrand())
if h.B > 31-bucketCntBits {
  r += uintptr(fastrand()) << 31
}
it.startBucket = r & bucketMask(h.B)
it.offset = uint8(r >> h.B & (bucketCnt - 1))
it.bucket = it.startBucket

We generate a random number using fastrand() and then use it to get the starting bucket and a random offset within that bucket (remember, maps in go are implemented as an array of buckets with 8 elements in each bucket). mapiternext then iterates over the elements to return the first valid entity — while doing so, it skips over any empty ones

for ; i < bucketCnt; i++ {
  offi := (i + it.offset) & (bucketCnt - 1)
  if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {
    // TODO: emptyRest is hard to use here, as we start iterating
    // in the middle of a bucket. It's feasible, just tricky.
        continue
  }
  ...
}

Because the element we start with could be empty, the probability of getting a valid element is actually dependent on the number of empty buckets and elements immediately preceding it. For example, if there is 1 bucket with 2 valid entities like in the example below —

[NULL, NULL, 10, NULL, NULL, NULL, NULL, 20]

We’ll get 10 if we start with elements 0, 1 or 2 and 20 if we start with 3, 4, 5, 6 or 7. So the perceived probability of getting a 10 is 3/8 and for 20 is 5/8 .

While this was a toy problem that I was trying to solve, the broader learning for me was to not base solutions on ones interpretation of library documentation. It’s almost always a good idea to test how things behave in practice even if the documentation feels clear and correct.

Map iteration in Go was originally published in i0exception on Medium, where people are continuing the conversation by highlighting and responding to this story.

Defer scopes to a function, not a block

A variable exists only within the scope of a code block. However, a defer statement within a block is only executed when the enclosing function returns. I’m not sure what the rationale for this is, but it can catch you off guard if you’re, say, allocating resources in a loop but defer the deallocation.

func do(files []string) error {
  for _, file := range files {
    f, err := os.Open(file)
    if err != nil {
      return err
    }
    defer f.Close() // This is wrong!!
    // use f
  }
}

Chaining methods

If you chain methods in a defer statement, everything except the last function will be evaluated at call time. defer expects a function as the “argument”.

type logger struct {}
func (l *logger) Print(s string) {
  fmt.Printf("Log: %v\n", s)
}

type foo struct {
  l *logger
}

func (f *foo) Logger() *logger {
  fmt.Println("Logger()")
  return f.l
}

func do(f *foo) {
  defer f.Logger().Print("done")
  fmt.Println("do")
}
 
func main() {
  f := &foo{
    l: &logger{},
  }
  do(f)
}

Prints —

Logger()
do
Log: done

The Logger() function is called before any of the work in do() is executed.

Function arguments

Okay, but what if the last method in the chain takes an argument? Surely, if it is executed after the enclosing function returns, any changes made to the variables will be captured.

type logger struct {}
func (l *logger) Print(err error) {
  fmt.Printf("Log: %v\n", err)
}

type foo struct {
  l *logger
}

func (f *foo) Logger() *logger {
  fmt.Println("Logger()")
  return f.l
}

func do(f *foo) (err error) {
  defer f.Logger().Print(err)
  fmt.Println("do")
  return fmt.Errorf("ERROR")
}
 
func main() {
  f := &foo{
    l: &logger{},
  }
  do(f)
}

Guess what this prints?

Logger()
do
Log: <nil>

The value of err is captured at call time. Any changes made to this variable are not captured by the defer statement because they don’t point to the same value.

Calling methods on non-pointer types

We saw how chained methods behave in a defer statement. Exploring this further, if the called method is not defined on a pointer receiver type, calling it in a defer will actually make a copy of the instance.

type metrics struct {
  success bool
  latency time.Duration
}

func (m metrics) Log() {
  fmt.Printf("Success: %v, Latency: %v\n", m.success, m.latency)
}

func foo() {
  var m metrics
  defer m.Log()

  start := time.Now()
  // Do something
  time.Sleep(2*time.Second)
  
  m.success = true
  m.latency = time.Now().Sub(start)
}

This prints —

Success: false, Latency: 0s

m is copied when defer is called. m.Foo() is basically shorthand for Foo(m)

Conclusion

If you’ve spent enough time writing go, these might not feel like “traps”. But for someone new to the language, there are definitely a lot of places where the defer statement does not satisfy the principle of least astonishment. There are a bunch of other places that go into more detail about some other common mistakes while writing go. Do check them out.

Common traps while using defer in go was originally published in i0exception on Medium, where people are continuing the conversation by highlighting and responding to this story.

Using defer, however, is not free. Using go’s benchmarking support, we can try to quantify this overheard.

The following two functions do the same work, but one calls a function in a defer statement while the other doesn’t

package main

func doNoDefer(t *int) {
  func() {
    *t++
  }()
}

func doDefer(t *int) {
  defer func() {
    *t++
  }()
}

Let’s benchmark these —

package main

import (
  "testing"
)

func BenchmarkDeferYes(b *testing.B) {
  t := 0
  for i := 0; i < b.N; i++ {
    doDefer(&t)
  }
}

func BenchmarkDeferNo(b *testing.B) {
  t := 0
  for i := 0; i < b.N; i++ {
    doNoDefer(&t)
  }
}

Running this with go -bench on an 8 core google cloud VM gives us

⇒ go test -v -bench BenchmarkDefer -benchmem
goos: linux
goarch: amd64
pkg: cmd
BenchmarkDeferYes-8  20000000   62.4 ns/op  0 B/op  0 allocs/op
BenchmarkDeferNo-8   500000000  3.70 ns/op  0 B/op  0 allocs/op

As expected, both these functions don’t allocate any memory. But doDefer is roughly 16 times more expensive than doNoDefer. To understand why defer is this expensive, let’s look at the disassembled code.

The disassembly for the actual functions called inside doDefer and doNoDefer is the same

main.go:10   MOVQ 0x8(SP), AX
main.go:11   MOVQ 0(AX), CX
main.go:11   INCQ CX
main.go:11   MOVQ CX, 0(AX)
main.go:12   RET

The doNoDefer sets up the necessary registers and then calls main.doNoDefer.func1

TEXT main.doNoDefer(SB) main.go
main.go:3  MOVQ FS:0xfffffff8, CX
main.go:3  CMPQ 0x10(CX), SP
main.go:3  JBE 0x450b65
main.go:3  SUBQ $0x10, SP
main.go:3  MOVQ BP, 0x8(SP)
main.go:3  LEAQ 0x8(SP), BP
main.go:3  MOVQ 0x18(SP), AX
main.go:6  MOVQ AX, 0(SP)
main.go:6  CALL main.doNoDefer.func1(SB)
main.go:7  MOVQ 0x8(SP), BP
main.go:7  ADDQ $0x10, SP
main.go:7  RET
main.go:3  CALL runtime.morestack_noctxt(SB)
main.go:3  JMP main.doNoDefer(SB)

The doDefer function also sets up registers, but there are additional function calls — the first one to runtime.deferproc which sets up the deferred function to be called. The second one is to runtime.deferreturn — which in turn calls itself for every defer statement encountered in the function.

TEXT main.doDefer(SB) main.go
main.go:9    MOVQ FS:0xfffffff8, CX
main.go:9    CMPQ 0x10(CX), SP
main.go:9    JBE 0x450bd3
main.go:9    SUBQ $0x20, SP
main.go:9    MOVQ BP, 0x18(SP)
main.go:9    LEAQ 0x18(SP), BP
main.go:9    MOVQ 0x28(SP), AX
main.go:12   MOVQ AX, 0x10(SP)
main.go:10   MOVL $0x8, 0(SP)
main.go:10   LEAQ 0x218e3(IP), AX
main.go:10   MOVQ AX, 0x8(SP)
main.go:10   CALL runtime.deferproc(SB)
main.go:10   TESTL AX, AX
main.go:10   JNE 0x450bc3
main.go:13   NOPL
main.go:13   CALL runtime.deferreturn(SB)
main.go:13   MOVQ 0x18(SP), BP
main.go:13   ADDQ $0x20, SP
main.go:13   RET
main.go:10   NOPL
main.go:10   CALL runtime.deferreturn(SB)
main.go:10   MOVQ 0x18(SP), BP
main.go:10   ADDQ $0x20, SP
main.go:10   RET
main.go:9    CALL runtime.morestack_noctxt(SB)
main.go:9    JMP main.doDefer(SB)

deferproc and deferreturn are both non-trivial functions and they do a bunch of accounting and setup at entry and exit. In short, don’t use defer in hot code paths. The overhead is non-trivial and not obvious.

Runtime overhead of using defer in go was originally published in i0exception on Medium, where people are continuing the conversation by highlighting and responding to this story.

At a high level, the mmap system call lets you read and write to a file as if you were accessing an array in memory. There are two main modes in which files can be mapped — MAP_PRIVATE and MAP_SHARED. In MAP_PRIVATE, any changes that you make to the file are in memory and not written back to it. In MAP_SHARED, changes made to the file are visible to other memory mappings of that file and are eventually committed to disk.

To understand what happens on calling mmap, it’s important to understand two things — how linux handles files and how memory addressing works.

You can open a file for reading or writing using the open system call. This returns a file descriptor. Linux maintains a global file descriptor table and adds an entry to it representing the opened file. This entry is represented by the file structure which is local to the process. Internally, linux uses the inode struct to represent the file. The file struct has a pointer to this and linux ensures that multiple file descriptors that touch the same file point to the same inode so that their changes are visible to each other. The i_mapping field on the inode struct is what’s used to get the right set of pages from the page cache for an offset in the file.

In linux, processes have a virtual memory address space that’s, well, virtual. This memory is not usually backed by physical memory unless you’re actually reading or writing to some part of it. Linux further divides the memory space into equal sized pages and a page is the unit of access as far as the kernel is concerned. So, when a process calls mmap, the short answer is that nothing really happens. The kernel simply reserves some part of this virtual memory address space and returns the address. The do_mmap function is what eventually gets called after some bookkeeping and does most of the work for allocating this virtual memory in the process’ address space. This function stores a pointer to the file struct in the vm_area_struct struct that represents the returned address.

When the process accesses the address, a page fault occurs. The page fault handler locates the vm_area_struct struct in the process’s address space and eventually finds the pages in the page cache that map to the file offsets being accessed. These pages are marked as dirty if there’s a write and mapped directly to user space — this way there is no need to copy data from kernel to user space.

Once you’re done using the memory mapped area, the munmap system call can be used to free up the memory. Any data written to the page cache is periodically committed to disk, although you can force it with msync. While mmap is useful, it definitely has drawbacks. Misses in the page cache always result in the page being read into the cache even if a write is going to overwrite the contents. Offsets need to be aligned to page boundaries. Error handling happens via signals because there is no way to indicate otherwise. And finally, you can’t mmap all types of file descriptors(pipes for example). As usual, conditions apply — so make sure you don’t use mmap indiscriminately.

Memory Mapped Files was originally published in i0exception on Medium, where people are continuing the conversation by highlighting and responding to this story.

For those of you who haven’t used Go, consider using it for your next side project. It’s a very opinionated programming language with a spec that you can mostly hold in your head and a fairly comprehensive standard library. Also, unlike most other languages, you don’t have to deal with a ton of testing frameworks. Although the standard library provides good support for writing tests, I’ve found the following techniques useful in writing better testable code.

It’s okay to test unexposed functions

The default package layout in Go encourages housing code and tests in the same package. Tests can access “private” functions and members — this is okay. I’ve mostly encountered this in the context of helper functions that are only used within a package. The alternative is to expose them publicly, which has its drawbacks.

Control time

Avoid using the time package to block or schedule execution. Consider using something like clockwork to pass in a fake, controllable clock in unit tests. Controlling time lets you write more deterministic unit tests. This is useful when you’re testing behavior that depends on time — timeouts, retries, scheduled runs etc.

Use Go’s race detector

Data access races are really hard to debug. Fortunately, Go has support for detecting them — so use it. This is a good starting point to understand how to use the race detector. Remember that it will only test the code paths that your tests execute. So you still need to write a test that exercises the race.

Write benchmarks

Go makes writing benchmarks easy. This is a good starting point to understand how to write them. Make sure you have benchmarks for the performance sensitive parts of your code.

Use setup functions

This is useful if you want to setup some external state that is used by the function or implementation being tested. An example would be something that operates on a directory. Instead of having every test function create a temporary directory and clean up after itself, write a generator function that does this.

func withTempDir(t *testing.T, f func(d string)) {
 dir, err := ioutil.TempDir(...)
 if assert.NoError(err) {
  defer os.RemoveAll(dir)
  f(dir)
 }
}

func Test(t *testing.T) {
 withTempDir(t, func(dir string) {
  // use dir in test
 })
}

Accept interfaces, return structs

Interfaces can be mocked; structs cannot. Having interfaces as member variables makes it easy to mock their behavior. Returning structs (concrete implementations) means that the caller gets to decide how to use the returned value.

That said, use mocks carefully. With mocks, you’re testing your understanding of the interface, at the time the test was written. While this is ideal, it’s not always practical — especially in high velocity codebases. If you think the underlying implementation is unstable, test it in a separate package to avoid diverging.

Lastly, use a mock generator like mockery instead of writing them yourself.

Use self referential interfaces

This is a neat trick that I’ve found useful for testing behavior that is either non-deterministic or doesn’t fit well in a unit test because it makes network calls or depends on an external service. Let’s say you want to test the behavior of a function A() on a struct of type Foo that makes a non-deterministic function call that uses a member variable (like a network connection) in Foo . An easy way to do this is to move the non-determinism into a function B() on Foo and introduce a new member variable on Foo that satisfies an interface exposed by B() and call B() on this member. The actual code can use an instance of Foo as the member variable and the tests can provide a mock. The code below should make things clearer.

package main

import (
 "fmt"
)

type doer interface {
 B()
}

type Foo struct {
 msg string
 d doer
}

func (f *Foo) B() {
 fmt.Printf("i am non deterministic: %v\n", f.msg)
}

func (f *Foo) A() {
 f.d.B()
 fmt.Println("test me")
}

func main() {
 x := &Foo{
  msg:"go",
 }
 x.d = x // x.d = MockDoer() in tests
 x.A()
}

Although many of these techniques are useful, deciding where to use them is always a judgement call. Choose wisely!

Writing tests in Go was originally published in i0exception on Medium, where people are continuing the conversation by highlighting and responding to this story.

Aniruddha on Twitter: "Finally gave in and bought the kinesis keyboard @kinesisergo pic.twitter.com/lJLFQssj8V / Twitter"

Finally gave in and bought the kinesis keyboard @kinesisergo pic.twitter.com/lJLFQssj8V

For the first few days, typing on the Advantage was difficult. As a touch typist, going from 100 WPM to 30 was very frustrating.

Aniruddha on Twitter: "Hunt and peck programmers, how do you live with yourself? / Twitter"

Hunt and peck programmers, how do you live with yourself?

But within a week, I regained most of my original speed. My wrists felt a lot better and going back to a regular keyboard caused noticeable stiffness around my shoulders.

Aniruddha on Twitter: "One week with the @kinesisergo and I'm up to 84 WPM (I usually type at > 100) pic.twitter.com/6XsBMwf9Zw / Twitter"

One week with the @kinesisergo and I'm up to 84 WPM (I usually type at > 100) pic.twitter.com/6XsBMwf9Zw

Although I could type without having to look up keys on every alternate keypress, I kept bottoming out and in general disliked the feel of the keyboard. I knew why — it was the switches.

The Advantage uses Cherry MX Brown switches. In fact, Cherry made them specifically for the original contoured Kinesis keyboard. While they are tactile, the browns aren’t clicky like the blues. I’ve been a huge fan of the blues ever since I got my hands on the TVS Bharat Gold keyboard. What I wanted was a Kinesis Advantage, but with the clicky blues.

Kinesis doesn’t make the Advantage with blues (they’re exploring a limited run for the Advantage2). I sent a DM to their Twitter account to explore possibilities and they suggested that I get in touch with their support team.

Their support team is amazing and super responsive. Within 10 minutes of me sending an email, they responded. I wasn’t the first one trying to modify an Advantage. They sent me links to blogs and part numbers for pieces I needed to make this happen.

I was surprised at how cheap the pieces were — especially given that a new Advantage costs over $250. The only problem was that my experience with soldering was limited to what I did in school, which was around 10 years ago. I spoke to a few people, who assured me that it isn’t as hard as it sounds and that watching a few youtube videos should be enough.

So I went ahead and ordered the 2 key-wells and their PCBs (the first 4 parts in the email). I didn’t order the thumb cluster because the switches are PCB-mounted and I could simply swap them. I also ordered a cheap soldering kit from Amazon along with solder and diodes.

Next, I had to source the switches. Original Cherry MX Blues are expensive! I needed roughly 70 of them and the cheapest ones I found were still around $50 with shipping. I’d heard a lot of good things about Gateron Blues from the friendly folks over at /r/MechanicalKeyboards and Switchtop sells them for $0.275 each (I’m fairly happy with the folks at switchtop for shipping the switches within a day!). In 4 days I had all the things I needed to make the “switch”.

Soldering was pretty daunting at first. I opened up an old alarm clock and tinkered with the PCB. I desoldered a bunch of components and tried to solder them back. I thought I did everything right, but the clock refused to start. Not a good first step. I did, however, get a hang of using the soldering iron and the solder. Now, the worst thing I could do was screw up a PCB worth $7.50.

I started by mounting the switches on the right hand key-well. Some switches were duds, so I made sure I tested the clicky-ness (if that’s even a word) before using a switch. This was the easy part.

Next up was adding the PCB and soldering the switches. Given the contoured shape of the key-wells, the PCB is flexible and, at times, difficult to align with the switch leads. The bottom row switches would keep falling out, so I removed them and decided to deal with the rest of the switches first. What worked best was soldering one column at a time, starting with the outermost one. I used a crocodile clip (the picture below shows the left key-well instead of the right, but you get the idea) to hold the PCB in place while I soldered away to glory.

I added the bottom row at the very end and unsurprisingly, this went a lot smoother now that the rest of the PCB was in place.

I then started soldering the diodes. With diodes, it’s important to make sure that you get the orientation right. On the Kinesis, the black part of the diode is oriented towards the left if the switch leads are to the top. This is true for both key-wells. I tested the board right after soldering one diode by removing the ribbon cable from the original PCB and plugging it into the new one.

Aniruddha on Twitter: "One key out of the 28 currently works. @kinesisergo #excited pic.twitter.com/IC0PVUGurE / Twitter"

One key out of the 28 currently works. @kinesisergo #excited pic.twitter.com/IC0PVUGurE

At this point, I was somewhat confident of being on the right track. I soldered the rest of the diodes

and replaced the old key-well.

I tested all the switches using www.keyboardtester.com to make sure they registered and then added the keycaps. Doing the second key-well was much faster now that I had a good idea of what needed to be done, and in what order. It took me around 8 hours from start to finish, but that included time off to get dinner.

Aniruddha on Twitter: "And done with key wells! I now have a clicky kinesis advantage! pic.twitter.com/d1MpsW4Pio / Twitter"

And done with key wells! I now have a clicky kinesis advantage! pic.twitter.com/d1MpsW4Pio

I haven’t modified the thumb cluster yet, mainly because I’m planning to add Gateron greens instead of blues. I’m also waiting for blank PBT keycaps that I ordered for cheap from China. All in all, this was a fun project and completely worth the hassle. I’ll post a photo of the keyboard once I get the new keycaps.

Update — I got the Chinese PBT keycaps.

Aniruddha on Twitter: "New blank keycaps on my kinesis advantage! pic.twitter.com/gMPWKwUkao / Twitter"

New blank keycaps on my kinesis advantage! pic.twitter.com/gMPWKwUkao

Update #2— SA profile keycaps look great on the Kinesis

Aniruddha on Twitter: "Absolutely loving the SA profile keycaps. Can't use a regular keyboard, so I put them on my Kinesis @kinesisergo pic.twitter.com/NevEX4ewXZ / Twitter"

Absolutely loving the SA profile keycaps. Can't use a regular keyboard, so I put them on my Kinesis @kinesisergo pic.twitter.com/NevEX4ewXZ

Kinesis Blue was originally published in i0exception on Medium, where people are continuing the conversation by highlighting and responding to this story.