differential_dataflow/operators/int_proxy/
mod.rs

1//! Backend-agnostic operator tactics using ordered, copyable proxies.
2//!
3//! The tactics support custom operator implementations without rebuilding the non-trivial and often non-obvious time-based logic that supports them.
4//! They run DD's operator logic over consolidated `[((key, val), time, diff)]` lists.
5//! Keys identify independent groups; values identify data within a group.
6//! Both require only `Copy + Ord` and need not be the types presented to user logic.
7//! The tactics elicit proxies, perform time and difference computations, and return proxies to the backend for interpretation.
8//! The backend is oblivious to the navigation of time, and the operator to the backend's implementation.
9//!
10//! The default proxy types remain `u64`, with the interpretation described below.
11//! Exact key proxies do not require collision handling.
12//!
13//! Input and output value proxies may have different types.
14//! Standalone reduce calls can use borrowed strings whose storage outlives the call and any pending keys.
15//! Deferred join work still requires `'static` proxies.
16//! Borrowing directly from backend-owned presentation storage needs a further lifetime or container abstraction.
17//!
18//! # The two integers
19//!
20//! The two integers play the role of key and value to the operator, but their connection
21//! to the key and value of the intended computation is nuanced.
22//!
23//! *   `key_hash: u64` — a content hash of the intended key.
24//!     This value should be identical for each instance of identical keys.
25//!     The value is not assumed to be a well-distributed quality hash, only distinct.
26//!     There may be collisions, and the next identifier should assist with this.
27//!
28//! *   `value_id: u64` — an ephemeral intra-hash value identifier.
29//!     These values should be distinct for each distinct datum with the same key_hash.
30//!     In particular, they should account for the conventional `(key, val)` data,
31//!     rather than only the value component, to avoid errors due to colliding keys.
32//!
33//! The key hash acts as an independence marker: keys with different hashes will be isolated,
34//! and their incremental updates performed independently. By forcing the keyspace into `u64`,
35//! there is the risk of hash collision. This means that per-hash logic should be prepared for
36//! this, and should not discard key information that remains semantically important.
37//!
38//! Informally, one should mentally rewrite one's `(key, val)` into `(hash(key), (key, val))`.
39//! Retaining the `key` as data provides access to it, and allows one to certainly respond to
40//! hash collisions that can occur. Although the operator will treat `hash(key)` as the "key",
41//! the backend implementation can apply its own subseqent logic to resolve unwanted matches.
42//! As examples, join logic can follow its hash-wise cross product with key-based filtering,
43//! and reduce logic can group by keys and apply logic to slices within the per-hash list.
44//! Both are welcome to efficiently notice that there have been no collisions and optimize,
45//! or to ignore the risk entirely and live dangerously.
46
47mod history;
48
49pub mod join;
50pub mod reduce;
51mod pending;
52pub mod frontier;
53pub mod vec_backend;
54
55/// A consolidated collection of `[((key, val), time, diff)]` proxies.
56///
57/// The [`debug_assert_sorted_bridge`] method is (and can be) used to validate this property.
58pub type ProxyBridge<T, R, K = u64, V = u64> = Vec<((K, V), T, R)>;
59
60/// Debug check that a presented [`ProxyBridge`] is consolidated.
61///
62/// Operator harnesses use the test to flag backend implementations that do not uphold it. It is
63/// public so that a tactic built outside this crate over the same bridges, such as dogs3's proxy
64/// half join, checks the contract its backends owe with the same test.
65pub fn debug_assert_sorted_bridge<T: Ord, R, K: Copy + Ord, V: Copy + Ord>(bridge: &ProxyBridge<T, R, K, V>, who: &str) {
66    debug_assert!(
67        bridge.windows(2).all(|w| (w[0].0, &w[0].1) < (w[1].0, &w[1].1)),
68        "{}: a presented bridge must be sorted & consolidated by ((key, val), time)",
69        who,
70    );
71}
72
73pub use join::{JoinInstance, ProxyJoinBackend, ProxyJoinTactic};
74pub use reduce::{ProxyReduceBackend, ProxyReduceTactic, ReduceInstance, ReduceWindow};
75pub use frontier::{read_as_of, BackendFrontier};
76
77/// A position between windows of an ordered key space.
78/// No minimum key or successor operation is required.
79#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
80pub enum KeyPosition<K> {
81    /// No keys have been visited.
82    Start,
83    /// The inclusive lower bound on keys still to visit.
84    At(K),
85    /// All keys have been visited.
86    End,
87}
differential_dataflow/operators/int_proxy/mod.rs

differential_dataflow/operators/int_proxy/
mod.rs
