O(n.log.n) Set Reconciliation for Efficient System Design

Yours, Mine, and Ours Reconciling SETS in O(n log n) Where n = Set-Difference-Size (Not Set-Size) Offers New Opportunities in System Design! Pat Helland September 2024 These are my own ideas and opinions Not necessarily reflective of the position of my employer, Salesforce

Outline Practical Rateless Set Reconciliation Concepts Items & Slot-Sequences Items & Slots Encoding & Decoding O(n log n) Set-Difference Summary: Set Reconciliation Discussing Emerging Opportunities Conclusion 2

Inspiration for Scalable Set Reconciliation SET-A SET-B A A C D E F G XOR can find ONE missing value in O(1) time Assuming there s only one 1 million values XORed (1 million + 1) values O(1) C B C D E F G A B D E F G C A D E F G Problem: Find MORE THAN ONE missing element cheaply Encode a logarithmic set to find the difference Find the difference in O(n log n) of the DIFFERENCE, not SET SIZES Variant of Erasure Coding Specifically Fountain Codes A forward error correction mechanism for message transmission. Cross between data communication error recovery and storage error recovery A B C F Erasure codes are not JUST for data you ve lost They can be for data you don t have yet! 3

Practical Rateless Set Reconciliation New Paper SIGCOMM (Aug 2024) Set-A Set-B Yang, Gilad, & Alizadeh. Practical Rateless Set Reconciliation SMALL Prefix of Encoded Set-A Set Reconciliation SYMMETRIC DIFFERENCE: (A B) / (A B) Very useful for LARGE sets with small-ish differences Less than O(n log n) work for n = size of SET-DIFFERENCE Reconciliation is worst case O(n log n) where n is the difference between the two sets. STOP!! Server-A + Symmetric Difference (items in 1 set but not both) Paper describes an analysis claiming excellent performance and it points to an open-source implementation of the algorithm. TINY Difference TINY Prefix Sent & TINY Computation Server-B Observes the Applicability of Erasure Codes to Sets that Do Not Actually Exist YET! ----------------------------------------------------- Just Agree on What the Set IS ! SIGCOMM (Aug 2024) 4

Goals and Underlying Techniques SET DIFFERENCE Cost is O(n log n) where n is the cardinality of the DIFFERENCE Goals: Efficient Set Operations and Reconciliation Assume two sets of fixed length items (Set-A and Set-B) Small Underlying Techniques: Symmetric Difference: Both for (ITEMS in SETS) and (ITEMS in SLOTS) Remove common ITEMS leaving only the difference . (A - B) (B A) Also described as (A B) / (A B) Pseudo-Random Sequences: Deterministic map ITEMS Deterministically regenerate the sequence of slots based solely on the ITEM itself Infinite Sequence-of-Slots Exponential Distribution: New slots in Sequence-of-Slots have ever larger gaps Rapidly dropping probability of colliding with a slot from another item s sequence 5

Concepts and Terms A fixed-length UNIQUE set element (includes a HASH code derived from the item) There are many ways to extend this to a variable length item payload We don t discuss variable length payloads in this talk Item A sequence of slots identified by their index (encodes 1 or more items in slot) Slot contents and slot-index are transmitted in increasing order starting at SLOT-ZERO Empty slots cost nothing to transmit because index numbers can skip forward in a prefix Prefix of an Encoded Set One element of an encoded prefix of a set (includes its slot-index) Slot Contents(0 or more items) 0: Empty Slot: Exactly 0 items in the slot 1: Pure Slot: Exactly 1 item in the slot >1: Impure Slot: > 1 items added into the slot Slot ITEM-SUM XOR of slot s item values Slot MERGE XOR contents of 2 slots 1 technique to increase & decrease items present HASH-SUM XOR of slot s item hashes Sequence of slot indexes: (generated per-item)(from ZERO to Infinity) Uses ITEM as seed Unique and repeatable per-ITEM Per-Item Sequence of Slot-Indexes PSEUDO-RANDOM EXPONENTIAL Gap to next index in sequence approximately doubles 6

Outline Practical Rateless Set Reconciliation Concepts Items & Slot-Sequences Items & Slots Encoding & Decoding O(n log n) Set-Difference Summary: Set Reconciliation Discussing Emerging Opportunities Conclusion 7

Understanding Slots Every item maps to an infinite sequence of slots Larger slot index Fewer items in slot ------------------------ More become PURE ------------------------ More become EMPTY Per-item sequence of slot indexes (from ZERO to Infinity) Starts at ZERO Every item maps to slot zero Uses ITEM as seed Unique and repeatable per-ITEM Pseudo-Random Exponential Gap to next index in sequence approximately doubles The beginning of the prefix is very dense Same item Same sequence for all sets Deterministic Each slot has 0 or more items combined into it The tail of the prefix becomes sparse # of Items in Slot Term Used Detected by: 0 Empty Slot (ITEM-SUM = 0) AND (HASH-SUM = 0) HASH-SUM = Hash (ITEM-SUM) 1 Pure Slot HASH-SUM Hash (ITEM-SUM) >1 Impure Slot 8

Infinite Sequence-of-Slots per Item Each item maps to an infinite sequence of slots All items start at ZERO Gap to next slot is pseudo-random and approximately doubles each time Gap (Prev-Slot-Index + 1) * 2 * PRNG(Item) Next-Slot-Index Prev-Slot-Index + Gap <Gap to Next-Slot Averages about 2X Last Gap> PRNG (Pseudo-Random-Number Generator) Seed = ITEM s Set Element Returns a sequence of random values [0..1] PRNG distribution impacts encoding density Need not be evenly distributed across [0..1] Paper focuses on encoding density and efficiency Sequence of Slots 1 2 3 4 5 6 7 8 9 0 A A B B B C C C D D D D D D 1 0 A A 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 A A 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 A A 2 8 2 9 3 0 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 4 0 4 1 4 2 A B A B B B C C C C A A B A A A Item-A Item-B Item-C Item-D B B C C C B B B B B B B B B B C C C C C C C C C C D D D D D D D D D Infinite Sequence Possible places that an item MAY live if needed for a prefix Essential Properties of a Sequence-of-Slots-Generator Pseudo-Random using Item as a Seed: Deterministic & Repeatable PER- ITEM Exponential Increase of Slot-Indexes: Probability of collisions drops rapidly 9

Generators: Find Items Sharing the Next Slot Consider an event-horizon with the set of items in the next larger slot-index Start at ZERO, add elements, move to next slot that is non-empty for the items in question Move to next slot with some generated items Skip empty slots not in the priority queue Add items into slot Per-item, generate next slot-index in its sequence Keep a priority queue of next slots to come Sequence of Slots 1 2 3 4 5 6 7 8 9 0 A A B B B C C C D D D D 1 0 A A 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 A A 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 A A 2 8 2 9 3 0 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 4 0 4 1 4 2 A B C A B A A Item-A Item-B Item-C Item-D B C B C C B B B B B B B B B C C C C C C C C C D D D D D D D D B C C B A B B A C C A B A B D D A A D D B B C C A D D A B B A A C C D D C C B B D D C C C C B B Priority Queue of Next Slots . 10

Outline Practical Rateless Set Reconciliation Concepts Items & Slot-Sequences Items & Slots Encoding & Decoding O(n log n) Set-Difference Summary: Set Reconciliation Discussing Emerging Opportunities Conclusion 11

Envisioning a Slot & Its Items Sequence of Slots 1 2 3 4 5 6 7 8 9 0 A B C D D D D 1 0 A A 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 A A A B C A B B A A A B B Item-A Item-B Item-C Item-D B B B B C C C C C C D D D D Slot-0 ITEM-SUM: A Slot-4 ITEM-SUM: A Slot-8 ITEM-SUM: A B C D B C D B C D HASH-SUM: A B C D HASH-SUM: A B C D HASH-SUM: A B C D ITEM-A Item Value Hash of Item ITEM-B Item Value Hash of Item ITEM-C Item Value Hash of Item ITEM-D Item Value Hash of Item ITEM-C Item Value Hash of Item ITEM-D Item Value Hash of Item ITEM-C Item Value Hash of Item 12

MERGE Two Slots MERGE Slot-X ITEM-SUM: A Slot-Y ITEM-SUM: A Merged (Slot-X & Slot-Y) ITEM-SUM: A B C D B C D B A B HASH-SUM: A B C D HASH-SUM: A B C D HASH-SUM: A B A B ITEM-A Item Value Hash of Item ITEM-B Item Value Hash of Item ITEM-A Item Value Hash of Item ITEM-B Item Value Hash of Item ITEM-C Item Value Hash of Item ITEM-D Item Value Hash of Item ITEM-C Item Value Hash of Item ITEM-D Item Value Hash of Item ITEM-C Item Value Hash of Item ITEM-D Item Value Hash of Item MERGE combines two cells by XORing their contents ITEM-SUMs from each are XORed New ITEM-SUM HASH-SUMs from each are XORed New HASH-SUM 13

Outline Practical Rateless Set Reconciliation Concepts Items & Slot-Sequences Items & Slots Encoding & Decoding O(n log n) Set-Difference Summary: Set Reconciliation Discussing Emerging Opportunities Conclusion 14

Encoding a Set of Items, One at a Time Building an encoding from a set of items (one item at a time) Start at Slot-Zero, and MERGE the item to Slot-Zero (XOR Item & XOR Hash) LOOP: < through the item s sequence of slots> IF PURE-SLOT Exit loop IF IMPURE-SLOT Keep going Move to next slot in item s sequence MERGE the item to next slot Next, process another item 15

ENCODING a Set: Add Item C Sequence of Slots 1 2 3 4 5 6 7 8 9 0 A B C D D D D 1 0 A A 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 A Start with A, B, & D in the set Add item C by following its sequence Add C to Slot-0 Add C to Slot-4 Add C to Slot-8 PURE! Done Adding C A B C C A A B B A A B B Item-A Item-B Item-C Item-D B B B Not PURE Continue C C C C C C C C Not PURE Continue D D D Slot-0 ITEM-SUM: A ITEM-SUM: A Slot-0 Slot-4 ITEM-SUM: A ITEM-SUM: A Slot-4 Slot-8 ITEM-SUM: A ITEM-SUM: A Slot-8 B B C C D D B B C C D D B B C C D D HASH-SUM: A HASH-SUM: A B B C C D D HASH-SUM: A HASH-SUM: A B B C C D D HASH-SUM: A HASH-SUM: A B B C C D D ITEM-A Item Value Hash of Item Hash of Item ITEM-A Item Value ITEM-B Item Value Hash of Item Hash of Item ITEM-B Item Value ITEM-C Item Value Hash of Item ITEM-D Item Value Hash of Item Hash of Item ITEM-D Item Value ITEM-C Item Value Hash of Item ITEM-D Item Value Hash of Item Hash of Item ITEM-D Item Value ITEM-C Item Value Hash of Item 16

Decoding a Set by Peeling An encoded set comprises many slots # of Items in Slot Detected by: (ITEM-SUM = 0) AND (HASH-SUM = 0) 0 Empty Slot HASH-SUM = Hash (ITEM-SUM) 1 Pure Slot HASH-SUM Hash (ITEM-SUM) >1 Impure Slot PEELING: Decode incrementally back to SLOT-ZERO Look for Pure Slots: HASH-SUM = Hash (ITEM-SUM) PEEL the Pure Slot back to SLOT-ZERO MERGE the Pure Slot into each slot in its sequence back to (and including SLOT-ZERO) MERGE means XOR the Pure-Slot into the other slots (both Item-Sum and Hash-Sum) Continue until SLOT-ZERO is Empty: (ITEM-SUM = 0) AND (HASH-SUM = 0) 17

Decoding a Set from a Prefix Sequence of Slots 1 2 3 4 5 6 7 8 9 0 A B C D D D D 1 0 A 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 A Receive encoded set a slot at a time Wait until a pure slot arrives Slot 7 is a PURE value for B! Remember B Start PEEL-ing it from the encoding A B C A A B B A B B A Item-A Item-B Item-C Item-D B B B C C C C D D Slot-0 ITEM-SUM: A Slot-1 Slot-3 Slot-4 Slot-7 B C D ITEM-SUM: A B ITEM-SUM: A B ITEM-SUM: C D ITEM-SUM: B HASH-SUM: A B C D HASH-SUM: A B HASH-SUM: A B HASH-SUM: C D HASH-SUM: B ITEM-C Item Value Hash of Item ITEM-A Item Value Hash of Item ITEM-B Item Value Hash of Item ITEM-A Item Value Hash of Item ITEM-A Item Value Hash of Item ITEM-B Item Value Hash of Item Hash of Item ITEM-B Item Value ITEM-C Item Value Hash of Item ITEM-D Item Value Hash of Item ITEM-B Item Value Hash of Item ITEM-B Item Value Hash of Item ITEM-D Item Value Hash of Item 18

PEEL Item B from the Slots in the Prefix Sequence of Slots 1 2 3 4 5 6 7 8 9 0 A A A A A A B C D 1 0 A 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 A PEEL Item-B from each slot it is in Follow the Sequence-of-Slots for B Item-A Item-B Item-C Item-D B B C D D B B B B B B B B B B C D C C C Remember that A is now PURE in Slot-3. D D B B B B B B B B B Stop PEELing B at Slot-Zero PURE Slot-7 starts the PEELING Slot-0 ITEM-SUM: A ITEM-SUM: A Slot-0 Slot-1 Slot-1 Slot-1 Slot-3 Slot-3 Slot-3 Slot-7 Slot-7 Slot-4 B C C D D ITEM-SUM: A ITEM-SUM: A ITEM-SUM: A B B ITEM-SUM: A ITEM-SUM: A ITEM-SUM: A B B ITEM-SUM: C D ITEM-SUM: B ITEM-SUM: ZERO HASH-SUM: A HASH-SUM: A B C D D C HASH-SUM: A HASH-SUM: A HASH-SUM: A B B HASH-SUM: A HASH-SUM: A HASH-SUM: A B B HASH-SUM: C D HASH-SUM: B HASH-SUM: ZERO ITEM-C Item Value Hash of Item ITEM-A Item Value Hash of Item Hash of Item ITEM-A Item Value ITEM-B Item Value Hash of Item ITEM-A ITEM-A Item Value Hash of Item Hash of Item Hash of Item ITEM-A ITEM-A Item Value Hash of Item Hash of Item Hash of Item ITEM-A Item Value Item Value ITEM-A Item Value Item Value ITEM-B Item Value Hash of Item ITEM-C Item Value Hash of Item Hash of Item ITEM-C Item Value ITEM-D Item Value Hash of Item Hash of Item ITEM-D Item Value ITEM-B Item Value Hash of Item Hash of Item ITEM-B Item Value Hash of Item Item Value ITEM-B Item Value ITEM-B Item Value ITEM-D Item Value Hash of Item 19

Now, You Can PEEL Item-A Sequence of Slots 1 2 3 4 5 6 7 8 9 0 A A A B C D 1 0 A 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 A Now, PURE slots with Item-A exist Extract Item-A from the Encoding PEEL them out A A B C D D A A B B B A A B B B Item-A Item-B Item-C Item-D B B B C D C C C Remember that A is now PURE in Slot-3. D D A A A A A A A A Stop PEELing A at Slot-Zero PURE Slot-3 starts the PEELING Slot-4 Slot-0 ITEM-SUM: A ITEM-SUM: C Slot-0 Slot-1 Slot-1 Slot-3 Slot-3 C D D ITEM-SUM: C D ITEM-SUM: A ITEM-SUM: ZERO ITEM-SUM: A ITEM-SUM: ZERO HASH-SUM: A HASH-SUM: C C D D HASH-SUM: C D HASH-SUM: A HASH-SUM: ZERO HASH-SUM: A HASH-SUM: ZERO ITEM-C Item Value Hash of Item ITEM-A Item: Value ITEM-A Item Value Hash of Item ITEM-A Item Value Hash of Item ITEM-A Item Value Hash of Item Hash of Item ITEM-D Item Value Hash of Item ITEM-C Item Value Hash of Item Hash of Item ITEM-C Item Value ITEM-D Item Value Hash of Item Hash of Item ITEM-D Item Value 20

When Slot-8 Arrives, PEEL Out C Sequence of Slots 1 2 3 4 5 6 7 8 9 0 A B B B B B C 1 0 A 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 A Keep accepting prefix slots Slot-8 is PURE with C Extract C from encoding PEEL Out C A A B C D D A B Item-A Item-B Item-C Item-D B B B B C C C C D D C C C C C D D C C C C C C C C C C C Stop PEELing C at Slot-Zero Remember that D is now PURE in Slot-4. Slot-4 Slot-4 Slot-0 ITEM-SUM: C ITEM-SUM: D Slot-0 Slot-8 Slot-8 D ITEM-SUM: C ITEM-SUM: D D ITEM-SUM: C ITEM-SUM: ZERO Finally, PEEL D and notice that SLOT-ZERO is empty HASH-SUM: C HASH-SUM: D D HASH-SUM: C HASH-SUM: D D HASH-SUM: C HASH-SUM: ZERO ITEM-C Item Value Hash of Item ITEM-C Item Value Hash of Item Hash of Item ITEM-C Item Value The set is decoded! ITEM-D Item Value ITEM-C Item Value Hash of Item ITEM-D Item Value Hash of Item Hash of Item ITEM-D Item Value ITEM-D Item Value Hash of Item Hash of Item 21

Outline Practical Rateless Set Reconciliation Concepts Items & Slot-Sequences Items & Slots Encoding & Decoding O(n log n) Set-Difference Summary: Set Reconciliation Discussing Emerging Opportunities Conclusion 22

Set-Difference from Prefix of Encoding Slots & Items Item-F F F F F F F A B A B C C A A A A A A Item-A Item-B Item-C Reconcile Slot-Zero Set-A B B C C B A B C F A C D E F G C C C C A B C F B D E G C A D E F G A A C D D E F A C A A C C A A A C Item-A Item-C Item-D Item-E Slots & Items C D C C A B C D E F G Set-B D D E E F G G G E E E F F E Symmetric Difference F Item-F G G G Item-G Peel B B Peel E E B D E G G B D B B (A B) / (A B) Peel G G E E E G G E E Peel D D 23

Understanding O(n log n) DIFFERENCE 1,000,000 items the same 1 item is DIFFERENT SET-A SET-B Recall how we found ONE item of difference: Slot by slot, XOR the sets O(1) How about finding THREE items of difference? Slot by slot, XOR the sets O(n log n) 3 (2-4 or so) Sequence of Slots 1 2 3 4 5 6 7 8 9 0 A B C C C C C C C A A C D E F C D B C D A B C D A 1 0 A 1 1 1 2 1 3 1 4 A B B B A A A B B A A A A B B B Item-A A B C B B B B Item-B Item-C 1,000,000 items the same 3 items are DIFFERENT SET-B SET-A A D E F Peel C C Slot-10 Slot-11 Slot-12 Slot-13 Slot-14 Slot-8 Slot-0 Slot-0 Slot-1 Slot-1 Slot-2 Slot-2 Slot-3 Slot-3 Slot-4 Slot-4 Slot-5 Slot-5 Slot-6 Slot-6 Slot-7 Slot-7 Slot-9 C B C D B D SET A Peel B B Notice A is pure D A Slot-10 Slot-11 Slot-12 Slot-13 Slot-14 Slot-8 Slot-0 Slot-0 Slot-1 Slot-1 Slot-2 Slot-2 Slot-3 Slot-3 Slot-4 Slot-4 Slot-5 Slot-5 Slot-6 Slot-6 Slot-7 Slot-7 Slot-9 SET B Peel A A A A B C C 24

Outline Practical Rateless Set Reconciliation Concepts Items & Slot-Sequences Items & Slots Encoding & Decoding O(n log n) Set-Difference Summary: Set Reconciliation Discussing Emerging Opportunities Conclusion 25

Summary of Set Reconciliation Practical Rateless Set Reconciliation: New technique for SET DIFFERENCE Low cost: Set difference in less than O(n log n (DIFFERENCE)) NOTO(n log n (SET-SIZE)) Leverages three concepts: Per-Item infinite slot sequence Exponential and pseudo-random Always starts at ZERO XOR (symmetric difference) per slot Items in both slots are removed after XOR PURE slots start peeling of items Peel (XOR) to remove item IMPURE slots until Slot-ZERO is 0 Each set has an encoding created for it Flexible encoding:pre-calculated(faster to get) or dynamically calculated(less storage) Reconciliation in either (or both) directions PREFIX transmission:(Prefix of encoding) When enough, receiver says STOP Transmission is a prefix of the encoding of a static set Receiver reconciles PREFIX with a local set: XOR of slots rapidly finds difference Each side can send batches concurrently Reconciles correctly 26

Outline Practical Rateless Set Reconciliation Concepts Items & Slot-Sequences Items & Slots Encoding & Decoding O(n log n) Set-Difference Summary: Set Reconciliation Discussing Emerging Opportunities Conclusion 27

Let Me Tell You about Gossip Protocols Efficient Gossip Protocols Many replicas of a set Each replica just squirts a prefix encoding to ANY other replica SET-DIFFERENCE Receiving replica rapidly gets only new items Effectively free for any items the receiver already had New items propagate in O(n log n) of number of replicas An Algorithmic variant modifies the SLOT structure to include a COUNT field (slot s COUNT of items) When a SET-DIFFERENCE is performed, COUNT tells the receiving server WHICH set had the new item Count = 1 means PURE from local set Count = -1 means PURE from remote set Receiver only ADDS incoming items into its replica See Practical Rateless Set Reconciliation (SIGCOMM 2024) for details of using COUNT to differentiate which of the sets had the item not in the other set Extremely efficient GOSSIP across many replicas Each new item is peeled out EXACTLY ONCE at each replica Items do NOT have a prescribed delivery order but they DO arrive exactly once! 28

Rapid Database Repair Occasionally faulty DBs Fix a bounded number of faults without changing roundtrips Better than Merkle Deadlines and Commitment (I know what you knew) Agreeing to existence without knowing contents Uncoordinated data discovery in O(n log n) time Pat s fascination came from tracking changes in scalable OLTP systems Replication can consolidate quorum state in very short time 29

Outline Practical Rateless Set Reconciliation Concepts Items & Slot-Sequences Items & Slots Encoding & Decoding O(n log n) Set-Difference Summary: Set Reconciliation Discussing Emerging Opportunities Conclusion 30

Takeaways In the past, DBs adjudicated change Not just the truth of the transaction log! Efficient event processing is emerging as an important pattern We can have vibrant sets of knowledge Rapidly visible to many servers Now, they can discover change Fast reconciliation can change the nature of dynamic systems Faster (accurate) knowledge of recent events across the system Likely can be used to improve existing systems It s essential to track the frontiers between disciplines Fountain codes (in data communications) have been around since 1998 Applying them to virtual (not yet reified) sets is exciting 31

The End! 32

Some Special Tricks CLOSED & OPEN sets Bounding time Bounding time Single timekeeper Bounding time Quorum of timekeepers Efficient subsets from an encoded set Many subsets per set: SLOT-ZERO of a subset precisely represents the subset s membership Consider a hierarchical key space of N columns Each subtree can be represented by its SLOT-ZERO of membership Peeling of a subset can be done by keeping delta slots while peeling the subset Set remains read-only Copy-on-Write to maintain set variations Encoded sets may use copy-on-write to efficiently capture variable state SET-UNION stops when slot-by-slot (from 0 forward) symmetric addition of slots exceeds the smaller of the sets Checking item membership within an in-memory encoding Slot procession can be calculated by CPU speculation Ignore empty-slots (for a moment) CPU cache can be predictively fetched for procession Compressing out empty slots while still using CPU speculation??? 33