Skipfilter
Tags: go, bitmap, skiplist
Published: 2022-03-26 22:56:27

---
title: Skipfilter
published: true
description: An inverted bitmap index written in Go.
tags: go, bitmap, skiplist
cover_image: https://dev-to-uploads.s3.amazonaws.com/uploads/articles/mrmgm1h7sosbteb3ys0g.png
 
 
 
---

A **skipfilter** is a skip list of arbitrary elements that can be efficiently filtered using roaring bitmaps stored in an LRU cache.

https://github.com/kevburnsjr/skipfilter

We will use this data structure to make an open source pub/sub messaging system **20,000x more efficient**.

## Use Case

[Mercure](https://mercure.rocks/spec#topic-selectors) is a pub/sub message protocol for Server Sent Events. 
- _Topics_ are identified by their URI
- _Subscriptions_ are expressed as URI Templates (topic selectors)

###  Problem

Each time a message is published to the hub, every topic selector in every subscription must be tested against every one of the message's topics. So if you have 5000 subscribers with 3 topic selectors each and each message is published to 2 topics, that's 30,000 topic selector comparisons per message.

The [Mercure Hub](https://github.com/dunglas/mercure) originally dealt with this issue using an in memory cache to eliminate duplicate regular expression evaluations. 

- Key (string): `${uri_template}-${topic_uri}`
- Value (boolean): `regexp.Match(uri_template, topic_uri)`

While this worked well initially to improve latency, it still required 30,000 hash table lookups per message which did not scale well to large numbers of subscribers.

{% embed https://github.com/dunglas/mercure/issues/558 %}

The O(n) growth in topic selector comparisons for each message meant that the computational complexity grows as a product of the number of subscribers and the volume of messages. Highly concurrent access to these caches caused a lot of lock contention which made the Go scheduler a bottleneck.

### Solution

1. The subscriber list is represented as a skipfilter. The test function uses the subscriber's topic selectors (compiled to RegExp) to match the topic.

2. For each message, the list of subscribers that will receive the message is retrieved from the skipfilter.

{% embed https://gist.github.com/kevburnsjr/76ce79f5de1c75ca8c017c3b5bc9e23e %}

{% embed https://gist.github.com/kevburnsjr/10242e721b637e5214b6c67ad85e23b6 %}

### Implementation

Each subscriber is stored in a [skip list](https://github.com/MauriceGit/skiplist). As subscribers are added, they are assigned an autoincrementing ID and the skip list grows. Skip lists are preferred over slices here due to their discontinuous nature. Subscribers can be added and removed at random and the memory usage will remain bounded.

Each topic has a [roaring bitmap](https://github.com/RoaringBitmap/roaring). Each bit corresponds to a subscriber in the skip list. For each topic, a cursor is maintained to ensure that newly added subscriptions are always tested. Deleted subscriptions are lazily evicted from the topic bitmaps on lookup. Roaring bitmaps are compressed and discontinuous so memory usage again remains bounded as subscribers come and go.

Finding the complete list of subscribers to which any message must be delivered thus requires only taking the logical `And` of a set of bitmaps. This sort of operation has been made exceptionally efficient by leveraging [SIMD instructions](https://en.wikipedia.org/wiki/Single_instruction,_multiple_data) on modern CPUs.

### Result

A multidimensional benchmark test shows a *20,000x improvement* in throughput for certain highly concurrent and highly selective workloads.

{% embed https://gist.github.com/kevburnsjr/7c5e3dbc5f2a9be9af81ce2d5423f23d %}

An efficiency improvement of **4 orders of magnitude**.

{% embed https://gist.github.com/kevburnsjr/daaec0bd6bd12a28de5eea9cd31e4e8f %}

## Conclusion

This technique has existed since at least 1980. ZeroMQ refers to it as [inverted bitmaps](http://wiki.zeromq.org/whitepapers:message-matching).

The whitepaper was not discovered until after the implementation was complete. As with most computer algorithms, the creation of skipfilter turns out to be a rediscovery of a technique that predates the birth of its author.

---

{% embed https://github.com/kevburnsjr/skipfilter %}