Foundationdb Tape Layer: A Multi-Tenant Structured Datastore

This is a 2019 arxiv report. Back inwards 2019, when the study was out, I wrote a review close it, but did non disclose it thence because I felt I didn't take maintain plenty information on FoundationDB yet. With FoundationDB Sigmod 2021 newspaper out recently, I am at nowadays releasing that before write up. I volition follow upward on this presently amongst a review of the Sigmod21 newspaper on FoundationDB.

Introduction

FoundationDB made a bold blueprint selection of ACID key-value store. They had released a transaction manifesto:

• Everyone needs transactions
• Transactions brand concurrency simple
• Transactions enable abstraction
• Transactions enable efficient information representations
• Transactions enable flexibility
• Transactions are non equally expensive equally you lot think
• Transactions are the hereafter of NoSQL

FoundationDB, available equally opensource, consists of the transactional minimalist storage engine equally the base of operations layer, as well as other layers are developed on overstep of the base of operations layer to extend functionality. The tape layer, that the study describes, is stateless! 

Unfortunately, I couldn't detect a newspaper explaining the base of operations layer, the storage layer of FoundationDB (Update: Now at that topographic point is the Sigmod'21 paper). This newspaper skips over the base of operations layer, as well as I had to acquire that through watching unopen to YouTube talks.

FoundationDB, storage engine

I wanted to start amongst the base of operations layer, although it is glossed over inwards this paper.  The inwards a higher house figure from the FoundationDB website shows a logical abstraction pic of the base of operations layer architecture, which is a distributed database that organizes information equally an ordered key-value shop amongst ACID transactions. The base of operations layer is composed of 2 logical clusters, i for storing information as well as processing transactions, as well as i for coordinating membership & configuration of the root cluster (using Active Disk Paxos). Reads acquire close which version (commit-timestamp) to read from the transactional ascendance as well as thence direct contact the corresponding storage node to acquire the value. For commits, the transactional ascendance "somehow" enforces ACID guarantees as well as the storage nodes asynchronously re-create updates from committed transactions. The newspaper does non elaborate on this, as well as says the following. FoundationDB provides ACID multi-key transactions amongst strictly-serializable isolation, implemented using multi-version concurrency command (MVCC).  Neither reads nor writes are blocked past times other readers or writers, instead conflicting transactions neglect at commit fourth dimension (and are commonly retried past times the client).
 

This figure is from the FoundationDB storage engine technical overview talk. Unfortunately, at that topographic point is no newspaper or documentation explaining this to a greater extent than concrete/detailed architecture figure.

The transactional ascendance is comprised of 4 dissimilar type of components. The master is tasked amongst providing increasing monotonic timestamps, which serve equally commit-times of transactions. Proxies convey commit requests as well as coordinate the commits. There are likewise resolvers to cheque if the transactions conflict amongst each other as well as neglect the conflicting ones. Resolvers cheque the recent transactions to encounter if they take maintain changed the read values inwards the transaction that the proxy is trying to commit.  Resolvers are key-range sharded, for a multikey transaction many demand to live contacted, leading to conflict amplification. Resolvers don't know close the decisions others are making for that transaction, thence a resolver that thinks the transaction should live OK, may unnecessarily as well as indirectly causing farther transactions to neglect on behalf of this non-existing transaction that is potentially a conflict. Finally, the quaternary type of cistron is the transaction logs. If the transaction clears the resolvers, it volition live made durable at the transaction logs. Transaction logs are replicated for durability against a node crash.

The proxy waits until all transaction logs replicate the transaction, as well as thence sends the commit to the client. Finally, the transaction logs are asynchronously streamed to the storage servers, thence that the storage servers tin execute them as well as brand them durable. The proxies likewise demand to communicate amidst each other really frequently: inwards fellowship to ensure external consistency for Get-Read version requests, each proxy demand to live aware of other every committed transaction on that key, which mightiness take maintain happened on unopen to other proxy. (I wonder if a information race status is possible here? Does this hateful proxy waits until it hears from all other proxies?) This is an intricate dance. The write takes 3-4 hops, if the components are on dissimilar nodes, this is going to add together to the latency. The proxies as well as the resolvers demand to commutation information continually, which makes them susceptible to acquire throughput as well as latency bottlenecks at scale.

by treatment whatever node failure amongst the same way, they acquire a pretty robust as well as well-exercised way of recovery.

The tape layer

Keys are part of a unmarried global namespace, as well as it is upward to the applications to separate as well as deal that namespace amongst the aid of APIs at higher layers. One representative is a tuple layer. The tuple layer encodes tuples into keys such that the binary ordering of those keys preserves the ordering of tuples as well as the natural ordering of typed tuple elements. A mutual prefix of the tuple is serialized equally a mutual byte prefix as well as defines a commutation subspace. E.g., a customer may shop the tuple (state, city) as well as afterwards read using a prefix similar (state,*).

The tape layer takes this further. It amends the key-value information model of the base of operations layer, which is insufficient for applications that demand structured information storage, indexing, as well as querying. It likewise provides the multi-tenancy features the base of operations layer lacks: isolation, resources sharing, as well as elasticity.

The tape layer provides schema management, a rich laid of inquiry as well as indexing facilities. The layer provides a KeySpace API which exposes the commutation infinite similar a filesystem directory structure. The tape layer likewise inherits FoundationDB's ACID semantics from the base of operations layer, as well as ensures secondary indexes are updated transactionally amongst the data. Finally, it is stateless as well as lightweight.

I actually similar that the tape layer is stateless. This simplifies scaling of the compute service: only launch to a greater extent than stateless instances. A stateless blueprint way that load-balancers as well as routers demand solely view where the information (at the base of operations layer) are located, as well as demand non worry close routing to specific compute servers that tin serve them.

The tape shop abstraction

The layer achieves resources sharing as well as elasticity amongst its record store abstraction. Each tape shop is assigned a contiguous arrive at of keys, ensuring that information belonging to dissimilar tenants is logically isolated.


The tape shop is the commutation abstraction here. The type of records inwards a tape shop are defined amongst Protocol Buffer definitions.

The schema, likewise called the metadata, of a tape shop is a laid of tape types as well as index definitions on these types. The metadata is versioned as well as stored separately.

The tape shop is responsible for storing raw records, indexes defined on the tape fields, as well as the highest version of the metadata it was accessed with.

Isolation betwixt tape stores is commutation for multitenancy. The keys of each tape shop start amongst a unique binary prefix, defining a FoundationDB subspace, as well as the subspaces of dissimilar tape stores do non overlap. To facilitate resources isolation further, the Record Layer tracks as well as enforces limits on resources consumption for each transaction, provides continuations to resume work, as well as tin live coupled amongst external throttling.

management

Because the Record Layer is designed to back upward millions of independent databases amongst a mutual schema, it stores metadata separately from the underlying data. The mutual metadata tin live updated atomically for all stores that utilization it.

Since records are serialized into the underlying key-value shop equally Protocol Buffer messages, unopen to basic information development properties are inherited. New fields tin live added to a tape type as well as exhibit upward equally uninitialized in  former records. New tape types tin live added without interfering amongst former records. As a best practice, land numbers are never reused as well as should live deprecated rather than removed altogether.

Indexing at the tape layer

Index maintenance occurs inwards the same transaction equally the tape alter itself, ensuring that indexes are ever consistent amongst the data, achieved via FoundationDB's fast multi-key transactions. Efficient index scans utilization arrive at reads as well as rely on the lexicographic ordering of stored keys.

A commutation aspect defines a logical path through records; applying it to a tape extracts tape land values as well as produces a tuple that becomes the primary commutation for the tape or commutation of the index for which the aspect is defined.

The index is updated using FoundationDB’s atomic mutations, which do non conflict amongst other mutations:

• COUNT: number of records
• COUNT UPDATES: num. times a land has been updated
• COUNT NON NULL: num. records where a land isn't null
• SUM: addition of a  field's value across all records
• MAX (MIN) EVER: max (min) value ever assigned to a field, over all records, since the index has been created.

VERSION indexes are really similar to VALUE indexes inwards that they define an index entry as well as a mapping from each entry to the associated primary key; CloudKit uses this index type to implement change-tracking as well as device synchronization.

The Record Layer controls its resources consumption past times limiting its semantics to those that tin live implemented on streams of records. For example, it supports ordered queries (such equally inwards SQL’s ORDER BY clause) solely when at that topographic point is an available index supporting the requested separate order. It doesn't create novel joins. It looks similar FoundationDB does non fully back upward SQL. I empathise that at unopen to indicate at that topographic point was unopen to piece of job on a SQL layer, but it wasn't regarded really highly. "What’s Really New amongst NewSQL?" newspaper said this: "We exclude [FoundationDB] because this organisation was at its substance a NoSQL key-value shop amongst an inefficient SQL layer grafted on overstep of it."

For the tape layer, the newspaper lists equally hereafter piece of job the following: avoiding hotspots, providing to a greater extent than inquiry operations, providing materialized views, as well as edifice higher layers providing unopen to SQL similar support.

CloudKit usecase

FoundationDB is used past times CloudKit, Apple's cloud backend service to serve millions of users. Within CloudKit a given application is represented past times a logical container, defined past times a schema that specifies the tape types, typed  fields, as well as indexes that are needed to facilitate efficient tape access as well as queries.

The application clients shop records inside named zones to organize records into logical groups which tin live selectively synced across customer devices.


CloudKit was initially implemented using Cassandra; Cassandra prevented concurrency inside a zone, as well as multi-record atomic operations were scoped to a unmarried partition. The implementation of CloudKit on FoundationDB as well as the Record Layer addresses both issues. Transactions are at nowadays scoped to the entire database, allowing CloudKit zones to grow significantly larger than before. Transactions likewise back upward concurrent updates to dissimilar records inside a zone.

Share this post