DEV Community: Amir Keshavarz

AWS Summit Amsterdam 2025 – Key Takeaways & Reflections

Amir Keshavarz — Fri, 18 Apr 2025 11:35:49 +0000

AWS Summit Amsterdam 2025 – Key Takeaways & Reflections

With the AWS Summit Amsterdam 2025 now wrapped up, I thought it was worth writing down some reflections. This isn't your typical event recap—consider it part observation, part opinion.

After speaking with attendees and walking the floor, it seems many felt this year’s summit was one of the most thought-provoking in recent memory. While not as flashy or extravagant as previous editions, it made up for it with substance and energy.

Unsurprisingly, the dominant themes were AI and EU–US relations. Conversations repeatedly circled around these two topics, often with a sense of unease about where the industry is headed—plenty of nervous laughter to go around.

Interestingly, while there appeared to be tighter budgets when it came to marketing and luxuries, there was no lack of investment—especially in hyperscale initiatives backed by major cloud providers and venture capital.

AI

AI is no longer a novelty—it's infrastructure. We've clearly entered the second wave of AI adoption, and it’s not a passing trend. It's already delivering measurable gains in engineering productivity, and the sheer scale of investment being poured in is staggering.

Notably, no one is talking about whether to use generative AI anymore. If your team hasn’t already embraced it, you’re already behind—and yes, it’s okay to feel a bit of FOMO.

Talking Points

The major AI-related discussions revolved around:

Choosing the right model for the job
Cost management
AI agents

The first two are fairly self-explanatory, so let’s focus on the third: agents.

The limitations of traditional chatbots are well-known—they lack contextual awareness, task execution abilities, and multi-step reasoning. AI agents aim to solve this by enabling more autonomous, capable systems.

MCP is quickly becoming the standard for context injection. For other use cases, there's still a lot of variation in approaches across teams.

In short, this is the new normal.

If your team isn’t using AI yet—start.

If your team isn’t working with AI agents—start.

If you’re building infrastructure for developers and don’t yet offer AI tooling—start.

EU–US

No big surprises here. There’s growing concern among European companies and governments about dependency on American hyperscalers. Despite heavy investment from both private and public sectors, tangible alternatives are still lacking.

Europe has a software problem (read this excellent article: Europe's Software Problem), and it won’t be solved overnight. The US has spent the last three decades—and vast sums—developing its software ecosystem and pulling far ahead.

The concern is valid: for many critical services, there simply are no viable European alternatives, and geopolitical dynamics are shifting quickly. The upside? There's newfound enthusiasm and funding to explore European-built solutions.

So, it’s a complicated mix—growing interest, rising budgets, and a tough road ahead. The next few years are likely to be tense but hopefully transformative.

Conclusion

This post is a mix of hallway chats, session takeaways, and personal impressions. I’ve kept it short, so of course, much has been left out. Still, I hope it gives you a good sense of the broader picture.

People have been saying “the world is changing fast” my whole life—but for the first time, I’m really feeling it. Exciting years lie ahead :)

Developing Custom Plugins for CoreDNS

Amir Keshavarz — Sun, 30 Jun 2024 14:05:27 +0000

Introduction To CoreDNS

CoreDNS is a powerful, flexible DNS server written in Go. One of its key features is its plugin-based architecture, which allows users to extend its functionality easily. In this blog post, we'll explore how to write custom plugins for CoreDNS.

As previously mentioned, CoreDNS utilizes a plugin chain architecture, enabling you to stack multiple plugins that execute sequentially. Most of CoreDNS's functionality is provided by its built-in plugins. You can explore these bundled plugins by Clicking here.

Architecture Overview

CoreDNS follows a similar approach to Caddy, as it is based on Caddy v1:

Load Configuration: Configuration is loaded through the Corefile file.
Plugin Setup: Plugins must implement a setup function to load, validate the configuration, and initialize the plugin.
Handler Implementation: You need to implement the required functions from the plugin.Handler interface.
Integrate Your Plugin: Add your plugin to CoreDNS by either including it in the plugin.cfg file or by wrapping everything in an external source code. Further details can be found below.

Develop

Configuration

As mentioned above, everything is done through the Corefile. If you're not familiar with the syntax, check this short explanation: https://coredns.io/2017/07/23/corefile-explained/



. {
    foo
}

In the example above, . defines a server block, and foo is the name of your plugin. You can specify a port or add arguments to your plugin.



.:5353 {
    foo bar
}

Now CoreDNS is running on port 5353 and my plugin named foo is given the argument bar.

It's useful to enable the plugins log and debug during the development.

Checkout the list of bundled plugins to figure out which ones you need in your setup: https://coredns.io/plugins/

Setup

The first thing you need to do is to register and set up your plugin. Registration is done through a function called init which you need to include in your go module.



package foo

import (
    "github.com/coredns/caddy"
    "github.com/coredns/coredns/core/dnsserver"
    "github.com/coredns/coredns/plugin"
)

func init() {
    plugin.Register("foo", setup)
}

Now we need to implement setup() which parses the configuration and returns our initialized plugin.



package foo

import (
    "github.com/coredns/caddy"
    "github.com/coredns/coredns/core/dnsserver"
    "github.com/coredns/coredns/plugin"
)

func init() {
    plugin.Register("foo", setup)
}

func setup(c *caddy.Controller) error {
    c.Next() // #1
    if !c.NextArg() { // #2
        return c.ArgErr()
    }

    dnsserver.GetConfig(c).AddPlugin(func(next plugin.Handler) plugin.Handler {
        return Foo{Next: next, Bar: c.val()} // #3
    })

    return nil // #4
}

Skip the first token which is foo, the name of our argument.
Return an error if our argument didn't have any value.
Put the value of our argument bar in the plugin struct and return it to be put in the plugin chain. Read more details on the plugin struct further down.
return nil as an error if everything is good to go.

Handler

All plugins need to implement plugin.Handler which is the entry point to your plugin.

First, we need to write a struct containing the necessary arguments, runtime objects, and also the next plugin in the chain.



type Foo struct {
    Bar string
    Next plugin.Handler
}

This is the actual struct that we created in the previous step.

We also need a method to return the name of the plugin.



func (h Foo) Name() string { return "foo" }

Now it's time for the most important method which is ServeDNS(). This is the method that is called for every DNS query routed to your plugin. You can also generate a response here making your plugin work as a data backend.



func (h Foo) ServeDNS(ctx context.Context, w dns.ResponseWriter, r *dns.Msg) (int, error) {

  return h.Next.ServeDNS(ctx, w, r)

}

What you see here does nothing but call the next plugin in the chain. But we don't have to do that :)

Use r *dns.Msg to get some info on the DNS query.



state := request.Request{W: w, Req: r}
qname := state.Name()

List of variables you can get from state:

state.Name() name of the query - includes the zone as well
state.Type() type of the query - e.g. A, AAAA, etc
state.Ip() IP address of the client making the request
state.Proto() transport protocol - tcp or udp
state.Family() IP version - 1 for IPv4 and 2 for IPv6 > Read the following file for the complete list: https://github.com/coredns/coredns/blob/master/request/request.go

You can also generate a response and return from the chain. For that, you need to use the amazing github.com/miekg/dns package and build a dns.Msg to return.



func (h Foo) ServeDNS(ctx context.Context, w dns.ResponseWriter, r *dns.Msg) (int, error) {

    dummy_ip := "1.1.1.1"

    state := request.Request{W: w, Req: r}
    qname := state.Name()

    answers := make([]dns.RR, 0, 10)

    resp := new(dns.A)
    resp.Hdr = dns.RR_Header{Name: dns.Fqdn(qname), Rrtype: dns.TypeA,
        Class: dns.ClassINET, Ttl: a.Ttl}
    resp.A = net.ParseIP(dummy_ip)
    answers = append(answers, resp)


    m := new(dns.Msg)
    m.SetReply(r)
    m.Authoritative, m.RecursionAvailable, m.Compress = true, false, true

    m.Answer = append(m.Answer, answers...)

    state.SizeAndDo(m)
    m = state.Scrub(m)
    _ = w.WriteMsg(m)
    return dns.RcodeSuccess, nil
}

In the example shown above, we create an A record response and return it to the client.

Check out the DNS package we used for more details on how to create DNS objects: https://pkg.go.dev/github.com/miekg/dns

If successful, we return dns.RcodeSuccess. To see more return codes, check out here: https://pkg.go.dev/github.com/miekg/dns#pkg-constants

A few important return codes:

RcodeSuccess: No error
RcodeServerFailure: Server failure
RcodeNameError: Domain doesn't exist
RcodeNotImplemented: Record type not implemented

Logging

You can use the logging package provided by the CoreDNS itself, github.com/coredns/coredns/plugin/pkg/log.



package Foo

import (
    clog "github.com/coredns/coredns/plugin/pkg/log"
)

var log = clog.NewWithPlugin("foo")

Now you can log anything you need with different levels:



log.Info("info log")
log.Debug("debug log")
log.Warning("warning log")
log.Error("error log")

Final Example



package Foo

import (
    "github.com/coredns/coredns/request"
    "github.com/miekg/dns"
    "golang.org/x/net/context"
    clog "github.com/coredns/coredns/plugin/pkg/log"
)

var log = clog.NewWithPlugin("foo")

type Foo struct {
    Bar string
    Next plugin.Handler
}

func (h Foo) Name() string { return "foo" }

func (h Foo) ServeDNS(ctx context.Context, w dns.ResponseWriter, r *dns.Msg) (int, error) {

    dummy_ip := "1.1.1.1"

    state := request.Request{W: w, Req: r}
    qname := state.Name()

    answers := make([]dns.RR, 0, 10)

    resp := new(dns.A)
    resp.Hdr = dns.RR_Header{Name: dns.Fqdn(qname), Rrtype: dns.TypeA,
        Class: dns.ClassINET, Ttl: a.Ttl}
    resp.A = net.ParseIP(dummy_ip)
    answers = append(answers, resp)

    log.Debug("answers created")


    m := new(dns.Msg)
    m.SetReply(r)
    m.Authoritative, m.RecursionAvailable, m.Compress = true, false, true

    m.Answer = append(m.Answer, answers...)

    state.SizeAndDo(m)
    m = state.Scrub(m)
    _ = w.WriteMsg(m)
    return dns.RcodeSuccess, nil
}

Compile

CoreDNS gives you two different ways to run your plugin, both are static builds.

Compile-time Configuration

In this method, you need to clone the CoreDNS source code, add your plugin to the plugin.cfg file (plugins are ordered), and compile the code.



etcd:etcd
foo:github.com/you/foo

Then you need to do a go get github.com/you/foo and build the CoreDNS binary using make.

Run ./coredns -plugins to ensure your plugin is included in the binary.

If your plugin is on your local machine you can put something like replace github.com/you/foo => ../foo in your go.mod file.

Wrapping in External Source Code

You also have the option to wrap the CoreDNS components and your plugin in an external source code and compile from there.



package main

import (
    _ "github.com/you/foo"
    "github.com/coredns/coredns/coremain"
    "github.com/coredns/coredns/core/dnsserver"
)

var directives = []string{
    "foo",
    ...
    ...
    "whoami",
    "startup",
    "shutdown",
}

func init() {
    dnsserver.Directives = directives
}

func main() {
    coremain.Run()
}

As with any other go app, do a go build and you should have the binary.

Extending Envoy with WebAssembly Proxy Filters

Amir Keshavarz — Tue, 12 Jul 2022 00:41:33 +0000

Introduction To Envoy

Envoy is an open-source edge and service proxy designed for cloud-native applications.

We can use Envoy as a gateway or a sidecar proxy in scenarios where we need connectivity between services.

It works by applying a number of filters on the data that goes through its proxy.

We can read or manipulate the data using built-in or custom filters/plugins via a filter chain architecture. This design has a proven record for this kind of application, as we've also seen a similar design in NGINX and other reverse proxies.

Envoy Filters

As explained above, we can use filters to do all kinds of stuff on the data received by the listener. Envoy already has many built-in filters written in C++ that you can use.

You can also write your custom filters if any built-in filters aren't suitable for you. These filters can be written in the native C++, Lua, or WASM.

We'll focus on WebAssembly filters in this article.

WebAssembly

WebAssembly is a portable binary instruction format for virtual stack machines.

It aims to execute at native or near-native speed by assuming a few characteristics of the execution environment.

WebAssembly is designed to be executed in a fully sandboxed environment with linear memory. Because of that design, the binary is entirely blind to the host environment. That being said, we can set up some kind of communication by reading memory or importing functions. But don't worry about that since we won't need to implement these interfaces ourselves.

Proxy-Wasm

Proxy-Wasm is a set of ABI specifications to use between L4/L7 proxies (and/or other host environments) and their extensions delivered as WebAssembly modules.

Even though it was first designed for Envoy, other proxy projects have also picked it up as the ABI spec for their WASM integration.

Writing Filters

We've chosen AssemblyScript to write our filter. AssemblyScript is a TypeScript-like designed for WebAssembly.

To interact with the proxy-wasm host, We'd need to export a set of low-level interfaces to the host, but fortunately, There's a package called solo-io/proxy-runtime that does the most of the heavy lifting for us. See here for code samples

Create a project by using these commands:

npm install --save-dev assemblyscript
npx asinit .

add --use abort=abort_proc_exit to the asc in packages.json:

    "asbuild:optimized": "asc assembly/index.ts -b build/optimized.wasm --use abort=abort_proc_exit -t build/optimized.wat --sourceMap --optimize",

assembly/index.ts is now our entrypoint to the WebAssembly module.

Open it and use this sample code as a demo:

// @ts-ignore
export * from "@solo-io/proxy-runtime/proxy";
import { RootContext, Context, registerRootContext, FilterHeadersStatusValues, stream_context } from "@solo-io/proxy-runtime";

class AddHeaderRoot extends RootContext {
    createContext(context_id: u32): Context {
        return new AddHeader(context_id, this);
    }
}

class AddHeader extends Context {
    constructor(context_id: u32, root_context: AddHeaderRoot) {
        super(context_id, root_context);
    }
    onResponseHeaders(a: u32, end_of_stream: bool): FilterHeadersStatusValues {
        stream_context.headers.response.add("Hello", "World!");

        return FilterHeadersStatusValues.Continue;
    }
}

registerRootContext((context_id: u32) => { return new AddHeaderRoot(context_id); }, "add_header");

proxy-wasm has a few hook points you can use to inject your module. We used onResponseHeaders / proxy_on_response_headers here to add our custom header to the response. Using this filter, we should see an additional header in the response.

Hello: World!

Now It's time to run Envoy and configure it to use our module.

I recommend using func-e as it makes installing and running Envoy extremely easy. More Info

curl https://func-e.io/install.sh | bash -s -- -b /usr/local/bin

Open envoy.yaml and configure your Envoy. As we discussed before, Envoy works by chaining several filters, starting from TCP connections to http and more.

I've put a sample config here, but we'll go through each section to explain what the configuration means:

admin:
  address:
    socket_address: { address: 127.0.0.1, port_value: 9901 }

static_resources:
  listeners:
  - name: listener_0
    address:
      socket_address: { address: 127.0.0.1, port_value: 8080 }
    filter_chains:
    - filters:
      - name: envoy.filters.network.http_connection_manager
        typed_config:
          "@type": type.googleapis.com/envoy.extensions.filters.network.http_connection_manager.v3.HttpConnectionManager
          stat_prefix: ingress_http
          codec_type: AUTO
          route_config:
            name: local_route
            virtual_hosts:
            - name: local_service
              domains: ["*"]
              routes:
              - match: { prefix: "/" }
                route: { cluster: service_0 }
          http_filters:
          - name: envoy.filters.http.wasm
            typed_config:
              "@type": type.googleapis.com/udpa.type.v1.TypedStruct
              type_url: type.googleapis.com/envoy.extensions.filters.http.wasm.v3.Wasm
              value:
                config:
                  name: "add_header"
                  root_id: "add_header"
                  vm_config:
                    vm_id: "my_vm_id"
                    runtime: "envoy.wasm.runtime.v8"
                    code:
                      local:
                        filename: "/path/to/optimized.wasm"
                    allow_precompiled: false
          - name: envoy.filters.http.router
            typed_config:
              "@type": type.googleapis.com/envoy.extensions.filters.http.router.v3.Router
  clusters:
  - name: service_0
    connect_timeout: 0.25s
    type: STRICT_DNS
    lb_policy: ROUND_ROBIN
    load_assignment:
      cluster_name: service_0
      endpoints:
      - lb_endpoints:
        - endpoint:
            address:
              socket_address:
                address: 127.0.0.1
                port_value: 80

admin: here, we tell Envoy where to listen for its admin interface. The admin interface exposes some administration and monitoring functionalities.
static_resources: here is where the most exciting stuff happens. We set up our listeners and filters here.
static_resources.listeners: we setup our actual listeners here.
static_resources.filter_chains: All traffic filters are configured here. We have the http_connection_manager filter as ingress for our http traffic. This filter has http_filters, which defines what http filters to run. That's the part where we set up our module.
static_resources.filters[0].http_filters[0]: this is our WebAssembly module. We specify where to find the module itself (/path/to/optimized.wasm) and what is the root (add_header).
clusters: we put our origin services here.

To run Envoy, simply run this command:

func-e run -c /path/to/envoy.yaml

Now try it out and you should see the additional header:

curl -I http://127.0.0.1:8080

Response:

HTTP/1.1 200 OK
content-type: text/html
date: Mon, 11 Jul 2022 23:59:07 GMT
server: envoy
content-length: 345
x-envoy-upstream-service-time: 196
Hello: World!

Yay! We just used a WebAssembly module to inject custom headers into the response.

Conclusion

Even though this post only touches on the tip of the iceberg, It represents what proxy-wasm is capable of. You can write your filters in whatever language you desire, and It'll run at near-native speeds.

Many companies are investing hugely in server-side WebAssembly, and more exciting things are to come.

I'm also trying to write more on WebAssembly and its future if you're interested in the subject.

Cache Replacement Algorithms: How To Efficiently Manage The Cache Storage

Amir Keshavarz — Thu, 14 Oct 2021 12:30:22 +0000

Caching

Let's start at the beginning and talk about what caching even is.

Caching is the process of storing some data near where It's supposed to be used rather than accessing them from an expensive origin, every time a request comes in.

Caches are everywhere. From your CPU to your browser. So there's no doubt that caching is extremely useful. implementing a high-performance cache system comes with its own set of challenges. In this post, we'll focus on cache replacement algorithms.

from wikipedia.com

Cache Replacement Algorithms

We talked about what caching is and how we can utilize it but there's a dinosaur in the room; Our cache storage is finite. Especially in caching environments where high-performance and expensive storage is used. So in short, we have no choice but to evict some objects and keep others.

Cache replacement algorithms do just that. They decide which objects can stay and which objects should be evicted.

After reviewing some of the most important algorithms we go through some of the challenges that we might encounter.

LRU

The least recently used (LRU) algorithm is one of the most famous cache replacement algorithms and for good reason!

As the name suggests, LRU keeps the least recently used objects at the top and evicts objects that haven't been used in a while if the list reaches the maximum capacity.

So it's simply an ordered list where objects are moved to the top every time they're accessed; pushing other objects down.

LRU is simple and providers a nice cache-hit rate for lots of use-cases.

from progressivecoder.com

LFU

the least frequently used (LFU) algorithm works similarly to LRU except it keeps track of how many times an object was accessed instead of how recently it was accessed.

Each object has a counter that counts how many times it was accessed. When the list reaches the maximum capacity, objects with the lowest counters are evicted.

LFU has a famous problem. Imagine an object was repeatedly accessed for a short period only. Its counter increases by a magnitude compared to others so it's very hard to evict this object even if it's not accessed for a long time.

FIFO

FIFO (first-in-first-out) is also used as a cache replacement algorithm and behaves exactly as you would expect. Objects are added to the queue and are evicted with the same order. Even though it provides a simple and low-cost method to manage the cache but even the most used objects are eventually evicted when they're old enough.

from wikipedia.com

Random Replacement (RR)

This algorithm randomly selects an object when it reaches maximum capacity. It has the benefit of not keeping any reference or history of objects and being very simple to implement at the same time.

This algorithm has been used in ARM processors and the famous Intel i860.

The Problem of One-hit Wonders

Let's talk about a problem that occurs in large-scale caching solutions, one-hit wonders.

One-hit wonders are objects that are rarely or never accessed twice. This happens quite often in CDNs where the number of unique objects is huge and most objects are rarely used again.

This becomes a problem when every bit of storage performance matters to us. By caching these objects we basically pollute our storage with junk since these cache objects are always evicted before they're used again. So we waste a large amount of resources just to persist some objects that we're not going to use.

So what's the solution? Unfortunately, there's no silver bullet here. The most used solution is just not caching an object when it's first accessed!

By keeping a list of object signatures, we can only cache the objects that are seen more than one time. This might seem weird at first but overall it improves your disk performance significantly.

After accepting this solution, we immediately encounter another challenge. In many scenarios, the number of object signatures is extremely large so storing the list itself becomes a challenge. In this case, we can use probabilistic data structures such as the bloom filter data structure.

I've covered probabilistic data structures in a previous post: Rate Limiting in IPv6 Era Using Probabilistic Data Structures

from wikipedia.com

In short, probabilistic data structures like bloom filter use a lot less memory but in return, they only give a probabilistic answer to our queries. In our case, the bloom filter offers a nice solution since we don't need definite answers to improve our cache performance.

Conclusion

In this post, we went through multiple cache replacement algorithms and understood how we can efficiently manage our cache storage. We also covered the famous problem of one-hit wonders and a solution that helps in most cases.

A Closer Look Into The World of Database Replication

Amir Keshavarz — Sun, 15 Aug 2021 17:45:21 +0000

We all have used or heard about database replication at some point but have you ever wondered how It works underneath?

That's exactly what we'll be doing here.

Replication is basically copying an object from one space into another. Replicating immutable objects like a movie file is as simple as copying its bytes.

Replication a database which is a mutable object comes with its own challenges. How do you copy an object that is always changing? You don't!

Logs

Logs are the most important part of a database replication process. The basic idea of a log is to record every action database does. We should be able to replay these logs to reconstruct a corrupt database object from scratch so It makes sense to keep them in order.

Let's imagine a key/value store. In this database, we have 3 different types of operation:

SET: Sets a value to a key
GET: Retrieves the value of a key
DELETE: Delete a key

These are the instruction set of our database. Now, let's use them.

I want to set the value of john to the key name, so my operation log would be:

{
  "operation": "SET",
  "key": "name",
  "value": "john"
}

Now let's change the value of that same key to eli:

{
  "operation": "SET",
  "key": "name",
  "value": "eli"
}

And at last, let's remove it:

{
  "operation": "DELETE",
  "key": "name"
}

As you see, logs are only the operations that mutate the database in some way. But something is missing from these logs. Order!

We have to somehow not only keep them in order but to be able to recover from a specific position in the logs.

2 obvious options are:

Incremental integer: Assign an incrementing number to each log
Timestamp: Record the timestamp when the log was executed

We go with the first option for now. We executed 3 operations so the logs will be:

[
  {
    "id": 1,
    "operation": "SET",
    "key": "name",
    "value": "john"
  },
  {
    "id": 2,
    "operation": "SET",
    "key": "name",
    "value": "eli"
  },
  {
    "id": 3,
    "operation": "DELETE",
    "key": "name"
  }
]

Now our logs are ordered and seekable from an id. We can recover the database at any point in time.

I think you get the idea now. When we talk about replication, we're talking about copying these logs into another space. If we're replication the database into another server, we continuously send these logs to the second server and tell it to replay these logs exactly. If the connection drops or something bad happens we always know where to start again because we already have a sortable id.

We now know how databases share their state with other instances. In the next section, we talk about 2 very basic types of replication.

Types

Synchronous

In synchronous replication, we commit changes to all of the instances before getting back to the client.

Imagine we have 3 instances in a database cluster and we want to use the synchronous replication type.

When we send a SET operation to instance A which is the master, It immediately sends the log to other replica instances. These replicas execute the log and let the master know that they've executed the logs. After making sure all replicas have executed the change, the master itself also executes the log and returns a response to let the user know that the change was done successfully.

The advantage of this type is the level of consistency that we get by executing the change on all instances before committing the change.

And the disadvantage is the overhead in latency which causes the whole process to be slow.

Asynchronous

Unlike the synchronous type, in this type, we can't guarantee consistency because we consider the change committed before it's executed on other instances.

As before, imagine we have 3 instances in a database cluster and we want to use an asynchronous replication type.

When we send a SET operation to instance A which is the master, It generates a log and executes it. After that, the asynchronous process of sending the logs to other instances begins but the master won't wait on these and it immediately gets back to the user with a successful response.

The advantage of this type is the low latency write operations since it only mutates the master before being considered committed.

The disadvantage of this type is the lack of consistency guarantee since we can't be sure the replication takes place at all. Master might be caught on fire before getting the chance to send log to other replicas :)

Consistency

We talked about how the replication process can be synchronous or asynchronous. But let's get back one step backward and discuss consistency from distributed systems' point of view.

In a distributed system like a replicated database cluster, we need some type of consistency because that's the whole purpose of replication!

Consistency is achieved when multiple nodes agree on a single state.

Let's show it by an example.

The state of node A is:

[
  {
    "key": "name",
    "value": "eli"
  }
]

The state of node B also is:

[
  {
    "key": "name",
    "value": "eli"
  }
]

As you can see, both nodes agree that the value of name is eli so they're consistent.

There are multiple levels of consistency and at the most basic level, it correlates to the replications types.

We'll discuss 2 types of consistency here.

Strong Consistency

In a distributed system that supports strong consistency, all nodes are always consistent at any given moment. It doesn't matter what node you write to or read from; the result is always guaranteed to be the same.

This consistency is achieved using consensus protocols like Paxos or Raft.

Weak Consistency

In many cases, we don't really need strong consistency or need some other property that can't coexist with strong consistency.

In this type of consistency, there's no guarantee that the state of your replica is up-to-date with the master.

Eventual Consistency

Eventual consistency is a type of weak consistency itself. As the name suggests, eventual consistency guarantees that even though replicas may not be up-to-date but will be consistent with the master eventually.

Basically, if you stop writing to the master, after some time, all nodes will be consistent and all replicas will answer the most recent values to you.

Sync Replication

We already talked about synchronous and asynchronous replication but in this section, we discuss in more detail and also about its real-world implementation.

Before committing any transaction, we need to make sure all nodes are on the same page. That's just consensus so we need one.

Synchronous replication requires a round-trip from master to most or all nodes for every single log and that's why synchronous replication can be really slow compared to asynchronous replication. Strong consistency has a huge cost!

The most famous consensus protocol is Paxos but It's not the easiest protocol to explain. There's a new shiny protocol called Raft that has gotten lots of traction in the past few years and lots of big projects like etcd are already using it. It's a lot easier to learn compared to Paxos.

Raft

Raft is a relatively new asymmetric consensus protocol designed to be really easy to understand.

Nodes in Raft are always in one of these states:

Follower
Candidate
Leader

One of the most important things in Raft is the fact that followers trust the leader and will redirect all write operations to the leader. The leader will coordinate all changes.

Raft slices the time into terms. Think of them exactly as election terms. At the beginning of the term, nodes become candidates, vote for themself and ask others to vote for them. After some time, a leader is elected and Raft begins to exchange messages between nodes.

An election timeout is specified to make sure there's always a leader present. This timeout is pushed back by ping messages by the leader but If the leader steps back or has failed, another election will take place and all of those steps are repeated until another leader is elected.

Real-world

The etcd key/value store which powers Kubernetes is a good example here. It uses Raft to replicate logs synchronously to achieve strong consistency.

You can see the etcd implementation of Raft in here:
https://github.com/etcd-io/etcd/tree/main/raft

Asynchronous replication

Ok, let's talk a bit more about asynchronous replication. You now know how asynchronous replication works in theory. Some logs are sent asynchronously and there's no guarantee of consistency at any given moment.

We'll discuss Ordered Log Replication here which is really simple with a few challenges.

Ordered Log Replication

As the name suggests, this technique involves persisting an ordered list of logs and sending them over the wire, asynchronously.

Ordering means that writes are usually written to master to ensure the consistency of end result. All logs are tagged with a timestamp or an incremental number.

Immediately you notice a bottleneck here since all logs need to be ordered. Some databases use sharding in order to increase the throughput.

Each of these challenges can be a post themself and most of them are also present in the synchronous type of replication.

Real-world

MySQL replication is a really good example of this type of replication.

MySQL keeps an ordered log of every change in the master by using an incremental integer known as position.

Logs are kept in binlog-* files and are rotated regularly. Replicas (known as slaves in MySQL - fortunately, it's about to change) receive these logs and execute them.

The basic process of adding replicas to MySQL is a little bit too hard. It requires you to take a snapshot of the database and recording the master position and then restoring that snapshot in replica and starting the replication process from that exact position. Lots of other databases do that same thing underneath but I think MySQL could do these without requiring users to do these tasks manually.

Conclusion

In this post, we learned a bit more about database replication and its different types. We discussed different levels of consistency and how replication works in the real world.

I might write more about databases in the future. Let me know If you're interested :)

Thank you for your time.

Rate limiting using the Sliding Window algorithm

Amir Keshavarz — Thu, 12 Aug 2021 06:51:27 +0000

In this part of the rate-limiting series, we will introduce the Sliding Window algorithm and implement it in Python.

Even though there are more rate-limiting algorithms out there, I'm going to end the series here since I think These three algorithms are a pretty good gateway to the rate-limiting techniques.

Sliding Window

Unlike the previous Fixed Window algorithm, this algorithm does not limit the requests based on a fixed time unit.

A problem with Fixed Window was that It allowed a huge burst at the edge of windows because you can combine the capacity of the current and the next window to send a burst of requests.

Sliding Window tries to fix that by taking the previous counter into account, causing the flow to be more smooth.

Let's explain it with an example. Imagine that we have a rate limiter with a time unit of 60 seconds and a capacity of 50.

A request has entered at 00:01:20. The current time unit still has capacity left but as we learned the previous counter also affects the outcome.

The previous counter only affects as much as the space it still has occupied in the window. In our example, that would be ~67%.

So with that in mind, we use the following formula to calculate an estimated count.

ec = previous counter * ((time unit - time into the current counter) / time unit) + current counter

ec = 50 * 0.67 + 20 = 53.5

Our capacity was 50 and because of that, this request is dropped since 53.5 > 50.

Now, If another request comes in at 00:01:40, the ec would be:
ec = 50 * 0.34 + 20 = 37

This request is allowed to pass since 37 < 50.

Implementation

In this very simple implementation, We will build a rate-limiter that uses Sliding Window to limit packets in 1-second time frames.

We start by defining a class with 3 arguments when It's being instantiated.

capacity: number of the allowed packets that can pass through in a second.
time_unit: length of time unit in seconds.
forward_callback: this function is called when the packet is being forwarded.
drop_callback: this function is called when the packet should be dropped.



from time import time, sleep


class SlidingWindow:

    def __init__(self, capacity, time_unit, forward_callback, drop_callback):
        self.capacity = capacity
        self.time_unit = time_unit
        self.forward_callback = forward_callback
        self.drop_callback = drop_callback

        self.cur_time = time()
        self.pre_count = capacity
        self.cur_count = 0

cur_time is the edge of our current time unit.
pre_count is the previous counter. We pre-fill this to prevent bursting at the beginning of the rate limiter.
cur_count is the current counter that will get filled as new requests come in.

Then, we define handle() where the magic happens.



def handle(self, packet): #1
    if (time() - self.cur_time) > self.time_unit: #2
        self.cur_time = time()
        self.pre_count = self.cur_count
        self.cur_count = 0

    ec = (self.pre_count * (self.time_unit - (time() - self.cur_time)) / self.time_unit) + self.cur_count #3

    if (ec > self.capacity): #4
        return self.drop_callback(packet)

    self.cur_count += 1 #5
    return self.forward_callback(packet)

handle accepts only 1 parameter: the packet.
If the current time unit is passed, switch over to a new time unit.
Calculate the estimated count based on the given formula
Drop the packet if ec is bigger than the capacity.
Otherwise, add one to the current counter and forward the packet.

Final Code



from time import time, sleep


class SlidingWindow:

    def __init__(self, capacity, time_unit, forward_callback, drop_callback):
        self.capacity = capacity
        self.time_unit = time_unit
        self.forward_callback = forward_callback
        self.drop_callback = drop_callback

        self.cur_time = time()
        self.pre_count = capacity
        self.cur_count = 0

    def handle(self, packet):

        if (time() - self.cur_time) > self.time_unit:
            self.cur_time = time()
            self.pre_count = self.cur_count
            self.cur_count = 0

        ec = (self.pre_count * (self.time_unit - (time() - self.cur_time)) / self.time_unit) + self.cur_count

        if (ec > self.capacity):
            return self.drop_callback(packet)

        self.cur_count += 1
        return self.forward_callback(packet)


def forward(packet):
    print("Packet Forwarded: " + str(packet))


def drop(packet):
    print("Packet Dropped: " + str(packet))


throttle = SlidingWindow(5, 1, forward, drop)

packet = 0

while True:
    sleep(0.1)
    throttle.handle(packet)
    packet += 1

You should be getting something like this:



Packet Forwarded: 0

Packet Forwarded: 1

Packet Dropped: 2

Packet Forwarded: 3

Packet Dropped: 4

Packet Forwarded: 5

Packet Dropped: 6

Packet Forwarded: 7

Packet Dropped: 8

Packet Forwarded: 9

Packet Dropped: 10

Packet Forwarded: 11

Packet Dropped: 12

Packet Forwarded: 13

Packet Dropped: 14

Packet Forwarded: 15

Packet Dropped: 16

Packet Forwarded: 17

Packet Dropped: 18

Packet Forwarded: 19

Packet Dropped: 20

Packet Forwarded: 21

Packet Dropped: 22

Packet Forwarded: 23

Conclusion

In this post, we learned about the Sliding Window algorithm and tried to implement it in Python.

During this series, we covered Token Bucket, Fixed Window, and Sliding Window. Even though there are famous algorithms like Leaky Bucket or Sliding Log, I decided to end this series here since I believe these three covers the basic ideas of most rate-limiting algorithms, and this series was also expected to be short and simple.

Thank you for your time and I hope to see you on my other posts :)

CPU Time: How To Accurately Benchmark Your Code

Amir Keshavarz — Wed, 04 Aug 2021 17:37:42 +0000

I'm going to assume that everyone reading this post has done some benchmarking here and there. But have you ever thought about how accurate are your readings?

In this post, we will talk about a few misconceptions, task schedulers, CPU timings, and a real example in C.

Misconceptions

Time matters

Ok, to be fair, the title is click-bait. Time really matters but not the time you see on your clock! We only care how much time is CPU spending on our process and that's usually not the wall-clock time.

Slow software = Slow code

The speed of your software depends on the environment that's running. I'm not talking about your computer specs. Softwares rely heavily on syscalls or I/O interfaces.
During a benchmark, You really should pay attention to this subject since I/O is really really slow and I've seen too many times when software is considered slow without realizing that a huge part of this problem is caused by slow I/O and can be improved with technics like caching and etc.

Performance is not important

Performance is UX but most micro-optimizations are usually time-wasting and not worth it. I think there's a fine line that we shouldn't cross when developing a product. You can pack your product with features but most people will hate it at a glance if It's too slow or sluggish.
I'd say that finding this line may not be as easy as saying it but I don't see another way around it.

Schedulers

With the notion of multi-tasking operating systems, it came task schedulers. To be able to run multiple programs at the same time we need a "scheduler" to schedule the work between limited CPU cores.

We will discuss two types of schedulers.

Preemptive Multitasking

In this model of multitasking, the kernel preemptively schedules tasks and interrupts processes to let other processes run.

Our software doesn't notice these interrupts since its state is frozen to be used later when there's free CPU time for the process.

The Linux kernel scheduler is an example of this model.

Cooperative Multitasking

Unlike preemptive multitasking, this model relies solely on the code itself to free the resources back to the scheduler.

So the scheduler itself has no control over the process until the process yields back to let the scheduler know that the job is done or It's blocked so the CPU can be used for other processes.

The Go language goroutine scheduler is an example of this model.

CPU Time

CPU Time is the time that is actually spent on the CPU. So no I/O time is included in this.

For example, if you're doing HTTP requests and each request takes a second to respond, the CPU time doesn't include that second since during that time, we didn't do any CPU work and just waited for the response.

In Linux, A POSIX compliant kernel, these times are kept for each process or thread.

Code

In this very simple program, we use the clock() function to benchmark a simple pi calculation code.



#include <time.h>

// https://crypto.stanford.edu/pbc/notes/pi/code.html
int pi_calculate()
{
    int r[2800 + 1];
    int i, k;
    int b, d;
    int c = 0;

    for (i = 0; i < 2800; i++)
    {
        r[i] = 2000;
    }

    for (k = 2800; k > 0; k -= 14)
    {
        d = 0;

        i = k;
        for (;;)
        {
            d += r[i] * 10000;
            b = 2 * i - 1;

            r[i] = d % b;
            d /= b;
            i--;
            if (i == 0)
                break;
            d *= i;
        }
        c = d % 10000;
    }

    return 0;
}

int main(void)
{
    clock_t start_time = clock();
    int pi;

    for (int i = 0; i < 100; i++)
    {
        pi = pi_calculate();
    }

    double elapsed_time = (double)(clock() - start_time) / CLOCKS_PER_SEC;
    printf("%f seconds\n", elapsed_time);
}

A few relevant and useful functions:

`clock()`



#include <time.h>

clock_t clock(void);

This is the function that we used in our code to get the clock time of our current process.

`clock_getcpuclockid()`



#include <time.h>

int clock_getcpuclockid(pid_t pid, clockid_t *clockid);

This function returns a CPU clock id by using a PID. By obtaining the clock id you're able to get the CPU usage.

As you can see, you can easily get the time of a clock.

`pthread_getcpuclockid()`



#include <pthread.h>
#include <time.h>

int pthread_getcpuclockid(pthread_t thread, clockid_t *clockid);

If you're working in multi-thread software, You may use this function to get the clock of a POSIX thread.

`clock_gettime()`



#include <time.h>

int clock_gettime(clockid_t clockid, struct timespec *tp);



struct timespec {
     time_t   tv_sec;        /* seconds */
     long     tv_nsec;       /* nanoseconds */
};

Use this function to get the time of a clock.

Conclusion

In this post, we went through a few terminologies regarding the schedulers and timing and then learned how to accurately benchmark our code using the CPU clock time that kernel provides for us.

I really hope you enjoyed this post.

Rate limiting using the Fixed Window algorithm

Amir Keshavarz — Wed, 21 Jul 2021 17:21:33 +0000

In the previous post, we went through rate-limiting and what it is. Then, we introduced an algorithm called Token Bucket and implemented it in Python.

I've decided to turn this into a series and dedicate each post to an algorithm.

And in this post, we will learn about Fixed Window and its implementation in Python.

Fixed Window

As the name suggests, It's all about windows. In this algorithm, we divide the time into fixed windows and then map the incoming events into these windows.

The algorithm itself is pretty simple without any analogy but let's start with one anyway.

Imagine a moving train. There's a gateway and at any moment, people only can board one wagon (Yep, people are boarding a moving train, nothing weird).

Assume that the window of boarding for each wagon is 1 minute. So if a wagon gets full you need to wait for up to a minute for the next wagon.

In this analogy, the train is the time! The time is always moving forward and in each time frame, we have a fixed window of passing through.

Implementation

In this very simple implementation, We will build a rate-limiter that uses Fixed Window to limit packets in 1-second time frames.

We start by defining a class with 3 arguments when It's being instantiated.

capacity: number of the allowed packets that can pass through in a second.
forward_callback: this function is called when the packet is being forwarded.
drop_callback: this function is called when the packet should be dropped.

We prefill a property named allowance to allow the packet to pass through in the first second.

current_time is the current time frame that the rate-limiter is using.



from time import time, sleep


class FixedWindow:

    def __init__(self, capacity, forward_callback, drop_callback):
        self.current_time = int(time())
        self.allowance = capacity
        self.capacity = capacity
        self.forward_callback = forward_callback
        self.drop_callback = drop_callback

Then, we define handle() where the magic happens.



def handle(self, packet): #1
    if (int(time()) != self.current_time): #2
        self.current_time = int(time()) #3
        self.allowance = self.capacity #3

    if (self.allowance < 1): #4
        return self.drop_callback(packet) #5

    self.allowance -= 1 #6
    return self.forward_callback(packet) #6

handle accepts only 1 parameter: the packet.
check if we're in the current time frame or not.
if we're not in the current time frame, update the current_time and reset the allowance.
check if we have any allowance left.
drop the packet if we don't have any allowance left.
in this part, we already know that there is allowance left, so we remove one from the allowance and forward the packet.

As you can see, Fixed Window is extremely simple. This is the final code:



from time import time, sleep


class FixedWindow:

    def __init__(self, capacity, forward_callback, drop_callback):
        self.current_time = int(time())
        self.allowance = capacity
        self.capacity = capacity
        self.forward_callback = forward_callback
        self.drop_callback = drop_callback

    def handle(self, packet):
        if (int(time()) != self.current_time):
            self.current_time = int(time())
            self.allowance = self.capacity

        if (self.allowance < 1):
            return self.drop_callback(packet)

        self.allowance -= 1
        return self.forward_callback(packet)


def forward(packet):
    print("Packet Forwarded: " + str(packet))


def drop(packet):
    print("Packet Dropped: " + str(packet))


throttle = FixedWindow(1, forward, drop)

packet = 0

while True:
    sleep(0.2)
    throttle.handle(packet)
    packet += 1

You should be getting something like this:



Packet Forwarded: 0
Packet Dropped: 1
Packet Dropped: 2
Packet Forwarded: 3
Packet Dropped: 4
Packet Dropped: 5
Packet Dropped: 6
Packet Dropped: 7
Packet Forwarded: 8
Packet Dropped: 9
Packet Dropped: 10
Packet Dropped: 11
Packet Dropped: 12
Packet Forwarded: 13

In the code above, we built a rate-limiter with a rate of one packet per second. Then, we send a packet every 0.2 seconds to see the rate-limiter do its thing.

This algorithm is pretty useful to learn about rate-limiting but we rarely see it in the wild since it allows a burst of events at the beginning of the time frame but it really depends on your application.

Thank you for your time.

Rate Limiting in IPv6 Era Using Probabilistic Data Structures

Amir Keshavarz — Thu, 17 Jun 2021 15:01:01 +0000

In any system where two parties communicate with each other, we hear things like rate-limiting, flow control, etc. The problem is that all systems have limits and to protect the system, you'd need to somehow control the flow of information passing through.

As you may have already figured out, we're going to talk about a specific problem regarding rate-limiting in IPv6 networks.

Packets

When we communicate through computer networks, we need to break down our data into smaller pieces called packets. These packets are basically like the letters you send through the post.

Each letter (packet) has 3 important components:

Source Address
Destination Address
The actual data

As you can see, real packets also have those things. (The picture only shows the IP header which doesn't include the data body)

We only care about the source and destination addresses in this context, so we call them a 2-tuple.

IP Addresses

Until now, IPv4 is still dominant in most countries but its address pool is limited, thus, It's not future-proof.

IPv6 is the successor to the IPv4 and instead of a 32-bit address, it provides 128-bit addresses so It's a huge bump in the case of the address pool.

IPv4 address pool: 4,294,967,296
IPv6 address pool: 340,282,366,920,938,463,463,374,607,431,768,211,456

Yep, that's a huge difference.

Even though IPv6 itself is not a new protocol, but the process of migrating to IPv6 from IPv4 has been a tedious and very long battle. The issue is that IPv6 is not backward compatible and lots of old hardware and software don't and will not support IPv6.

Nonetheless, IPv6 is already here and its users are rising by the day. Google's statistics show IPv6 availability of its users at around 30.30–35.10% depending on the day of the week (greater on weekends), as of April 2021.

Before continuing, you can also read another post of mine which goes through different technics on how to implement a rate-limiter:

Rate limiting using the Token Bucket algorithm

As we talked about before, that's not the case for IPv6 addresses because of its huge address pool. Even if you may see no difference in normal times, the existing risk won't be accepted by lots of people.

So what's the solution? How can we store the frequency of these events in a space-efficient data structure?
Like all solutions, we compromise.

Challenge

Even in the simplest forms of rate-limiting, we're required to store the number of times that packets with similar 2-tuple have been processed.

In most IPv4-era systems, that information is stored in an array or a tree, or some other normal data structure. They'll do the job perfectly since the IPv4 address pool is not that big so keeping all of the data won't be an issue.

For this purpose, we can use probabilistic data structures, specifically Count-Min Sketch.

Probabilistic Data Structures

Unlike normal data structures which are deterministic, probabilistic data structures are not deterministic and won't give you definite answers but only an estimation or a probability.

This kind of data structure is useful when an unknown stream of data is being processed.

You'd be amazed to find out in how many cases we don't really need deterministic data structures especially when we're processing data streams.

Probabilistic data structures are lossy but that's not really an issue for our use case since we only need to know the heavy-hitters. With an enough large space, the risk of collision should be low enough for most people.

Count-Min Sketch

The Count-Min Sketch, or CMS for short, is a probabilistic data structure to count the frequencies of events.

We can argue that the whole CMS is like a 3-D table.

w: a fixed width
d: pairwise-independent hash functions
c: total count of an event

w is basically an arbitrary width. The bigger it is, the lower the overestimation is.
d is a list of hash functions that shouldn't have many collisions with each other.
c is the number that we increment when an event is repeated.

The process of incrementing or estimation is really simple.

Incrementing

Calculate the hash of your event using the hash function h1.
Normalize the hash value to the w so you would get an index.
Increment the element w[hash] by 1.
Repeat the process for all hash functions in d.

Estimation

Calculate the hash of your event using the hash function h1.
Normalize the hash value to the w so you would get an index.
Get the value of element w[hash].
Repeat the process for all hash functions and then jump to 5.
Between all the values that you got, the lowest one is your estimation.

As you may have already guessed, the whole CMS is quite similar to other probabilistic data structures like bloom filters. It's relatively simple and quite fast.

Implementation

Now we can implement a dead simple Count-Min Sketch data structure in Python.

import mmh3

class CountMinSketch():
    def __init__(self, w, d): #1
        self.w = w
        self.d = d
        self.tables = []
        for _ in range(d):
            self.tables.append([0] * w) #2

    def hash(self, x, seed):
        return mmh3.hash(x, seed) % self.w #3

    def add(self, x):
        for i in range(self.d): #4
            self.tables[i][self.hash(x, i)] += 1 #5

    def get(self, x):
        items = []
        for i in range(self.d): #6
            items.append(self.tables[i][self.hash(x, i)]) #7
        return min(items) #8

We require 2 parameters to create a CMS object. w: the width of our table and d: number of hash functions.
We pre-populate the tables with zeros. Notice that one dimension is s and the other w which is basically a matrix.
This is our hash function. It requires 2 parameters. x which is the input and seed that is used to seed the mmh3 hash function. seed needs to be unique for each d. Later you'll see that I used the index of d elements for seed but that's not good :) You need to generate random numbers when creating the CMS object for each element. After generating the hash, we normalize it relative to w to generate an index for w arrays.
In the add function, we should iterate over all hash function elements (d).
For each element, we calculate a hash which itself is an index for w arrays. Now we have an index for both dimension and increment the value by one.
In the get function like the one in add, we iterate over all hash function elements (d).
Like before, we calculate the hash, and using the table index, we get the value inside and put it in a temporary array named items.
After going through all hash function elements (d), we select the minimum of all items and return it. This is basically our estimation.

Example

sketch = CountMinSketch(10, 10)

sketch.add("2001:0db8:85a3:0000:0000:8a2e:0370:7334")
sketch.add("2001:0db8:85a3:0000:0000:8a2e:0370:7334")

print(sketch.get("2001:0db8:85a3:0000:0000:8a2e:0370:7334")) # prints 2

Conclusion

By combining this and a simple rate-limiter explained in another post (Rate limiting using the Token Bucket algorithm
), You'll have a rate-limiter ready for IPv6.

There's lots of optimization you can do and one of them is making the object, CIDR-aware. You can also tweak the implementation or use different hash functions to get the best performance possible.

Even though we used Count-Min Sketch to store the frequency of incoming packets, but its application is extremely broad, especially when you're dealing with stream processing workloads.

This post was so fun to write and I hope you found it fun to read. :)

Function as a service: behind the scenes

Amir Keshavarz — Sun, 28 Mar 2021 14:49:05 +0000

Function as a service: behind the scenes

It's been months when I first decided to write this post but I honestly didn't know to structure all the materials. With that in mind, I started writing it so let's see how It goes.

This article tends to be a little bit unfair because I won't cover all topics equally. There are some things that interest me more than others.

Introduction to Function as a service

As the name suggests, in this model we deploy units of "function" or "code". These platforms are designed to make developers stop worrying about the underlying infrastructure needed to run their code.

In this model, the FaaS platform is language-aware so the only thing developers need to do is exposing a function to the FaaS runtime and the rest will be taken care of by the FaaS platform. So no servers, only an entry point function!

This doesn't mean that your code magically is deployed without any kind of server. The server stuff is provided and managed by the FaaS platform so you don't have to worry about it.

By using a FaaS platform, You can achieve Serverless, the buzzword of the year! In a true Serverless platform, some concepts like servers, containers, scaling, reserved resources and etc simply don't exist in users' world. Also in most platforms, billing is done on a per-request basis which is awesome :)

These things sound amazing and I do believe it is. But most legacy systems are not designed to be deployed using this model and lots of them for good reasons. It's worth noting that most FaaS platforms assume that your software is stateless so their use case might be limited for now.

Anyway, we're not here to discuss the pros and cons of FaaS. So let's dive in and find out how a FaaS platform is made.

FaaS is used for a variety of use cases including:

Data Processing
IoT Backend Services
Cron Jobs
All kinds of web access control
Middlewares
Caching
Serving static sites

Categorization

Depending on the context, we can define multiple categories for FaaS.

Locality

Central and local deployments
Edge Computing

Central and local deployments is what we think of FaaS platforms when we first think about them. A central and local system that runs our code.

Edge Computing truly deserves its own blog post but to make it short, we can say that edge computing is when our code is deployed to multiple regions, and when a user calls our code, we serve them from the nearest location. This model is usually well integrated into CDNs.

Infrastructure

VM-based
Container-based
Sandbox-based

No matter what kind of infrastructure, one of the most important goals is isolation. This can be achieved in different ways which we will be discussing in the next section.

Infrastructures

VM-based Platforms

VMs provide a large amount of isolation between instances without any noticeable performance penalty but it has a huge flaw which is the overhead of an OS!

FaaS platforms are event-based systems so it needs an extremely fast orchestrator. It's quite a challenge to design a VM-based orchestrator that's fast!

VM-based orchestrators are usually sluggish and don't perform well under stress and yet you just might be able to design a VM-based orchestrator suitable for FaaS platforms if you play your cards well :)

But the appealing level of isolation and performance in VMs is not something we can forget about. Here's where microVMs enter the game!

microVM is a lightweight and stripped-down version of a VM. The goal is to reduce the overhead associated with VMs.

Here are some links to get you started:

Container-based Platforms

Some platforms settle for containers to reduce their overhead. In Linux, containers use cgroups and namespaces to provide a "good enough" level of isolation between instances and the host. The small size of container instances and their native performance has turned this method into the most desirable way to provide infrastructure for FaaS.

But there's a catch. Containers are not sandboxed! They don't have the same level of isolation as in VMs or sandboxes. That's why we have been seeing some new projects which provide sandboxing for containers like gVisor.

Sandbox-based platforms

Sandboxes provide limited space for processes to play in like when you played in one when you were a kid. (Fun fact: we didn't have sandboxes in our country while growing up)

Processes that run in a sandbox can't interact with OS directly, instead, they rely on the interface that the sandbox runtime provides. This allows us to trace interface calls and prevent malicious processes to access the host.

Sandboxes are hard! It's not easy to design and implement a sandbox with decent performance but in the end, the result is worth it.

Some of the most noticeable sandbox implementation currently used in the FaaS world:

WebAssembly runtimes
V8 JavaScript engine
gVisor

FaaS Sandbox Implamantations

In this section, We review 2 FaaS implementations using sandboxes: V8 and WebAssembly.

WebAssembly

WebAssembly is a portable binary instruction format for virtual stack machines.

It aims to execute at native or near-native speed by assuming a few characteristics about the execution environment.

WebAssembly is designed to be executed in a fully sandboxed environment with linear memory. The binary is completely blind to the host environment by default because of that design. That being said, we can set up some kind of communication by reading memory or importing functions.

I've written about WebAssembly before. You can read about it before continuing:
WebAssembly, Wasmer And Embedding Wasmer in C program

WebAssembly is extremely appealing for FaaS since It's designed with sandboxing in mind, It's light and It has many compiler implementations including an LLVM backend which means you can compile any language that has an LLVM compiler to WebAssembly.

There are a few challenges though:

Running WASM modules is inherently a blocking operation. You should consider this and find a solution suitable for your environment If you plan to use WASM for long-running executions.
Memory is completely isolated. So input data should be copied into the WASM memory.
CPU limitation! You'll need a plan to limit CPU usages like timeouts or metering. There's no native support for that.

Even though these challenges may limit the use of WASM for some use cases but, in my opinion, It's still the best candidate for FaaS platforms.

There's currently one implementation in the wild that I know of. Fastly Serverless uses lucet to run WASM modules at the edge.

V8

Chrome V8 is a JavaScript engine by Google used in Google Chrome, Node.js and etc. In addition to JavaScript V8 is also able to run WASM modules too. V8 is a huge project and It's one of the best JavaScript engines you can find in terms of performance and security. Its development is also guaranteed by the fact is It's used in hundreds of millions of devices. (Java installation flashback :D)

Isolation in V8 is achieved by using Isolates. Isolates basically create an isolated environment for your codes to run in.

Implementing a FaaS platform using V8 is a complex task but the reward is an easy and fast entryway for end-users since They can use plain JavaScript and It just works.

Cloudflare Worker is the only user of V8 at the edge.

Commercial Products

Amazon Lambda: VM-based
Cloudflare Workers: Sandbox / V8-based
Fastly Serverless: Sandbox / WASM-based

There are many more like Google Cloud Functions, Fly.io, Stackpath EdgeEngine but I wasn't able to confirm what kind of infrastructure they use.

Future

It's hard to say what will happen in the future. Even though FaaS brings many advantages but migrating legacy and existing code may not be easy. In my mind its future is bright but in reality, it might be nothing more than a hype. But I'd say that even If this turned out to a terrible service, We can apply the good parts of FaaS to other services like serverless.

People don't like to manage their infrastructure and that's just a fact. They don't want to know what is a container, They don't want to know how to scale their service, They only want to worry about their code and I think that's fair. Current PaaS products don't have enough abstractions and the success of services like Vercel shows just that.

Conclusion

In this article, I tried to categorize different kinds of FaaS implementations and the technology used in them. I tried to make it short without many details because If I included the details, It had the potential to be a book! And as I said at the beginning, This has been an unfair post since I didn't cover all topics equally.

Thank you for your time.

Rate limiting using the Token Bucket algorithm

Amir Keshavarz — Thu, 17 Dec 2020 13:33:59 +0000

Rate Limiting

The term "rate-limiting" is known to almost everyone who has worked with web servers. I think It's one of those subjects that we often just use and don't think about it. But I think knowing how rate limiting works is useful If you have ever used it.

As you may know, "rate-limiting" is basically monitoring the incoming requests and making sure they don't violate a threshold. Basically, we define a rate of requests per time-unit and discard packets of a stream that is sending more packets than the one defined in our rate.

You probably noticed that I used the word "discard" when our threshold is reached. That's not always the case. In a lot of cases, we put the packets in a queue to keep the packets at a constant output rate. (And packets won't be discarded.)

What we'll be discussing doesn't require a queue and I dare say It's probably the simplest way to implement rate-limiting.

The most famous ways of implementing rate-limiting (Traffic Shaping) are:

Token Bucket
Leaky Bucket
(r, t) Traffic Shaping

The Leaky Bucket is somewhat similar to the Token Bucket but right now we don't care about the constant output rate and Token Bucket is the only algorithm we will talk about.

Token Bucket

The Token Bucket analogy is very simple. It's all about a bucket and tokens in it. Let's discuss it step by step.

Picture a bucket in your mind.
Fill the buckets with tokens at a constant rate.
When a packet arrives, check if there is any token in the bucket.
If there was any token left, remove one from the bucket and forward the packet. If the bucket was empty, simply drop the packet.

That's it. Wasn't it simple?

Implementation

Enough talking. Let's write a simple Token Bucket throttler in Python.

We start by defining a class with 4 arguments when It's being instantiated.

tokens: number of tokens added to the bucket in each time unit.
time_unit: the tokens are added in this time frame.
forward_callback: this function is called when the packet is being forwarded.
drop_callback: this function is called when the packet should be dropped.

We also prefill the bucket with the given tokens. This allows for a burst of packets when the throttler first starts working.

last_check is the timestamp that we previously handled a packet. For initialization, we set the time when we created the bucket.



import time


class TokenBucket:

    def __init__(self, tokens, time_unit, forward_callback, drop_callback):
        self.tokens = tokens
        self.time_unit = time_unit
        self.forward_callback = forward_callback
        self.drop_callback = drop_callback
        self.bucket = tokens
        self.last_check = time.time()

Then, we define handle() where the magic happens.



def handle(self, packet): #1
    current = time.time() #2
    time_passed = current - self.last_check #3
    self.last_check = current #4

    self.bucket = self.bucket + \
        time_passed * (self.tokens / self.time_unit) #5

    if (self.bucket > self.tokens): #6
        self.bucket = self.tokens

    if (self.bucket < 1): #7
        self.drop_callback(packet)
    else:
        self.bucket = self.bucket - 1 #8
        self.forward_callback(packet)

handle accepts only 1 parameter: the packet.
The current timestamp is put into current.
The time passed between now and the previous handle call is put into time_passed.
We update the last_check to the current timestamp.
This is the most important part. By multiplying the time_passed and our rate (which is tokens / time_unit) we find out how many token needs to be added to the bucket.
Reset the bucket if it has more tokens than the default value.
If the bucket doesn't have enough token, drop the packet.
Otherwise, remove one token and forward the packet.

That's all. This is the final working version:



import time


class TokenBucket:

    def __init__(self, tokens, time_unit, forward_callback, drop_callback):
        self.tokens = tokens
        self.time_unit = time_unit
        self.forward_callback = forward_callback
        self.drop_callback = drop_callback
        self.bucket = tokens
        self.last_check = time.time()

    def handle(self, packet):
        current = time.time()
        time_passed = current - self.last_check
        self.last_check = current

        self.bucket = self.bucket + \
            time_passed * (self.tokens / self.time_unit)

        if (self.bucket > self.tokens):
            self.bucket = self.tokens

        if (self.bucket < 1):
            self.drop_callback(packet)
        else:
            self.bucket = self.bucket - 1
            self.forward_callback(packet)


def forward(packet):
    print("Packet Forwarded: " + str(packet))


def drop(packet):
    print("Packet Dropped: " + str(packet))


throttle = TokenBucket(1, 1, forward, drop)

packet = 0

while True:
    time.sleep(0.2)
    throttle.handle(packet)
    packet += 1

You should be getting something like this:



Packet Forwarded: 0
Packet Dropped: 1
Packet Dropped: 2
Packet Dropped: 3
Packet Dropped: 4
Packet Forwarded: 5
Packet Dropped: 6
Packet Dropped: 7
Packet Dropped: 8
Packet Dropped: 9
Packet Forwarded: 10
Packet Dropped: 11
Packet Dropped: 12
Packet Dropped: 13
Packet Dropped: 14
Packet Forwarded: 15

As you can see in the code, our rate is 1 packet per second. We also send a packet every 0.2 seconds. When we first send a packet it quickly empties the bucket and it takes some time for the bucket to be filled again and that's why 4 packets are dropped between each successful forward.

Rate limiting and traffic policing, in general, is a very vast subject so If you liked what you just read, there are many materials available online about this subject that you can use to have a much deeper understanding of traffic policing.

Thank you for your time.

Absolute Beginner's Guide to BCC, XDP, and eBPF

Amir Keshavarz — Thu, 26 Nov 2020 10:52:03 +0000

Introduction

If you're reading this, chances are you have some idea of eBPF and XDP. In this article, we'll write an eBPF program that will count and categorize packets based on the destination port.

eBPF

Writing low-level tracing, monitoring, or network programs in Linux is not easy. Through all the layers of the kernel, people have been squeezing every bit of performance they could get.

And that's where eBPF comes in. eBPF is basically an extended and modern variation of BPF which is like a virtual machine inside the Linux kernel. It can execute user-defined programs inside a sandbox in the kernel.

These programs can be executed in various hook points but we will focus on XDP for now.

XDP

XDP provides a data path which we can intercept or even edit packets using an eBPF program. The execution can happen in 3 different places depending on your setup:

Offloaded - NIC: eBPF program can be offloaded to the network card itself, provided that the card supports XDP offloading.
Native - NIC Driver: eBPF will fallback to the driver if your card doesn't support offloading. The good news is that most drivers support this and performance is still impressive since this is all before entering the Linux network stack.
Generic - Linux Network Stack: This is the last option if the mentioned methods are not supported. Performance is not as good since the packet has entered the network stack.

The fate of packets is decided by action codes that your program returns:

XDP_PASS: let the packet continue through the network stack
XDP_DROP: silently drop the packet
XDP_ABORTED: drop the packet with trace point exception
XDP_TX: bounce the packet back to the same NIC it arrived on
XDP_REDIRECT: redirect the packet to another NIC or user space socket via the AF_XDP address family

BCC

BCC is a toolkit for creating eBPF programs with bindings to a few languages like Python, Lua and etc. BCC makes it pleasantly easy to write eBPF programs and their GitHub page is filled with examples to get you started.

We'll use BCC in Python to write our program.

eBPF Program in C

We start by writing the eBPF program itself before getting into the bcc stuff.

Entry Point

eBPF is event-driven so it'll call our exposed function when a packet arrives. Hence, we'll define a function that receives packet metadata and returns an XDP action code.

#define KBUILD_MODNAME "udp_counter"
#include <linux/bpf.h>
#include <linux/if_ether.h>
#include <linux/ip.h>
#include <linux/udp.h>

int udp_counter(struct xdp_md *ctx) {
    bpf_trace_printk("packet received\n");
    // MORE CODE HERE
}

UDP Packet Data

using the ctx we can extract everything we need about the arrived packet.

void *data = (void *)(long)ctx->data;
void *data_end = (void *)(long)ctx->data_end;
struct ethhdr *eth = data;

if ((void *)eth + sizeof(*eth) <= data_end) {

    struct iphdr *ip = data + sizeof(*eth);
    if ((void *)ip + sizeof(*ip) <= data_end) {

        if (ip->protocol == IPPROTO_UDP) {

            struct udphdr *udp = (void *)ip + sizeof(*ip);
            if ((void *)udp + sizeof(*udp) <= data_end) {
                // MORE CODE HERE
            }

        }

    }

}

As you can see, we go through the eth and IP packet to get to the UDP packet. Here, we can get the destination port that needs to be stored in a histogram. But what histogram!? In the next section, we learn about BPF maps.

BPF Maps

If you were wondering how will we be able to store our results, there is amazing news. BPF provides multiple useful data structures that we can use to store persisted data or even exchange data to and from userland.

Here is a list of some of the most noticeable data BPF data structures:

BPF_TABLE
BPF_HASH
BPF_ARRAY
BPF_HISTOGRAM
BPF_PERF_ARRAY

We'll use BPF_HISTOGRAM to count UDP packets based on their port.

Syntax:

BPF_HISTOGRAM(name [, key_type [, size ]])

Now we define the histogram outside of the udp_counter like this:

BPF_HISTOGRAM(counter, u64);

You'll need only one method to work with histograms: increment().

increment will increment the value based on the key that you provided.
Syntax:

map.increment(key[, increment_amount])

In the next section, we go back to the UDP packet and try to count them.

Counter

In the UDP Packet Data section, we extracted the UDP packet and left a place to count them.

Since we have a histogram ready, the only thing you need to do is to increment the value based on the port that you extract from the UDP packet.

u64 value = htons(udp->dest);
counter.increment(value);

The htons() function converts the unsigned short integer hostshort from host byte order to network byte order.

XDP Action Code

Now that we're done with the packet, we need to pass the packet so it can go through the network stack. We can just return XDP_PASS at the end of our function.

return XDP_PASS;

Final Code

#define KBUILD_MODNAME "udp_counter"
#include <linux/bpf.h>
#include <linux/if_ether.h>
#include <linux/ip.h>
#include <linux/udp.h>

BPF_HISTOGRAM(counter, u64);

int udp_counter(struct xdp_md *ctx)
{
    void *data = (void *)(long)ctx->data;
    void *data_end = (void *)(long)ctx->data_end;
    struct ethhdr *eth = data;

    if ((void *)eth + sizeof(*eth) <= data_end)
    {

        struct iphdr *ip = data + sizeof(*eth);
        if ((void *)ip + sizeof(*ip) <= data_end)
        {

            if (ip->protocol == IPPROTO_UDP)
            {

                struct udphdr *udp = (void *)ip + sizeof(*ip);
                if ((void *)udp + sizeof(*udp) <= data_end)
                {
                    u64 value = htons(udp->dest);
                    counter.increment(value);
                }
            }
        }
    }
    return XDP_PASS;
}

BCC Program

The only thing left to write is a simple bcc program to load our eBPF code and attach it to a device like loopback.

from bcc import BPF #1
from bcc.utils import printb

device = "lo" #2
b = BPF(src_file="udp_counter.c") #3
fn = b.load_func("udp_counter", BPF.XDP) #4
b.attach_xdp(device, fn, 0) #5

try:
    b.trace_print() #6
except KeyboardInterrupt: #7

    dist = b.get_table("counter") #8
    for k, v in sorted(dist.items()): #9
        print("DEST_PORT : %10d, COUNT : %10d" % (k.value, v.value)) #10

b.remove_xdp(device, 0) #11

As you can see, the program is fairly simple.

Steps explained:

Import the BPF python lib.
Specify which device you want your eBPF code to get attached to.
Create the BPF object and load the file.
Load the function.
Attach the function to the xdp hook of the device that was specified earlier.
Read the trace_pipe file so we can trace what's happening.
Catch the exit signal so we can exit gracefully.
Get the contents of the histogram.
Iterate over the content.
Print the results.
Deattach our code from the device.

Execution

Simple run the python code:

sudo python main.py

Wait for some data to be gathered. You can send out some packets using nc:

nc -u 127.0.0.1 5005

Send multiple packets to different ports and then exit from the python program. You should see something like this:

DEST_PORT : 5007, COUNT : 1
DEST_PORT : 5005, COUNT : 5
DEST_PORT : 5006, COUNT : 2

As you can see, the result shows how many packets were sent to these ports separately.

Conclusion

In this article, we learned about eBPF and XDP and why they matter so much. We also were able to write a program to count UDP packets based on their ports using the amazing BCC toolkit.

I really hope this article has been helpful. Thank you for your time.

DEV Community: Amir Keshavarz

AWS Summit Amsterdam 2025 – Key Takeaways & Reflections

AWS Summit Amsterdam 2025 – Key Takeaways & Reflections

AI

Talking Points

EU–US

Conclusion

Developing Custom Plugins for CoreDNS

Introduction To CoreDNS

Architecture Overview

Develop

Configuration

Setup

Handler

Logging

Final Example

Compile

Compile-time Configuration

Wrapping in External Source Code

Links

Extending Envoy with WebAssembly Proxy Filters

Introduction To Envoy

Envoy Filters

WebAssembly

Proxy-Wasm

Writing Filters

Conclusion

Links

Cache Replacement Algorithms: How To Efficiently Manage The Cache Storage

Caching

Cache Replacement Algorithms

LRU

LFU

FIFO

Random Replacement (RR)

The Problem of One-hit Wonders

Conclusion

Links

A Closer Look Into The World of Database Replication

Logs

Types

Synchronous

Asynchronous

Consistency

Strong Consistency

Weak Consistency

Eventual Consistency

Sync Replication

Raft

Real-world

Asynchronous replication

Ordered Log Replication

Real-world

Conclusion

Links

Rate limiting using the Sliding Window algorithm

Sliding Window

Implementation

Final Code

Conclusion

CPU Time: How To Accurately Benchmark Your Code

Misconceptions

Time matters

Slow software = Slow code

Performance is not important

Schedulers

Preemptive Multitasking

Cooperative Multitasking

CPU Time

Code

clock()

clock_getcpuclockid()

pthread_getcpuclockid()

clock_gettime()

Conclusion

Links

Rate limiting using the Fixed Window algorithm

Fixed Window

Implementation

Rate Limiting in IPv6 Era Using Probabilistic Data Structures

`clock()`

`clock_getcpuclockid()`

`pthread_getcpuclockid()`

`clock_gettime()`