Three years back we at #MoEngage encountered a problem statement which is quite interesting. Before I jump into the problem statement, a bit of context is necessary to get complete understanding of the problem and reasoning behind our solution.
For those who don’t know what MoEngage does, MoEngage is a B2B marketing platform which enables our clients to engage their users via multiple channels which include push notifications, SMS, Emails and In-Apps. They can do so by creating different type of campaigns from our dashboard.
In-Apps is a special use case where message content is shown inside mobile application in the form of popup.
Problem Statement : Allow marketers to create In-Apps campaigns such that they can target users based on their past behaviour. This simple statement makes our problem very complex. Rules to segment users based on past behaviour can be very complex. For example, if a marketer wants to show an in-app message to all users who performed an event “AddedToCart” and did not “purchase”, he/she will have to create rules like this in #MoEngage Dashboard while creating a campaign.
So what’s the problem here? Each time we get a sync call from a user’s device(mobile), we serve the active In-Apps campaigns payload to be displayed on the device. Checking if a user falls in a segment (target audience) of a campaign or not is a very costly operation. This will increase our latency as well as put heavy load on our underlying infrastructure if we make a query every time we get a sync call from a device.
When we looked for alternative solutions, after initial discussions we settled for BloomFilters.
Bloom filter is a probabilistic data structure(memory efficient) designed to check membership of an item in O(1) time. Bloom filters can return false positives, but the rate of false positives can be controlled by pre-defining accuracy(99.9% in our case). To know more about bloom filters please visit this blog.
In our case, all users who fall in one campaign’s segment are fetched from our datastore and are put in a bloom filter. Now we can test the membership of a user in a campaign by just checking if the user is present in the respective bloom filter or not. All bloom filters are pre-loaded on the API server’s RAM, so checking if a user falls in a campaign or not is now an O(1) operation.
After 1–2 days of experimentation and performance evaluation, we went ahead with the implementation. The diagram shown below is an evolved version of our initial implementation, but the basic idea remains the same. I skipped a lot of details which are very specific to our system.
Performance/Results
Bloom filters are very easy to create and it takes very little time to create a bloom filter with millions of items.
Before creating a bloom filter, we must specify a size. Given a fixed accuracy, size and # of items in bloom filters are related to each other. Accuracy, i.e the false positive rate is fixed for us as a business requirement.
As we know the number of users in a segment and we have a pre-defined accuracy, we can calculate the size using formula below;
number of hash functions =10
false_positive_rate = 0.001 ( our use case)
no_of_bits = user_count * log(1/false_positive_rate) / 0.4804530139182014
no_of_bits = int(no_of_bits)+int(431327)
431327 is added as additional buffer to increase the accuracy.
Bloom filters which can contain ~14 million users (items) have only ~24.5 MB size with 99.9 % accuracy. Also, it takes only 46 seconds to create bloom filters with 4.7 million users (items).