Hvordan spenne beina på et IT-prosjekt? (Del 2 av 3) - Motstridende forretningsmål

Let's take a look at Bloom Filters and how it works! Based on a talk and an article from Scott Helme.

Ever since I heard a talk from Troy Hunt and Scott Helme at NDC 2.5 years ago, I have been fascinated by the two guys. Not necessarily because of all the great work they have done over the years (e.g. HaveIBeenPawned by Troy Hunt), but simply because of their presenting skills and how they can explain things in a way I think most people can understand. Of course, I speak only on behalf of myself, but they managed to fill 60 minutes without me being overwhelm or left with a feeling of imposter syndrome. Therefore, when I found out that Scott Helme was on the list of speakers for NDC in Oslo this year, I had to attend! The talk was about how Bloom Filter became the solution to a relatively simple but at the same time complex problem at his company Report URI.

This article will try to create a summary of that talk in combination with an article,  to give a brief introduction to Bloom Filters and how Report URI put this into practice. The full article is available here:

The problem

Report URI is a company that monitors security features in your application, e.g. watching over your Content Security Policy (CSP) reports. Report URI receives over 4,620,000,000 reports every week, and one of the most important features they have is filtering out the reports that are not usable. To filter out these reports, it can be very useful to know if you have seen this particular CSP report before. Mainly because if you have not seen it before, you can assume a closer look will be necessary. So the question is simple; Have we seen this report before?

Report URI only hold on to the data for 90 days. Despite this, they have around 3.27TB of data on disk and process around 14,000 inbound CSP per second! Which means asking the database for a specific report will be demanding and add a lot of extra activity.

Bloom Filter

Then to the simple but perhaps ingenious solution! Bloom Filters. Many people may remember this word from school. Personally, I remember having memorized the name and formula to be prepared for an exam, without really thinking about putting it into practice. In a Bloom filter, you will be able to see if a set of items contains a special item, without actually having to save the entire set of items. Which makes the filter extremely space efficient! As Scott writes in his article, you can do many cool things with probabilistic data, IF you are willing to sacrifice a small amount of accuracy for time and space efficiency.

Bloom filters are really just a list of bits, where every bit has an initial value of 0. To be able to add a new item to the filter, in this case a CSP report for Report Uri, you have to hash the item to find out which bits to set as 1 in the array. In a Bloom Filter K is the number of hash functions and M is the size of the filter. To be able to add an item to the filter, you must put bits in K locations, which means using the hash functions on all the items. This sounds simple enough, right? One of the disadvantages of using Bloom Filters, as mentioned earlier, is that you have to sacrifice a small amount of accuracy. This is because in a Bloom filter you can encounter hash collisions. There is no guarantee that another item has not yet set the bits in the Bloom filter, which will give a false positive result. It is therefore impossible to say:

The item is definitely part of the set

However, we always know if an item is not a part of the set, because then the bits is not set in the filter. So we can say:

The item is most likely part of the set.

It is also possible to control how likely collisions are in your Bloom filter, by using these three values:

M: the size of the array

N: number of items in the filter

K: how many hash functions used

The larger the filter is, it is less likely to encounter hash collisions and this reduces the chances for false positives. At the same time, it increases the memory requirements. Reducing the number of items and increasing the number hash functions will also reduce the probability of collisions. It is important to think carefully through before calculating these values, because it is also possible to overpopulate the array. As Helme writes in his article:

“Consider our array of size m = 10 and assume we had k = 10 hash functions. Once the first item was set in the filter, everything would be a false positive after that because all bits in the array are set.”

Additionally, you can configure the probability (p) of of false positives. Let's say we want it to be 1%, which really is not that bad. This is helping us create the most suitable filter for our use case! 

The formula for calculating these values ​​are:

n = ceil (m / (-k / log (1 - exp (log (p) / k))))

p = pow (1 - exp (-k / (m / n)), k)

m = ceil ((n * log (p)) / log (1 / pow (2, log (2))));

k = round ((m / n) * log (2));

Luckily, as Helme said during his presentation: there are some great Bloom Filter calculators available online!

After creating a Bloom Filter, you can query against it after a specific item, and not the database, which means that you save a lot of time. An important thing to be aware of is that after creating the filter it is not possible to change the value for M and K. 

As Scott writes in his article, this seems like just the solution for the problem and the use of a Bloom Filter at Report URI is being tested and considered for further use. He also mentions other examples where such a filter may be relevant, e.g. checking the quality of a password. Instead of checking weak passwords (or trusted web pages) in an enormous dataset on every submit, you can have a local bloom filter in your browser, saving a lot of time preventing unnecessary queries.

That's it!

Before I went to this talk, I knew what a Bloom Filter was, but found it difficult to imagine the use in practice. Hope you learned something after reading this article, if nothing else picked up a few names it might be worth following to learn new things!

Definitely Maybe with Bloom Filters

 What are distributed systems and where can we find them in our everyday life? Bottle CAP and CAP theorem what is the difference?

To answer these questions we need to go back in time to the introduction of network communication between different machines in the '60s and the continued technological advances during the next decades that set the foundation for machine-to-machine communication as we know it today. Machine-to-machine communication provided the ability for machines to coordinate their work towards a common task by communicating. This gave birth to a new kind of system, distributed replication systems, or distributed systems for short, are defined as multiple devices connected via a network cooperating to perform some task. Sabu M. Thampi explains one of the many reasons why distributed systems have grown with the entrance of the information era:




"When a handful of powerful computers are linked together and communicate with each other, the overall computing power available can be amazingly vast. Such a system can have a higher performance share than a single supercomputer."




A problem designers of distributed systems are faced with is the CAP Theorem. CAP stands for Consistency, Availability, and Partitioning. When designing a distributed system you want the system to have strong consistency, always be available, and be operational even when the network is partitioned (you want to reach the center of the illustration in the image below). When a distributed system has geographically long distanced replicas of data and information is sent between the replicas, network partitioning will always be present, may it be due to the human factor or a glitch in the matrix.

What the CAP theorem states are that you can only have two out of the three CAP properties, thus there are two main options when handling a system that is in a partitioned state (always present). One of the options is to block all operations to replicas thus keeping consistency but providing no availability. The other is to allow all operations to replicas even though it breaks consistency. However, choosing between consistency and availability is not exclusive, trade-offs between consistency and availability can be made, for example, reading but not writing may be allowed or certain data might be changed thus keeping some level of relation between consistency and availability.




Strong consistency is desirable but costly for the system's performance and it also blocks operations thus lowering the availability of the system. A bank transfer requires stronger consistency because of the nature of the transaction than for example Amazon Dynamo 

 which has sacrificed strong consistency for better availability. Let's face it, in today's society, availability is extremely important. When people can’t access their Facebook or Instagram accounts it is on every newspaper around the globe. 

Even though these incidents probably didn't happen because of their servers dropping availability to reach a consistent state, you and I would probably not “accept” their services to be down for a couple of hours every other Tuesday night for them to reach consistency.




The structure of a system can be constructed in two different ways: centralized, where one replica is the primary and the rest of the replicas in the network are secondary, or decentralized where all nodes have the same priority. In a centralized system, all communication from the slave nodes is directed towards the primary node while in the decentralized system communication is made between arbitrary replicas.




The above image displays a possible network of five replicas where four out of the five replicas are symmetric and the middle replica differs from the other replicas. This is the primary replica and the others are secondary replicas. Secondary replicas that receive updates (e.g. an upvote on a post, illustrated by the  👍 emoji), do not apply the 👍 immediately. Instead, they notify the primary replica that a 👍has been received and wait for the main replica to process consequent updates. An example would be when two secondary replicas receive a 👍 at the same time, notify the primary replica at the same time and apply the two 👍 in the same order due to the decision of order being made by the primary replica. 



Now you are thinking why does it matter in which order the 👍 are made, and it doesn't matter for this specific case as in this case two 👍 will increase the total count by two always. But what if the updates were 👍 and 👎 on the same cat picture from the same user? If 👎 is performed before 👍 nothing will happen for the first update as there is no 👍 to remove resulting in one more 👍 on the picture. If the order was reversed, the thumbs would remove each other resulting in no more likes for the cat. 





In a decentralized system, all nodes perform actions to reach a consistent state by communicating with other replicas. Actions are performed locally and the changes of the state are communicated to replicas currently in the network. The updates made, propagate across the network and reach all replicas either directly or indirectly if no replica crashes or disconnects indefinitely.

There are pros and cons for a centralized system, where simplicity is a strong argument for this kind of system. A weakness in a centralized system is the single point of failure, all secondary nodes rely on the primary replica for updates. If the primary replica never responds with updates to the secondary replicas they can never update and thus lose both availability and consistency. The system is also faced with the possible bottleneck of the primary replica not having the performance to handle all requests from the secondary replicas, making the whole system not function properly. If this is the case then it does not matter if the secondary replicas might have enough performance to handle their tasks if the primary replica is the point of congestion.

In comparison to centralized replication, decentralized replication has no single point of failure, all replicas can continue working if any replica disconnects. The advantage of no single point of failure leads to higher complexity for keeping consistency when replicating data as all replicas must reach consensus. The complexity of the replication depends on the level of consistency required in the system. Stronger consistency requires more complex solutions than weak consistency.

Both systems have their pros and cons but there is never a universal fit for all use cases. For a larger system like Facebook, a decentralized system may be the best fit and for a DIY project, maybe the less complex central system is the better choice.






Is CAP just used by truckers that distribute systems?

Style Dictionary is one of the very best tools I've ever encountered. It's powerful, fun, and great for managing your design tokens!

Throughout the years, I have worked with lots of companies, trying to structure their front end code into reusable bits and pieces. At some places we created component libraries, created and maintained by the community. Other places we set up cross-functional design system teams, with complete autonomy and huge impacts. 

I love working with design systems - and particularly the work I do with designers. It lets me peek into a world I don't master myself, while still collaborating intensely to create a shared product we all can use.

What are design tokens?

In order to create this shared product, we need to have a shared vocabulary. And in many ways, that's what design tokens are about. 

If you've ever heard about Atomic Design, you can think of design tokens as the quarks of your design system. You might have molecules (a search widget or cards) composed of atoms (buttons, input fields and boxes), but what are those atoms composed of?

All atoms in design have colors, font styles, spacing values, drop shadows and some kind of transitions applied when they change state. And it's those discreet values – the colors, font styles, spacing values etc – that we define as design tokens.

Jina Anne came up with the concept of design tokens while working on the Salesforce design system, which has revolutionized the entire world of design systems for both me and the rest of the industry. So if you see her, tell her I said thanks 🤗

To make it a bit more clear - here are some design tokens as CSS variables:

Here, we have a (small) spacing scale, which have discreet names we can share between designers and developers, making less things lost in translation.

What is Style Dictionary?

The first lesson of using design tokens, is that you'll end up with a lot of them. In order to encapsulate all possible values in your design, you shouldn't be surprised if you end up with a hundred or more!

Structuring these tokens in a way that still makes them discoverable then becomes important. And what happens when your app team needs to use the same design tokens as you do in your scss-based front end?

Style Dictionary is a simple, yet very powerful, system for managing your design tokens. it lets you structure your tokens in whatever fashion makes sense to you (it ships with some neat defaults too, if you just want that structure decided for you), and it lets you export a normalized set of tokens into lots of different formats. Lastly, it's easily extendible to solve the needs that aren't solved by default.



Setting up your first tokens

To get started, create a new folder my-tokens and run npm init -y:



Next, let's install style-dictionary as a dev dependency:

Now we're ready to add some tokens!

Tokens are saved as basic JSON-files (or plain JavaScript files if you want), placed in the tokens folder. You can structure your tokens as you'd like, but Style Dictionary suggests that you follow the CTI structure, which stands for Category, Type, Item.

Let's show you an example. If we want to add the spacing scale from our example, we would want the following structure:

Inside the spacing.json file, we would put the following code:

That looks like a lot of boilerplate instead of just creating an object with three key values in it, but luckily it's much more flexible than a plain old object would be! We'll look at how later.

In real life, you'll have much more tokens to deal with. You'll have size/font.json, size/borderRadius.json and a lot more. Style Dictionary will then merge all of these objects together, before processing them.

Configuring Style Dictionary

Next up, we need to specify how we want Style Dictionary wants to work for us. In our example, we want to consume tokens as SCSS variables, and JavaScript variables.

First, let's create the config file itself - config.json. Here's 

This tells us that we want to base our transformations on all files that match the glob "tokens/**/*.json", which is all json-files inside any subfolder of the tokens folder. We also specify two different platforms we want to support.

Next, let's specify what we want to happen for the "scss" platform:

Here, we specify that we want the "transform group" scss to be applied. A transform group is a – well, predefined group of transforms – that either ships with Style Dictionary, or that you specify programmatically. You can see all the predefined transform groups here, but the scss transform group includes the following transforms:

If you wanted to, you could specify this list instead of "transformGroup

We won't go into detail in what each of these transforms do, but we can kind of figure out that any timing related tokens will be assumed to be in seconds (and suffixed accordingly), and any sizes will be assumed to be rem-based. You can look at all the implementations of these transforms here.

After we've specified the transforms we want, we specify what files we want to generate, and what "format" we want that file to be in. For the SCSS case, we want to use the format "scss/variables", and we want to output the file to lib/_tokens.scss. 

The "format" is a function that receives the combined JSON from the tokens folder, after being passed through all the transforms specified above, and returns a single string to be printed to file.

Next, let's add support for JavaScript tokens (and their corresponding TypeScript typings) as well:

Here, we specify the transform group "js" (here's how that looks), and then we specify two different file outputs, with two different formats. One creating an ES6 export, and one creating the TypeScript declarations.

Creating the tokens

Alright, it's been a long way here, but we're ready. Let's create a new npm command to build our tokens!

After we run npm run build, we should have three new files in our lib folder:

The next step is to release the lib folder as an NPM package, and consume them in your various projects.

If you want to add support for ios or android tokens, for example, adding it is as simple as adding a few lines of configuration.

In summary

If you're using a design system, you should definitely be using design tokens. And if you're using design tokens, your life will be much easier if you use Style Dictionary to manage them. It's extensible, customizable, and well documented. 

These are all reasons why I love Style Dictionary, and why you should too.

21-Dec

Today's posts

Hvordan spenne beina på et IT-prosjekt? (Del 2 av 3) - Motstridende forretningsmål

Definitely Maybe with Bloom Filters

Is CAP just used by truckers that distribute systems?

Why I love Style Dictionary, and why you should too