Crate dbsp

The dbsp crate implements a computational engine for continuous analysis of changing data. With DBSP, a programmer writes code in terms of computations on a complete data set, but DBSP implements it incrementally, meaning that changes to the data set run in time proportional to the size of the change rather than the size of the data set. This is a major advantage for applications that work with large data sets that change frequently in small ways.

The tutorial is a good place to start for a guided tour. After that, if you want to look through the API on your own, the circuit module is a reasonable starting point. For complete examples, visit the examples directory in the DBSP repository.

Theory

DBSP is underpinned by a formal theory:

• Budiu, Chajed, McSherry, Ryzhyk, Tannen. DBSP: Automatic Incremental View Maintenance for Rich Query Languages, Conference on Very Large Databases, August 2023, Vancouver, Canada

• Here is a presentation about DBSP at the 2023 Apache Calcite Meetup.

The model provides two things:

1. Semantics. DBSP defines a formal language of streaming operators and queries built out of these operators, and precisely specifies how these queries must transform input streams to output streams.

2. Algorithm. DBSP also gives an algorithm that takes an arbitrary query and generates an incremental dataflow program that implements this query correctly (in accordance with its formal semantics) and efficiently. Efficiency here means, in a nutshell, that the cost of processing a set of input events is proportional to the size of the input rather than the entire state of the database.

Crate overview

This crate consists of several layers.

• dynamic - Types and traits that support dynamic dispatch. We heavily rely on dynamic dispatch to limit the amount of monomorphization performed by the compiler when building complex dataflow graphs, balancing compilation speed and runtime performance. This module implements the type machinery necessary to support this architecture.

• typed_batch - Strongly type wrappers around dynamically typed batches and traces.

• trace - This module implements batches and traces, which are core DBSP data structures that represent tables, indexes and changes to tables and indexes. We provide both in-memory and persistent batch and trace implementations.

• operator::dynamic - Dynamically typed operator API. Operators transform data streams (usually carrying data in the form of batches and traces). DBSP provides many relational operators, such as map, filter, aggregate, join, etc. The operator API in this module is dynamically typed and unsafe.

• operator - Statically typed wrappers around the dynamic API in operator::dynamic.

Re-exports

• pub use crate::time::Timestamp;
• pub use algebra::DynZWeight;
• pub use algebra::ZWeight;
• pub use circuit::ChildCircuit;
• pub use circuit::Circuit;
• pub use circuit::CircuitHandle;
• pub use circuit::DBSPHandle;
• pub use circuit::RootCircuit;
• pub use circuit::Runtime;
• pub use circuit::RuntimeError;
• pub use circuit::SchedulerError;
• pub use circuit::Stream;
• pub use operator::input::IndexedZSetHandle;
• pub use operator::input::InputHandle;
• pub use operator::input::MapHandle;
• pub use operator::input::SetHandle;
• pub use operator::input::ZSetHandle;
• pub use operator::CmpFunc;
• pub use operator::FilterMap;
• pub use operator::OrdPartitionedIndexedZSet;
• pub use operator::OutputHandle;
• pub use trace::DBData;
• pub use trace::DBWeight;
• pub use typed_batch::Batch;
• pub use typed_batch::BatchReader;
• pub use typed_batch::FallbackKeyBatch;
• pub use typed_batch::FallbackValBatch;
• pub use typed_batch::FallbackWSet;
• pub use typed_batch::FallbackZSet;
• pub use typed_batch::FileIndexedWSet;
• pub use typed_batch::FileIndexedZSet;
• pub use typed_batch::FileKeyBatch;
• pub use typed_batch::FileValBatch;
• pub use typed_batch::FileWSet;
• pub use typed_batch::FileZSet;
• pub use typed_batch::IndexedZSet;
• pub use typed_batch::OrdIndexedWSet;
• pub use typed_batch::OrdIndexedZSet;
• pub use typed_batch::OrdWSet;
• pub use typed_batch::OrdZSet;
• pub use typed_batch::Trace;
• pub use typed_batch::TypedBox;
• pub use typed_batch::ZSet;

Modules

• algebra
  This module contains declarations of abstract algebraic concepts: monoids, groups, rings, etc.
• circuit
  Synchronous circuits over streams.
• dynamic
  This module contains type and trait declarations that support the DBSP dynamic dispatch architecture.
• mimalloc
• monitor
  Trace monitor that validates event traces from a circuit. It is used to test both the tracing mechanism and the circuit engine itself.
• operator
  DBSP stream operator implementations.
• profile
  Built-in profiling capabilities.
• storage
  Storage APIs for Feldera.
• time
  Logical time
• trace
  Traces
• tutorial
  Developer tutorial
• typed_batch
  Strongly typed wrappers around dynamically typed batch types.
• utils

Macros

• circuit_cache_key
  Declare an anonymous struct type to be used as a key in the cache and associated value type.
• circuit_cache_key_unsized
• count_items
• declare_trait_object
• declare_trait_object_with_archived
• declare_tuples
• declare_typed_trait_object
• derive_comparison_traits
  Derive PartialEq, Eq, PartialOrd, Ord for trait objects that wrap around concrete types that implement these traits.
• derive_erase
• indexed_zset
  Create an indexed Z-set with specified elements.
• lean_vec
• measure_items
• metadata
• num_entries_scalar
  Macro to implement NumEntries for a scalar type whose size is 1.
• zset
  Create a Z-set with specified elements.
• zset_set
  Create a Z-set with specified elements all with weight 1.

Enums

• Error

Traits

• DetailedError
• NumEntries
  Trait to report object size as the number of entries.

Functions

• default_hash
  Default hashing function used to shard records across workers.

Type Aliases

• Scope