Dmitry Eroshenko

How I reduced 19GB to 40MB with a single trick: bitfields

This optimization may not look very useful at first glance, but as this is a long-term project that has been running for 10 years already, it's important that each feature we add to the project doesn't use much resources. Because if we don't think about optimizations it will not become a problem because of one feature, but if we add 10 of them and load the server 100% this has bad consequences.

We have complex conditions for sending emails tied to time of day, we stop sending emails to somebody who doesn't open them for the last N days etc, we send only 1 email of each type before the user opens any email the first time etc.

To send an email only once for each user before the user opens an email the first time (tracked by HTML pixel) I need to know whether a certain email has been sent to a certain user at least once.

We have:

  • 148 email templates
  • 7,000,000 users
  • ~40,000,000 checks happen daily; part of the emails get sent because part of them are blocked by pre-checks (including this one I was making optimizations for)
  • ~600,000 emails sent every day

So, that check "did user ever receive this template" runs pretty often, each time we send an email. And even more than 600,000 times, as some emails were not sent because the user didn't open any emails yet — but when email sending is triggered we should check if sending is not restricted by any rules; if it is restricted, it doesn't go into those 600,000, but the check is still executed.

So with this in mind I started thinking how I can make it work with minimal load on database/storage/CPU.

We have logs of all emails we ever sent, but that collection is huge and querying it to check if a certain email was ever sent to a user will be slow as hell.

I threw out the option of storing these values the normalized way in a separate collection and then querying it every time, as it means that collection can grow up to a billion records and later even more:

148 templates x 7,000,000 users = 1,036,000,000 records

Even storing one record per user with a user_id field and a templates_sent array will lead to a 7,000,000-document collection (storage + index + separate queries).

So, I started thinking the MongoDB way here. I have a users collection and the normal NoSQL approach is to store related data together with the entity it's related to. So, it's related to each user and we can store already-sent templates in the users collection.

Now we need to think how to do it exactly. For example, we can add another field to each document in the users collection, name it something like tpls_sent_at_least_once and just put there template names as strings:

{
  tpls_sent_at_least_once: ['welcome', 'abandon_upgrade_like_followup', ...]
}

Ok, that works, but 148 templates for each user (potentially) will take a lot of storage and redundant network usage as we fetch user documents across the whole codebase.

(Calculations below are approximate as in MongoDB we store strings in an array structure and we also have to store the field name itself, but this error won't make much of a difference.)

MongoDB stores strings in UTF-8 and template names consist of ASCII characters only, which means 1 byte per character.

Average length of a template name is 20 characters — 20 bytes.

148 templates x 20 bytes = 2960 bytes = 2.890625 Kbytes

The maximal size of a MongoDB document is 16 megabytes, so those 3KB will not get us any closer to the limits.

2960 bytes x 7,000,000 users = 20,720,000,000 bytes = ~19,760 MB = ~19.3 GB

So, 19.3GB is not something critical and probably we will have much less, as part of the users never received some emails and we will not add those to the tpls_sent_at_least_once field.

But let's see what we can do more. Instead of using strings we can define a numeric index for each template on the application side and then only store those indexes:

{
  tpls_sent_at_least_once: [1, 7, ...]
}

For numbers from 0 to 148 it will be enough to use a 32-bit integer (Int32 type in MongoDB) which is 4 bytes.

148 templates x 4 bytes = 592 bytes = 0.578125 Kbytes

So, with integers we will use ~5 times less storage.

592 bytes x 7,000,000 users = ~3.86 GB

As we started with all that stuff let's see what we can do more :)

As the status "was email sent at least once" has only 2 values — yes or no — it means this is something that perfectly fits one bit (!) of information.

Int32 is 4 bytes or 32 bits, but we actually need only one bit per template name, and 0.0390625GB (or 40MB) of data for all 7 million users and 148 templates.

On the application level I have a templates list with different configuration options; I added one more option which is bitIndex, starting from 0 and ending at 147 (148 templates - 1). So, now I assigned its own bit index to each email.

How to write it to the database? There are different ways. One Int32 takes 32 bits, so I could store it as an array of Int32 numbers and I'd need 5 elements in the array to cover all templates (148 / 32 = 4.625). But it's not so comfortable to use an array, and also the array itself is something we don't actually need.

In the C/C++ world we have bitfields. I needed something like this in Node.js and here is the library I used: bitfield.

So, I create a bitfield and store it as a BLOB in MongoDB.

When we are sending emails the user object is already available; the only thing is now we have a new blob field tpls_sent_at_least_once. Before sending an email, when we need to check if a certain email was ever sent before for a certain user, I just check if the bit at bitIndex is set:

bitField = new Bitfield(user.tpls_sent_at_least_once.buffer)
bitField.get(tplConfig.bitIndex)

So, at the end this feature was added, I used less than 40MB of storage and almost no RAM/CPU, keeping hardware resources for other more important stuff :)

← Back to blog