A recipe is just a set of steps that worked for somebody and then they wrote them down. I will give you my recipe, but understand that you’re probably going to need to change something based on your exact circumstances: the type(s) of flour you have, where you live (altitude, temperature, humidity), amount of free time. Your goals might be different than mine, so perhaps you’ll want to adjust my process. My goal for my process was to minimize the active time, but also the start-to-eating time. This ruled out multi-day fridge ferments common to high-hydration sourdough and no-knead recipes, and also using a pre-ferment. I wanted to reduce dishes and cleanup, so I decided to knead in my mixing bowl rather than on a floured countertop. This also meant no stand mixer or food processor. I wanted to eliminate single-use plastic, so I use a wet tea-towel to cover my dough while proofing and resting instead of plastic wrap.

This recipe is for one loaf, but note that doubling it and baking two loaves is not much more work than baking a single loaf, and then you have one to give away or stuff in the freezer.

I use an Escali Primo digital scale with a small metal mixing bowl on it to scale out my dry ingredients. This is a compromise between dumping everything straight into the large mixing bowl and scaling out everything into tiny prep bowls. This matches with my “minimize dishes” goal. I measure the yeast and salt with a ¾ tsp measure.

Bread lies between the exact science of baking and the free-for-all of cooking. Bread tends to be quite forgiving. Having so many different sets of instructions for effectively the same product makes it clear that bread is fungible. All the different steps and ingredient alterations affect the output, but less so that you might think.

Scale out and add (in this order):

• 3–4g instant dry yeast (~¾ tsp). Don’t bother with Active Dry. Instant can be added directly in with the flour, Active Dry needs to be proofed in water first (although modern manufacturing methods have made this step less important ). Active dry offers zero benefits over Instant, and is pretty much only used by home bakers out of tradition and familiarity at this point.
• 150g whole wheat flour
• 10g salt (~1.5 tsp)
• 350g AP flour. Because I live in Canada, I can get away with the regular all-purpose flour for bread baking. If you’re somewhere else, you probably need to choose a bread flour. Or use AP and adjust the hydration level down.

I use this order to avoid putting the salt directly on top of the yeast out of bakery’s superstition although it doesn’t actually matter in practice.

Mix the dry ingredients together with a bowl scraper. Add in 325g of “wet” water. “Wet” in this sense means it shouldn’t feel hot and it shouldn’t feel cold. It should just feel — wet. For an actual temperature, it’s about body temp. I get this by adding 100g freshly-boiled water to 225g cold water from my tap. And yes, I actually did the math on this. This water gives me a desired dough temperature of about 78F, as expected. You may need a slightly different water temperature based on where you live, or know that your bread might take longer to proof.

Pour the water into the bowl and mix to a shaggy mass with the dough scraper. I begin with a mixing motion, and when the dough gets stiffer I change to more of a cutting motion make places for the remaining dry flour to get into the center of the dough. Once it’s almost into a single mass, I use the bits of dry flour in the bottom of the bowl to rub off any dough from the scraper and switch to kneading by hand. It only takes 30s to a minute to knead in the bowl to get the dough into a single cohesive mass with no remaining dry flour in the bottom of the bowl or stuck to the sides. Kneading in the bowl instead of on the counter reduces additional countertop cleanup. Scraping down the sides of the bowl will also ease cleanup later.

Next step is the autolyse. Cover the dough with a wet tea towel (I use hot water from the tap) and set a timer for 20 minutes. Many recipes will say not to add salt for autolyse, but it’s trickier to knead it in afterwards by hand (since I’m not using a stand mixer) and with a dryer dough (since I’m making a sandwich-type loaf). Also, traditional autolyse doesn’t have yeast, but similarly for the salt it’s tricky to knead it in afterwards, and since instant yeast takes about 20 minutes to fully hydrate anyway nothing will happen during the short period. Some autolyse can wait for up to 1–2 hours, but I decided those were too long for me.

Next, knead in the bowl for another 30s or so and then let rest for 15 minutes. Kneading just ensures that all the flour has a chance to come in contact with water, thus forming gluten. This happens slowly over time, or quickly with mechanical agitation. These two quick kneading and restings replace the longer 8–10 minute period of full kneading, or a 12–24h period of just waiting.

(While I said 20m and then 15m rests, my actual ranges are probably 15–30m for the autolyse period and 10–20m for the second rest.) If you do choose to do the full knead instead of the periods of kneading and resting, don’t worry about over-kneading: your arms will give out before the dough will.

Knead once more for 30s, then shape into a ball and cover. This is the bulk fermentation stage. In the summer it usually takes 90m before this step is finished, in the winter maybe 2h. I set a timer for 90m and check on it to see if it needs more time. You can set the dough in your oven (turned off!) with the light on to provide a bit of sheltered warmth. Stretch-and-folds are less important for a sandwich type loaf we’re making here, but are a good idea if you’re using a wetter dough to develop a nicer gluten cloak.

When the bulk fermentation step is done, it’s time to shape. Dust a bit of flour onto the top of the dough and a bit on your counter. Using your dough scraper get all the dough out of the bowl. Try not to leave any bits of dough in the bowl; this will make cleanup easier.

Preshape the dough into a round, let it rest for 20 minutes or so to relax the gluten, then shape into your final loaf. These steps are difficult to describe with words, so I’m just going to link to Ciril Hitz’s basic bread shaping tutorial. Boules are easiest to start with. If you’re not using a loaf pan it will probably take a while before your loaves look like what you’d get in the bakery. Bread shaping is a physical skill that needs to be acquired. You can watch lots of videos on it (I certainly did!) but you need to train your hands to make the right motions. One of the issues of being a home baker is that you only get shaping practice once a week or so. It certainly took me a while before I was happy with my free-form loaves. You can also use a loaf tin which solves some of the shaping issues, but you’re going to want to play with other shapes eventually so may as well learn.

Re-cover your proofing loaf with your wet tea towel for 45–60m, maybe longer. The dough should be marshmallowy. Soft, with a gentle spring-back, kind of like the pad of flesh at the base of your thumb when you’re making an “ok” sign. If it doesn’t spring back at all when you press it, it’s probably over-proofed. You can probably reshape it and rescue it.

To clean up your counter, scrape the rest of the flour into your bowl and rub it around to clean up any remaining bits of dough. Preventing dried on bits of dough will again ease cleanup. They should be easy to remove straight into the compost. Dough going down your drain will clog it.

Preheat your oven to 425F with a roasting tray on the bottom rack, and boil some water in a kettle. 450F gives a nicer crust but I find the loaf was a bit stale by the time we finished the loaf, so I’m happy for a slightly cooler bake. Also, ovens lie. The recipe developer’s oven lied to them, and your oven is lying to you. Take notes in your journal and adjust for next time.

Score your loaf and put it straight into the oven for 40 minutes. The scoring is more easily explained with a video. If you have a baking/pizza stone, you should probably use it (and it should be heating in your oven for an hour) I have one, but it’s tiny, and baking on a half-sheet pan easily lets me do two loaves. The debate is still out on pizza steels: I’ve heard they’re more likely to burn the bottom crust, but I have no first-hand experience with this. I’m happy with a silpat on my sheet-pan and I can fit two loaves on it.

Right after putting your loaf in, pour about a cup of water into the roasting tray. This is an important step. It significantly helps the crust. If you’re baking in a Dutch oven, the covered environment handles the steaming for you. But again, I’m baking on a half-sheet pan. I didn’t want to deal with trying to transfer loaves into a 450F hunk of metal with small kids potentially underfoot. Also going with a Dutch oven basically limits you to boules, and I enjoy experimenting with different loaf shapes.

When the timer goes, pull out your bread and cool it on a rack to avoid steaming the bottom and getting a soggy crust. Don’t cut into them yet — they’re not finished cooking until they cool.

Hope this helps. This is obviously a lot of detail, but this is how I bake bread. It takes a lot more space written out than it actually feels when baking it.

And remember: Baking your first loaf encourages you to bake more loaves.

Bake more bread.

Like this article? Buy me a coffee.

A classic piece of advice, but I don’t really know anything about fishing. I do however know about baking bread. (See poorly-lit pictures of my bakes on my instagram account with slightly nicer photos here.) And instead of only giving you a recipe, I’m going to add another meta level and talk about my process for learning how to make bread. Replicating that will give you a much better lifetime of bread than a single bread recipe.

My process, and the path I suggest you follow, is to treat bread baking as a series of experiments, controlling for different variables until you reach both a loaf you’re happy to eat and a process to get you there that fits your life.

1. Get a scale. This is probably my most important baking tip. Using volumetric measurements introduces too many variables between bakes, especially with flour. A gram scale leads to consistency of ingredients. Baking the same quality loaf needs consistency.
2. Keep a notebook. Experimentation is the process of iteration, changing as few things as possible and examining the result. Writing everything down let me recreate my successes and diganose my failures. It’s important to take notes on each loaf you bake. What were the quantities of the ingredients? What was the mixing procedure? How long did it bulk ferment? At what temperature? What shape and scoring pattern did you use? What temperature did you bake at? For how long? And finally, are you happy with the loaf and what will you do differently next time? (Some thoughts on notebook usage. I stuck with a physical notebook because it had the lowest friction of use for me. But that does mean I need an index to quickly find my “master recipes” and particularly important notes — I can’t grep dead trees. It gets a bit cluttered having reference (recipes), actions (modifications for next time) and someday/maybe (recipes to try in the future) in the same place. Similarly, when using a shorthand for recipes, be sure to include enough to fully recreate it. More than once I’ve had the formula but missed recording exactly the steps (rest times, proofing, etc) and the next batch was less successful. Here are some actual sample entries from my notebook: “Reduce rye percentage next time. Dough was too sticky”, “No significant difference for 25–15 autolyse/knead vs 20–10–10 autolyse-fold-knead schedule”, “Don’t flour workbench for bagels; they just slide around”, and “85g too small for hamburger buns but ok for dinner rolls”.) There are lots resources on keeping journals, but don’t go overboard. Your goal is baking bread, not bullet journalling or moleskine geekery.
3. Perfect one single recipe. Your flour type, your environment, your climate, your life. This is so that your learnings are directly applicable to your next bake. If you’re constantly switching up the kind of loaf you’re baking, from an experimental point of view it will be harder to know if you’re improving. I recommend a French-style lean dough with only flour, water, salt and yeast, possibly with a small portion (10%-30%) of the flour being whole-wheat. Don’t worry about fancy flours when you’re first learning. They’re expensive and you’ll feel guilty about throwing out your mistakes / bricks. Secondly, they’re more likely to behave differently from the recipes you find online.
4. Learn Bakers Percentage. This step is optional but highly recommended. Maybe it’s just my math degree talking, but having bread formulas laid out like this makes it easier to look at a recipe and understand what to expect from it, and also to scale them up or down to make the amount of dough you need for what you want to bake. Recipes in BP% list all ingredient amounts as a percentage of the flour weight, so adding more or less flour will skew the ratios. If you’re trying a new recipe, you can hold back BP 2% of the water and adjust from there. This also means that unlike most home recipes where a range of flour quanity is provided (most will say to add more or less flour until the dough is the right consistency), recipes in BP% will instead adjust the amount of water to control the dough consistency.
5. Use resources from professional bakers instead of home bakers. This is a follow-on from the previous tip. (Be particularly aware of recipes from American home bakers: they tend to use way too much yeast and way too much sugar/fats for “regular” breads.) People have been baking bread for thousands of years and have accumulated lots of folk wisdom around it. Luckily, modern bakeries have studied bread making in pursuit of commercial optimization, so much of this folk wisdom has either been disproven and discarded, or analyzed, distilled and improved. There is a lot of science involved in bread baking, and many people have written tomes about it. You don’t need to know all the science to make good bread, but it helps to figure out why things turned out the way they did and what direction to move in until you find a recipe you’re happy with.
6. Learn to knead and shape high hydration dough. You will end up with it accidentally anyway, either during your own experiments or when testing a new recipe. Just switch kneading methods, note it in your journal, and keep baking. Different flours absorb different amounts, and so a recipe that says 80% hydration but uses organic, stone-ground whole wheat flour will be a very different dough if made with regular supermarket all-purpose flour. In general, you want to put in as much water as you’re comfortable with for a nice tender open crumb, but high hydration loaves have their own issues. They’re tricker to knead and trickier to shape. (When you start playing with bagels and pretzels, then you’ll get experience with low-hydration doughs.) Some videos on working with wet doughs: How to Mix Wet Dough (Trevor Wilson), Shaping High Hydration Dough (FoodGeek) .
7. Play with different bread shapes. Shaping is a fun way to have a lot of variety with the same dough. You can bake your dough as a boule, or in a loaf pan, or flattened out as a focaccia or fougasse, divided small and shaped into buns (of which there are a zillion variations), rolled thinly into breadsticks or flattened and baked as pitas. These are all worth experimenting with to vary your bakes from the same-old loaf.
8. Don’t lust after the Instagram-perfect loaf. This is one specific type of bread. These tend to be high-hydration sourdough loaves which are tricky to work with and take a while to get right. A simple yeasted straight-dough will be a much quicker win. Also, ask yourself how useful a loaf with huge open holes in the crumb is for spreading jam or peanut butter on. While they may look pretty, they make lousy sandwiches for my kids’ lunch boxes.
9. Relax. Bread is very forgiving and people have been baking it for a very long time without any of the tools I’m recommending here. In my 18 months of baking multiple loaves per week, only once have I ended up with an actually inedible loaf: a failed sourdough attempt. The loaves may not be beautiful, but they’ll all be edible and most will be delicious.
10. Understanding your one bread recipe will let you move around the bread “map” with more confidence. When you’re comfortable with a basic bread dough, other items like brioche, bagels, foccacia, pretzels, English muffins, and cinnamon buns are a much smaller step.

Consider the universal bread recipe:

Flour: different flours (whole wheat, rye, kamut, …), different mixes (all white vs 50% whole wheat, …)

Pre-ferment: none, poolish, biga, old-dough

Water: bagels are low hydration (50%), ciabatta is much higher (85%)

Salt: 2% of flour weight is pretty standard

Yeast: 0.6% of flour weight for a 90m-2h rise, less for longer proof times and higher for enriched doughs. None at all for flat breads like tortillas and roti.

Fats: Butter, oil, milk. Generally under 5%, but higher for grissini (Italian bread sticks) and brioche.

Add-ins: seeds, nuts, fruit, cheese, chocolate, …

Fillings/Toppings: cinnamon/sugar, apple cinnamon, meats, cheeses, …

As with the shaping, small variations in the ingredients can lead to a huge variety of breads. Your local bakery probably makes most of their loves with the same large batch of dough but different add-ins, shapes, and mark-ups.

Once you can bake your single perfect loaf, bread becomes a delicious Choose-Your-Own-Adventure(tm).

I also recommend avoiding sourdough at the start. Since learning to bake bread is a series of experiments, you want your iterations to be as fast as possible. Waiting 3 days to see if a change has had the desired affect is a huge slowdown compared to 4–5 hours for testing buns or a regular yeasted bread and will affect how quickly you can learn and improve.

And since many people have been asking me for book recommendations, my favourite is “Bread: A Baker’s Book of Techniques and Recipes” by Jeffrey Hamelman. I’ve found there are three categories of baking resources: thoose aimed at the home baker who just wants to make bread, those aimed at people attempting to recreate “artisan-style” bread at home, and those aimed at the professional baker working in industry. Jeffrey Hamelman’s book is definitely the third category but is totally accessible for the home baker.

The next post in this series is be the recipe and process I currently use to bake our regular 30% whole wheat bread, along with the little tips and tricks I’ve added to the process.

Like this article? Buy me a coffee.

Engineering Guidelines are a collection of your an organizations’ Best Practices; a distillation of the institutional knowledge around “how things should be done here”. They are a cross between a Mission Statement, Company Values, and an Employee Handbook for your engineering department.

Does your company have engineering guidelines? It should.

Consider the original promise of the 12-factor app: “If you write your code in this way, you get all these nice things.” Engineering guidelines are the same, but for your organization. It should explain both the overarching guiding principles, but also the nitty-gritty details of how to actually do things.

You need to lay out standards for

• The code (formatting, style, tests)
• The development process (CI, code review, deployments)
• The service (flags, configs, metrics, logging)

(This blog post will be focusing primarily on the technical aspects. There should also be thought put into writing down the *cultural* guidelines for your engineering department, but those will be hand-waved over for now. Similarly on the design side, user-visible aspects will need to have consistent UI and UX. Those are beyond the scope of this article.)

You need a rationale so people understand the context in which these decisions have been made. This allows exceptions when these base assumptions do not hold, or updating the guidelines when the larger context changes. It’s about making decisions once for consistency. It’s about avoiding known issues or edge cases. It’s about choosing a specific technique with known tradeoffs for dealing with problems.

This is the role guidelines play. The goal is consistency. You may not agree with a particular guideline, but having *something* means relieving cognitive burden from both writers and readers.

Consistency is important once there are multiple developers working on a code base. It keeps everybody on the same page. As new developers join, all the projects they look at follow similar rules. SREs who are paged in the middle of the night have an idea what they’re up against.

More things work as expected with fewer surprises.

At smaller organizations, guidelines manage the freedom from less corporate inertia around how to do things. This freedom can easily lead to a much larger variety of practices which can be difficult to rein in later.

Your guidelines don’t exist in isolation. They frequently need institutional support to be effective. For example, if the guidelines state the recommended way to set up automated CI builds requires multiple commits to different repositories with different teams needing to +1 the changes *and* multiple coordinated rollouts, then few projects are going to bother to properly set up CI for their projects. You need to make it easy to do the right thing.

The Code

This is what most people think of when they think of guidelines: a document that specifies four-space indents, Allman style braces and that every function have a 10-line Javadoc listing inputs and outputs.

But beyond that, this section needs to describe not only the “allowed languages”, but how they should be written at your company. Note that this might be at odds with how the chosen languages are written elsewhere. For example, Google famously does not use C++ exceptions. Note that If you plan on deviating substantially from the existing cultural norms for your chosen languages, it’s worth reading the Goals section of Google’s guidelines and similarly Titus Winters’ CppCon talk on “The Philosphy of Google’s C++ code”.

Documenting and/or linking to existing guides also helps people working with this language for the first time in your organization.

This quote from Rob Pike’s “Go Proverbs” sums it up: “Gofmt’s style is no one’s favorite, yet gofmt is everyone’s favorite.” The exact style is less important than the fact that there is consistency. And if a style decision is hard to make, it means both options are fine and just flip a coin.

The Development Process.

Modern software development has lots of steps between writing code in your editor and having it successfully merged into HEAD. This section will have policies in place for each of them.

Some suggested topics:

• commit message format
• how and where code review takes place
• setting up CI
• compiler flags (optimization levels, debug info, warnings)
• expectations for tests, including coverage and policies for unit/integration/end-to-end tests.
• which static analysis tooling to run
• when and how code generation tooling is run and kept updated
• branch usage and naming
• squash/merge and multi-commits vs. rebase/force-push during code review iterations
• issue trackers need size estimates (S/M/L/XL), bug priorities, and workflow documented
• for deployments: staging, canaries, incremental deployments, rollbacks
• documents outlining incident-handling and post-mortems,

A number of these items cover mostly vocabulary and definitions so that everybody is talking the same language.

The Service

This will probably be the largest section of your guidelines. It covers a wide range of topics covering how the code you write interacts with the rest of the environment. If the previous section covered *how* you code, this section covers *what* you code.

How does your service integrate itself into the rest of the existing infrastructure?

From the moment your service starts up, it’s going to need to be need information to configure itself. Standard configuration file locations and formats, as well and guides for naming command line flags are useful. Does your service need to reload its configuration in-place while still running, or a graceful restart while not dropping network connections? Should you aim for graceful-shutdowns or crash-only with recovery on startup?

Once your service is up and running, how does it communicate with other services? Does it need to contact a directory service? What about service authentication? Does it speak JSON over HTTP(S) or something else? What should the retry strategy be? How does it handle API versioning? And all of these need to be answered for the service as a client and a server.

Finally, how do you report to the rest of the world what’s happening? At the bare minimum, what are the policies around logging and metrics? For logs, what should be logged and where does it go? Are the logs structured for free-form? If using structured logs, what are the naming guidelines for common fields? Do you have different logging verbosity levels? If so, what are they and what should be logged at each level? Metrics again need a common destination and consistent guidelines around what to track and what to name them. How are distributed traces collected?

This section can also list recommended libraries for different tasks and banned libraries, each with their own justification sections.

Writing Your Own Guidelines

As the first internal advocate for Go at a large technology company, I took on the task of coming up with guidelines for our Go code. While we already had engineering guidelines, they were focused on the Perl side of things. Part of the guidelines I wrote were to a make rules for my playground. Part of it was an onboarding guide to Go. Part was how to integrate Go into the existing Perl infrastructure.

As this was all basically greenfield and I was on my own at the start. Part of it clarifying what development was like on the Go side of things (also for advocacy purposes — “Come play with our nice tools!”), but at the same time making clear my expectations for code people commited. This mostly covered differences from the development processes that the company had deemed acceptable for the multi-million line Perl codebase.

I spent a lot of time looking for best practices from similar organizations, with rationales if possible so that I could see if their goals matched mine. For example, people often point to Google engineering practices and try to imitate them and apply them to their own organization. But lots of practices that make sense at Google do not make sense in other organizations. You can not just absorb another company’s guidelines wholesale without taking their assumptions about their culture and associated infrastructure. (I might explore this more in another blog post I’m tentatively calling “The parable of glog”.)

I also spent time thinking about how I wanted my GOPATH to look and feel. I could look at what wasn’t working for me on the Perl side things, and write down a reasonable policy that made sense within the culture I wanted to foster.

The document I ended up writing was mostly a FAQ for developers new to Go, with specific attention paid to devs moving from Perl, as well as lots of notes on how to integrate into the existing infrastructure. In an effort to keep some parity with the existing Perl guidelines, I did end up implementing a number of packages that matched base libraries on the Perl side so make the transition easier. For example, being able to load existing standard config files and have some APIs familiar to people familiar with the Perl code base.

My guidelines were also a living document, not written in stone. Every time something happened that could have been caught sooner, it was added as something to watch out for.

Before I left, I added a final section to the guidelines document: a list of code janitor tasks I handled that would need to be picked up. “If everybody is responsible, then nobody is responsible”

How do you eat an elephant? One bite at a time.

Having guidelines is all good for greenfield development: As new code arrives, you ensure it conforms to the current known Best Practices. But what about applying these to an existing legacy codebase? The short answer is “It’s hard”. In the short term, document the known exceptions.

Decide if it’s worth code churn to an existing system. Some things, like updating the formatting, can be just done once at the cost of making git archeology a bit trickier. Fixing issues found by static analysis tooling are more suited to be worked on slowly.

Updating interactions with the environment are harder to justify. They’re no longer self-contained fixes, but have ripple on effects to either consumers or clients. Patching “working code” for no externally visible gain can be a hard sell, and may not always be the right choice. If the system is old, you may be able to default on the technical debt if a replacement is in the works.

Like this article? Buy me a coffee.

These articles represents only a fraction of the words that have been written about Go style, and this is by design my own opinionated list. Items which I feel don’t contradict each other (too much..) and come backed by significant experience writing high-quality Go code. Don’t feel sad if your favourite has been left out (but please let me know about it!)

The Classics

These lists are the fundamental Go guidelines. They’ve been around for ages and almost all Go projects do (or should) follow their advice.

Effective Go: The grand-parent of them all. There’s an open bug about freezing it and replacing it with something more dynamic, but until then this is absolutely Required Reading.

CodeReviewComments: The second fundamental building block of Go style guides. Probably the most linked-to. The description: “This page collects common comments made during reviews of Go code, so that a single detailed explanation can be referred to by shorthands. This is a laundry list of common mistakes, not a comprehensive style guide.” Many of these guidelines are checked by golint.

Go Proverbs: Rob Pike’s list of pithy, poetic statements. It’s a bit terse, so go watch the associated talk . The list of proverbs can be printed out and hung next to your monitor.

These first three are Primary Sources, or perhaps Word Of God for those familiar wth TVTropes. Ideas and tips from the language designers on how the language is meant to be used.

Googler Talks

This second set of resources are from Googlers sharing code style guidelines. These again come from the experience of writing, reading, and reviewing large amounts of Go code.

What’s in a name? : Andrew Gerrand talks about naming things.

Package Names: From Sameer Ajmani on the Go blog. Packages are important, and so are the names you choose for the various pieces.

When in Go, do as Gophers do : Fumitoshi Ukai talks about writing “readable” code in Go.

Twelve Go Best Practices : From Francesc Campoy. (And don’t forget to subscribe to Just For Func).

Style guidelines for Go packages : JBD’s write-up of package-level practices.

Idiomatic Go: From Dmitri “shurcooL” Shuralyov. Similar to CodeReviewComments. A short list backed with examples from the standard library. (I’m putting this under Googlers because even though he wasn’t at Google when he started this list, they were all gleaned from “official” sources.)

There are some relevant pages on the Go Wiki for more esoteric topics. These are more specific to the Go project, but provide reasonable guidance none-the-less: Target-specific code, Assembly Policy, Commit Messages, TestComments .

Non-Googlers

It feels silly to make this distinction. However, not everything that applies inside the Big G makes sense externally. It’s important to look at what the experience is for developer outside of Google’s walls.

Go Best Practices 2016: Peter Bourgon’s updated version of his talk from 2014. Lots of good info here. A voice of experience deploying production Go code in a number of environments.

Go for Industrial Programming : Another excellent article from Peter, this one focussing on writing Go code that allows for stability and clarity in the face of highly mutable business requirements of modern small software shops.

Practical Go: Real world advice for writing maintainable Go programs: From Dave Cheney, a full workshop.

The Zen of Go. More brilliant wisdom from Dave Cheney.

godocgo: Effective Go documentation: Documentation is important. Nate Finch gives a tutorial on how to make the most of godoc.

Further Reading

Many of Go’s best practices stem from the desire to solve issues encountered with large-scale software engineering. I wrote about these early influences in The Ideas That Shaped Go. You can also read about Software Engineering at Google and see how these practices fit within the larger Google development model.

Find this useful? Buy me a coffee!

I have a few hobbies I rotate through. One of them is memory techniques. I did magic when I was a kid, and I always loved the memory sections of mentalism books. I remember using these techniques in high school to memorize details of the first 20 elements of the periodic table for a chemistry test.

These techniques are easy. I started teaching them to my daughter when she was 5. I don’t use them to memorize long sequences of digits or multiple decks of cards, although it can be used for that. Mostly I use them to make my life a little bit easier. I remember grocery lists, seat numbers, addresses, directions, PINs and passwords.

You Can Have A Super-Power Memory

The basic strategy for remembering something is taking the thing you want to remember, encoding it in a way you can visualize, and linking it to something you know.

When you want to recall it, you think of the thing you know (which should be easy, because you know it) and the link brings you the image of what it was you wanted to remember.

The encoding and linking steps require actually paying attention to what it is you want to remember. Frequently when you don’t remember something it’s because you didn’t pay enough attention to it in the first place. You’re distracted with other goings on. You’re skimming but not actually taking the time to focus. By forcing yourself to pay attention, you’re much more likely to remember it even if the techniques didn’t actually work.

But of course the techniques do work, and they’re thousands of years old. The oldest surviving written memory text is more than 2000 years old and nothing has changed. Everything in it, the techniques and the tips, are still used today. The techniques themselves are older than that; we have evidence that non-literate cultures did and do all these things too. This is how knowledge was preserved and transferred before books and writing were commonplace.

You should actually try to use each of these techniques to memorize a list of items just so you can see how simple and effective they are. Don’t just read this article. Take some time to try them out. You can use a list of random words, but it will be more helpful to use it with something meaningful to you. Pick 20 years of Oscar winners, or the entries on the IMDB Top 250, or your company values, or a list of books on your bookshelf, or maybe this week’s grocery list.

We’ll look at each of the above stages: encoding, linking, and “something you know”.

Encoding

If what you want to remember is something nice and concrete, then the encoding stage can be easy. If it’s your grocery list, for example, you can picture apples, butter, milk, bananas, and chicken. These are nice, concrete images. If it’s a task you’re trying to remember, then pick something that will remind you of the task. Mailing a letter, picture a mailbox. Pick up your dry cleaning, picture a suit on a hanger. Call the dentist, picture a giant tooth or a toothbrush. Your “true” memory will make the link from the “hint” (the image) back to what the actual task is.

Abstract ideas can be more tricky. You have to find a way to turn them into a picture. “Anger” might be hard, but you can picture an angry *person*. Justice is abstract, but you can picture a judge with a wig and a black robe banging a gavel. Or the woman with the blindfold holding the scales. You need to turn the idea into something visual that you can manipulate in your mind’s eye.

Sometimes you’ll need to get more creative. Let’s say you’re trying to remember directions. Left and right are pretty abstract and hard to picture distinctly from each other. A giant arrow pointing one way is pretty similar to an arrow pointing the other way. But rabbits and lobsters are easy to picture. “Turn left at the gas station” might be hard to remember, but a lobster trying to use its claws to pump gas is not.

If I needed to remember that my seat is “27C”, I picture a cow on a cell phone. Cow for “C”, and the cell phone to me means “Nokia” which is “27”. (I’ll explain where this mapping comes from when I talk about encoding numbers.) For times, :15 is a 25-cent coin, :30 is a half of a grapefruit, :45 is a Pacman. Whatever you want to remember you have to create a picture for.

Sometimes there is no obvious equivalent for a word. Maybe it’s a name, or something in a foreign language. The solution is to break it down into syllables and make an image from those. For example, if you needed to remember the Canadian province of Manitoba, you could split it up into “man” and “tuba”, and picture an old man playing a tuba. I’m saying “old man” here to make it a more interesting picture to remember. It could be so heavy he’s having trouble picking it up, so it’s resting on the floor and he’s leaning over trying to blow in.

These are all different examples of encoding: visualizing an abstract idea by finding a mapping between it and something concrete.

Linking

The next step is linking: taking two or more things and creating a picture in your mind that combines them in a funny, surprising, disgusting, violent way.

This is how you connect the thing you want to remember to the thing you already know. That way, when you think of the thing you know, you’ll be reminded of the thing you wanted to remember.

You must actually see the picture you create. It must be vivid, in full colour, with lots of action and details. The vivid part is vital. Let’s say we want to want to link “monkey” and “orange”. It’s not enough to just think. “Ok, the monkey was peeling the orange”. That’s a boring image. Exaggerate the scale. Make it a huge orange. Or exaggerate the number. Make it millions of oranges. The monkey is diving into a ball pit filled with oranges. Make them interact. Exaggerate the action. It’s not peeling an orange, it’s throwing them at airplanes. Imagine King Kong climbing up, throwing oranges at airplanes and they’re hitting into the propellers to make orange juice that’s raining down. Close your eyes and really see the picture. Involve your senses. How does the sticky monkey fur feel? What is it doing with the peels? How is the monkey reacting? Involve your emotions. How does witnessing this scene make you feel? Sad? Amused? Grossed out? Actually feel that emotional response. All these will make it easier to reconstruct the image, and so remember what the items were.

There are lots of way to combine items. You can create images where A is being used instead of B or being made of B. If you needed to link “orange” and “candle”, you could picture peeling an orange and taking a bite, but it’s actually a wax candle inside complete with a burnt wick. Or peeling an orange and stacking the peel up on the orange like a candle and trying to light it for a romantic orange-lit dinner.

You don’t need to tell anybody your images. You can make them as obscene as you’d like.

You can use the linking method to remember a list. Just link together the first two items in the list, then make another image linking the second and the third, and so on. In this case the “something you know” is the previous item in the chain. I find this easier and faster than the story method, where you come up with a small story that incorporates all the items on the list. It’s just a set of unrelated images. Monkey links to orange. Orange links to candle. Candle links to dentist. It’s also easier to traverse the list backwards when linking than trying to tell the story in reverse: Dentist linked to candle, candle linked to orange.

Something You Know: Pegs

The last thing you need is “something you know”. These are called “pegs”, but instead of hanging your coat on them we’re going to be hanging memories. Pegs can be anything that you remember without having to think about it. This lets you link the something you want to remember to a peg, then want to remember it, you think of peg (this is easy because you know it) and your link will remind you of the item.

Here’s a set of rhyming pegs that you probably already know and can start using right away.

One — sun

Two — shoe

Three — tree

Four — door

Five — hive

Six — sticks

Seven — heaven

Eight — gate

Nine — wine

Ten — hen

When you want to remember a list of 10 items, link the thing you want to remember to one of the pegs. Going back to our list with the monkey, we would start with linking “monkey” and “sun”, since “sun” is our rhyming peg for “one”. Maybe the monkey is trying to get a sun tan, and is rubbing sun cream into its fur. Stuffing your toes into your shoe they squash up against orange slices making your socks wet and sticky. A tree filled with candles growing on it as the peasants arrive with their baskets for the traditional candle harvest.

To recall the items, go through the pegs: One, rhymes with sun, links to monkey. Two, rhymes with shoe, links to orange.

Remembering a list with pegs is more useful than linking the items together in a list. If you forget one item on a peg, you can still remember all the others. But forgetting a single link in a list breaks the chain completely. It also makes it easier to remember jump around the list. What was item 4? The item linked to “door”. Note that it’s easier to insert an item into a linked list than with pegs. This is the exact same trade-off as in computer science.

You’re not limited to only storing a single item on a peg. Each item could be a complex image linking several ideas, or the first link in another list.

You can mark items as “done” by destroying the image somehow. Set the monkey on fire, break the candle. They will stand out when you skim through your list.

What do you want to do if you want to remember more than 10 things? You create another peg list.

Here’s another peg system for numbers, where the pictures match the shape of the digit.

1 spear

2 swan

3 handcuffs / heart / bra / moustache

4 sailboat

5 hook+pulley / unicycle / curling rock

6 golf club

7 boomerang / scythe / ikea lamp

8 snowman / hourglass

9 balloon / elephant trunk

0 pancake / donut / frisbee

You can also create alphabet peg lists with different themes:

For example, animals:

Anteater / Bee / Cow / Dog / Elephant / Frog / Goat / Hippo / …

Or foods:

Apple / Banana / Corn / Dumpling / Egg / Fudge / Gravy / Honey / …

Pick whatever topic you like as long as you can fill the entire alphabet and make sure the images are all easy for you to visualize.

Some people use peg lists that are parts of their bodies: on top of head, ears, eyes, nose, all the way down to toes. You can probably get 15 items there.

Peg lists are great. There are lots of them out there. The problem is you have to keep coming up with them. And it’s sometimes hard to remember all the different peg lists. But there is another system that you can use to provide you with as many pegs as you need.

Something You Know: Memory Palaces

There are lots of names for this system: memory palace, mind palace, Roman room, method of loci. Sherlock Holmes has one. So does Hannibal Lecter. But these don’t just exist in fiction. They’re totally real and they totally work.

Close your eyes. Think of someplace familiar. Humans have excellent spatial memories, so this should be easy. A room in your house. A classroom. A park. A Favourite restaurant or cafe. The house where you grew up. Even a level of a video game, as long as you’re confident you know it inside out. Anywhere.

If you have to think too much about the space then you’ll have to spend mental energy on remembering your palace and that’s less to spend on remembering the items in it. Choose someplace you can already easily picture and navigate through in your imagination.

Pick a path through the space. Whatever makes sense to you, and to the location. You’ll need to follow this path every time through because that preserves the order of the items in the list. I generally go clockwise around the room, starting with something on my left as I walk in. I select locations left to right, top to bottom and further away to closer. Having a defined ordering helps me ensure I follow the same path if it has been a while since I used that particular route. It also helps reduce thinking when I’m creating it the first time.

Don’t trap yourself in a dead end or backtrack. Don’t cross your path. This keeps following the path smoother.

Maybe you’ll be standing in the doorway looking at everything, scanning. Maybe you’ll be travelling through. I do both, depending on what the space is. Rooms I tend to have a more-or-less fixed viewpoint. Some larger outdoor journeys I glide through.

When you’re creating your space, you can walk through your space in person, but it’s better to just do it in your mind. That way you’ll focus on the things that are important to you that you’ve *already* internalized, and temporary items (like a sock on the floor) won’t be considered for items.

Pick out 5 features. Pieces of furniture are good. Chairs, coffee tables, windows, bookshelves, lamps, cupboards. Things don’t move. Permanent fixtures in the room. Things that you can interact with. They should be different from each other because otherwise they’ll be hard to tell apart. They should be well spaced so they’re not too crowded together. Choosing items at different heights can help. As with selecting the palace, the path and items should be easy, obvious, and very familiar.

These items are the pegs that you will link images to.

Expand the journey through 5 rooms in your house with 5 things each. There’s 25 memorable pegs. 5 items in a room is low, actually, but it’s a good starting point. My rooms are more crowded. I put usually 10 or 15 pegs in a room. My most crowded ones have ~30. I have one in my kitchen, for example, that has fridge, freezer, inside various shelves of cupboards, cutting boards, stove-top, oven, dishwasher, sink, under sink, dish rack, garbage and recycling and so-on.

You’ll need to be able to walk through your locations confidently, in the correct order, both forwards and backwards. You don’t want to have to think about what the next peg is. You don’t want to miss a location, or visit them in the wrong order. Practice walking through it until you’re comfortable.

Some journeys will have entire rooms as stages, some will have many details in a room as stages. It all depends on how familiar you are with the spaces. My kitchen I know well and there are lots of nooks and crannies.

Journeys don’t have to be inside. A walk around the neighborhood can be a journey, with particular hedges, lamp posts, shops, porches, mailboxes, benches, crosswalks, and fountains as stages.

If you have a long list you might want to be able to jump to the 10th, or 20th item. Knowing you have 10 items per room just means start at the second room. The oldest surviving written memory text “Ad Herennium” suggests adding items to mark different spots. For example, a Golden Hand placed at location 5, or a friend named Decimus at 10.

You can also use each location as the start of its own linked list, with the main image being the central point with smaller details chained to it.

Before I start to memorize something, I figure out approximately how many items there are on it, and pick an appropriate journey. If I need more than one “room”, I figure out which ones I’m going to use. I close my eyes and run through the stages quickly so I know where I’m going to put each item. I make sure to rotate through the rooms in my house for grocery lists. This means I don’t have interference and by the time I reuse one the old items have faded away.

Memory palaces like this are incredibly useful. The have been used for thousands of years. If you want to remember the main points of a long speech, just put images representing the main points along the a journey. The phrase “In the first place” comes “In the first place in my memory palace”. When I gave this talk, the images I had in my memory palace for the first section on encoding were: a grocery list, an angry face, a lobster claw, a cow on a cell phone eating a grapefruit, and a man playing the tuba. This was enough to remind of the different points I wanted to cover.

It’s easy to use memory palaces to store categorized or hierarchical information: use a set of buildings, which are already grouped and hierarchical by default. Speeches might have less pull, but sales information or product information might be useful. Have one room for product A, another room for product B. You don’t need to remember a place you’ve been perfectly down to every tiny detail. As long as your mental model of it is consistent, that’s enough to use for memorizing.

Much like destroying items to mark them as done on a peg list, you can mark an room of section as done by setting it on fire or otherwise destroying the room. That makes it obvious when walking through the section has been dealt with.

Connect journeys into larger ones, to create a huge palace you can walk around in. Not restricted to physical limitations. Add a door that takes you somewhere else. I have journeys where an existing staircase in Amsterdam takes me to a door (non-existent) that opens into an apartment in San Francisco. You can create your own video game hub level where you attach doors that lead to other places.

Personally, I find it’s just fun to walk around these when I’m bored or trying calm my mind or fall asleep.

To help train yourself to create memory palaces, you can think back through your day and try to walk through all the places you’ve been. You can pretend to be a spy while you’re there, capturing as many details as possible to turn into locations. Make sure to memorize them without any people there — they’re just distractions. Even if even you don’t keep it as a long term memory palace, it’s a good exercise.

I have a number of journeys. They’re all mostly from places in Amsterdam, although I have started to create some here. I also have some permanent journeys for things I want to remember longer term. I have one that gives me 120 digits of Pi. This is totally useless, except that I find walking through it backwards a good way to calm my brain when I’m falling asleep is. I also have one for my credit card: it’s a bank in Amsterdam. Among the ATMs and the teller counters are images that remind me of the number, the CVC code, expiry date, and pin. 28 digits in all.

This brings me to my final topic: numbers.

Numbers

How do you memorize numbers? These are entirely abstract. Like playing cards, they have no intrinsic meaning. Nothing to picture or to manipulate. If you picture a giant digit “two”, or “27”, it’s easy to get it confused with a “12” or a “37”. How do you make these concrete, and distinct.

The point of this is not to memorize long strings of digits, although you can. I mostly use this to remember smaller numbers. PIN codes. Model numbers. Prices. IP addresses. Seat numbers.

Part numbers at the hardware store. Aisle number at IKEA. Bin numbers in the bulk section of the grocery store. Passports. Parking lot locations. Dewey call numbers at the library. Your kid’s shoe size. Numbers are everywhere.

I’m going to talk about the system I use. I’ve tried a few others, and this is what works for me. You will need to find the one that works for you.

The system is called the 2-digit Major system. I won’t bore you with the history other to note that it’s hundreds of years old.

We will assign each digit a consonant sound:

0 — s, z, soft ‘c’

1 — t, d

2 — n

3 —m

4 — r

5 — l

6 — sh, j, ch, soft ‘g’

7 — hard ‘c’, k, hard ‘g’

8 — f, v

9 — p, b

If you’ve studied phonetics you’ll notice that there are voiced/unvoiced pairs here. S is unvoiced, Z is voiced.

W, H, and Y aren’t assigned digits.

The mapping between letters and numbers is arbitrary, but the advantage of using this one is that this is the “standard” one that will allow you to use other lists and sites you find online.

Remembering the number/letter pairs is the only thing you need to just learn. The Wikipedia page for the Major System has mnemonics for the pairs, but I don’t know if these would be helpful. I learned the basic letter mappings so long ago I don’t know what “tricks” I used. My advice is to just drill it.

To remember a number, you turn the digits into letters, and then add vowels until you have a word you can picture. So, “86” is “f-sh”: fish. If you want to remember the number “127”, “TNK”, you could think of a tank. “0947” is “SBRG”: iceberg. 9495 84 1470 can be encoded as “Purple Firetrucks”.

I mentioned it’s the sound that’s important, not the spelling. For example, “knock” is “n-k”, or 2–7, because the first “k” is silent. Cough is “7–8” because the “g” (the “gh”) is an F sound. “Towel” is “15”, because the W sound isn’t part of the system, so there’s just T and L.

Figuring out how to split up the digits into words and which vowels to add to make a good image takes time. It’s fine for things you want to store longer term. There are websites and wordlists to help with this.

To make this system faster for everyday use, I have a standard picture I use for each of the 2-digit numbers. 00 is “ss”, which is “see-saw”. 42 is “r-n”, rain. 98 is “p-f”, a puff a smoke. I have a hundred of these.

To remember a sequence of digits like my credit card, I turn each two digits into a picture and combine two of them into a single image, and then I put that image in a location in a memory palace. I always construct the images so that I know which digits come first. For me, top to bottom, left to right, actor-object. Again, it doesn’t matter what you choose as long as you’re always consistent and when you see the image you can pick it apart again. I find two images is a good fit. Trying to stuff three images can get muddled sometimes.

If I have one digit left over (because the number has an odd number of digits) then I use a number shape peg.

Getting a 2-digit major system takes work. There’s a couple issues. First, you need to get pictures that resonate with you. Ones that you can picture. It took me a while to settle down all my numbers. Having to make sure no conflicts with other images. For example, I knew I wanted the alphabet peg list, so I had to make sure I didn’t have things twice. I knew I didn’t want any disconnected body parts. “20 for Nose”, “27 Neck”, “81 Foot” were out, so I had to come up with words for those. You’ll find lists online, but I don’t necessarily recommend taking one of them wholesale. Take the time to think about the words and the images and feel free to come up with something that works better for you. This is one person’s list, but by definition they’re very personal.

And once you have to words, you need to be able to get to them quickly. This is just practice. No joke, I put them in a flash card app on my phone. Any pair of numbers I saw I would translate, and numbers are everywhere. If I saw a car packed outside an address, I’d practice making a link between the address numbers and the plate numbers. I wouldn’t try to memorize them long term, but just to practice going through the steps. I actually enjoyed this phase, as it was fun to keep picturing all these bizarre combinations of items.

Another popular system is the Dominic System, which turns pairs of numbers into people. I won’t cover it here, but many people prefer it as they find people more memorable than objects. That wasn’t the case for me, which is why the items in my system are all things.

Object Placement

As I mentioned, I use two images per location. You could also use only 1, or even 3, as long as you can reconstruct the order. There’s another very common system that handles ordering for you. It was popularized by Joshua Foer’s book Moonwalking with Einstein

Person-Action (PA) or Person-Action-Object (PAO) groups numbers in sets of four (PA) or six (PAO). Every two digit pair is associated with a person and their action, or a person with both an action and an object. Each action must be unique, and it helps if it’s easy to associate with the person. I’m going to use the Dominic System for the this example, which translates digits into initials. The number 15 maps to AE, which we’ll turn into Albert Einstein. We then choose an appropriate action: in this case, “writing on a blackboard. For “72” (GB) we’ll use George Bush and have him waving an American flag.

To encode a number with PA, you use the first two digit to find a person and the next two digits to select an action. In our case, we would encode 1572 as “Albert Einstein waving an American flag.” If our picture was “George Bush writing on a blackboard”, then we’d decode that into the person GB=72, performing the action of AE=15: 7215.

PAO is similar but with an object added into the mix for one million distinct images: 721511 becomes “George Bush writing on a blackboard with a tennis racket”. In this example, the tennis racket comes from Andre Agassi, AA=11.

People like this system because of its high information density (6 digits per location) and you “automatically” get silly images that preserve digit order.

Keeping Track

I have a spreadsheet with all my memory palaces listed, as well as all my different peg systems. This includes the extra visualizations like the lobster/rabbit for left/right, grapefruit for times, and some others. This sounds strange, but don’t feel bad about writing down the things you want to remember.

Names

Everybody wants to know how to remember people’s names. I’m not going to cover this in detail. The basic idea is to attach an image of their name (Steve = “Stove”, Ashley = “Ash tray”) to some feature that stands out on their face. Everybody has something you can use. This also requires that you actually pay attention what their name is in the first place. Most of the time you’re too busy thinking of the next thing you’re going to say and the introduction phase is just a ritual that happens on autopilot. You can practice this by using names from photograph captions in newspapers and magazines.

Cards

Memorizing a deck of cards is basically a party trick. It’s excellent training to use your memory palace and create images, but doesn’t have any practical application. The underlying idea is the same: you need to turn an abstract card into a concrete thing you can use. One way is to use reuse the major system pegs. Spades are 1–13. Hearts are 21–33. Or create a new set of pegs with the first letter representing the suit, and the second letter from the major system, finally using rhymes for the face cards. The Dominic System has its own mapping from cards to people. Another system is based on visual shapes. The ace of spades is an airplane taking off. The two of clubs is a swan eating some clover. 2 shape, clover clubs. As with everything else, the images are combined and placed into a memory palace which you walk back through to recover the order.

Conclusion

Having a super-power memory isn’t hard. The techniques are simple and effective. Yes, it takes a bit of work to get used to, but so does everything else in life. And even if you just shove everything in Evernote, memorizing a deck of cards is still a cool party trick.

This was a lot to digest. Please reach out if you have any questions.

Say Thanks. Buy me a coffee.

Here’s a problem. I have a set of keys and values. I also have some servers for a key-value store. This could be memcached, Redis, MySQL, whatever. I want to distribute the keys across the servers so I can find them again. And I want to do this without having to store a global directory.

One solution is called mod-N hashing.

First, choose a hash function to map a key (string) to an integer. Your hash function should be fast. This tends to rule out cryptographic ones like SHA-1 or MD5. Yes they are well distributed but they are also too expensive to compute — there are much cheaper options available. Something like MurmurHash is good, but there are slightly better ones out there now. Non-cryptographic hash functions like xxHash, MetroHash or SipHash1–3 are all good replacements.

If you have N servers, you hash your key with the hash function and take the resulting integer modulo N.

 server := serverList[hash(key) % N]

This setup has a number of advantages. First, it’s very easy to explain. It’s also very cheap to compute. The modulo can be expensive but it’s almost certainly cheaper than hashing the key. If your N is a power of two then you can just mask off the lower bits. (This is a great way to shard a set of locks or other in-memory data structure.)

What are the downsides of this approach? The first is that if you change the number of servers, almost every key will map somewhere else. This is bad.

Let’s consider what an “optimal” function would do here.

• When adding or removing servers, only 1/nth of the keys should move.
• Don’t move any keys that don’t need to move.

To expand on the first point, if we’re moving from 9 servers to 10, then the new server should be filled with 1/10th of all the keys. And those keys should be evenly chosen from the 9 “old” servers. And keys should only move to the new server, never between two old servers. Similarly, if we need to remove a server (say, because it crashed), then the keys should be evenly distributed across the remaining live servers.

Luckily, there’s a paper that solves this. In 1997, the paper “Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web” was released. This paper described the approach used by Akamai in their distributed content delivery network.

It took until 2007 for the ideas to seep into the popular consciousness. That year saw two works published:

• last.fm’s Ketama memcached client.
• Dynamo: Amazon’s Highly Available Key-value Store

These cemented consistent hashing’s place as a standard scaling technique. It’s now used by Cassandra, Riak, and basically every other distributed system that needs to distribute load over servers.

This algorithm is the popular ring-based consistent hashing. You may have seen a “points-on-the-circle” diagram. When you do an image search for “consistent hashing”, this is what you get:

You can think of the circle as all integers 0 ..2³²-1. The basic idea is that each server is mapped to a point on a circle with a hash function. To lookup the server for a given key, you hash the key and find that point on the circle. Then you scan forward until you find the first hash value for any server.

In practice, each server appears multiple times on the circle. These extra points are called “virtual nodes”, or “vnodes”. This reduces the load variance among servers. With a small number of vnodes, different servers could be assigned wildly different numbers of keys.

(A brief note on terminology. The original consistent hashing paper called servers “nodes”. Papers will generally talk about“nodes”, “servers”, or “shards”. This article will use all three interchangeably.)

One of the other nice things about ring hashing is that the algorithm is straight-forward. Here’s a simple implementation taken from groupcache (slightly modified for clarity):

To add the list of nodes to the ring hash, each one is hashed m.replicas times with slightly different names ( 0 node1, 1 node1, 2 node1, …). The hash values are added to the m.nodes slice and the mapping from hash value back to node is stored in m.hashMap. Finally the m.nodes slice is sorted so we can use a binary search during lookup.

func (m *Map) Add(nodes ...string) {
    for _, n := range nodes {
        for i := 0; i < m.replicas; i++ {
            hash := int(m.hash([]byte(strconv.Itoa(i) + " " + n)))
            m.nodes = append(m.nodes, hash)
            m.hashMap[hash] = n
        }
    }
    sort.Ints(m.nodes)
}

To see which node a given key is stored on, it’s hashed into an integer. The sorted nodes slice is searched to see find the smallest node hash value larger than the key hash (with a special case if we need to wrap around to the start of the circle). That node hash is then looked up in the map to determine the node it came from.

func (m *Map) Get(key string) string {
    hash := int(m.hash([]byte(key)))
    idx := sort.Search(len(m.keys),
        func(i int) bool { return m.keys[i] >= hash }
    )
    if idx == len(m.keys) {
        idx = 0
    }
    return m.hashMap[m.keys[idx]]
}

A Brief Digression on Ketama

Ketama is a memcached client that uses a ring hash to shard keys across server instances. I needed a compatible Go implementation and came across this problem.

What’s the Go equivalent of this line of C?

unsigned int k_limit = floorf(pct * 40.0 * ketama->numbuckets);

It’s a trick question: you can’t answer it in isolation. You need to know these types and also C’s promotion rules:

float floorf(float x);
unsigned int numbuckets;
float pct;

The answer is this:

limit := int(float32(float64(pct) * 40.0 * float64(numbuckets)))

And the reason is because of C’s arithmetic promotion rules and because the 40.0 constant is a float64.

And once I had this sorted out for my go-ketama implementation, I immediately wrote my own ring hash library (libchash) which didn’t depend on floating point round-off error for correctness. My library is also slightly faster because it doesn’t use MD5 for hashing.

Lesson: avoid implicit floating point conversions, and probably floating point in general, if you’re building anything that needs to be cross-language.

End of interlude.

“Are we done?” OR “Why Is This Still a Research Topic?”

Ring hashing presents a solution to our initial problem. Case closed? Not quite. Ring hashing still has some problems.

First, the load distribution across the nodes can still be uneven. With 100 replicas (“vnodes”) per server, the standard deviation of load is about 10%. The 99% confidence interval for bucket sizes is 0.76 to 1.28 of the average load (i.e., total keys / number of servers). This sort of variability makes capacity planning tricky. Increasing the number of replicas to 1000 points per server reduces the standard deviation to ~3.2%, and a much smaller 99% confidence interval of 0.92 to 1.09.

This comes with significant memory cost. For 1000 nodes, this is 4MB of data, with O(log n) searches (for n=1e6) all of which are processor cache misses even with nothing else competing for the cache.

Jump Hash

In 2014, Google released the paper “A Fast, Minimal Memory, Consistent Hash Algorithm” known as “Jump Hash”. The algorithm was actually included in the 2011 release of the Guava libraries and indicates it was ported from the C++ code base.

Jump Hash addresses the two disadvantages of ring hashes: it has no memory overhead and virtually perfect key distribution. (The standard deviation of buckets is 0.000000764%, giving a 99% confidence interval of 0.99999998 to1.00000002).

Jump Hash is also fast. The loop executes O(ln n) times, faster by a constant amount than the O(log n) binary search for Ring Hash, and made faster even still by the fact that the computation is done entirely in a few registers and doesn’t pay the overhead of cache misses.

Here’s the code taken from github.com/dgryski/go-jump, translated from the C++ in the paper. The algorithm works by using a hash of the key as the seed for a random number generator. It then uses the random numbers to “jump forward” in the list of buckets until it falls off the end. The last bucket it lands in is the result. The paper has a more complete explanation of how it works and a derivation of this optimized loop.

func Hash(key uint64, numBuckets int) int32 {
  var b int64 = -1
  var j int64
  for j < int64(numBuckets) {
    b = j
    key = key*2862933555777941757 + 1
    j = int64(float64(b+1) *
      (float64(int64(1)<<31) / float64((key>>33)+1)))
  }
  return int32(b)
}

Jump Hash looks great. It’s fast and splits the load evenly. What’s the catch? The main limitation is that it only returns an integer in the range 0..numBuckets-1. It doesn’t support arbitrary bucket names. (With ring hash, even if two different instances receive their server lists in a different order, the resulting key mapping will still be the same.) A better way to think of Jump Hash is as providing a shard number, not a server name. Secondly, you can only properly add and remove nodes at the upper end of the range. This means it doesn’t support arbitrary node removal. You can’t use it for distributing keys among a set of memcached instances where one of them might crash — there’s no way to remove the crashed node from the list of possible destinations.

These combined make Jump Hash better suited for data storage applications where you can use replication to mitigate node failure. It can also be tricky to use with node weights.

“Are we done?” OR “Why Is This Still a Research Topic?” (2)

Ring hashing provides arbitrary bucket addition and removal at the cost of high memory usage to reduce load variance. Jump Hash provides effectively perfect load splitting at the cost of reduced flexibility when changing the shard counts.

Is there a way to have flexible ring resizing and low variance without the memory overhead?

Multi-Probe Consistent Hashing

Another paper from Google “Multi-Probe Consistent Hashing” (2015) attempts to address this. MPCH provides O(n) space (one entry per node), and O(1) addition and removal of nodes. The catch? Lookups get slower.

The basic idea is that instead of hashing the nodes multiple times and bloating the memory usage, the nodes are hashed only once but the key is hashed k times on lookup and the closest node over all queries is returned. The value of k is determined by the desired variance. For a peak-to-mean-ratio of 1.05 (meaning that the most heavily loaded node is at most 5% higher than the average), k is 21. With a tricky data structure you can get the total lookup cost from O(k log n) down to just O(k). My implementation uses the tricky data structure.

As a point of comparison, to have the equivalent peak-to-mean ratio of 1.05 for Ring Hash, you need 700 ln n replicas per node. For 100 nodes, this translates into more than a megabyte of memory.

Rendezvous Hashing

Another early attempt at solving the consistent hashing problem is called rendezvous hashing or “highest random weight hashing”. It was also first published in 1997.

The idea is that you hash the node and the key together and use the node that provides the highest hash value. The downside is that it’s hard to avoid the O(n) lookup cost of iterating over all the nodes.

Here’s an implementation taken from github.com/dgryski/go-rendezvous. My implementation optimizes the multiple hashing by pre-hashing the nodes and using an xorshift random number generator as a cheap integer hash function.

func (r *Rendezvous) Lookup(k string) string {
	khash := r.hash(k)

	var midx int
	var mhash = xorshiftMult64(khash ^ r.nhash[0])

	for i, nhash := range r.nhash[1:] {
		if h := xorshiftMult64(khash ^ nhash); h > mhash {
			midx = i + 1
			mhash = h
		}
	}

	return r.nstr[midx]
}

Even thought rendezvous hashing is O(n) lookups, the inner loop isn’t that expensive. Depending on the number of nodes, it can be easily be “fast enough”. See the benchmarks at the end.

Maglev Hashing

In 2016, Google released Maglev: A Fast and Reliable Software Network Load Balancer. One section of the paper described a new consistent hashing algorithm which has come to be known as “maglev hashing”.

One of the primary goals was lookup speed and low memory usage as compared with ring hashing or rendezvous hashing. The algorithm effectively produces a lookup table that allows finding a node in constant time. The two downsides is that generating a new table on node failure is slow (the paper assumes backend failure is rare), and this also effectively limits the maximum number of backend nodes. Maglev hashing also aims for “minimal disruption” when nodes are added and removed, rather than optimal. For maglev’s use case as a software load balancer, this is sufficient.

The table is effectively a random permutation of the nodes. A lookup hashes the key and checks the entry at that location. This is O(1) with a small constant (just the time to hash the key).

For a more in-depth description of how the table is built, see the original paper or the summary at The Morning Paper .

Replication

Replication is using the consistent hash to choose secondary (or more) nodes for a given key. This can be either to protect against node failure, or simply as a second node to query to reduce tail latency. Some strategies use full node replication (i.e, having two full copies of each server), while others replicate keys across the servers.

You can always mutate the key or key hash in a predictable way and do a full second lookup. You need to be careful to avoid landing on the same node for the replica key too.

Some algorithms have straightforward ways to choose multiple nodes for fallback or replication. For ring hash you use the next nodes you pass on the circle; for multi-probe you use the next closest. Rendezvous you take the next highest (or lowest). Jump is a bit tricky, but it can be done.

Like everything else in this post, choosing a replication strategy is filled with trade-offs. Vladimir Smirnov talks about some different trade-offs in replication strategy during his talk about Graphite Metrics Storage at Booking.com.

Weighted Hosts

Consistent hashing algorithm vary in how easy and effective it is to add servers with different weights. That is, send more (or less) load to one server as to the rest. With a ring hash, you can scale the number of replicas by the desired load. This can increase memory usage quite considerably. Jump Hash and Multi-Probe consistent hashing are trickier to use and maintain their existing performance guarantees. You can always add a second “shadow” node that refers back to an original node, but this approach fails when the load multiple is not an integer. One approach would be to scale all node counts by some amount, but this increases both memory and lookup time.

Maglev hashing approaches weights by having altering the table construction procedure so that more heavily weighted nodes choose entries in the lookup table more frequently.

Weighted rendezvous hashing is a one-line fix to add weights to rendezvous: choose the highest combined hash scaled by -weight / math.Log(h) .

Load Balancing

Using consistent hashing for load balancing seems like an appealing idea. But depending on the algorithm this can end up no better than random assignment which leads to unbalanced distribution.

Luckily (again from Google) we have two consistent hashing approaches for load balancing in addition to Maglev.

The first, from 2016, Consistent Hashing with Bounded Loads. As the keys are distributed across servers, the load is checked and a node is skipped if it’s too heavily loaded already. There’s a detailed post detailing how it was added to HAProxy at Vimeo, (with a cameo by Yours Truly :). It’s also available as a standalone package.

For clients in a choosing which set of backends to connect to, Google’s SRE Book outlines an algorithm called “deterministic subsetting”. For full details, see the description in chapter 20, “Load Balancing in the Datacenter”. I have a quick implementation at github.com/dgryski/go-subset . A similar approach is described in this blog post from Amazon on “shuffle sharding”.

Load balancing is a huge topic and could easily be its own book. For two overviews, see

• Load Balancing Is Impossible by Tyler McMullen
• Predictive Load-Balancing: Unfair But Faster & More Robust by Steve Gury

Benchmarks

And now what you’ve all been waiting for. Hopefully you didn’t just skip down to the bottom of the article and ignore all the caveats and tradeoffs that each consistent hashing function has.

Conclusion

As you can see, there is no perfect consistent hashing algorithm. They all have trade-offs. There are many others I haven’t covered here. But like the above they’re all struggling to balance distribution, memory usage, lookup time, and construction time (including node addition and removal cost).

Source Code

Here are all the repositories implementing the algorithms I discuss:

• https://github.com/dgryski/go-ketama
• https://github.com/dgryski/libchash
• https://github.com/golang/groupcache
• https://github.com/dgryski/go-jump
• https://github.com/dgryski/go-mpchash
• https://github.com/dgryski/go-rendezvous
• https://github.com/dgryski/go-maglev
• https://github.com/dgryski/go-subset

Say Thanks. Buy me a coffee.

So the next question is, what is this context and where did it come from?

The most obvious is the article by Rob Pike “Language Design in the Service of Software Engineering” (2012).

But we can learn more. Go came from the software engineering practices at Google. So what are those like? Titus Winters gave two talks at CppCon:

• The Philosophy of Google’s C++ Code (2014)
• Lessons in Sustainability: How to Maintain a C++ Codebase for Decades (2015)

And from Carmen Andoh, another look into the technical and cultural pressures that influenced Go: The Why of Go (2017)

Finally, we can see the influence of experience on Rob Pike’s way of programming through his writing. There are glimpses of proto-Go scattered throughout “The Practice of Programming” (1999).

The effects of “designing for scale” are visible not only in the original draft of the language, but in both the proposals for type aliases and vgo. Both of these are solutions to problems that might arise in smaller projects, but are much more difficult to tackle in the context of Go’s scale at Google.

Mark the code as autogenerated. In order for the generated source code to be recognized by the build tooling, there must be a comment that matches this regular expression:

^// Code generated .* DO NOT EDIT\.$

This text must appear as the first line of a properly formatted Go // comment, and that comment must appear before but not be attached to the package clause and before any /* */ comment. This is similar to the rules for build tags. Files with this header will be ignored by Go Lint and collapsed by default by GitHub in PRs and diffs. It’s also nice if you indicate the name of the tool and the arguments that produced the file.

Use _ when needed. Assigning to _ can simplify your code generation step by always importing maybe-needed packages and assigning a method or package-level variable to_, and similarly for variables that may end up not getting used.

gofmt the output. People will be reading the code while debugging issues — it’s nice if it’s formatted. Also, since editors will gofmt on save, this prevents accidental whitespace changes. You should probably run other linters on the generated code, at least for correctness. Lint violations are Ok (but discouraged), as code written by machines is held to a lower standard than code written by people.

Have deterministic output. Multiple runs of the tool without changing the input should generate the same output. Don’t rely on map ordering or add randomness to the output. I have mixed opinions on timestamps. It’s nice to know when the file was generated, but if there no updates to the file, it’s maybe nice not to output anything at all.

Have readable diffs. This ties into the previous point. People commit code to repositories, and if they generate a new file it’s nice to be able to look at the changes when there’s an update and see the effect it had on the code.

These are some things I’ve noticed when working with code generation tools that make me happy (or more likely when using code generation tools that make me sad). What do you like to have in auto-generated code?

This blog post will walk through the steps required to fuzz a Perl XS module with American Fuzzy Lop, the coverage-based fuzzing tool.

At Booking.com, we use Perl. A lot. Perl has a lot of upsides for us (which I won’t go into), and it has been a large factor in our success. For many, though, the biggest downside can be its speed. Being an interpreted language, it runs 10x-100x slower for CPU intensive tasks. When Perl isn’t fast enough, the most common thing to do is write XS modules. But XS modules are in C, and writing safe, secure C is hard. (Side note: one of my coworkers gave a presentation on writing XS modules in Rust ) Most of the time we can get away with unit tests and code review. But for parsers, you need to go one step further: fuzzing.

A few years ago, we decided to create our own serialization format. Sereal grew out of our dissatisfaction with existing Perl serialization options. (More details can be found in the original announcement .) While Sereal is geared towards dynamic languages (and Perl in particular), there are now high-quality Go and Java implementations to match our more diverse tech stack.

Fuzzing is mostly used in computer security industry to find exploits. I wasn’t expecting our Sereal decoders to be attack vectors, but rather I wanted to be able to handle errors from corrupted data. Errors happen all the time at scale. We joke that a “one in a million” problem is happening 20 times a day. And there are real reasons why our deserialization code will need to handle bad data. Maybe a data packet will get truncated in a database column because it’s too big. Maybe it will pass through a system which adds utf8 encoding. In all these cases, it’s much better to return an error to the user than to segfault.

So, how do you get bad data? Well, the easiest way is to start with a corpus of good data and change it slightly. Then, you see if your change had any effect. If the new input causes a crash, great! You just found a bug. If the new input caused the program to hit new code paths, it’s marked as “interesting” and added back to the corpus.

This is called “coverage guided fuzzing”. For the Go implementation, I was able to use the excellent go-fuzz package from Dmitry Vyukov. The Perl module, being an XS module which is loaded into the Perl executable at runtime was a bit trickier. However, it can be done using American Fuzzy Lop. (The strange name comes from a species of particularly fuzzy bunnies.)

AFL is normally used for C libraries where it’s easy to write a small program to feed corrupted input directly into the function you want to test. Fuzzing an interpreter is a bit more complicated. First, we have to build the perl binary with AFL. Then we need to build the Sereal XS module with AFL. Then we need to write a perl script that the instrumented perl binary runs that will load the instrumented XS module and pass in our fuzzed input. Phew.

This took me a few tries to get every detail correctly sorted out.

First, build the latest release of AFL. We’re going to be using the LLVM mode, which means you need to have a recent LLVM install on your machine. My Ubuntu install has 3.8, so that’s what I used.

curl http://lcamtuf.coredump.cx/afl/releases/afl-latest.tgz
tar xf afl-latest.tgz
cd afl-2.32b
make
cd llvm_mode
LLVM_CONFIG=llvm-config-3.8 make

Next, clone the Perl source code and build that with AFL

git clone git://perl5.git.perl.org/perl.git perl

OR from GitHub

git clone https://github.com/Perl/perl5

Next, configure Perl to use AFL as the compiler and install it in a custom perl-afl directory.

sh Configure -des -Dusedevel \
    -Dcc=/home/dgryski/src/afl-2.32b/afl-clang-fast \
    -Dprefix=/home/dgryski/src/perl-afl \
    -Dld=/home/dgryski/src/afl-2.32b/afl-clang-fast \
    -Dloclibpth=' '

In order to AFL to recognize that we want to use persistent mode while fuzzing (more below), we need to insert a tiny patch at the start of Perl’s main function. The perl build system is pretty hairy, but edit ext/ExtUtils-Miniperl/lib/ExtUtils/Miniperl.pm and add the following line as a declaration before main(): This magic constant is detected by AFL.

volatile char *__afl_persistent_sig = "##SIG_AFL_PERSISTENT##";

This will add sufficient magic for AFL’s detection to work.

Now, build and install perl. The perl binaries that are created will have the version number on the end. By the time you read this, that might be something other than what I have here (5.25.5).

make && make install

Next we need a target to fuzz. I’ve created a small XS module to make this easier. All it does it check if the input starts with ABCD and crashes if it does.

First, generate all the boilerplate we need for the module:

~/src/perl-afl/bin/h2xs5.25.5 -A -n Fuzz

Then add the following to Fuzz.xs

void
fuzzme(input)
    char *input
    CODE:
        if (strlen(input) < 4) { return ; }
        if (input[0] == 'A') {
            if (input[1] == 'B') {
                if (input[2] == 'C') {
                    if (input[3] == 'D') {
                        abort();
                    }
                }
            }
        }

Finally, we need to add a routine to our fuzzing module to call back into AFL’s persistent mode handler:

int
afl_persistent_loop(count)
       unsigned int count;
    CODE:
        extern int __afl_persistent_loop(unsigned int);
        RETVAL = __afl_persistent_loop(count);
    OUTPUT:
        RETVAL

Now, build the module. Perl will automatically use the compiler it was built with, which in our case is AFL.

~/src/perl-afl/bin/perl5.25.5 Makefile.PL
make

Next, our perl script that will feed the input from STDIN (where AFL will put it ) to our buggy XS module. Note this script is using AFL’s persistent mode to avoid spawning the perl interpreter for every test case.

Here’s our test script, afl.pl:

use blib "Fuzz/blib";
use Fuzz;

while(Fuzz::afl_persistent_loop(1000)) {
    my $input;
    sysread(STDIN, $input, 1024);
    Fuzz::fuzzme($input);
}

And we’ll test that we have a correctly broken module:

bash$ echo "ABCD" | ~/src/perl-afl/bin/perl5.25.4 afl.pl
Aborted (core dumped)
bash$ echo "1234" | ~/src/perl-afl/bin/perl5.25.4 afl.pl
bash$

Create input corpus:

mkdir corpus
echo 1234 > corpus/input

Finally, start the fuzzing!

~/src/afl-2.32b/afl-fuzz \
    -i ./corpus/ \
    -o ./crashers/ \
    -- \
    ~/src/perl-afl/bin/perl5.25.5 afl.pl

Now we wait. On my laptop I get ~17k execs per second per core, which is not that bad.

Another environment variable we can set when building perl is AFL_USE_ASAN=1. This links the perl binary against Google’s Address Sanitizer plugin. This will unfortunately slow down AFL to about half of what it’s running now, but it catches a larger class of bugs that don’t necessarily trigger a crash, only an out-of-bounds memory read. You will also need to build the XS module with AFL_USE_ASAN=1 set.

For many cases, PCRE is in fact faster than regexp. PCRE has had many years of optimization work; Go’s regexp package is being kept deliberately simple. (Russ Cox, the author of both regexp and re2 has expressed his desire to prevent regexp from becoming as over-engineered as re2.) In addition, while Go’s code generation has been improving with every release (notably with the new backend in 1.7), C code is still faster on average than equivalent Go code.

So, if you want to use regular expressions in Go, should you switch to PCRE? Probably not. Go’s regular expression package is fast enough for most uses. If you’re writing a server, guaranteed linear time matching from regexp eliminates a class of security and performance issues. Having a crash due to exponential-time matching on pathological inputs for some regular expressions present in backtracking engines is a real concern. StackOverflow was brought down for precisely this reason: ( Read their post-mortem at http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016 for more information.) The re2 C++ library was written for Google Code Search to prevent this class of problems too. Finally, you don’t have to fight with cgo in order to use it.

How can you speed up regular expression matching in Go? As Rob Pike points out, the benefit of regular expressions is their dynamic nature. If you know what you’re going to be matching, you can do better. Sometimes doing better just means a for loop with an if check. ( Rob’s comments on regular expressions goes into more detail: https://commandcenter.blogspot.ca/2011/08/regular-expressions-in-lexing-and.html )

Occasionally, though, you really do have complex regular expressions you need to match against. Perhaps you’re porting code from a different language where regexps are heavily used. Perhaps you’re doing text processing and a for-loop just won’t cut it.

If Go’s regular expression engine turns out to be the bottleneck, you can use ragel to generate the state machine to match your regexp ahead of time. Rather than being interpreted through the regexp engine, ragel produces Go code that can be compiled into your package. This can easily give 7x-10x speedups.

Lets walk through a simple example:

To build this, first we need ragel. Many distributions package ragel already, so installing it could be as easy as:

apt-get install ragel OR yum install ragel

or grab the source from the home page https://www.colm.net/open-source/ragel/ :

curl -O https://www.colm.net/files/ragel/ragel-6.9.tar.gz
tar xf ragel-6.9.tar.gz
cd ragel-6.9
./configure && make && make install

Next, check that ragel is in your path:

bash$ ragel -version
Ragel State Machine Compiler version 6.9 Oct 2014
Copyright (c) 2001-2009 by Adrian Thurston

We’ll start with an example from the post that inspired me to write this tutorial: http://crypticjags.com/golang/can-golang-beat-perl-on-regex-performance.html

The blog post was comparing the speed of Perl to Go’s native regexp implementation with the following expression:

sshd\[\d{5}\]:\s*Failed

We can benchmark this with the following framework in sshd_test.go:

package main

import (
    "regexp"
    "testing"
)

// sample input line from the blog post
var data = []byte(`Jan 18 06:41:30 corecompute sshd[42327]: Failed keyboard-interactive/pam for root from 112.100.68.182 port 48803 ssh2`)

// make sure the benchmark isn't optimized away
var hits int

var reSSHD = regexp.MustCompile(`sshd\[\d{5}\]:\s*Failed`)

func BenchmarkRegex(b *testing.B) {
    for i := 0; i < b.N; i++ {
        if reSSHD.Match(data) {
            hits++
        }
    }
}

To turn our regex into something we can use with ragel, we can use the following template (in sshd.rl):

package main

func matchSSHD(data []byte) bool {

%% machine scanner;
%% write data;

    cs, p, pe, eof := 0, 0, len(data), len(data)

        _ = eof

    %%{
        main := any* 'sshd[' digit{5} ']:' space* 'Failed' @{ return true } ;

        write init;
        write exec;
    }%%

        return false
}

There’s more boilerplate for matchers created with ragel, but we can still see the regexp there. The @{ return true } says that if the state machine gets to that point, the action should be to return true from the function. Otherwise, execution falls through the state machine and we return false for no match. The input language is fully documented in the manual available online at https://www.colm.net/files/ragel/ragel-guide-6.9.pdf

Next, tell ragel to compile this into a Go state machine:

bash$ ragel -Z sshd.rl

This produces sshd.go containing table-driven generated code. (We will see other matcher machine types later.)

Add the following benchmark to sshd_test.go

func BenchmarkRagel(b *testing.B) {
    for i := 0; i < b.N; i++ {
        if matchSSHD(data) {
            hits++
        }
    }
}

We can now benchmark the difference between them:

bash$ go version
go version go1.7rc3 linux/amd64
bash$ go test -test.bench=.
testing: warning: no tests to run
BenchmarkRegex-4     3000000           441 ns/op
BenchmarkRagel-4     5000000           360 ns/op
PASS
ok      github.com/dgryski/ragel-examples/regexp1   3.944s

The default machine type for ragel is a table-based matcher, which is not much faster than Go’s regular engine and in some cases might be slower. Go basically computes similar tables at regexp compile time, so evaluation is similar. There are other goto-based machines that can be used instead by passing -G0, -G1, or -G2. These matchers are increasingly faster at the cost of larger binaries. (For this simple example, the differences in binary sizes are small). We will see other cases later where we can use more features from ragel to make matching more powerful.

We can see the difference in speed between the matcher types with the following command line:

bash$ for opt in "" -G0 -G1 -G2; do echo "opt=$opt"; ragel $opt -Z sshd.rl; go test -test.bench=Ragel; done 
# slightly edited output
opt=
BenchmarkRagel-4     3000000           368 ns/op
opt=-G0
BenchmarkRagel-4    10000000           142 ns/op
opt=-G1
BenchmarkRagel-4    10000000           136 ns/op
opt=-G2
BenchmarkRagel-4    20000000            65.9 ns/op

Running these a bunch more and tweaking the output so we can compare the benchmarks directly with Russ Cox’s benchstat utility ( https://godoc.org/rsc.io/benchstat ), we can see the matcher built with -G2 is a significant win over the regular matcher.

bash$ benchstat bench.old bench.new
name     old time/op  new time/op  delta
Regex-4   448ns ± 3%    66ns ± 3%  -85.36%  (p=0.000 n=17+19)

Code for this post is at https://github.com/dgryski/ragel-examples/