Photo by Samuel Regan-Asante on Unsplash

When working with threads, locks are widely used to protect critical sections. Algorithms utilising locks tend to straightforward to reason about, but from a throughput perspective they fall short. Lock-free algorithms solve this issue by replacing locks with cheaper CAS (compare-and-swap) instructions. A downside is that lock-free algorithms often do not guarantee that threads will finish in a finite amount of time. Wait-free algorithms are a subset of lock-free algorithms that don’t utilise locks, so not threads are waiting for each other, but that give back the guarantee that the algorithm will finish in a finite amount of time. …


Photo by Maksym Kaharlytskyi on Unsplash

Have you ever wondered what data structures are used in search engines and why? If yes, you’ll probably find this article interesting. We’ll cover the theory behind indexing, what makes a data-structure well-suited for search applications, what data structures are used in the popular open source search engines, and the relationship between physical hardware and search performance.

If you have not read my introduction post, you can read it here. I’ll not explain the basic terms in this post.

Boring theory

When working with search the main data-structure is an inverted index.

An inverted index is formally a data-structure with the following…


Photo by Brett Jordan on Unsplash

In the first version of this post I showed how we can make a simple search engine in 100 lines of Python. I’ll build on this to create a highly efficient full text search library in Rust.

In my last blog post I described how to build a basic search engine from scratch. In this post I’ll go into one part of that process, which is converting the documents into tokens.

Our goal will be to explore what the possible throughput for the tokenisation part of the pipeline is.

When we are working with tokenisation we are in the domain…


Have you ever wondered what happens when you type “what is the meaning of life” into Google?

If yes, that means two things:

  1. We have a lot in common.
  2. You will probably find this article interesting.

Search engines are infinitely complex. Millions of servers are: scraping websites from the internet, storing and aggregating the information, doing huge matrix calculations and inching the world ever closer to the singularity.

Still, the basics of what a Search engine does is relatively simple. You give it a question in the form of a query. The search engine finds pages that are relevant for…


In this guide I will show you how to configure your next project to use the cutting-edge OAuth2 standard.

I will assume no prior knowledge to Django.

Django

Written in Python, Django is opinionated web framework with a lot of third party packages.

A couple of sites using Django:

  • Disqus
  • Pinterest
  • Giphy

You can find out more and read their documentation at:

OAuth2

If you have ever used a website like Google or Facebook, you have used OAuth2. When you log in with Google, the same thing is happening.

If you want to learn more about it before starting, you can go…


This is an article about the basics of Rust. It is intended for people with some expirience programming, but it will not go too deep into the details, just to get you up and going in Rust. If you do not already have Rust installed:

A basic program in Rust

To make a new project in rust, you can use cargo. In the beginning:

 cargo new helloworld

This will generate a lot of files, including a “src” folder. This is where you put your “main.rs” file, with the following content:

fn main() {  println!("Hello, world!");}

Your folder structure should look like this:

helloworld…

Halvor Fladsrud Bø

Software Engineer. Interested in security, distributed systems and databases. Using this as a scratchpad.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store