Snapshot Isolation (SI), is a multi-version concurrency control algorithm introduced in [BBGMOO95] and later implemented by Oracle. SI avoids many concurrency errors, and it never delays read-only transactions. However it does not guarantee serializability. It has been widely assumed that, under SI, read-only transactions always execute serializably provided the concurrent update transactions are serializable. The reason for this is that all SI reads return values from a single instant of time when all committed transactions have completed their writes and no writes of non-committed transactions are visible. This seems to imply that read-only transactions will not read anomalous results so long as the update transactions with which they execute do not write such results. In the current note, however, we exhibit an example contradicting these assumptions: it is possible for an SI history to be non-serializable while the sub-history containing all update transactions is serializable.

Ouroboros is a peer-to-peer packet network prototype. It unifies all packet communications –whether it is two programs the same machine or a set of programs in computers on different continents – using a small set of abstractions, which we call layers and flows. The Ouroboros architecture improves security, privacy and efficiency through simplicity. It provides a very compact API for writing distributed software and networked application libraries, with support for both unicast and multicast communications. Being rebuilt from the ground up, Ouroboros is not directly compatible with IP or UNIX sockets, but it can run on top of and/or below UDP/IP and Ethernet

This page describes the JSON Lines text format, also called newline-delimited JSON. JSON Lines is a convenient format for storing structured data that may be processed one record at a time. It works well with unix-style text processing tools and shell pipelines. It's a great format for log files. It's also a flexible format for passing messages between cooperating processes

Particularly in bigger organizations with lots of services where a standard has to be adopted, you often end up in a situation where you track things like "95th percentile of response time is under 100ms for 99% of minutes for each reporting period" or "99.95% of responses return a status code below 500" (meaning "successful or not broken by our fault"). So sure, those are the surrogate variables. What's the true one? User satisfaction? How "snappy" the product feels? Are the metrics chosen truly representative of that experience? What are the things that can pollute or mess with this measurement? Have we even asked these questions, or did we just go with a value some FAANG player published 10 years ago?

Consider a social media platform with hundreds of millions of online users at any time, utilizing a social graph that has many billions of nodes and edges. The problem this paper addresses is how to provide each user a continuously fresh, up-to-date view of the parts of the social graph they are currently interested in, so as to provide a positive interactive user experience. The problem is challenging because the social graph mutates at a high rate, users change their focus of interest frequently, and some mutations are of interest to many online users. We describe Bladerunner, a system we use at Facebook to deliver relevant social graph updates to user devices efficiently and quickly. The heart of Bladerunner is a set of back-end stream processors that obtain streams of social graph updates and process them on a per application and per-user basis before pushing selected updates to user devices. Separate stream processors are used for each application to enable application-specific customization, complex filtering, aggregation and other message delivery operations on a per-user basis. This strategy minimizes device processing overhead and last-mile bandwidth usage, which are critical given that users are mostly on mobile devices.

HTTP Toolkit is an open-source tool for debugging, testing and building with HTTP(S) on Windows, Linux & Mac. You can use it to intercept, inspect & rewrite HTTP(S) traffic, from everything to anywhere. Explore Android app traffic, mock requests between your microservices, and x-ray your browser traffic to debug, understand and test anything.

Pitfalls of how we use latency metrics (with the actual service names anonymized per a comms request). Since this presentation, significant progress has been made on this on the infra side, so the situation is much improved over what was presented, but I think this is still relevant since, from talking to folks at peer companies, many folks are facing similar issues.

In January 2020, we grew Steady's language support from 2 to 9 languages. Those initial efforts, as well as adding new features to the platform afterwards, taught us a few good practices for working with Gettext.

Query your existing PostgreSQL database with GraphQL. pg_graphql inspects your PostgreSQL schema and reflects a GraphQL schema with resolvers.

You can use a Kalman filter in any place where you have uncertain information about some dynamic system, and you can make an educated guess about what the system is going to do next. Even if messy reality comes along and interferes with the clean motion you guessed about, the Kalman filter will often do a very good job of figuring out what actually happened. And it can take advantage of correlations between crazy phenomena that you maybe wouldn’t have thought to exploit!

This course provides a rapid overview of optimal control (controllability, observability, LQR, Kalman filter, etc.). It is not meant to be an exhaustive treatment, but instead provides a high-level overview of some of the main approaches, applied to simple examples in Matlab.

Let’s get this straight: The effort to host Google web fonts on your own server is immense! First of all you need to download all .eot, .woff, .woff2, .ttf and .svg files, then copy them onto your server and finally paste a CSS snippet. Sounds easy? Well it could be, if Google would actually provide any direct links to download these files and a customized CSS for self-hosting them. To fix this problem without using font generation services like Font Squirrel, I decided to publish a little service called google-webfonts-helper.

RLBox is a toolkit for sandboxing third-party libraries. The toolkit consists of (1) a Wasm-based sandbox and (2) an API for retrofitting existing application code to interface with a sandboxed library

I’ve been working on an extendible general purpose shard coordinator, Shardz. In this article, I will explain the main concepts and the future work.

In this paper, we present an auction-inspired approach in which application developers bid on resources while fog nodes decide locally which functions to execute and which to offload in order to maximize revenue. Unlike many current approaches to function placement in the fog, our approach can work in an online and decentralized manner. We also present our proof-of-concept prototype AuctionWhisk that illustrates how such an approach can be implemented in a real FaaS platform. Through a number of simulation runs and system experiments, we show that revenue for overloaded nodes can be maximized without dropping function requests.

This fast script allows you to insert your GitHub README in your static site and apply transformations

I have noticed that a number of new features in Python 3 have made it possible to use objects in the same style of ADTs, in idiomatic Python with virtually no boilerplate

Sub-nanosecond precision clock synchronization over the packet network has been achieved by the White Rabbit protocol for a decade. However, few computer systems utilize such a technique. We try to attract more interest in the clock synchronization problem. We first introduce the basics of clock and synchronization in the time and frequency discipline. Then we revisit several related works, such as Google's Spanner, Huygens, FARMv2, DTP, and Sundial, explain why these works could be improved. Finally, we briefly discuss an independent time network approach towards low-cost and high-precision synchronization.

Based on our experience implementing it into our data centers, BGP can form a robust routing foundation, but it requires tight codesign with the data center topology, configuration, switch software, and data center–wide operational pipeline

Enterprise cloud developers have to build applications that are resilient to failures and interruptions. We advocate for, formalize, implement, and evaluate a simple, albeit effective, fault-tolerant programming model for the cloud based on actors, reliable message delivery, and retry orchestration. Our model guarantees that (1) failed actor invocations are retried until success, (2) in a distributed chain of invocations only the last one may be retried, (3) pending synchronous invocations with a failed caller are automatically cancelled. These guarantees make it possible to productively develop fault-tolerant distributed applications ranging from classic problems of concurrency theory to complex enterprise applications. Built as a service mesh, our runtime system can interface application components written in any programming language and scale with the application. We measure overhead relative to reliable message queues. Using an application inspired by a typical enterprise scenario, we assess fault tolerance and the impact of fault recovery on application performance

Fast and secure remote UI for your bots, backup scripts, cron jobs, crawlers. No knowledge of HTML, CSS or JavaScript required

Programming Fonts with Ligatures added (& a script to add them to other fonts)

Elfshaker is a low-footprint, high-performance version control system fine-tuned for binaries

Traffic shaping, including pacing and rate limiting, is fundamental to the correct and efficient operation of both datacenter and wide area networks. Sample use cases include policy-based bandwidth allocation to flow aggregates, rate-based congestion control algorithms, and packet pacing to avoid bursty transmissions that can overwhelm router buffers. Driven by the need to scale to millions of flows and to apply complex policies, traffic shaping is moving from network switches into the end hosts, typically implemented in software in the kernel networking stack. In this paper, we show that the performance overhead of end-host traffic shaping is substantial limits overall system scalability as we move to thousands of individual traffic classes per server. Measurements from production servers show that shaping at hosts consumes considerable CPU and memory, unnecessarily drops packets, suffers from head of line blocking and inaccuracy, and does not provide backpressure up the stack. We present Carousel, a framework that scales to tens of thousands of policies and flows per server, built from the synthesis of three key ideas: i) a single queue shaper using time as the basis for releasing packets, ii) fine-grained, just-in-time freeing of resources in higher layers coupled to actual packet departures, and iii) one shaper per CPU core, with lock-free coordination. Our production experience in serving video traffic at a Cloud service provider shows that Carousel shapes traffic accurately while improving overall machine CPU utilization by 8% (an improvement of 20% in the CPU utilization attributed to networking) relative to state-of-art deployments. It also conforms 10 times more accurately to target rates, and consumes two orders of magnitude less memory than existing approaches.

Datacenter systems and I/O devices now run at single-digit microsecond latencies, requiring ns-scale operating systems. Traditional kernel-based operating systems impose an unaffordable overhead, so recent kernel-bypass OSes [73] and libraries [23] eliminate the OS kernel from the I/O datapath. However, none of these systems offer a general-purpose datapath OS replacement that meet the needs of μs-scale systems.' AB@This paper proposes Demikernel, a flexible datapath OS and architecture designed for heterogenous kernel-bypass devices and μs-scale datacenter systems. We build two prototype Demikernel OSes and show that minimal effort is needed to port existing μs-scale systems. Once ported, Demikernel lets applications run across heterogenous kernel-bypass devices with ns-scale overheads and no code changes.

We describe the design and implementation of Protean -- the Microsoft Azure service responsible for allocating Virtual Machines (VMs) to millions of servers around the globe. A single instance of Protean serves an entire availability zone (10-100k machines), facilitating seamless failover and scale-out to customers. The design has proven robust, enabling a substantial expansion of VM offerings and features with minimal changes to the core infrastructure. In particular, Protean preserves a clear separation between policy and mechanisms. From a policy perspective, a flexible rule-based Allocation Agent (AA) allows Protean to efficiently address multiple constraints and performance criteria, and adapt to different conditions. On the system side, a multi-layer caching mechanism expedites the allocation process, achieving turnaround times of few milliseconds. A slight compromise on allocation quality enables multiple AAs to run concurrently on the same inventory, resulting in increased throughput with negligible conflict rate. Our results from both simulations and production demonstrate that Protean achieves high throughput and utilization (85-90% on a key utilization metric), while satisfying user-specific requirements. We also demonstrate how Protean is adapted to handle capacity crunch conditions, by zooming in on spikes caused by COVID-19.

In this article, I’ll share why and how we built the UDF engine, its outstanding features, and how we look forward to tapping into more of its potential.

FS sandboxing, dynamic users, privileged ports, secrets with systemd

We believe that the simplest way to use Paxos to decide a log of values is not to use many instances of Paxos but to use one modified instance of Paxos, generalized to decide an append-only log of values instead of a single value.

Provides an extended, production-ready HTTP server

Co-location and memory sharing between latency-critical services, such as key-value store and web search, and best-effort batch jobs is an appealing approach to improving memory utilization in multi-tenant datacenter systems. However, we find that the very diverse goals of job co-location and the GNU/Linux system stack can lead to severe performance degradation of latency-critical services under memory pressure in a multi-tenant system. We address memory pressure for latency-critical services via fast memory allocation and proactive reclamation. We find that memory allocation latency dominates the overall query latency, especially under memory pressure. We analyze the default memory management mechanism provided by GNU/Linux system stack and identify the reasons why it is inefficient for latency-critical services in a multi-tenant system. We present Hermes, a fast memory allocation mechanism in user space that adaptively reserves memory for latency-critical services. It advises Linux OS to proactively reclaim memory of batch jobs. We implement Hermes in GNU C Library. Experimental result shows that Hermes reduces the average and the 99th percentile memory allocation latency by up to 54.4% and 62.4% for a micro benchmark, respectively. For two real-world latency-critical services, Hermes reduces both the average and the 99th percentile tail query latency by up to 40.3%. Compared to the default Glibc, jemalloc and TCMalloc, Hermes reduces Service Level Objective violation by up to 84.3% under memory pressure.

This pattern language1 describes a way of testing object-oriented code without using mocks. It avoids the downsides of mock-based testing, but it has tradeoffs of its own.

Cache eviction algorithms are used widely in operating systems, databases and other systems that use caches to speed up execution by caching data that is used by the application. There are many policies such as MRU (Most Recently Used), MFU (Most Frequently Used), LRU (Least Recently Used) and LFU (Least Frequently Used) which each have their advantages and drawbacks and are hence used in specific scenarios. By far, the most widely used algorithm is LRU, both for its O(1) speed of operation as well as its close resemblance to the kind of behaviour that is expected by most applications. The LFU algorithm also has behaviour desirable by many real world workloads. However, in many places, the LRU algorithm is is preferred over the LFU algorithm because of its lower run time complexity of O(1) versus O(logn). We present here an LFU cache eviction algorithm that has a runtime complexity of O(1) for all of its operations, which include insertion, access and deletion(eviction).

Developers have access to a wide range of storage APIs and functionality in large-scale systems, such as relational databases, key-value stores, and namespaces. However, this diversity comes at a cost: each API is implemented by a complex distributed system that is difficult to develop and operate. Delos amortizes this cost by enabling different APIs on a shared codebase and operational platform. The primary innovation in Delos is a log-structured protocol: a fine-grained replicated state machine executing above a shared log that can be layered into reusable protocol stacks under different databases. We built and deployed two production databases using Delos at Facebook, creating nine different log-structured protocols in the process. We show via experiments and production data that log-structured protocols impose low overhead, while allowing optimizations that can improve latency by up to 100X (e.g., via leasing) and throughput by up to 2X (e.g., via batching).

In this post, I’ll share some patterns for automating TLS certificate management in Docker when using an internal PKI, and show several examples. The examples use our open-source step CLI tool, which connects to either your own step-ca server or a Smallstep Certificate Manager hosted CA, but many of the approaches here could be adapted for other CAs, or for Web PKI certificates.

I’m going to rattle off a bunch of different isolation techniques. I’ll spoil the list for you now: we use Firecracker, the virtualization engine behind Amazon’s Lambda and Fargate services. But the solution space we chose Firecracker from is interesting, and so you’re going to hear about it.

As the volume of data that needs to be processed continues to increase, we also see renewed interests in near-data processing in the form of computational storage, with eBPF (extended Berkeley Packet Filter) being proposed as a vehicle for computation offloading. However, discussions in this regard have so far ignored viable alternatives, and no convincing analysis has been provided. As such, we qualitatively and quantitatively evaluated eBPF against WebAssembly, a seemingly similar technology, in the context of computation offloading. This report presents our findings.

The Little Book of Semaphores is a free (in both senses of the word) textbook that introduces the principles of synchronization for concurrent programming

A list of useful features you already have, but may not know about! In this article I share lesser known features of PostgreSQL.

A Go library for the Linux Landlock sandboxing feature

Sometimes you just want to know how fast your code can go, without benchmarking it. Sometimes you have benchmarked it and want to know how close you are to the maximum speed. Often you just need to know what the current limiting factor is, to guide your optimization decisions. Well this post is about that determining that speed limit1. It’s not a comprehensive performance evaluation methodology, but for many small pieces of code it will work very well.

Agreement among a set of processes and in the presence of partial failures is one of the fundamental problems of distributed systems. In the most general case, many decisions must be agreed upon over the lifetime of a system with dynamically changing membership. Such a sequence of decisions represents a distributed log, and can form the underlying abstraction for driving a replicated state machine. While this abstraction is at the core of many systems with strong consistency requirements, algorithms that achieve such sequence consensus are often poorly understood by developers and have presented a significant challenge to many students of distributed systems. In these lecture notes we present a complete and practical Paxos-based algorithm for reconfigurable sequence consensus in the fail-recovery model, and a clear path of simple step-by-step transformations to it from the basic Paxos algorithm

A Bloom filter can be remarkably efficient. But can you do better?

According to style(9), it is not a good practice to call exit(3) with arbitrary values to indicate a failure condition when ending a program. Instead, the pre-defined exit codes from sysexits should be used, so the caller of the process can get a rough estimation about the failure class without looking up the source code.

In this post, I’ll outline a simple, practical alternative: using reservoir sampling to turn any batch function into a streaming operator. Given a function that operates over a static set of data, we can use this trick to evaluate the function over essentially arbitrarily-sized streams – while using limited space. While the resulting accuracy may vary considerably from function to function, with modestly-sized memory budgets sampling can be remarkably useful.

PAKE — which stands for Password Authenticated Key Exchange — is actually one of the most useful technologies that (almost) never gets used. It should be deployed everywhere, and yet it isn’t.

How can you help the compiler do its job better and when does it make sense to do the optimizations manually? In this post we try to give answers to those questions, and as you will see, the answer is not simple to give.

The Open Time Server (OTS) is an Open, Scalable and Validated reference architecture that can be deployed in Data Centers or in an edge environments.

'home.arpa.' is designated for non-unique use in residential home networks.

We propose PAIO, the first general-purpose framework that enables system designers to build custom-made Software-Defined Storage (SDS) data plane stages. It provides the means to implement storage optimizations adaptable to different workflows and user-defined policies, and allows straightforward integration with existing applications and I/O layers. PAIO allows stages to be integrated with modern SDS control planes to ensure holistic control and system-wide optimal performance. We demonstrate the performance and applicability of PAIO with two use cases. The first improves 99th percentile latency by 4x in industry-standard LSM-based key-value stores. The second ensures dynamic per-application bandwidth guarantees under shared storage environments

Designing and implementing efficient parallel priority schedulers is an active research area. An intriguing proposed design is the Multi-Queue: given n threads and m≥n distinct priority queues, task insertions are performed uniformly at random, while, to delete, a thread picks two queues uniformly at random, and removes the observed task of higher priority. This approach scales well, and has probabilistic rank guarantees: roughly, the rank of each task removed, relative to remaining tasks in all other queues, is O(m) in expectation. Yet, the performance of this pattern is below that of well-engineered schedulers, which eschew theoretical guarantees for practical efficiency. We investigate whether it is possible to design and implement a Multi-Queue-based task scheduler that is both highly efficient and has analytical guarantees. We propose a new variant called the Stealing Multi-Queue (SMQ), a cache-efficient variant of the Multi-Queue, which leverages both queue affinity -- each thread has a local queue, from which tasks are usually removed; but, with some probability, threads also attempt to steal higher-priority tasks from the other queues -- and task batching, that is, the processing of several tasks in a single insert / delete step. These ideas are well-known for task scheduling without priorities; our theoretical contribution is showing that, despite relaxations, this design can still provide rank guarantees, which in turn implies bounds on total work performed. We provide a general SMQ implementation that can surpass state-of-the-art schedulers such as Galois and PMOD in terms of performance on popular graph-processing benchmarks. Notably, the performance improvement comes mainly from the superior rank guarantees provided by our scheduler, confirming that analytically-reasoned approaches can still provide performance improvements for priority task scheduling.

Software caches optimize the performance of diverse storage systems, databases and other software systems. Existing works on software caches automatically resort to fully associative cache designs. Our work shows that limited associativity caches are a promising direction for concurrent software caches. Specifically, we demonstrate that limited associativity enables simple yet efficient realizations of multiple cache management schemes that can be trivially parallelized. We show that the obtained hit ratio is usually similar to fully associative caches of the same management policy, but the throughput is improved by up to X5 compared to production-grade caching libraries, especially in multi-threaded executions.

Linux gained support for VRF interfaces in Linux 4.3. And since Alpine 3.13, we have supported managing VRFs and binding services to them, primarily for the purpose of low-cost service isolation

Go library providing algorithms optimized to leverage the characteristics of modern CPUs

Amazon Ion is a richly-typed, self-describing, hierarchical data serialization format offering interchangeable binary and text representations. The text format (a superset of JSON) is easy to read and author, supporting rapid prototyping. The binary representation is efficient to store, transmit, and skip-scan parse. The rich type system provides unambiguous semantics for long-term preservation of data which can survive multiple generations of software evolution.

A standard technique from the hashing literature is to use two hash functions h1(x) and h2(x) to simulate additional hash functions of the form gi(x) = h1(x) + ih2(x). We demonstrate that this technique can be usefully applied to Bloom filters and related data structures. Specifically, only two hash functions are necessary to effectively implement a Bloom filter without any loss in the asymptotic false positive probability. This leads to less computation and potentially less need for randomness in practice.

The answer is yes, you can write a server that does no syscalls for handling requests, if you are willing to forego memory allocations, don’t count asynchronous syscalls as being “real” syscalls and are also willing to use 100% of one CPU for the process and some unspecified amount of CPU for the kernel thread. Clearly this is not really a viable approach for production-quality applications, but it was fun to see how low we could go

The reason is because this entire problem is built on a flawed premise. Asking what the most user-friendly way to implicitly insert overflows is is like asking what the driest kind of water is. All the answers are unsatisfactory because you are asking the wrong question in the first place. The right question is “Why do you even need multiple integer types in the first place?”

Filibuster is the prototype implementation of Service-level Fault Injection Testing (ACM SoCC ‘21) written in Python. Service-level Fault Injection Testing is a technique for identifying resilience issues in microservice-based applications in development, before code ships to production. Filibuster has been designed to be easy to use, lightweight, and able to be integrated into a continuous integration environment, like GitHub Actions or Amazon’s CodeBuild CI/CD environment.

Modern key-value (KV) stores adopt the LSM-tree as the core data structure for managing KV pairs, but suffer from high write and read amplifications. Existing LSM-tree optimizations often make design trade-offs and are unable to simultaneously achieve high performance in writes, reads, and scans. To resolve the design tensions, we propose DiffKV, which builds on KV separation to carefully manage the ordering for keys and values. DiffKV manages keys using the conventional LSM-tree with fully-sorted ordering (within each level of the LSM-tree), while managing values with partially-sorted ordering with respect to the fully-sorted ordering of keys in a coordinated way for preserving high scan performance. We further propose fine-grained KV separation to differentiate KV pairs by size, so as to realize balanced performance under mixed workloads. Experimental results show that DiffKV can simultaneously achieve the best performance in all aspects among existing LSM-tree-optimized KV stores.

An open source collection of Design Principles and methods.

This tool is a syscall fault injector built on top of eBPF that has no requirements on the target machine other than a kernel version good enough to support the required features

Build distroless images with apk! Witchery is a collection of tools which can be composed to build distroless images. It is intended to be portable for use with any package management tooling, but is primarily focused on apk-based distributions at the moment, such as Alpine.

SLO Tracker allows you to balance service reliability with the pace of innovation. You can define the target SLO and use corresponding SLIs to track Error Budget. The error budget thus forms a control mechanism for diverting attention to stability as needed

This is the API job people generally refer to as IAM. There are a bunch of different ways to do the IAM job, and they're all fun to nerd out about.

Facebook’s graph store TAO, like many other distributed data stores, traditionally prioritizes availability, efficiency, and scalability over strong consistency or isolation guarantees to serve its large, read-dominant workloads. As product developers build diverse applications on top of this system, they increasingly seek transactional semantics. However, providing advanced features for select applications while preserving the system’s overall reliability and performance is a continual challenge. In this paper, we first characterize developer desires for transactions that have emerged over the years and describe the current failure-atomic (i.e., write) transactions offered by TAO. We then explore how to introduce an intuitive read transaction API. We highlight the need for atomic visibility guarantees in this API with a measurement study on potential anomalies that occur without stronger isolation for reads. Our analysis shows that 1 in 1,500 batched reads reflects partial transactional updates, which complicate the developer experience and lead to unexpected results. In response to our findings, we present the RAMP-TAO protocol, a variation based on the Read Atomic Multi-Partition (RAMP) protocols that can be feasibly deployed in production with minimal overhead while ensuring atomic visibility for a read-optimized workload at scale

Modern applications tend to be composed from relationships between smaller applications. Secure modern applications thus need a way to express and enforce security policies that span multiple services. This is the “server-to-server” (S2S) authentication and authorization problem

What do you do when a set of key/value pairs no longer fits in memory, and you want to design a disk-friendly structure to store them all?

Pluggable caching engine to build and scale high performance cache services

This repo contains an implementation of the Homa transport protocol as a Linux kernel module