16 November 2018 Engineering

The Birthday Paradox (and Concurrently Indexing in Elasticsearch)

By Jason TedorZachary Tong

Two engineers on the Elasticsearch team recently had children with identical birthdays. This reminded us of one of our all-time favorite mathematical problems. It may surprise you that this has come up in our work on Elasticsearch too.

We're speaking of the birthday problem. This problem asks: if you take a group of randomly1 chosen people at a small party and ask them what their birthday is, what is the probability that some pair of them will have the same birthday? Naïvely, we think this is low because there are 365 possible birthdays2 and with a small group of people the proportion of taken birthdays will be low, so the chances of colliding birthdays should be low too. This is why it's surprising that it turns out that if you have 23 people at a party then there is a greater than 50% chance that there is a pair in the group with the same birthday!

We call this The Birthday Paradox.

Happy Birthday to All of You

Going beyond the naïve thinking, what matters is not how many birthdays are taken by the small group of people, but whether any pair of them have the same birthday. The number of pairs of people from a group of n people is On2, so it grows fast. To avoid there being a birthday in common, all of these pairs must have distinct birthdays.

With 23 people, there are 23*222=253 possible pairs. Every single one of these pairs must have distinct birthdays — and that's hard with only 365 birthdays. Precisely, the chances the second person doesn't share a birthday with the first person is 1-1365, the chances the third person doesn't share a birthday with the first and second people is 1-2365, and so on so that for 23 people the chances that no one shares a birthday is 1*1-1365*1-2365*...*1-22365=0.492703. So the chances that there is a birthday in common is 0.507297. That is, with 23 people, the chances are greater than not that there is a birthday in common.

We can generalize this to n people. You might know that 1-k365 is approximately equal to exp-k365. So then like the above probability calculation, the chance that no one among n people shares a birthday is 1*1-1365*1-2365*...*1-n365 which is approximately equal to exp-1-2-...-n365=exp-n*n-12*365. That is, for n people, the chances of having a birthday in common is roughly 1-exp-n22*365. Note the quadratic effect here reflecting the number of pairs of people: the logarithm of the probability that no one among n people shares a birthday grows like n2.

Surprise Birthday Party

What does this have to do with Elasticsearch?

We allow concurrent indexing. This means that sometimes two threads will try to index the same document, and we have to guard against this occurring simultaneously to ensure proper semantics. To guard against this, we initially used a traditional strategy of a "striped lock". A striped lock is an array of N locks, with each lock guarding 1N of the document ID space. We would hash modulo N the document ID of the document being indexed, and then take out a lock on the element of the array of locks corresponding to that hash. If two threads try to simultaneously index the same document, they would produce the same hash, try to grab the same lock, and only one of them would win giving us the guard we need. Yay!

This also means that documents with different IDs could contend if they happen to hash to the same lock. This striping strategy was chosen to use ten times the number of processors, which seems that it should reasonably spread out the hash space, especially since we only allow as many threads as there are cores to be concurrently indexing3.

Yet awhile ago, we noticed some heavy contention on these locks. Boo. How could that be?

This is the birthday problem in disguise.

Having our Cake and Eating it Too

The days are the locks, and the hashes of the document IDs are the ones that we do not want to be having the same birthday (i.e., colliding on the same lock). Since we are only growing the locks linearly in the number of processors, but the number of possible pairs that could be colliding grows quadratically in the number of indexing threads, contention would become more likely on machines with high core counts. If we wanted to target a specific probability p for c threads indexing on c cores, we would want approximately -c2log1-p locks in the pool. That is, we would have to grow the number of locks quadratically in the core count, and we consider that a non-scaling solution. We looked for a different approach.

The Cake is no Lie

The ideal approach is a keyed lock. This is a lock specific to each document ID. We keep track of a lock per document ID, creating them on demand per document ID and throwing them away when no thread is trying to write to the same document ID (otherwise we would blow up memory). Keep in mind though, these locks have to be managed concurrently, and this is quite a tricky problem to get right.

Luckily, we already had an implementation for this sitting in our networking infrastructure, where we also use keyed locks to manage connections. Switching from a striped lock to a keyed lock gave us a roughly 20% improvement in indexing throughput. We released this change with 2.4.0.

While these changes were introduced some time ago, the recent coincident births within the Elasticsearch team reminded us of this paradox, the concurrency problem here, and the resulting optimization. We wanted to share the birthday paradox because it is fun and a counterintuitive phenomenon. It also helps serve as a great lesson in why high-performance concurrency can be difficult, and equally counterintuitive.
  1. We assume all birthdays are equally likely, which is in point of fact not quite true; for example, the most common month for birthdays in the US is September and given 38-week gestation, means the traditional US holiday-time really is about family. 😉
  2. For simplicity we ignore leap years, but nothing changes if we include them.
  3. At the time of this work, we could actually have twice the number of cores indexing because the indexing and bulk thread pools were separate.