Compressed Log Processor (CLP) is a tool capable of losslessly compressing text logs and searching the compressed logs without decompression. To learn more about it, you can read our paper.

Learn how to segregate operations that read data from those that update data, using the CQRS (Command and Query Responsibility Segregation) pattern.

This book grew out of our own involvement in developing congestion control algorithms over the last three decades. There have been so many developments in congestion control over that time that it’s nearly impossible to include all of them. What we have tried to do in this book is provide a framework for understanding congestion control as a systems problem, and to characterize the many approaches along a few main themes. For example, our work on TCP Vegas opened up a line of research that continues today, where the aim is to avoid severe congestion rather than react after it has set in. We thus consider avoidance-based approaches as one of the main categories of congestion control.

Ordering guarantees are often defined using abstract execution models [2, 8-11, 19, 22]. Unfortunately, these models are complex and make different assumptions about system semantics. As a result, researchers find it impossible to compare the ordering guarantees of coherence, consistency and isolation. This paper presents a simple, unified model for defining ordering guarantees that is sufficiently general to model a wide range of systems, including processor memory, distributed storage, and databases. We define a new single constraint relationship, result visibility, which formalizes the "appears to execute before" relationship between operations. Using only result visibility, we define more than 20 ordering guarantees from different research areas, including PRAM [17], snapshot isolation [6] and eventual consistency session guarantees [21]. To our knowledge, these definitions form the broadest survey of ordering guarantees using a single constraint in the current literature.

I go through a (near complete?) selection of research papers and approaches therein that solve distributed consensus with strong consistency as provided by the Paxos family of algorithms. Multi-part blog post alert

Fibers (sometimes called stackful coroutines or user mode cooperatively scheduled threads) and stackless coroutines (compiler synthesized state machines) represent two distinct programming facilities with vast performance and functionality differences. This paper highlights efficiency, scalability and usability problems of fibers and reaches the conclusion that they are not an appropriate solution for writing scalable concurrent software

It can be very frustrating when Go applications use less memory than what is available to them, and yet they still manage to run out of memory and crash. Go 1.19 introduced GOMEMLIMIT, which completely changes how you can manage memory limits in Go.

We present data-parallel actors (DPA), a programming model for building distributed query serving systems. Query serving systems are an important class of applications characterized by low-latency data-parallel queries and frequent bulk data updates; they include data analytics systems like Apache Druid, full-text search engines like ElasticSearch, and time series databases like InfluxDB. They are challenging to build because they run at scale and need complex distributed functionality like data replication, fault tolerance, and update consistency. DPA makes building these systems easier by allowing developers to construct them from purely single-node components while automatically providing these critical properties. In DPA, we view a query serving system as a collection of stateful actors, each encapsulating a partition of data. DPA provides parallel operators that enable consistent, atomic, and fault-tolerant parallel updates and queries over data stored in actors. We have used DPA to build a new query serving system, a simplified data warehouse based on the single-node database MonetDB, and enhance existing ones, such as Druid, Solr, and MongoDB, adding missing user-requested features such as load balancing and elasticity. We show that DPA can distribute a system in <1K lines of code (>10× less than typical implementations in current systems) while achieving state-of-the-art performance and adding rich functionality.

@colmmacc: A quick rage-thread about credentials. When security auditors just say things like "Critical credentials need to be rotated every 90 days" you need to fire them into the sun with urgency. Here's what you ...…

In this paper, we re-examine how Paxos approaches the problem of consensus. We look again at quorum intersection in Flexible Paxos and observe that quorum intersection can be safely weakened further. Most notably, we observe that if a proposer learns that a value was proposed in some previous round then its phase one no longer needs to intersect with the phase two quorums from that round or from any previous rounds. Furthermore, in order to provide an intuitive explanation of our results, we propose a novel abstraction for reasoning about Paxos which utilizes write-once registers.

Safe memory reclamation (SMR) schemes are an essential tool for lock-free data structures and concurrent programming. However, manual SMR schemes are notoriously difficult to apply correctly, and automatic schemes, such as reference counting, have been argued for over a decade to be too slow for practical purposes. A recent wave of work has disproved this long-held notion and shown that reference counting can be as scalable as hazard pointers, one of the most common manual techniques. Despite these tremendous improvements, there remains a gap of up to 2x or more in performance between these schemes and faster manual techniques such as epoch-based reclamation (EBR). In this work, we first advance these ideas and show that in many cases, automatic reference counting can in fact be as fast as the fastest manual SMR techniques. We generalize our previous Concurrent Deferred Reference Counting (CDRC) algorithm to obtain a method for converting any standard manual SMR technique into an automatic reference counting technique with a similar performance profile. Our second contribution is extending this framework to support weak pointers, which are reference-counted pointers that automatically break pointer cycles by not contributing to the reference count, thus addressing a common weakness in reference-counted garbage collection.

Consus introduces a leaderless-consensus-based commit protocol that completes in three one way message delays in the wide area.

WebAssembly (Wasm) is a compact, well-specified bytecode format that offers a portable compilation target with near-native execution speed. The bytecode format was specifically designed to be fast to parse, validate, and compile, positioning itself as a portable alternative to native code. It was pointedly not designed to be interpreted directly. Instead, design considerations at the time focused on competing with native code, utilizing optimizing compilers as the primary execution tier. Yet, in JIT scenarios, compilation time and memory consumption critically impact application startup, leading many Wasm engines to later deploy baseline (single-pass) compilers. Though faster, baseline compilers still take time and waste code space for infrequently executed code. A typical interpreter being infeasible, some engines resort to compiling Wasm not to machine code, but to a more compact, but easy to interpret format. This still takes time and wastes memory. Instead, we introduce in this article a fast in-place interpreter for WebAssembly, where no rewrite and no separate format is necessary. Our evaluation shows that in-place interpretation of Wasm code is space-efficient and fast, achieving performance on-par with interpreting a custom-designed internal format. This fills a hole in the execution tier space for Wasm, allowing for even faster startup and lower memory footprint than previous engine configurations.

Typical can be compared to Protocol Buffers and Apache Thrift. The main difference is that Typical has a more modern type system based on algebraic data types, emphasizing a safer programming style with non-nullable types and exhaustive pattern matching

We recently rolled out a small change that reduced the CPU utilization of our API frontend servers at Twitch by ~30% and reduced overall 99th percentile API latency during peak load by ~45%.

Datacenters suffer from resource utilization inefficiencies due to the conflicting goals of service owners and platform providers. Service owners intending to maintain Service Level Objectives (SLO) for themselves typically request a conservative amount of resources. Platform providers want to increase operational efficiency to reduce capital and operating costs. Achieving both operational efficiency and SLO for individual services at the same time is challenging due to the diversity in service workload characteristics, resource usage patterns that are dependent on input load, heterogeneity in platform, memory, I/O, and network architecture, and resource bundling. This paper presents a tunable approach to resource allocation that accounts for both dynamic service resource needs and platform heterogeneity

I have written a proof-of-concept histogram data structure called hg64 [...]. It can load 1 million data items in about 5ms (5ns per item), and uses a few KiB of memory.

CheckSync provides applications with high availability via runtime-integrated checkpointing. This allows CheckSync to take checkpoints of a process running in a memory-managed language (Go, for now), which can be resumed on another machine after a failure. CheckSync uses the runtime to checkpoint only the process' live memory, doing without requiring significant changes to applications. CheckSync maintains the ease of use provided by virtual machines for the applications it supports without requiring that an entire virtual machine image be snapshotted. Because CheckSync captures only the memory used by an application, it produces checkpoints that are smaller (by an order of magnitude) than virtual machine snapshots if the memory footprint of the application is relatively small compared to the state of the rest of the operating system. Additionally, when running go-cache, a popular in-memory key/value store, CheckSync reduces throughput by only 12% compared to the 78% throughput loss when using go-cache's snapshot functionality, the 45% loss when using CRIU, and the 68% loss when using virtual machine live migration.

This paper from Sigmod 2015 describes the addition of Multi-Version Concurrency Control (MVCC) to the Hyper database, and discusses at length how they implement serializability efficiently with little overhead compared to snapshot isolation

In this paper, we present the design space of LSM-compactions, and evaluate state-of-the-art compaction strategies with respect to key performance metrics. Toward this goal, our first contribution is to introduce a set of four design primitives that can formally define any compaction strategy: (i) the compaction trigger, (ii) the data layout, (iii) the compaction granularity, and (iv) the data movement policy. Together, these primitives can synthesize both existing and completely new compaction strategies.

The development of programming languages can be quite complicated and costly. Hence, much effort has been devoted to the modular definition of language features that can be reused in various combinations to define new languages and experiment with their semantics. A notable outcome of these efforts is the algebra-based "datatypes a la carte" (DTC) approach. When combined with algebraic effects, DTC can model a wide range of common language features. Unfortunately, the current state of the art does not cover modular definitions of advanced control-flow mechanisms that defer execution to an appropriate point, such as call-by-name and call-by-need evaluation, as well as (multi-)staging. This paper defines latent effects, a generic class of such control-flow mechanisms. We demonstrate how function abstractions, lazy computations and a MetaML-like staging can all be expressed in a modular fashion using latent effects, and how they can be combined in various ways to obtain complex semantics. We provide a full Haskell implementation of our effects and handlers with a range of examples.

A special build of curl that can impersonate the four major browsers: Chrome, Edge, Safari & Firefox. curl-impersonate is able to perform TLS and HTTP handshakes that are identical to that of a real browser.

After I recently ordered a new laptop, I have been looking for a USB-C-connected dock to be used with my new laptop. This turned out to be quite complex, given there are really a lot of different bits of technology that can be involved, with various (continuously changing, yes I'm looking at you, USB!) marketing names to further confuse things.

This blog post compares the advantages and disadvantages of docker containers with VMs and describes why and how we execute docker images inside a QEMU MicroVM. The described approach makes it possible to combine the security of VMs with the existing ecosystem of docker (e.g. images and tools). Afterwards we take a look at ways how we can map features like bind mounts to solutions supported by QEMU and demonstrate this by running the NGINX docker image in QEMU.

This is where MiraclePtr comes in. It is a technology to prevent exploitation of use-after-free bugs

P is a state machine based programming language for modeling and specifying complex distributed systems. P allows programmers to model their system as a collection of communicating state machines. P supports several backend analysis engines (based on automated reasoning techniques like model checking and symbolic execution) to check that the distributed system modeled in P satisfies the desired correctness specifications. Not only can a P program be systematically tested (e.g., with model checking), but it can also be compiled into executable code. Essentially, P unifies modeling, specifying, implementing, and testing into one activity for the programmer.

Multi-Party Relays (MPR) provide privacy in the architecture itself. MPRs are the better, practical alternatives to VPNs. Only now, in 2022, are there fast MPR services that cover all mobile users: INVISV Relay (Android) and Apple’s iCloud Private Relay (iOS).

Stateroom is a minimalist framework for building lightweight, single-threaded services that send and receive messages through WebSockets. Services can either be native Rust code that runs in the server process, or be compiled into WebAssembly modules and loaded dynamically.

WasmBox turns running Rust code into a serializable data structure. It does this by compiling it to WebAssembly and running it in a sandbox. To snapshot the running code, it serializes the sandbox's linear memory, which contains the entire heap of the program.

So how can we spin up a cloned environment in 2 seconds? That's exactly what I'll be talking about here

Webhooks are the foundation of modern API development. They enable us to react to changes in our systems, an incoming text message, a successful payment, or that latest pull request no matter our stack. While webhooks are universal in concept, they are unstandardized API contracts with few organizations paying attention to their design, security controls, and overall operational experience. Webhooks.fyi seeks to change that.

Automatically set GOMEMLIMIT to match Linux cgroups(7) memory limit.

Usually the program has to put its generated code in memory that is specially marked as executable. However, this capability is missing in WebAssembly. How, then, to do just-in-time compilation in WebAssembly?

In this post I’m going to describe how to use eBPF syscall tracing in a creative way in order to detect process behaviour anomalies at runtime using an unsupervised learning model called autoencoder.

Do you want to facilitate lifetime management and maintenance of polymorphic objects in C++? Do you want to be able to write polymorphic code in C++ as easily as in languages with GC (like Java or C#), while still having excellent runtime performance? Have you tried other polymorphic programming libraries in C++ but found them deficient? If so, this library is for you. The "proxy" is a single-header, cross-platform C++ library that Microsoft uses to make runtime polymorphism easier to implement and faster

Sharding is a fundamental building block of large-scale applications, but most have their own custom, ad-hoc implementations. Our goal is to make sharding as easily reusable as a filesystem or lock manager. Slicer is Google’s general purpose sharding service. It monitors signals such as load hotspots and server health to dynamically shard work over a set of servers. Its goals are to maintain high availability and reduce load imbalance while minimizing churn from moved work.

Moq is a tool that generates a struct from any interface. The struct can be used in test code as a mock of the interface.

I’ve spend the last year writing strictly portable Makefiles. Not only has are my builds now portable across all unix-like systems, my Makefiles are cleaner and more robust. Many of the common make extensions — conditionals in particular — lead to fragile, complicated Makefiles and are best avoided anyway.

Autogenerated API documentation. Integrated Markdown pages. Instant search. Beautiful output. Create great documentation, painlessly.

A collection of research papers and other resources related to the theory and practice of computational effects.

SRV record support for legacy systems via LD_PRELOAD getaddrinfo/connect hooks. It works by intercepting calls to getaddrinfo, which would normally fail due to reliance on A/AAAA records, and using SRV instead for names prefixed with an underscore

KLoop is an implementation of the Python asyncio event loop written in Cython, using io_uring and kTLS features of the Linux kernel, therefore called k(ernel)Loop.

Back in the old days, I could just type route (or, later, ip route) in my Linux terminal and get an accurate picture of all my routes. This is no longer the case.

Omnitrace is a comprehensive profiling and tracing tool for parallel applications written in C, C++, Fortran, HIP, OpenCL, and Python which execute on the CPU or CPU+GPU. It is capable of gathering the performance information of functions through any combination of binary instrumentation, call-stack sampling, user-defined regions, and Python interpreter hooks. Omnitrace supports interactive visualization of comprehensive traces in the web browser in addition to high-level summary profiles with mean/min/max/stddev statistics. In addition to runtimes, omnitrace supports the collection of system-level metrics such as the CPU frequency, GPU temperature, and GPU utilization, process-level metrics such as the memory usage, page-faults, and context-switches, and thread-level metrics such as memory usage, CPU time, and numerous hardware counters.

Treadmill is a "real-time" in-place garbage collection algorithm designed by H. Baker. It is simple, elegant, efficient and surprisingly little known

A better localhost with HTTPS (SSL) and sub-domain support

Amazon DynamoDB is a NoSQL cloud database service that provides consistent performance at any scale. Hundreds of thousands of customers rely on DynamoDB for its fundamental properties: consistent performance, availability, durability, and a fully managed serverless experience. In 2021, during the 66 hour Amazon Prime Day shopping event, Amazon systems including Alexa, the Amazon.com sites, and Amazon fulfillment centers, made trillions of API calls to DynamoDB, peaking at 89.2 million requests per second, while experiencing high availability with single-digit millisecond performance. Since its launch in 2012, DynamoDB's design and implementation have evolved in response to our experiences operating it. The system has successfully dealt with issues related to fairness, traffic imbalance across partitions, monitoring, and automated system operations without impacting availability or performance. Reliability is essential, as even the slightest disruption can significantly impact customers. This paper presents our experience operating DynamoDB at a massive scale and how the architecture continues to evolve to meet the ever-increasing demands of customer workloads.

We present uKharon, a microsecond-scale membership service that detects changes in the membership of applications and lets them failover in as little as 50us. uKharon consists of (1) a multi-level failure detector, (2) a consensus engine that relies on one-sided RDMA CAS, and (3) minimal-overhead membership leases, all exploiting RDMA to operate at the microsecond scale

This paper presents iFed , an infrastructure for extensible and flexible dynamic library transformation. We design iFed in a pass-based architecture to compose various functional and optimization passes. iFed uses a runnable in-memory format to represent libraries and coordinate among multiple transformation passes. We further implement two optimization passes in iFed , which efficiently leverages hugepages and eliminates relocation overhead. iFed is implemented as a drop-in replacement of the current system default dynamic loader

Recently, Bronson et al. introduced a framework for understanding a class of failures in distributed systems called metastable failures. The examples of metastable failures presented in that work are simplified versions of failures observed at Facebook. In this work, we study the prevalence of such failures in the wild by scouring over publicly available incident reports from many organizations, ranging from hyperscalers to small companies. Our main findings are threefold. First, metastable failures are universally observed—we present an in-depth study of 22 metastable failures from 11 different organizations. Second, metastable failures are a recurring pattern in many severe outages—e.g., at least 4 out of 15 major outages in the last decade at Amazon Web Services were caused by metastable failures. Third, we extend the model by Bronson et al. to better reflect the metastable failures seen in the wild by categorizing two types of triggers and two types of amplification mechanisms, which we confirm through developing multiple example applications that reproduce different types of metastable failures in a controlled environment. We believe our work will aid in a deeper understanding of metastable failures and in coming up with solutions to them.

This web page contains a free electronic version of my self-published textbook Algorithms, along with other lecture notes I have written for various theoretical computer science classes at the University of Illinois, Urbana-Champaign since 1998.

This book is for those who will not settle for a black-box approach when working with a database. Briefly touching upon the main concepts of PostgreSQL, the book then plunges into the depths of data consistency and isolation, explaining implementation details of multiversion concurrency control and snapshot isolation, buffer cache and write-ahead log, and the locking system. The rest of the book covers the questions of planning and executing SQL queries, including the discussion of data access and join methods, statistics, and various index types.

Welcome to the Memory Management Reference! This is a resource for programmers and computer scientists interested in memory management and garbage collection.

I/O is the key to determining the performance bottleneck of a web server, and the traditional Linux I/O mechanism leads to a large number of data copy operations and loss of performance, so we urgently need a new technology to solve the problem of large number of data copies, and the answer is Zero-copy.

I was recently confronted with a nice example of how adding FOR UPDATE to a query can introduce transaction anomalies. This article will explain how that happens and how you can cope with the problem.

TLA+ is a “formal specification language”, a means of designing systems that lets you directly test those designs. Developed by the Turing award-winner Leslie Lamport, TLA+ has been endorsed by companies like AWS, Microsoft, and Crowdstrike. TLA+ doesn’t replace our engineering skill but augments it. With TLA+ we can design systems faster and more confidently

This post attempts to explain how Lisp condition systems surpass ordinary exception handling. Condition systems don't unwind the stack by default and thus allow computations to be restarted, which is a useful tool.

Recently, while idly browsing through the source code of Python, I came upon an interesting comment in the bytecode VM implementation (Python/ceval.c) about using the computed gotos extension of GCC. Driven by curiosity, I decided to code a simple example to evaluate the difference between using a computed goto and a traditional switch statement for a simple VM. This post is a summary of my findings.

K-Sortable Globally Unique IDs

Systemd (since version 239) supports a concept of “Portable Services”. “Portable Services” are a delivery method for system services that uses two specific features of container management: (1) Applications are bundled. I.e. multiple services, their binaries and all their dependencies are packaged in an image, and are run directly from it. (2) Stricter default security policies, i.e. sand-boxing of applications. The primary tool for interacting with Portable Services is portablectl, and they are managed by the systemd-portabled service.

Dragonfly is a modern in-memory datastore, fully compatible with Redis and Memcached APIs. Dragonfly implements novel algorithms and data structures on top of a multi-threaded, shared-nothing architecture. As a result, Dragonfly reaches x25 performance compared to Redis and supports millions of QPS on a single instance

Karmem is a fast binary serialization format. The priority of Karmem is to be easy to use while been fast as possible. It's optimized to take Golang and TinyGo's maximum performance and is efficient for repeatable reads, reading different content of the same type. Karmem has proven to be ten times faster than Google Flatbuffers, with the additional overhead of bounds-checking included

The standardization of NVMe Zoned Namespaces (ZNS) in the NVMe 2.0 specification presents a unique new addition to storage devices. Unlike traditional SSDs, where the flash media management idiosyncrasies are hidden behind a flash translation layer (FTL) inside the device, ZNS devices push certain operations regarding data placement and garbage collection out from the device to the host. This allows the host to achieve more optimal data placement and predictable garbage collection overheads, along with lower device write amplification. Thus, additionally increasing flash media lifetime. As a result, ZNS devices are gaining significant attention in the research community. However, with the current software stack there are numerous ways of integrating ZNS devices into a host system. In this work, we begin to systematically analyze the integration options, report on the current software support for ZNS devices in the Linux Kernel, and provide an initial set of performance measurements. Our main findings show that larger I/O sizes are required to saturate the ZNS device bandwidth, and configuration of the I/O scheduler can provide workload dependent performance gains, requiring careful consideration of ZNS integration and configuration depending on the application workload and its access patterns. Our dataset and code are available at https: //github.com/nicktehrany/ZNS-Study.

Ipftrace2 is a tool which allows you to trace the journey of packets inside the Linux kernel. It is similar to the ftrace in some sense but, you can trace which flow have gone through which functions inside the kernel which is usually more important information for the network people than which functions are called information provided by ftrace.

Today, companies and data centers are moving towards distributed and serverless storage systems instead of traditional file systems. As a result of such transition, allocating sufficient resources to users and parties to satisfy their service level demands has become crucial in distributed storage systems. The Quality of Service (QoS) is a research area that tries to tackle such challenges. The schedulability of system components and requests is of great importance to achieve the QoS goals in a distributed storage. Many QoS solutions are designed and implemented through request scheduling at different levels of system architecture. However, the bufferbloat phenomenon in storage backends can compromise the request schedulability of the system. In a storage server, bufferbloat happens when the server submits all requests immediately to the storage backend due to a too large buffer in the storage backend. In recent decades, many research works tried to solve the bufferbloat problem for network systems. Nevertheless, none of these works are suitable for storage system environments and workloads. This paper presents the SF_CoDel algorithm, an adaptive extension of the Controlled Delay (CoDel) algorithm, to mitigate the bufferbloat for different workloads in storage systems. SF_CoDel manages this purpose by controlling the amount of work submitted to the storage backend. The evaluation of our algorithm indicates that SF_CoDel can mitigate the bufferbloat in storage servers.

128-bit compatibility with UUID 1.21e+24 unique ULIDs per millisecond Lexicographically sortable! Canonically encoded as a 26 character string, as opposed to the 36 character UUID Uses Crockford's base32 for better efficiency and readability (5 bits per character) Case insensitive No special characters (URL safe) Monotonic sort order (correctly detects and handles the same millisecond)

Our engineering team focuses on getting the maximum amount of information from the network while sending as little traffic as possible. This lean approach to network discovery is driven by our goal of being fast and safe for all networks. The more we can learn about a system from a single measurement, the less traffic we create and the quicker things run. In this post, I want to share how Rumble uses one of the most common network protocols to obtain a wealth of information about network-attached devices.

ReadySet is a lightweight SQL caching engine that precomputes frequently-accessed query results and automatically keeps these results up-to-date over time as the underlying data in your database changes. ReadySet is wire-compatible with MySQL and Postgres and can be adopted without code changes

TCPLS solves the same issue as QUIC, is in userspace, provides new and modern transport features that directly work on the Internet, and is ensured to work through time thanks to the randomized protocol information.

A slim framework for building browser and gRPC-compatible HTTP APIs. Connect is production-ready — focused, simple, and debuggable — and it's fully compatible with gRPC clients and servers. If you're frustrated by the complexity and instability of today's gRPC libraries, we think you'll find Connect a breath of fresh air.