docs: arbitrarily reordering & sequence numbers
Document the arbitrary reordering of concurrent writes in an ingester,
and the potential divergence of WAL entries / buffered state.
Also documents that in ingester2, sequence numbers only identify writes,
not their ordering.
//! IOx Ingester V2 implementation.
+//!
+//! ## Write Reordering
+//!
+//! A write that enters an `ingester2` instance can be reordered arbitrarily
+//! with concurrent write requests.
+//!
+//! For example, two gRPC writes can race to be committed to the WAL, and then
+//! race again to be buffered into the [`BufferTree`]. Writes to a
+//! [`BufferTree`] may arrive out-of-order w.r.t their assigned sequence
+//! numbers.
+//!
+//! This can also lead to the ordering of entries in the [`wal`] diverging from
+//! the order of ops applied to the [`BufferTree`] (see
+//! <https://github.com/influxdata/influxdb_iox/issues/6276>).
+//!
+//! This requires careful management, but ultimately allows for high levels of
+//! parallelism when handling both writes and queries, increasing the
+//! performance of both.
+//!
+//! Because of re-ordering, ranges of [`SequenceNumber`] cannot be used to
+//! indirectly equality match (nor prefix match) the underlying data;
+//! non-monotonic writes means overlapping ranges do not guarantee equality of
+//! the set of operations they represent (gaps may be present). For example, a
+//! range of sequence numbers bounded by `[0, 2)` for thread 1 may not contain
+//! the same op data as another thread T2 with range with the same bounds due to
+//! reordering causing T1 to observe `{0, 1, 2}` and T2 observing `{0, 2}` and
+//! after a faulty range comparison, `{1}` to converge.
+//!
+//! [`BufferTree`]: crate::buffer_tree::BufferTree
+//! [`SequenceNumber`]: data_types::SequenceNumber
#![allow(dead_code)] // Until ingester2 is used.
#![deny(rustdoc::broken_intra_doc_links, rust_2018_idioms)]
