Modern computing systems are highly concurrent. Threads run concurrently in shared-memorymulti-core systems, and programs run in different servers communicating by sending messages to eachother. Concurrent programming is hard because it requires to cope with many possible, unpredictablebehaviors of the processes, and the communication media. The article argues that right from the startin 1960’s, the main way of dealing with concurrency has been by reduction to sequential reasoning. Ittraces this history, and illustrates it through several examples, from early ideas based on mutual exclu-sion (which was initially introduced to access shared physical resources), passing through consensus andconcurrent objects (which are immaterial data), until today distributed ledgers. A discussion is also pre-sented, which addresses the limits that this approach encounters, related to fault-tolerance, performance,and inherently concurrent problems

In this article, we focus on latencies rather than throughput. We first document the fact that LSM KVs exhibit high tail latencies. The techniques that have been proposed for optimizing throughput do not address this issue, and, in fact, in some cases, exacerbate it. The root cause of these high tail latencies is interference between client writes, flushes, and compactions. Another major cause for tail latency is the heterogeneous nature of the workloads in terms of operation mix and item sizes whereby a few more computationally heavy requests slow down the vast majority of smaller requests. We introduce the notion of an Input/Output (I/O) bandwidth scheduler for an LSM-based KV store to reduce tail latency caused by interference of flushing and compactions and by workload heterogeneity. We explore three techniques as part of this I/O scheduler: (1) opportunistically allocating more bandwidth to internal operations during periods of low load, (2) prioritizing flushes and compactions at the lower levels of the tree, and (3) separating client requests by size and by data access path. SILK+ is a new open-source LSM KV that incorporates this notion of an I/O scheduler.

The authors proposed four desirable properties in transaction processing systems forachieving low-latency ofreadtransactions, with asynchronous and reliable communications, andreferred to them collectively as theSNOW properties: The underlying properties, in the contextof an execution, are (i)strict serializability(S) property where read andwritetransactions seemto occur atomically; (ii)non-blocking(N) property implies that for every read operation on anyobject, during areadtransaction, the response at the corresponding server is non-blocking; (iii)one version and one round(O) property implies every read operation, during a read transaction,completes inone-roundof client-server communication and the respective server responds withonly one version of the object value; and (iv)concurrentwritetransactions(W) property statesthatreadtransactions can have concurrentwritetransactions. Then they argued that it isimpossible to implement all the four properties, in the same system, even with at least threeclients. They referred to their result as theSNOWtheorem, and they posed the two-clientsetting as an open question.

The exponential growth of digital information is imposing increasing scale and efficiency demands on mod-ern storage infrastructures. As infrastructure complexity increases, so does the difficulty in ensuring qualityof service, maintainability, and resource fairness, raising unprecedented performance, scalability, and pro-grammability challenges. Software-Defined Storage (SDS) addresses these challenges by cleanly disentanglingcontrol and data flows, easing management, and improving control functionality of conventional storage sys-tems. Despite its momentum in the research community, many aspects of the paradigm are still unclear, un-defined, and unexplored, leading to misunderstandings that hamper the research and development of novelSDS technologies. In this article, we present an in-depth study of SDS systems, providing a thorough descrip-tion and categorization of each plane of functionality. Further, we propose a taxonomy and classification ofexisting SDS solutions according to different criteria. Finally, we provide key insights about the paradigm anddiscuss potential future research directions for the field.

This guide walks through creating PlantUML diagrams

In today's enterprise storage systems, supported data services such as snapshot delete or drive rebuild can cause tremendous performance interference if executed inline along with heavy foreground IO, often leading to missing SLOs (Service Level Objectives). Typical storage system applications such as web or VDI (Virtual Desktop Infrastructure) follow a repetitive high/low workload pattern that can be learned and forecasted. We propose a priority-based background scheduler that learns this repetitive pattern and allows storage systems to maintain peak performance and in turn meet service level objectives (SLOs) while supporting a number of data services. When foreground IO demand intensifies, system resources are dedicated to service foreground IO requests and any background processing that can be deferred are recorded to be processed in future idle cycles as long as forecast shows that storage pool has remaining capacity. The smart background scheduler adopts a resource partitioning model that allows both foreground and background IO to execute together as long as foreground IOs are not impacted where the scheduler harness any free cycle to clear background debt. Using traces from VDI application, we show how our technique surpasses a method that statically limit the deferred background debt and improve SLO violations from 54.6% when using a fixed background debt watermark to merely a 6.2% if dynamically set by our smart background scheduler.

Cloud providers offer a variety of execution platforms in form of bare-metal, VM, and containers. However, due to the pros and cons of each execution platform, choosing the appropriate platform for a specific cloud-based application has become a challenge for solution architects. The possibility to combine these platforms (e.g. deploying containers within VMs) offers new capacities that makes the challenge even further complicated. However, there is a little study in the literature on the pros and cons of deploying different application types on various execution platforms. In particular, evaluation of diverse hardware configurations and different CPU provisioning methods, such as CPU pinning, have not been sufficiently studied in the literature. In this work, the performance overhead of container, VM, and bare-metal execution platforms are measured and analyzed for four categories of real-world applications, namely video processing, parallel processing (MPI), web processing, and No-SQL, respectively representing CPU intensive, parallel processing, and two IO intensive processes. Our analyses reveal a set of interesting and sometimes counterintuitive findings that can be used as best practices by the solution architects to efficiently deploy cloud-based applications. Here are some notable mentions: (A) Under specific circumstances, containers can impose a higher overhead than VMs; (B) Containers on top of VMs can mitigate the overhead of VMs for certain applications; (C) Containers with a large number of cores impose a lower overhead than those with a few cores

The efficient implementation of function calls and non-local control transfers is a critical part of modern language implementations and is important in the implementation of everything from recursion, higher-order functions, concurrency and coroutines, to task-based parallelism. In a compiler, these features can be supported by a variety of mechanisms, including call stacks, segmented stacks, and heap-allocated continuation closures. An implementor of a high-level language with advanced control features might ask the question "what is the best choice for my implementation?" Unfortunately, the current literature does not provide much guidance, since previous studies suffer from various flaws in methodology and are outdated for modern hardware. In the absence of recent, well-normalized measurements and a holistic overview of their implementation specifics, the path of least resistance when choosing a strategy is to trust folklore, but the folklore is also suspect. This paper attempts to remedy this situation by providing an "apples-to-apples" comparison of six different approaches to implementing call stacks and continuations. This comparison uses the same source language, compiler pipeline, LLVM-backend, and runtime system, with the only differences being those required by the differences in implementation strategy. We compare the implementation challenges of the different approaches, their sequential performance, and their suitability to support advanced control mechanisms, including supporting heavily threaded code. In addition to the comparison of implementation strategies, the paper's contributions also include a number of useful implementation techniques that we discovered along the way.

Smoltcp is a standalone, event-driven TCP/IP stack that is designed for bare-metal, real-time systems. Its design goals are simplicity and robustness. Its design anti-goals include complicated compile-time computations, such as macro or type tricks, even at cost of performance degradation

The libpoireau library intercepts a small fraction of calls to malloc/calloc/etc., to generate a statistically representative overview of an application's heap footprint

In this paper, we set out the goal to revisit the results of “Starringinto the Abyss [...] of Concurrency Control with [1000] Cores” [27]and analyse in-memory DBMSs on today’s large hardware. Despitethe original assumption of the authors, today we do not see single-socket CPUs with 1000 cores. Instead multi-socket hardware madeits way into production data centres. Hence, we follow up on thisprior work with an evaluation of the characteristics of concurrencycontrol schemes on real production multi-socket hardware with1568 cores. To our surprise, we made several interesting findingswhich we report on in this paper.

Hash tables are an essential data-structure for numerous networking applications (e.g., connection tracking, firewalls, network address translators). Among these, cuckoo hash tables provide excellent performance by allowing lookups to be processed with very few memory accesses (2 to 3 per lookup). Yet, for large tables, cuckoo hash tables remain memory bound and each memory access impacts performance. In this paper, we propose algorithmic improvements to cuckoo hash tables allowing to eliminate some unnecessary memory accesses; these changes are conducted without altering the properties of the original cuckoo hash table so that all existing theoretical analysis remain applicable. On a single core, our hash table achieves 37M lookups per second for positive lookups (i.e., when the key looked up is present in the table), and 60M lookups per second for negative lookups, a 50% improvement over the implementation included into the DPDK. On a 18-core, with mostly positive lookups, our implementation achieves 496M lookups per second, a 45% improvement over DPDK.

The fundamental challenges that every researcher, systems architect, or developer faces when designing a new access method are how to minimize, i) read times (R), ii) update cost (U), and iii) memory (or storage) overhead (M). In this project we first conjecture that when optimizing the read-update-memory overheads, optimizing in any two areas negatively impacts the third.

A collection of tools for developers who have little to no artistic talent.

Htmx allows you to access AJAX, WebSockets and Server Sent Events directly in HTML, using attributes, so you can build modern user interfaces with the simplicity and power of hypertext

DuckDB is an embedded database designed to execute analytical SQL queries fast while embedded in another process

C library for accessing the PostgreSQL parser outside of the server. This library uses the actual PostgreSQL server source to parse SQL queries and return the internal PostgreSQL parse tree.

"Distroless" images contain only your application and its runtime dependencies. They do not contain package managers, shells or any other programs you would expect to find in a standard Linux distribution.

For decades, applications deployed on a world-wide scale have been forced to give up at least one of (1) strict serializability (2) low latency writes (3) high transactional throughput. In this paper we discuss SLOG: a system that avoids this tradeoff for workloads which contain physical region locality in data access. SLOG achieves high-throughput, strictly serializable ACID transactions at geo-replicated distance and scale for all transactions submitted across the world, all the while achieving low latency for transactions that initiate from a location close to the home region for data they access. Experiments find that SLOG can reduce latency by more than an order of magnitude relative to state-of-the-art strictly serializable geo-replicated database systems such as Spanner and Calvin, while maintaining high throughput under contention.

The shared log paradigm is at the heart of modern distributed applications in the growing cloud computing industry. Often, application logs must be stored durably for analytics, regulations, or failure recovery, and their smooth operation depends closely on how the log is implemented. Scalog is a new implementation of the shared log abstraction that offers an unprecedented combination of features for continuous smooth delivery of service: Scalog allows applications to customize data placement, supports reconfiguration with no loss in availability, and recovers quickly from failures. At the same time, Scalog provides high throughput and total order.

Llvm-mca is a performance analysis tool that uses information available in LLVM (e.g. scheduling models) to statically measure the performance of machine code in a specific CPU. Performance is measured in terms of throughput as well as processor resource consumption. The tool currently works for processors with an out-of-order backend, for which there is a scheduling model available in LLVM.

An error kernel is the part of an application or system that should never fail. This is ideally as small as possible since the less surface area that it has, the less likely catastrophic failures will happen. When they do happen, the core system is small enough to reason about which greatly helps with triage and cauterizing of wounds.

C++ reactors, coros, datastructures, etc

Today I want to criticize the whole logging culture and provide a bunch of alternatives.

This is a collection of lectures and labs Linux kernel topics. The lectures focus on theoretical and Linux kernel exploration. The labs focus on device drivers topics and they resemble “howto” style documentation

MeiliSearch is a RESTful search API. It aims to be a ready-to-go solution for everyone who wants a fast and relevant search experience for their end-users

In this document, the internals of PostgreSQL for database administrators and system developers are described.

Quicly is a QUIC implementation, written from the ground up to be used within the H2O HTTP server.

Quiche is an implementation of the QUIC transport protocol and HTTP/3 as specified by the IETF. It provides a low level API for processing QUIC packets and handling connection state. The application is responsible for providing I/O (e.g. sockets handling) as well as an event loop with support for timers.

Random replication is widely used in data center storage systems to prevent data loss. However, random replication is almost guaranteed to lose data in the common scenario of simultaneous node failures due to cluster-wide power outages. Due to the high fixed cost of each incident of data loss, many data center operators prefer to minimize the frequency of such events at the expense of losing more data in each event. We present Copyset Replication, a novel general-purpose replication technique that significantly reduces the frequency of data loss events

This article discusses a new replica placement technique that reduces the probability of data loss.

I am a strong believer that Bourne-derived languages are extremely bad, on the same order of badness as Perl, for programming, and consider programming sh for any purpose other than as a super-portable, lowest-common-denominator platform for build or bootstrap scripts and the like, as an extremely misguided endeavor.

Lightweight, fault-tolerant message streams

Library for Restartable Sequences.

Data-oriented design is inspired by high-performance computing techniques, database design, and functional programming values. It provides a practical methodology that reduces complexity while improving performance of both your development team and your product. Understand the goal, understand the data, understand the hardware, develop the solution

Tracking, Benchmarking and Sharing Information about an open source embedded data storage engines, internals, architectures, data storage and transaction processing.

MsQuic is a Microsoft implementation of the IETF QUIC protocol. It is cross platform, written in C and designed to be a general purpose QUIC library

NPF is a layer 3 packet filter, supporting stateful packet inspection, IPv6, NAT, IP sets, extensions and many more. It uses BPF as its core engine and it was designed with a focus on high performance, scalability, multi-threading and modularity. NPF was written from scratch in 2009. It is written in C99 and distributed under the 2-clause BSD license. NPF is provided as a userspace library to be used in a bespoke application to process packets. It can run on Linux, typically, in combination with such frameworks like Data Plane Development Kit (DPDK) or netmap.

This informational document is an attempt to make the case for implementing network protocols without performing I/O, and to provide concrete assistance and instructions for doing so in Python

A small and efficient runtime for WebAssembly & WASI

WAVM is a WebAssembly virtual machine, designed for use in non-web applications.

Lucet is a native WebAssembly compiler and runtime. It is designed to safely execute untrusted WebAssembly programs inside your application

Krustlet acts as a Kubelet by listening on the event stream for new pods that the scheduler assigns to it based on specific Kubernetes tolerations. The default implementation of Krustlet listens for the architecture wasm32-wasi and schedules those workloads to run in a wasmtime-based runtime instead of a container runtime

I’m writing the book in Markdown, then use Pandoc to convert it to PDF and EPUB.

Setting up a new C++ project usually requires a significant amount of preparation and boilerplate code, even more so for modern C++ projects with tests, executables and contiguous integration. This template is the result of learnings from many previous projects and should help reduce the work required to setup up a modern C++ project.

Pg_auto_failover is an extension and service for PostgreSQL that monitors and manages automated failover for a Postgres cluster. It is optimized for simplicity and correctness and supports Postgres 10 and newer

The notion of consistency is used across different computer science disciplines from distributed systems to database systems to computer architecture. It turns out that consistency can mean quite different things across these disciplines, depending on who uses it and in what context it appears. We identify two broad types of consistency, state consistency and operation consistency, which differ fundamentally in meaning and scope. We explain how these types map to the many examples

This is a list of resources related to LD_PRELOAD, a mechanism for changing application behavior at run-time. Libraries can override specified functions with another, for example, making time(3) always return 0. This is often useful for testing or modifying application behavior without source code changes.

Distributed consensus is a fundamental primitive for constructing fault-tolerant, strongly-consistent distributed systems. Though many distributed consensus algorithms have been proposed, just two dominate production systems: Paxos, the traditional, famously subtle, algorithm; and Raft, a more recent algorithm positioned as a more understandable alternative to Paxos. In this paper, we consider the question of which algorithm, Paxos or Raft, is the better solution to distributed consensus? We analyse both to determine exactly how they differ by describing a simplified Paxos algorithm using Raft's terminology and pragmatic abstractions. We find that both Paxos and Raft take a very similar approach to distributed consensus, differing only in their approach to leader election. Most notably, Raft only allows servers with up-to-date logs to become leaders, whereas Paxos allows any server to be leader provided it then updates its log to ensure it is up-to-date. Raft's approach is surprisingly efficient given its simplicity as, unlike Paxos, it does not require log entries to be exchanged during leader election. We surmise that much of the understandability of Raft comes from the paper's clear presentation rather than being fundamental to the underlying algorithm being presented.

It is a reliable replication protocol inspired by the multiprocessor's cache-coherence protocols. Hermes combines a broadcast-based, invalidating design with logical timestamps and the idea of early value propagation to achieve the following desired properties for reliable datastores.

KCP is a fast and reliable protocol that can achieve the transmission effect of a reduction of the average latency by 30% to 40% and reduction of the maximum delay by a factor of three, at the cost of 10% to 20% more bandwidth wasted than TCP. It is implemented by using the pure algorithm, and is not responsible for the sending and receiving of the underlying protocol (such as UDP), requiring the users to define their own transmission mode for the underlying data packet, and provide it to KCP in the way of callback. Even the clock needs to be passed in from the outside, without any internal system calls.

SSH is a powerful tool which often grants a lot of access to anyone using it to log into a server. In this post, I’m going to talk about a few different ways that you can easily improve the security of your SSH model without needing to deploy a new application or make any huge changes to user experience.

Nested Intervals generalize Nested Sets. They are immune to hierarchy reorganization problem. They allow answering ancestor path hierarchical queries algorithmically - without accessing the stored hierarchy relation.

Io_uring is a clever new, high-performance interface for asynchronous I/O for Linux without the drawbacks of the aio set of APIs. In this 3-part article series, we look at how to use io_uring to get the most common programming tasks done under Linux

People often ask us for an overview of how Tailscale works. We’ve been putting off answering that, because we kept changing it! But now things have started to settle down. Let’s go through the entire Tailscale system from bottom to top, the same way we built it (but skipping some zigzags we took along the way).

And one of the most difficult and subtle topics in all of networking

Draw AWS, Azure, GCP, Kubernetes diagrams

He C++ programming language offers a strong exception mechanism for error handling at the language level, improving code readability, safety, and maintainability. However, current C++ implementations are targeted at general-purpose systems, often sacrificing code size, memory usage, and resource determinism for the sake of performance. This makes C++ exceptions a particularly undesirable choice for embedded applications where code size and resource determinism are often paramount. Consequently, embedded coding guidelines either forbid the use of C++ exceptions, or embedded C++ tool chains omit exception handling altogether. In this paper, we develop a novel implementation of C++ exceptions that eliminates these issues, and enables their use for embedded systems. We combine existing stack unwinding techniques with a new approach to memory management and run-time type information (RTTI). In doing so we create a compliant C++ exception handling implementation, providing bounded runtime and memory usage, while reducing code size requirements by up to 82%, and incurring only a minimal runtime overhead for the common case of no exceptions.

Serverless containers and functions are widely used for deploying and managing software in the cloud. Their popularity is due to reduced cost of operations, improved utilization of hardware, and faster scaling than traditional deployment methods. The economics and scale of serverless applications demand that workloads from multiple customers run on the same hardware with minimal overhead, while preserving strong security and performance isolation. The traditional view is that there is a choice between virtualization with strong security and high overhead, and container technologies with weaker security and minimal overhead. This tradeoff is unacceptable to public infrastructure providers, who need both strong security and minimal overhead. To meet this need, we developed Fire-cracker, a new open source Virtual Machine Monitor (VMM)specialized for serverless workloads, but generally useful for containers, functions and other compute workloads within a reasonable set of constraints. We have deployed Firecracker in two publically available serverless compute services at Amazon Web Services (Lambda and Fargate), where it supports millions of production workloads, and trillions of requests per month. We describe how specializing for serverless in-formed the design of Firecracker, and what we learned from seamlessly migrating Lambda customers to Firecracker.

Debezium is an open source distributed platform for change data capture. Start it up, point it at your databases, and your apps can start responding to all of the inserts, updates, and deletes that other apps commit to your databases. Debezium is durable and fast, so your apps can respond quickly and never miss an event, even when things go wrong.

The circllhist histogram is a fast and memory efficient data structure for summarizing large numbers of latency measurements. It is particularly suited for applications in IT infrastructure monitoring, and provides nano-second data insertion, full mergeability, accurate approximation of quantiles with a-priori bounds on the relative error. Open-source implementations are available for C/lua/python/Go/Java/JavaScript.

Recutils is a collection of tools, like recins, recdel, and recsel used to manage these recfiles/databases. They allow for all the normal basic relational database operations, typing, auto-incrementing, and even field-level crypto. All of this power is yours with the bonus that your database is a human-readable text file that you can grep/awk/sed freely, and a line-oriented structure makes it perfect for version control systems.

Function-as-a-Service (FaaS) platforms and "serverless" cloud computing are becoming increasingly popular. Current FaaS offerings are targeted at stateless functions that do minimal I/O and communication. We argue that the benefits of serverless computing can be extended to a broader range of applications and algorithms. We present the design and implementation of Cloudburst, a stateful FaaS platform that provides familiar Python programming with low-latency mutable state and communication, while maintaining the autoscaling benefits of serverless computing. Cloudburst accomplishes this by leveraging Anna, an autoscaling key-value store, for state sharing and overlay routing combined with mutable caches co-located with function executors for data locality. Performant cache consistency emerges as a key challenge in this architecture. To this end, Cloudburst provides a combination of lattice-encapsulated state and new definitions and protocols for distributed session consistency. Empirical results on benchmarks and diverse applications show that Cloudburst makes stateful functions practical, reducing the state-management overheads of current FaaS platforms by orders of magnitude while also improving the state of the art in serverless consistency

Bloom filters (BF) are widely used for approximate membership queries over a set of elements. BF variants allow removals, sets of unbounded size or querying a sliding window over an unbounded stream. However, for this last case the best current approaches are dictionary based (e.g., based on Cuckoo Filters or TinyTable), and it may seem that BF-based approaches will never be competitive to dictionary-based ones. In this paper we present Age-Partitioned Bloom Filters, a BF-based approach for duplicate detection in sliding windows that not only is competitive in time-complexity, but has better space usage than current dictionary-based approaches (e.g., SWAMP), at the cost of some moderate slack. APBFs retain the BF simplicity, unlike dictionary-based approaches, important for hardware-based implementations, and can integrate known improvements such as double hashing or blocking. We present an Age-Partitioned Blocked Bloom Filter variant which can operate with 2-3 cache-line accesses per insertion and around 2-4 per query, even for high accuracy filters.

We are open-sourcing Rezolus, our high-resolution systems performance telemetry agent. Rezolus began in an effort to help uncover performance anomalies and utilization spikes that were too brief to be captured through our normal observability and metrics systems. It has proven to be useful to help us quantify workload characteristics, provide data to drive optimization efforts, and has been used to diagnose runtime performance issues

In this blog post, we will walk through a new client-side load balancing technique we’ve developed and deployed widely at Twitter which has allowed our microservice architecture to efficiently scale clusters to thousands of instances. We call this new technique deterministic aperture

This paper discusses the ways in which automation of industrial processes may expand rather than eliminate problems with the human operator.

While a lot of work has gone into optimizing TCP implementations as much as possible over the years, including building offloading capabilities in both software (like in operating systems) and hardware (like in network interfaces), UDP hasn't received quite as much attention as TCP, which puts QUIC at a disadvantage. In this post we'll look at a few tricks that help mitigate this disadvantage for UDP, and by association QUIC.

Faker is a Python package that generates fake data for you. Whether you need to bootstrap your database, create good-looking XML documents, fill-in your persistence to stress test it, or anonymize data taken from a production service, Faker is for you.

Resilience engineering papers. Contribute to lorin/resilience-engineering development by creating an account on GitHub.