Did you know you can inspect your node application’s memory without instrumenting your code ? It’s possible using a tool called mdb_v8. With mdb_v8 we can produce a core dump of a running node process, and then later inspect the memory at the time the core dump was generated. This leads to some powerful postmortem debugging capabilities.

In this post I’m going to walk you through setting up mdb_v8 locally so that you can inspect your node application’s memory. Recently I went through this exercise myself and realized there was no good guide to do so. I decided to document the process and post it here.

The steps were going work through are as follows:

1. Generate a core dump of our running node application
2. Install a Solaris derivative in a VM
3. Install mdb_v8, and run it against the core dump

Be aware that this guide assumes a couple things about your workflow. First, that you are using a version of node at 0.10 or greater. At the time of this writing, all previous versions are no longer supported. Second, that your node service is running on a system where gcore is available, such as linux.

A Solaris derivative is required to run mdb_v8. There are two post mortem debuggers that don’t require Solaris, but they aren’t as fully featured. These are llnode and lldb_v8. Alternatively, if instrumenting your code isn’t an issue you may want to look into node-heapdump.

What is mdb_v8 anyways ?

We can’t talk about mdb_v8 without first talking about mdb. mdb is a low-level debugger developed by Sun for the Solaris operating system. What makes it unique is that is extremely extensible. It is possible to extend the tool with custom modules (“dmods”) for different contexts. This is exactly what Joyent has done with their mdb_v8 module. The mdb_v8 module adds a new set of commands instrumented specifically for the v8 javascript engine and node.js. It includes commands that allow you to inspect the application state, javascript frames, and javascript objects on the heap at the time the core dump was generated.

It’s worth emphasizing here that mdb only works on Solaris derivatives. That is — it won’t run OS X, Windows, or Linux. More on this in a moment.

Generating a core dump

A core dump is a file which consists of the working memory of an application. It also typically contains some other metadata such as process registers. In linux generating a core dump of our node.js application manually is pretty straight forward. We just run the following command:

gcore -o filename 

This will produce a core dump file.

You can also set up your node service to save a core dump when it crashes by using the — abort_on_uncaught_exception flag.

Installing mdb_v8

So mdb_v8 sounds great, right ? You will be able to inspect your application state, and find out where all of your sneaky memory leaks are hiding. Well, that’s true, but as I mentioned above mdb_v8 only works on Solaris.

Therefore, we will use VirtualBox to install a Solaris derivative (OmniOS).

Setting up VirtualBox with OmniOS

If you don’t already have VirtualBox installed, you can proceed to the downloads page to download the correct binary for your system and install it.

After you’ve installed VirtualBox you will download a Solaris derivative. Here we will use OmniOS. Download the current/stable release under “From CD/iso”

Once you’ve downloaded the image you can move back over to VirtualBox.

Select “Oracle Solaris 11”, and continue with everything else as the default.

Once the VM is running, start it up and choose the OmniOS image that you downloaded above.

Proceed through the installation process choosing your language, timezone, etc. Keep in mind that VirtualBox has a sandbox auto-resizing hard drive. It’s fine to install the image on the “whole disk”. You can also ignore any warnings about kvm: No hardware support.

After you’ve installed OmniOS, proceed to “Devices -> Optical drives -> Remove disk from virtual drive” in VirtualBox to unmount the disk. Finally, reboot the VM. You will be prompted to login once OmniOS starts up. The default login in OmniOS is root with no password.

Utilizing mdb_v8

If you’ve made it this far you should be staring at an empty shell. There are still a few remaining steps before we can begin using mdb_v8. Those steps are as follows:

1. We need to be able to SSH into our VM from our local machine
2. We need to install the mdb_v8.so module for mdb
3. We need to SCP our core dump, and node.js binary to the virtual machine

SSHing into our VM

The first issue is that our VM doesn’t have access to the local network. We need to enable this option in VirtualBox. We want to give our VM an internal IP that we can reach via SSH. We can do this by right clicking our VM in VirtualBox, and heading to the settings page. Here we will change our networking adapter from NAT to Bridged Adapter.

The next step is that we need to enable DHCP in OmniOS. This way our VM can be assigned an IP address on the network. We do that by using a tool called ipadm to create an IP interface.

# ipadm create-if e1000g0 # ipadm create-addr -T dhcp e1000g0/v4

Now that we have created our IP interface we can configure our DNS resolution. Run these commands to add a nameserver.

# echo 'nameserver 8.8.8.8' >> /etc/resolv.conf # cp /etc/nsswitch.dns /etc/nsswitch.conf

Hurray. Now we have network connectivity. Now let’s get our new local IP on the network by running ifconfig.

# ifconfig e1000g0

This will show us our local network IP address (directly after the inet).

Even though we have the network IP address, we still won’t be able to SSH into the machine. Why ? Well because by default OmniOS (and many distributions) don’t allow you to SSH in as the root user. This is typically a security precaution. However, because we are just doing this to run mdb_v8 locally, we can enable this functionality.

To allow us to SSH in as root we can edit the sshd_config

# vim /etc/ssh/sshd_config

and scroll down to the line that says PermitRootLogin no and change it to PermitRootLogin yes. After this we want to restart the SSH daemon.

# sudo svcadm restart SSH

Now we should be able to SSH into our VM. Nice! On to the next step.

Installing mdb_v8

Luckily, OmniOS comes with mdb installed by default, but it does not come with the mdb_v8 module. We need to manually install this. To do this we can simply use curl to download the binary.

Let’s first create a working directory.

# mkdir ~/mdbv8 # cd ~/mdbv8

You can first curl Joyent’s manta service to find the latest version of mdb_v8.

# curl https://us-east.manta.joyent.com/Joyent_Dev/public/mdb_v8/latest | cut -c 27-

Run the following command below (replace {version} below with version you got from the above curl i.e. “v1.1.2”)

# curl -O https://us-east.manta.joyent.com/Joyent_Dev/public/mdb_v8/{version}/mdb_v8_amd64.so

Great. Now we have everything we need to run mdb_v8.

Putting it all together

The last and final step is to move over both our core dump file(s), and our node binary. (Don’t have a core dump file ? See the beginning of this post for a snippet of how to use gcore.)

What’s all this about a node binary ? Well, mdb_v8 will only work against the node binary that was running your node application at the time that the core dump was generated. You can download it directly from the node.js website provided you know the exact version and build. The easiest way is to simply grab the node binary off of the machine where you generated the core dump. Typically you can find the node binary by running which node, but if you’re using something like nvm it may require a little bit more digging.

Provided you have downloaded the node binary and your core dump on your local machine, you can now SCP these files onto your VM.

# scp ./node root@192.168.1.82:~/mdbv8 # scp ./my-dump.gcore root@192.168.1.82:~/mdbv8

Now we can start the mdb_v8 debugger against our core dump and node binary.

# mdb ./node ./my-dump.gcore

This will drop us into the mdb shell. All we need to do now is to load the mdb_v8 module by executing:

::load /root/mdbv8/mdb_v8_amd64.so

Now we can proceed to run any of the mdb_v8 commands against our core dump.

I like to start my mdb_v8 search by listing all js objects in memory. Try it yourself by typing.

::findjsobjects

For a list of useful mdb_v8 commands I recommend the official mdb_v8 usage guide.

I also found this gist by tjfontaine to be pretty helpful.

In this guide I’ve walked you through generating core dumps, installing solaris locally, and setting up mdb_v8. Hopefully you will find that mdb_v8 is a very useful node.js debugging tool to have in your back pocket for postmortem debugging. Good luck plugging all your leaks!

Originally published at bryce.is on February 6, 2016.

Like most good TIFUs this didn’t happen today. It actually happened about two years ago. It is, however, still relevant. More significantly, it’s not just me who screwed up. Math.random() in the V8 Javascript engine is screwed up, too.

“Many random number generators in use today are not very good. There is a tendency for people to avoid learning anything about such subroutines; quite often we find that some old method that is comparatively unsatisfactory has blindly been passed down from one programmer to another, and today’s users have no understanding of its limitations.”

— Donald Knuth; The Art of Computer Programming, Volume 2.

By the end of this post I’m hoping we’ll all agree on two things, one of which may be slightly more controversial than the other:

• We were stupid not to understand the limitations of V8’s PRNG before using it, and CSPRNGs are a safer option if you’re feeling lazy.
• The implementation of Math.random() in V8 should be replaced. The current algorithm, which appears to have been passed down from one programmer to another, is comparatively unsatisfactory (and arguably completely broken) due to subtle, non-intuitive degenerate behavior that is likely to be encountered under realistic circumstances.

For the record, I do want to say that I think V8 is a very impressive piece of software and the people who work on it are clearly very talented. This isn’t an indictment of any of them. Rather, it’s an illustration of how subtle some aspects of software development can be.

Now that we all know where we’re headed, let’s begin at the beginning.

Betable is built on random numbers. Aside from other more obvious uses we like using randomly generated identifiers. Our architecture is distributed and microservice-y, and random identifiers are easier to implement than sequential identifiers in this sort of system.

For example, we generate random request identifiers whenever we receive an API request. We thread these identifiers through to sub-requests in headers, log them, and use them to collate and correlate all of the things that happened, across all of our services, as a result of a single request.

Generating random identifiers isn’t rocket science. There’s only one requirement —

It must be really, really unlikely that the same identifier will ever be generated twice, causing a collision.

And there are just two factors that impact the likelihood of a collision —

1. The size of the identifier space — the number of unique identifiers that are possible
2. The method of identifier generation — how an identifier is selected from the space of all possible identifiers

Ideally we want a big identifier space from which identifiers are selected at random from a uniform distribution (henceforth, we’ll assume that anything done “at random” uses a uniform distribution).

We did the birthday paradox math and settled on making our request identifiers 22 character words with each character drawn from a 64 character alphabet. They look like EB5iGydiUL0h4bRu1ZyRIi or HV2ZKGVJJklN0eH35IgNaB. Each character in the word has 64 possible values, there are 22 characters, so there are 64²² such words. That makes the size of our identifier space 64²² or ~2¹³².

With 2¹³² possible values, if identifiers were randomly generated at the rate of one million per second for the next 300 years the chance of a collision would be roughly 1 in six billion.

So we’ve got a big enough identifier space, but how do we generate identifiers at random? The answer is a decent pseudo-random number generator (PRNG), a common feature of many standard libraries. The top of our API stack is a Node.js service (we also use a lot of Go, but that’s another blog post). Node.js, in turn, uses the V8 Javascript engine that Google built for its Chrome web browser. All compliant ECMAScript (Javascript) implementations must implement Math.random(), which takes no arguments and returns a random number between 0 and 1. Good start.

So, given a sequence of pseudo-random numbers between 0 and 1 we need to generate a random word with characters from our 64 character alphabet. This is a pretty common problem, here’s the pretty standard solution we chose —

Before you start picking it apart, there’s nothing wrong with this code — it does exactly what it’s supposed to do.

We’re in business. A procedure for producing random identifiers that is extremely unlikely to produce a collision, even if we’re producing a million a second for 300 years. Test, commit, push, test, deploy.

The above code hit production and we forgot about it until a rather alarming email came through from a colleague, Nick Forte, telling us that the impossible had happened —

“Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.” John von Neumann was stating the obvious here — it’s a simple tautology that deterministic methods, like arithmetic, cannot produce random bits. It’s a contradiction in terms. So what is a PRNG?

What is a PRNG?

Let’s ground our discussion by looking at a simple PRNG and the “random numbers” it produces —

This should make von Neumann’s point clear — the sequence of numbers generated by this algorithm is obviously not random. For most purposes, this non-randomness doesn’t really matter. What we really need is an algorithm that can generate a sequence of numbers that appear to be random (technically, they should appear to be independent and identically distributed random variables having a uniform distribution over the generator’s range). In layman’s terms, we should be able to safely pretend that the pseudo-random numbers are truly random numbers.

If it’s hard to distinguish a generator’s output from truly random sequences we call it a high quality generator. If it’s easy, we call it a low quality generator.

For the most part, quality is determined empirically by pulling a bunch of numbers from the generator and running some statistical tests for randomness (e.g., by checking that there are an equal number of 0 bits and 1 bits, figuring out how many collisions there are, doing a Monte-Carlo estimation of pi, etc). Another, more pragmatic measure of PRNG quality is how well the algorithm actually works in practice as a stand-in for truly random numbers.

Apart from its non-randomness, our simple algorithm demonstrates another important characteristic of all PRNGs. If you keep pulling numbers, it will eventually start repeating the same sequence over again. This is called periodicity, and all PRNGs are periodic.

The period or cycle length of a PRNG is the length of the sequence of numbers that the PRNG generates before repeating.

You can think of a PRNG as a highly compressed codebook containing a sequence of numbers. The kind a spy might use as a one-time pad. The seed is the starting position in the book. Eventually, you’ll loop around the end of the book and get back to where you started. That’s a cycle.

A long cycle length doesn’t guarantee high quality, but it helps. Often, cycle length can be guaranteed by mathematical proof. Even when we can’t calculate cycle length exactly, we can determine an upper bound. Since a PRNG’s next state and output are both deterministic functions of its current state, the cycle length cannot be larger than the number of possible states. To achieve this maximum cycle length the generator must enter every possible state before returning, again, to its current state.

If a PRNG’s state has a k-bit representation, the cycle length is less than or equal to 2ᵏ. A PRNG that actually achieves this maximum cycle length is called a full-cycle generator.

Good PRNGs are designed so that their cycle length is close to this upper bound. Otherwise you’re wasting memory.

Let’s go one step further and analyze the number of distinct random values that a PRNG can produce through some deterministic transformation on its output. For instance, consider the problem of generating triples of random values between 0 and 15, like (2, 13, 4) or (5, 12, 15). There are 16³ or 4096 such triples, but our simple PRNG can only produce 16 of them.

It turns out that this is another general characteristic of PRNGs —

The number of distinct values that can be generated from a pseudo-random sequence is bounded by the sequence’s cycle length.

The same holds regardless of the sort of value we’re producing — we can only produce 16 distinct tuples of four values (or any other length), 16 distinct array shuffles, 16 random fuzz test values, etc. We will always only be able to generate 16 distinct values of any type. Ever.

Remember our algorithm for producing random identifiers? We randomly generated words consisting of 22 characters drawn from a 64 character alphabet. In other words, we generated tuples of 22 numbers between 0 and 63. It’s the same problem, and the number of distinct identifiers we can produce is bounded by the size of the PRNG’s internal state, and its cycle length, in the same way.

Math.random()

Back to our problem. In response to Nick’s email about identifier collisions we quickly reviewed our birthday paradox math and checked our scaling code. We couldn’t find anything wrong, so the problem had to be deeper. Armed with our general knowledge of PRNGs, let’s start digging.

The ECMAScript standard says the following about Math.random() —

Returns a Number value with positive sign, greater than or equal to 0 but less than 1, chosen randomly or pseudo randomly with approximately uniform distribution over that range, using an implementation-dependent algorithm or strategy.

The specification leaves a lot to be desired. First, it doesn’t mention anything about precision. Since ECMAScript Numbers are IEEE 754 binary64 double-precision floats, we might expect 53-bit precision (i.e., random values taking the form x/2⁵³ for all x in 0..2⁵³-1). Mozilla’s SpiderMonkey engine seems to agree but, as we’ll soon find out, V8’s Math.random() only has 32-bit precision (i.e., values taking the form x/2³² for all x in 0..2³²-1). Good to know, but no matter, we only need six bits to produce a random letter from our 64 character alphabet.

What does matter for us is that the specification leaves the actual algorithm up to implementors. It has no minimum cycle length requirement, and is hand-wavy about the PRNG’s quality — the distribution just needs to be “approximately uniform.” To do our analysis we need to know what algorithm V8 uses. It’s nowhere to be found in any documentation, so let’s go to the source.

The V8 PRNG

“Iwould have gone with mersenne twister since it is what everyone else uses (python, ruby, etc).” This short critique, left by Dean McNamee, is the only substantive feedback on the code review of V8’s PRNG when it was first committed on June 15, 2009. Dean’s recommendation is the same one I’ll eventually get around to making in this post.

V8’s PRNG code has been tweaked and moved around over the past six years. It used to be native code, now it’s in user-space, but the algorithm has remained essentially the same. The actual implementation uses internal API and is a bit obfuscated, so let’s look at a more readable implementation of the same algorithm —

Well, that’s still pretty opaque, but let’s slog through.

There is one more clue. A comment in older versions of the V8 source stated simply: “random number generator using George Marsaglia’s MWC algorithm.” A few minutes with Google teaches the following —

• George Marsaglia was a mathematician who spent much of his career studying PRNGs. He also created the original Diehard battery of statistical tests for measuring the quality of a random number generator.
• MWC stands for multiply-with-carry, a class of PRNGs that Marsaglia invented. MWC generators are very similar to classic linear congruential generators (LCGs) like our simple example from earlier (in fact, there is a one-to-one correspondence between MWCs and LCGs, see section 3.6 of this paper for details). Their advantage over standard LCGs is that they can produce sequences with longer cycle lengths with about the same number of CPU cycles.

So if you’re going to crib a PRNG off of someone, Marsaglia seems like a good choice, and MWC seems like a reasonable algorithm.

The V8 algorithm doesn’t look like a typical MWC generator though. It turns out that’s because the V8 algorithm is not an MWC generator. It’s two MWC sub-generators — one on line 5, the other on line 6 — combined to produce one random number on line 9. I’ll spare you the math, but each of the sub-generators have prime cycle lengths of about 2³⁰, making the combined cycle length of the generated sequence about 2⁶⁰.

If you’ll recall, we have 2¹³² possible identifiers, but now we know that V8’s Math.random() can only produce 2⁶⁰ of them. Still, assuming a uniform distribution, the probability of collision after randomly generating 100,000,000 identifiers should be less than 0.4%. We started seeing collisions after generating far fewer identifiers than that. Something must be wrong with our analysis. The cycle length estimate is provably correct, so we must not have a uniform distribution — there must be some additional structure to the sequence being generated.

A Tale of Two Generators

Before returning to the V8 PRNG, let’s look one more time at our random identifier generation code —

The scaling method on line 6 is important. This is the method that MDN recommends for scaling a random number, and it’s in widespread use in the wild. It’s called the multiply-and-floor method, because that’s what it does. It’s also called the take-from-top method, because the lower bits of the random number are truncated, leaving the left-most or top bits as our scaled integer result. (Quick note: it’s subtle, but in general this method is slightly biased if your scaled range doesn’t evenly divide your PRNG’s output range. A general solution should use rejection sampling like this, which is part of the standard library in other languages.)

Do you see the problem yet? What’s weird about the V8 algorithm is how the two generators are mixed. It doesn’t xor the numbers from the two streams together. Instead, it simply concatenates the lower 16 bits of output from the two sub-generators. This turns out to be a critical flaw. When we multiply Math.random() by 64 and floor it we end up with the left-most, or top 6 bits of the number. These top 6 bits come exclusively from the first of the two MWC sub-generators.

If we analyze the first sub-generator independently we see that it has 32 bits of internal state. It’s not a full-cycle generator — its actual cycle length is about 590 million (18,030*2¹⁵-1, the math is tricky but it’s explained here and here, or you can just trust me). So we can only produce a maximum of 590 million distinct request identifiers with this generator. If they were randomly selected there would be a 50% chance of collision after generating just 30,000 identifiers.

If that were true, we should have started seeing collisions almost immediately. To understand why we didn’t, recall our simple example where we pulled triples from a 4 bit LCG. Birthday paradox math doesn’t apply — for this application the sequence is nowhere near random, so we can’t pretend it is. It’s clear that we won’t produce a duplicate until the 17th triple. The same thing is happening with the V8 PRNG and our random identifiers — under certain conditions, the PRNG’s lack of randomness is making it less likely that we’ll see a collision.

In this case the generator’s determinism worked in our favor, but that’s not always true. The general lesson here is that, even for a high quality PRNG, you can’t assume a random distribution unless the generator’s cycle length is much larger than the number of random values you’re generating. A good general heuristic is —

If you need to use n random values you need a PRNG with a cycle length of at least n².

The reason is that, within a PRNGs period, excessive regularity can cause poor performance on some important statistical tests (in particular, collision tests). To perform well, the sample size n must be proportional to the square root of the period length. Page 22 of Pierre L’Ecuyer’s excellent chapter on random number generation has more detail.

For a use case like ours, where we’re trying to generate unique values using multiple independent sequences from the same generator, we’re less concerned about statistical randomness and more concerned that the sequences not overlap. If we have n sequences of length l from a generator with period p, the probability of an overlap is [1-(nl)/(p-1)]ⁿ⁻ ¹, or approximately ln²/p for a big enough p (see here and here for details). The point is we need a long cycle length. Otherwise we’re making a mistake pretending our sequence is random.

Long story short, if you’re using Math.random() in V8 and you need a sequence of random numbers that’s reasonably high quality, you shouldn’t use more than about 24,000 numbers. If you’re generating multiple streams of any substantial size and don’t want any overlap, you shouldn’t use Math.random() at all.

If the algorithm that V8’s Math.random() uses is poor quality, you might be wondering how it was chosen at all. Let’s see if we can find out.

A Brief History of MWC1616

“The MWC generator concatenates two 16-bit multiply-with-carry generators […] has period about 2⁶⁰ and seems to pass all tests of randomness. A favorite stand-alone generator — faster than KISS, which contains it.” That’s the extent of Marsaglia’s analysis of MWC1616, which is the name of the algorithm that powers V8’s Math.random(). If you take him at his word, the algorithm ticks the box for most of the important criteria you’d consider in choosing a PRNG.

MWC1616 was first introduced by Marsaglia in 1997 as a simple general purpose generator that, in his words, “seems to pass all tests of randomness put to it,” a comment that betrays Marsaglia’s largely empirical methodology. He seems to have trusted an algorithm if it passed his Diehard tests. Unfortunately, the Diehard tests he was using in the late 1990s weren’t that good, at least by today’s standards. If you run MWC1616 through a more modern empirical testing framework like TestU01's SmallCrush it fails catastrophically (it does even worse than the MINSTD generator, which was outdated even in the 1990s, but Marsaglia’s Diehard tests probably didn’t have the granularity to tell him that).

As far as I know, there’s no mathematical basis for combining sub-generators the way MWC1616 does — concatenating subsets of the generated bits. It’s more typical to see bits from sub-generators mixed using some form of modulo arithmetic (e.g., addition modulo 2³², or xor). It appears that Marsaglia, himself, became aware of this deficiency shortly after posting MWC1616 on Usenet as a component of one version of his KISS generator. On January 12, 1999, Marsaglia posted the version of MWC1616 used in V8. Eight days later, on January 20, he posted a different version of the algorithm. It’s subtle, but in the updated version, the upper bits of the second generator are not masked away, mixing bits from the two sequences more thoroughly.

Both versions of the algorithm appear in other places, adding to the confusion. The January 20 version of MWC1616 (i.e., the better version) is in Numerical Recipes, labeled MWC with Base b = 2¹⁶, under the heading When You Have Only 32-Bit Arithmetic, and only after first advising that, rather than implementing one of the algorithms listed, you should “get a better compiler!” Pretty discouraging words for an algorithm that’s better than what V8 has powering Math.random(). Rather inexplicably (because it’s so obscure) the January 20 version of MWC1616 is also given as an example computational method in Wikipedia’s article on random number generation. Implementations of the older January 12 version are included in TestU01 twice, once labeled MWC1616 and a second time labeled MWC97R. It’s also one of the generators available in R (apparently it used to be the default).

So there are lots of places the algorithm can be found. It was obscure to me, but given the bona fides listed above I guess it’s not surprising it was chosen. Hopefully this article will serve as a warning, strengthening and confirming Knuth’s observation that kicked off this post —

• In general, PRNGs are subtle and you should do your own analysis and understand the limitations of any algorithm you’re implementing or using
• Specifically, don’t use MWC1616, it’s not very good

There are lots of better options. Let’s look at a couple of them.

The CSPRNG Workaround

To fix our identifier code we needed a replacement for Math.random() and we needed it fast. Lots of alternative PRNG implementations exist for Javascript, but we were looking for something that —

• Has a long enough period to generate all of our 2¹³² identifiers
• Is well supported and battle tested

Luckily, the Node.js standard library has another PRNG that meets both requirements: crypto.randomBytes(), a cryptographically secure PRNG (CSPRNG) that calls OpenSSL’s RAND_bytes (which, according to the docs, produces a random number by generating the SHA-1 hash of 8184 bits of internal state, which it regularly reseeds from various entropy sources). If you’re in a web browser crypto.getRandomValues() should do the same job.

This isn’t a perfect general solution for three reasons —

• CSPRNGs almost always use non-linear transformations and are generally slower than non-cryptographic alternatives
• Many CSPRNG systems are not seed-able, which makes it impossible to create a reproducible sequence of values (e.g., for testing)
• CSPRNGs emphasize unpredictability over all other measures of quality, some of which might be more important for your use case

However —

• Speed is relative, and CSPRNGs are fast enough for most use cases (I can get about 100MB/s of random data from crypto.getRandomValues() in Chrome on my machine)
• In the limit, unpredictability implies an inability to distinguish the generator’s output from true randomness, which implies everything else we want out of a pseudo-random sequence
• It’s likely that a generator advertised as “cryptographically secure” has been carefully code reviewed and subjected to many empirical tests of randomness

We’re still making some assumptions, but they are evidence-based and pragmatic. If you’re unsure about the quality of your non-cryptographic alternatives, and unless you need deterministic seeding or require rigorous proofs of quality measures, using a CSPRNG is your best option. If you don’t trust your standard library’s CSPRNG (and you shouldn’t for cryptographic purposes) the right solution is to use urandom, which is managed by the kernel (Linux uses a scheme similar to OpenSSL’s, OS X uses Bruce Schneier’s Yarrow generator).

I can’t tell you the exact cycle length of crypto.randomBytes() because as far as I know there’s no closed form solution to that problem (i.e., no one knows). All I can say is that with a large state space and a continuous stream of new entropy coming in, it should be safe. If you trust OpenSSL to generate your public/private key pairs then it doesn’t make much sense not to trust it here. Empirically, once we swapped our call to Math.random() with a call to crypto.randomBytes() our collision problem went away.

In fact, Chrome could just have Math.random() call the same CSPRNG they’re using for crypto.randomBytes(), which appears to be what Webkit is doing. That said, there are lots of fast, high quality non-cryptographic alternatives, too. Let’s put a final nail in the MWC1616 coffin and take a look at some other options.

V8’s PRNG is Comparatively Unsatisfactory

My goal was to convince you that V8’s Math.random() is broken, and should be replaced. So far we’ve found obvious structural patterns in its output bits, catastrophic failure on empirical tests, and poor performance in the real world. If you still want more evidence, here are some pretty pictures that might sway you —

Hopefully you’ll agree at this point that V8’s Math.random() is comparatively unsatisfactory and should be fixed. The question is how should it be fixed? A one line patch would improve the bit-mixing, but I can’t see any reason to keep MWC1616 at all. There are better options.

A detailed comparison of the myriad existing methods for producing pseudo-random bits is going to have to wait for another post. Roughly, though, the requirements we’re looking for are —

• A large state space, and a large seed — ideally at least 1024 bits, since this will be an upper bound on other qualities of the generator. A state space of 2¹⁰²⁴ is enough for 99.9% of use cases, with a significant safety factor.
• Speed, let’s make it at least as fast as the current implementation which produces around 25 million numbers per second on my machine.
• Memory efficiency — we’ll probably need at least 256 bytes for a generator with 1024 bits of state in user-space Javascript (we can only use 32 bits per 64 bit Number), if that’s infeasible there are workarounds, but I’m going to assume we can afford this.
• A very long period, a full cycle generator is great but anything over 2⁵⁰ should be sufficient to avoid cycling. Anything over 2¹⁰⁰ should let us safely pull 2⁵⁰ values while continuing to pretend we’ve got a random sequence.
• At a minimum, passing marks on empirical tests of randomness like TestU01's SmallCrush — extra credit for passing marks on BigCrush and good equidistribution (which, unfortunately, I don’t have room to explain). TestU01 is more rigorous than Dieharder, and I don’t know much about the NIST tests or rngtest, but those might work too.

There are many PRNG algorithms that meet or exceed these requirements. Xorshift generators (also discovered by Marsaglia) are fast and do very well on statistical tests (much better than MWC1616). An xorshift variant called xorgens4096 has been implemented in Javascript by David Bau. It has a 4096-bit state space, a cycle length of ~2⁴⁰⁹⁶, and it runs faster than MWC1616 in Chrome on my machine. Moreover, it has no systematic failures on BigCrush.

Recently it’s been shown that taking the output of an xorshift generator and multiplying by a constant is a sufficient non-linear transformation for the generator to pass BigCrush. This class of generators, called xorshift*, is very fast, easy to implement, and memory efficient. The xorshift1024* generator meets or exceeds all of our requirements. If the memory premium turns out to be a real problem, the xorshift64* generator has the same memory footprint, a longer cycle length, and is faster than MWC1616, beating it on all counts. Another new family of linear/non-linear hybrid generator called PCG claims similar performance and quality characteristics.

So there are lots of good algorithms to chose from. That said, the safest choice is probably a standard Mersenne Twister. The most popular variant, MT19937, was introduced in the late 90s. Since then it’s become the standard generator in dozens of software packages. It’s not perfect, but it has been battle tested and thoroughly analyzed. Its properties are well understood, and it does well on empirical tests. With an ostentatiously long cycle length of 2¹⁹⁹³⁷-1 it’s hard to misuse, but it does have an imposing 2KB state space and is criticized for its memory footprint and relatively poor performance. A quick search uncovered an existing Javascript implementation, by Sean McCullough. Inexplicably, it’s as fast as the existing Math.random() implementation in Chrome on my machine.

So my advice is that V8 reconsider Dean McNamee’s comment from six years ago and use the Mersenne Twister algorithm. It’s fast enough, and robust enough to be safely used by developers who don’t have a deep understanding of how PRNGs work. A more exotic alternative is fine too. Just get rid of MWC1616, please!

In Summary

This was a long post, so let me re-cap the important bits —

• The PRNG algorithm behind V8’s Math.random() is called MWC1616. If you’re only using the most significant 16 bits it has a very short effective cycle length (less than 2³⁰). In general, it does poorly on empirical tests of quality. For most non-trivial use cases it’s not safe to pretend that it’s output is truly random. Be careful using it for anything you care about.
• Cryptographically secure PRNGs are a better option if you don’t have time to do proper diligence on non-cryptographic alternatives. The safest option (and the right solution for crypto) is to use urandom. In browser you can use crypto.getRandomValues().
• There are options for non-cryptographic PRNG algorithms that are faster and higher quality than MWC1616. V8 should replace its Math.random() implementation with one of them. There are no losers. Mersenne Twister (MT19937) is the most popular, and probably the safest choice.

I’ll note, in passing, that Mozilla’s use of the LCG from Java’s util.Random package isn’t much better than MWC1616. So SpiderMonkey should probably go ahead and upgrade too.

In the meantime, the browser continues to be a confusing and dangerous place. Be safe out there!

Special thanks to Nick Forte, who discovered the collision bug in our production code, Wade Simmons, who originally tracked the problem down to V8’s Math.random() implementation, and the entire Betable Engineering team, who put up with me ranting about random numbers for two weeks while I wrote this post.

Lately I’ve been doing more work in the Go programming language. Today I thought I would share three “gotchas” that caught me off guard, or otherwise produced results that I would not have expected in my work with Go.

1. The range clause

The range clause is very convenient. It allows you to iterate over a slice or map while giving you a reference to the index and the value of each item. For example:

for index, value := range mySlice {
    fmt.Println("index: " + index)
    fmt.Println("value: " + value)
}

However, something notable is happening under the hood. Let’s see a more complex example:

type Foo struct {
    bar string
}

func main() {
    list := []Foo{
        {"A"},
        {"B"},
        {"C"},
    }

    list2 := make([]*Foo, len(list))
    for i, value := range list {
        list2[i] = &value
    }

    fmt.Println(list[0], list[1], list[2])
    fmt.Println(list2[0], list2[1], list2[2])
}

In this example we are doing a few things.

1. We are creating a slice of Foo structs called list.
2. We are defining a second slice of pointers to Foo structs called list2.
3. We iterate through each struct in list in order to assign its pointer to the corresponding index in list2.

So therefore you might expect the output of the above code to be the following:

{A} {B} {C}
&{A} &{B} &{C}

However, this is not what is happening. Let’s take a look at the output of this code:

{A} {B} {C}
&{C} &{C} &{C}

The first line is as expected. These are the structs we initially created in list, but the second line is unexpected. It looks like we are printing out a pointer to the last struct in the list three times. But why is this happening ?

The culprit is the range clause.

for i, value := range list {
    list2[i] = &value
}

Here’s the problem: Go uses a copy of the value instead of the value itself within a range clause. So when we take the pointer of value, we’re actually taking the pointer of a copy of the value. This copy gets reused throughout the range clause, which leaves our list2 slice full of three references to the same pointer (the copy pointer).

According to the Go reference manual, “The iteration values are assigned to the respective iteration variables as in an assignment statement.” So effectively you can imagine the above range clause to be the same as writing:

var value Foo
for var i := 0; i < len(list); i++ {
    value = list[i]
    list2[i] = &value
}

In order to produce the output we expect, we should use the index to take a pointer to the actual value, instead of the copy.

for i, _ := range list {
    list2[i] = &list[i]
}

2. The append built-in function

Slices are primitive types in Go. In other languages you might reach for an Array where in Go you would reach for a Slice. Here’s an example of how we might add a value to the end of an integer slice.

list := []int{0,1,2}
list = append(list, 3)
fmt.Println(list) // [0 1 2 3]

On the surface it seems to be similar to a push() array method, but slices are not quite arrays, and the built-in append function surprised me with its behavior under the hood. Have a look at the example below:

func main() {
    a := []byte("foo")
    b := append(a, []byte("bar")...)
    c := append(a, []byte("baz")...)
        
    fmt.Println(string(a), string(b), string(c))
}

In this example we define a slice a of bytes with an initial value of [“foo”]. Next we append another slice [“bar”] to our initial slice a, and again we append another slice [“baz”] to our initial slice a. The output of the above snippet is:

foofoobazfoobaz

Whaaat? :) Shouldn’t it be foo foobar foobaz ?

In order to understand what’s going on here we have to understand what a slice really is. A slice is a descriptor which consists of three components:

1. A pointer to an underlying array — that is, one allocated by Go which you don’t have direct access to.
2. The capacity of said underlying array.
3. The effective length of the slice.

So what’s really happening ? Go will reuse the same underlying array in append() if it can do so without resizing the underlying array.

So all three of these structs are referencing the exact same array in memory. The only practical difference is their length value which in the case of a is 3, and in the case of b and c is 6.

Keep in mind, Go will only reuse the same underlying array if the length of the newly created slice is less than or equal to the capacity of the initial slice.

It’s important to understand what is happening under the hood when using some of the built-in slice functions. For more info, Robe Pike wrote a very helpful blog post which goes into a lot of useful details around slices.

3. Variable shadowing

When people first look at Go code for the first time, one of the first things they ask is “What is that := operator for?”. Well, as you know, it’s a shorthand variable declaration operator. It’s used for both declaring and setting the value of a variable. The type is implicitly declared. This is very convenient, but can lead to some problems if you aren’t careful. Specifically I’m talking about variable shadowing. This is something that has bitten me in particular, because I have been programming almost exclusively in es5 javascript for the last two years where there is no block-level scoping.

Check this out:

func main() {
    list := []string{"a", "b", "c"}
    for {
        list, err := repeat(list)
        if err != nil {
            panic(err)
        }
        fmt.Println(list)
        break
    }
    fmt.Println(list)
}

func repeat(list []string) ([]string, error) {
    if len(list) == 0 {
        return nil, errors.New("Nothing to repeat!")
    }
    list = append(list, list...)
    return list, nil
}

This is somewhat of a contrived example, so bear with me because I think it illustrates the point well. The run down of this snippet is as follows:

1. We create a slice of strings, list.
2. We enter a for loop.
3. The for loop calls a function repeat() which returns a new slice, and an error.
4. We break out of the for loop, and we print the value of list.

You might expect the output here to be:

[a b c a b c]
[a b c a b c]

but in fact, it is:

[a b c a b c]
[a b c]

Because we use the shorthand variable declaration operator, we are actually redeclaring the list variable inside of the scope of the for loop. This is awkward, because the second variable err is a new variable which we want to declare. We can fix this by changing the first few lines within the for block to:

var err error
list, err = duplicate(list)

One way to catch these problems early is by taking advantage of the go vet tool. It has an option -shadow which can help to detect issues with variable shadowing.

There is a good blog post called The Golang Beartrap that talks more in detail about variable shadowing.

Summary

Go is a great language, and once you understand its quirks it can be a real pleasure to work in. I really appreciate the fantastic tooling, and readablity of the language. Good luck, and happy gophering! :)

Again, originally published at bryce.is on November 1, 2015.

My name is Mike Malone and I’m CTO at Betable, a venture backed technology startup based out of San Francisco. In the past I’ve been fairly active writer of things, speaker at conferences, and contributor to open source and open standards projects. That stopped pretty abruptly about four years ago when I joined Betable, a tiny company with the ambitious goal of reinventing and safely opening up the $500 billion gambling industry to developers who can’t afford their own licenses.

When I joined, Betable was just an idea. We immediately started documenting a basic system architecture (on a white board in the founder’s garage, of course). Six months later we launched a payments flow and our first games. Fast forward about three years… last quarter we shuffled over $150 million through our accounting system. Lots of interesting stuff happened between then and now. To focus on that stuff, I took some time off from sharing my thoughts online. Now that the dust is settling a bit I’m back, and I’m excited to start documenting and sharing that journey here.

As an online gambling operator Betable is a special kind of e-commerce business that, legally, is treated something like a multinational bank that also sells liquor. Our regulatory requirements are as onerous as many publicly traded companies. There are a lot of things we need to get right the first time (e.g., security, payments, random number generation). As a platform, we’re built for scale and developer ease of use. We’ve also got all the normal non-functionals that you’d expect at a startup (move fast, keep it simple, be agile, avoid complacency, yada yada yada). The point is we’re an interesting hybrid of an organization. We need mature processes and technologies to manage risk. At the same time, we’ve got to stay agile, move fast, and attract startup talent to be successful. Balancing these requirements is not easy.

For the most part, we’re not managing this stuff the “normal” way you’d see in an enterprise. Rather, we’ve been pushing the boundaries of agile processes and modern technologies. The accounting system mentioned above uses Apache Cassandra. Our servers? 100% cloud-based and under config management. Overall architectural style? Chatty RESTish microservices speaking HTTPS and/or communicating over an event bus. QA and Deployments? Automated and on demand with a code-review and CI pipeline, and a whole lot of tests. Languages? We know a bunch of them. Pretty normal stuff for a startup (that does things right). Not so normal for a bank/liquor store. So, heads up to anyone who says this won’t work for their organization because insert stupid regulatory requirement here — you’re wrong. The only reason this stuff won’t work is organizational apathy.

That’s not to say there aren’t gotchas… there are lots. For example, it’s not easy getting regulatory waivers so you don’t have to implement password reset questions (because they’re stupid and insecure), or explaining how deploying a system via git + configuration management is a safe alternative to signed gold-masters like JARs or ISOs. We’ve also had our fair share of screw ups. Have you ever run into this Go language quirk? Combined with a bit of test failure fatigue, that little quirk ended up costing us more than $50,000. Stories like this make us all better. On this blog we fully intend to share the bad along with the good.

Oh yea, we also have lots of normal distributed systems, microservice, operational, and general computing problems too. Want to know how to manage more than forty microservices with thirteen engineers and a two person ops team? We do that. Need a high availability durable state machine? We built our own distributed database for that. Need simple security measures to keep all of your microservices safe? Got ’em. Want to keep track of tons of micro-transactions? We’ve got some ideas. Need to support ad-hoc queries, but your online database is a NoSQL distributed key-value store? We’ve got that problem too (spoiler alert: don’t use Hadoop). Anyways, we’ve got some stories to tell!

In the interest of intrigue I’ll save further discussion for future posts. I’m very excited to finally be sharing more about Betable engineering publicly. Follow us here and on twitter to stay up to date, and leave a comment if there’s anything you’re particularly excited to hear more about.

Originally published at medium.com.

First off, let me start by saying that this was my first conference ever, and also that I am not actually a front-end JavaScript developer. Day to day, I spend my time building back-end micro-services in GO for Betable, an online gambling platform. I only dabble in JavaScript when I need to work on our externally facing API, which is written in Node.js. Needless to say, I was a little intimidated going to an all-JavaScript conference where every single person there was probably a much better JavaScript developer than I currently am.

Luckily, it all went much better than I expected. I learned a ton from the amazing talks I saw (more on that a bit later) and met some really cool people: the organizers (@theophani, @hblank, @janl), the speakers (@razvancaliman, @whitneyhacks) and the attendees (too many to call out, sorry!). I also really enjoyed exploring Berlin — one of my favorite cities in my home country — with my friend from undergrad and fellow engineer @tdeekens.

I flew into Frankfurt a few days early to visit my family and then blasted up the Autobahn on Thursday afternoon to get a good night of sleep before heading over to Radialsystem V at 9am for breakfast and mingling. The opening by the curators blew everyone away (or so it appeared) and landed some serious applause. It was a sweet light show and a fun mashup music performance of samples from previous talks at JSConf by @thedeftone, @kahliltweets and @bonotes. Check it out here: https://youtu.be/lJ1kY-CSpBk

Talk slots were about 30 minutes and there was a coffee or food break after each block of three talks which made things very easy to follow without being overwhelmed with information. I did get a small hint of being back in school every now and then but unlike how I remember school, none of the talks at this conference disappointed or made me fall asleep. Every single one was interesting and engaging.

In broad terms they all centered around:

1. community and the people that write code
2. performance and how to write code correctly
3. cool shit and how to push the cutting edge

The breaks were filled with coffee by “The Barn,” arguably one of the best coffees in Berlin; ClubMate, a caffeine drink apparently very popular in Germany that I had never heard of before and fantastic food by a catering company that I didn’t get the name of but it was way better than I would have expected from such a large event.

Friday concluded with a party open to all JS conference attendees that weekend (RejectJS, JSConf, CSSConf) and plus-ones. @usefulthink kicked it off with a demo in which he used JavaScript and CSS to showcase a light cube he built himself, as well as taking control of the room’s lighting systems and making it go crazy. Needless to say, the crowd went wild. For the rest of the night the Red Bull DJ Champion of 2014 spun the decks in impressive fashion and played a really fun set.

Saturday was a gap day on which CSSConf happened and I took the time to explore Berlin, which was a nice change of pace in between two full days of talks.

Sunday was much like Friday, except with a venue change for the closing party. We took over a small “club” on board of the Hoppetosse with open bar until the money ran out. You can imagine how that went.

Let’s go into a bit more detail on the talks. As I said earlier, they were all great but I am going to pick a few of them out that I liked in particular.

Domo Arigato Mr. Roboto

Sam Richard from the IBM Watson project demonstrated a bunch of cool APIs that IBM recently made publicly available for processing human natural language (like speech). He put together a live speech-to-speech babelfish-like (hello Hitchhiker’s Guide to the Galaxy fans) translator as well as a GitHub commit tone extension that disables the “Submit” button if you’re using negative language in your commit. Interestingly, this was not the only talk on speech processing but I liked it the best.

(Dependency Hell Just Froze Over)

I completely missed this talk but it turned out to be all-the-hype that weekend so it deserves a mention here. If you are struggling with dependency version control in your JavaScript applications, go check out greenkeeper.io by Stephan Bönnemann.

Illusion of Time. When 60 seconds is not 1 minute.

Denys Mishunov took us on a tour of user deception. People absolutely HATE passive wait time aka waiting for something without anything else to do. How does this help us as developers? Build websites that deceive the user by showing something very quickly and doing the heavy processing in the background while the user is distracted. For example amazon.com takes 7 seconds to fully load! But we don’t care because we see it and interact with it much earlier.

Zen of JavaScript

I came into this talk thinking: Hey, maybe someone will explain to me how to write JavaScript the right way. Aaaaaand was immediately disappointed when Dmitry Baranoskiy said that he didn’t know either. However, he pointed out a lot of fun quirks of JavaScript and concluded that we all just need to start accepting and embracing how JavaScript works instead of hating on it. For example .charAt() will give you a result no matter what it is called on or what it is passed. Strings, numbers, objects, undefined. Anything. Point taken.

The year of the peer-to-peer web

Thomas Gorissen took the stage, put on a black turtleneck sweater and proceeded to pitch P2P in a manner similar to the former head of a weird fruit company (Forrest Gump, anyone?). Why is this the year of peer-to-peer web? Because it is seriously one of the coolest things I’ve seen. WebRTC is an open web standard to enable real-time communication and P2P is by the default of IP the shortest connection between two computers, which means sending audio or video that route can’t get any more performant. He demoed a webpage that enabled videocalling between multiple people with a one-line embedded script tag. Gone are the days of Skype and Google Hangouts if you can just do that in your web apps! Check out skylink.io and webtorrent.io for demos and more information.

If Walter Gropius was a JavaScripter

Whitney Williams, who I had met the day before over coffee, talked about the history of the Bauhaus, an art school that operated in Germany in the 1920s and early 1930s and fostered the connection of manufacturing with design. Her point was that we should inspire more collaboration between developers and designers and stop separating the two.

Evolving Complex Systems Incrementally

Christoph Pojer from Facebook demonstrated an impressive AST-based tool that helps them refactor massive amounts of code in seconds. It is called JScodeshift and is now an open-source project! Codemod tools give anyone the ability to align certain coding patterns over entire code bases without having to edit potentially thousands of files manually.

AirPlay protocol hacking

Thomas Watson was visibly nervous because he had worked on his demos until 3am the night before. He started off with a theory lesson on how AirPlay works and broke it down as essentially being multicast DNS plus some fancy encryption. As usual, Apple just took existing technology, put a little twist on it to confuse everyone and is selling it as innovative and amazing. Luckily, there are people like Thomas out there that put a lot of effort into reverse-engineering this stuff and then giving us open-source tools to use that technology. You can even use it to live stream audio over torrents with peervision.

Disconnected Networking

Razvan Caliman, another speaker that I had met on Friday, demonstrated some alternative methods of communication. Have you ever tried to transmit data using supersonic sound or via ambient light sensors? No? Well he built demos for both an more. Apparently this technology already exists to track movement through stores with visual light communication. Really impressive stuff and interesting alternative ideas. Supposedly you can even infect the BIOS with viruses just by sending sound waves that get picked up by your sound card …

Applying 3D Engineering Drawing Techniques To Web App Diagrams

Here is a new concept: Ever get tired of navigating your codebase and trying to keep the entire folder and file structure in your head until somebody comes and distracts you and that carefully crafted model in your head just shatters? Ola Adedoyin might have a solution for you by creating 3D models of your codebase. The idea sounds awesome and very promising but unfortunately there are hardly any tools available for this now. It’s something to watch for the future though!

The Rest…

There were of course many more talks that were technically interesting, thought provoking and mentally stimulating but sadly I can not call out all of them.

JSConf.eu was my first conference and I could not have asked for a better experience. By the end of it I was left with a ton of new ideas to bring back to our engineering team and with an overwhelming sense of wanting to be part of this community of awesome people. I am very thankful for the opportunity that @betable and especially our new VP of engineering, @admc, gave me and I hope to see everyone again next year!

Originally published at medium.com on October 9, 2015.