Concurrency Corner

What is a rate limiter The Rate Limiter (RL) is a middleware (think Redis) or some software strategy to limit access of clients to resources that are limited or for which we want to ensure that fair usage and access is encouraged. In the context of websites the approach also provides security as it limits access to adversarial clients who wish to abuse the system. This approach also finds use in the context of databases - which I will give details on in this post. Note: adversaries are a superset of the user set (they can do what users do plus other things we dont normally want to allow) who behave badly, and could be external actors to the system or registered members. Rate Limiters in Distributed Systems The poster child for rate limiting - in my opinion - is Redis as it is the first thing that comes to mind from my background and experience. The reason is that they have made the use of rate limiting simple via their api. You should check out Redis if you have not alre...

The present post is about Caches and the Buffer Pool Manager for a database named SparrowDB that I am building. The programming language is Rust. The DB is a SQL relational database I wish to take from scratch to distributed. If you wish to come along for the ride, I will post weekly on my thoughts, struggles and completed work. Disclaimer: A lot of what I know and some parts of this blog comes from lessons by Andy Pavlo from CMU who made a youtube course, and I highly recommend you learn from him if you desire to work with database internals. Cache Policies : There are several types of caches we could consider eg. course-grained and fine-grained, but we will only consider the former category. Furthermore we will only use LRU-K in this project, but I wish to give an honourable mention to frequency based cache policies such as Q2 and LFU. The LRU-K is an improvement on the LRU policy as it avoids thrashing in the database cache where we evict a page only to read it again in t...

Today I want to talk about work in software. So naturally/unnaturally I gravitate towards ... orchestrators, for reasons that will become clear shortly. Borg and K8's come to mind. What do these have in common and what do they contain that makes them indispensable to modern computing. I think its the ability to make distributed systems so easy to deploy (K8s). Perhaps also that it hides much of the complexity of failures, and writing software to handle these cases. In my opinion what I love about them is the concept of work. It's the same reason I like the MapReduce system, and the concept of doing work as a whole resonates with me. No this isn't an AI assistant writing for me, I use the word resonate because I like that word. So in this post I will model a Worker, and what does that actually mean for the system, ie. What do Workers do?  Manager (M) , Workers (W) and KVstores (KV) are the system we will think about today. Lets start with the following:  Worker comes to work...

You have all heard that you should initialise close to where you first use your variables instead of at the top of the class, since it's better to understand, less likely to break when modified, etc, but what other benefits will you get? We will look at the compiler to understand why you should care. But first we need to understand what your compiler is doing.  Escape Analysis in Compilers : Escape Analysis is an optimisation technique that allows your compiler to determine whether a variable is accessed, outside its scope. In other words: your compiler will check your variables and look for those which have only local access. If accesses are only local, then this is an opportunity for optimisation of the code via memory management. So what exactly is happening to these local variables? Stack Allocations : A variable found to be local, without accessing outside its scope, can be allocated on the stack instead of the heap. Fun fact : accessing data on the L1 cache takes 0.5 nanoseco...