⚡📦 CAR Pool & More 🚙💨 A Pragmatic Improvement to Sync Performance github.com/fission-suite/spec/car-pool
A presentation at IPFS þing in July 2022 in Reykjavík, Iceland by Brooklyn Zelenka
⚡📦 CAR Pool & More 🚙💨 A Pragmatic Improvement to Sync Performance github.com/fission-suite/spec/car-pool
The limitation of local knowledge is the fundamental fact about the setting in which we work, and it is a very powerful limitation – Nancy Lynch, A Hundred Impossibility Proofs for Distributed Computing
Some peers are “more peer” than others (especially in an operator context)
BROOKLYN ZELENKA JUSTIN JOHNSON @expede CTO @ Fission @justincjohnson IPFS Engineer @ Fission Won’t have time to cover everything in depth. Come talk to us after, or read the spec ;)
Caveat Trusted, Point-to-Point IPLD Transfer
The Problem Pain In Practice ❤🩹
The Problem Why?
The Problem Why? We 💕 IPLD Fission has deeply nested, cross-linked data that Cannot fit into browser storage Benefits from deduplication Has multiple writers Using mature, universally supported transports would be awesome “Light clients” Speed of light concerns
The Problem Food. Water. Shelter.
The Problem Food. Water. Shelter.
The Problem Flakiness in Browsers & CLI & GitHub Actions
The Problem Flakiness in Browsers & CLI & GitHub Actions 🖥
The Problem Are You There? 🤳
The Problem Are You There? 🤳 Keeping nodes reliably connected in production is extremely di cult (browser, server, desktop, mobile) Private networks don’t make sense for our use case ffi (We’d love to share an operator node architecture wish list with any maintainers, though)
The Problem Are You There? 🤳 Keeping nodes reliably connected in production is extremely di cult (browser, server, desktop, mobile) Private networks don’t make sense for our use case (We’d love to share an operator node architecture wish list with any maintainers, though) ffi Up/down over a HTTP Gateway is just LARPing decentralization 🌶
The Problem Are You There? 🤳 Keeping nodes reliably connected in production is extremely di cult (browser, server, desktop, mobile) Private networks don’t make sense for our use case (We’d love to share an operator node architecture wish list with any maintainers, though) Up/down over a HTTP Gateway is just LARPing decentralization 🌶 ffi Native push doesn’t make sense
The Problem Are You There? 🤳 Keeping nodes reliably connected in production is extremely di cult (browser, server, desktop, mobile) Private networks don’t make sense for our use case (We’d love to share an operator node architecture wish list with any maintainers, though) Up/down over a HTTP Gateway is just LARPing decentralization 🌶 Native push doesn’t make sense ffi 🖥
The Problem Are You There? 🤳 Keeping nodes reliably connected in production is extremely di cult (browser, server, desktop, mobile) Private networks don’t make sense for our use case (We’d love to share an operator node architecture wish list with any maintainers, though) Up/down over a HTTP Gateway is just LARPing decentralization 🌶 Native push doesn’t make sense ffi 🖥 💾
The Problem Bitswap Redux
The Problem Bitswap Redux
The Problem Bitswap Redux 🎁?
The Problem Bitswap Redux 🎁? 🎁!
The Problem Bitswap Redux 🎁? 👀 🎁!
The Problem Bitswap Redux 🎁? 👀 🎁! 🔑🌲?
The Problem Bitswap Redux 🎁? 👀 🎁! 🔑🌲? 🔑🌲!
The Problem Bitswap Redux 🎁? 👀 🎁! 🔑🌲? 🔑🌲! 👀
The Problem Bitswap Redux 🎁? 👀 🎁! 🔑🌲? 🔑🌲! 👀 💾 🎟 🖼?
The Problem Bitswap Redux 🎁? 👀 🎁! 🔑🌲? 🔑🌲! 👀 💾 🎟 🖼? 🎟!
The Problem Bitswap Redux 🎁? 👀 🎁! 🔑🌲? 🔑🌲! 👀 💾 🎟 🖼? 🎟! 👀
The Problem Bitswap Redux 🎁? 👀 🎁! 🔑🌲? 🔑🌲! 👀 💾 🎟 🖼? 🎟! 👀 🧸?
The Problem Bitswap Redux 🎁? 👀 🎁! 🔑🌲? 🔑🌲! 👀 💾 🎟 🖼? 🎟! 👀 🧸? 🧸!
The Problem Bitswap Redux 🎁? 👀 🎁! 🔑🌲? 🔑🌲! 👀 💾 🎟 🖼? 🎟! 👀 🧸? 🧸!
The Problem Bitswap Redux 🗜 🎁? 👀 🎁! 🔑🌲? 🔑🌲! 👀 💾 🎟 🖼? 🎟! 👀 🧸? 🧸!
The Problem Breadth vs Depth
The Problem Breadth vs Depth
The Problem Breadth vs Depth ✅
The Problem Breadth vs Depth ✅
The Problem Breadth vs Depth ✅ ❌
The Problem Breadth vs Depth ❌ ✅ ☝
Prior Art On the Shoulders of Giants
Prior Art IPFS Ecosystem
Prior Art IPFS Ecosystem Qri’s DSync GraphSync, Selectors (orthogonal) WNFS(v1) Hashed History Table Merkle Bloom
The Problem Papers 📜
The Problem Papers 📜 To Push or Pull: On Reducing Communication and Synchronization in Graph Computations What’s The Di erence? E cient Set Reconciliation Without Prior Context Synchronizing Namespaces with Invertible Bloom Filters The Hash History Approach for Reconciling Mutual Inconsistency HEX BLOOM: An E cient Method for Authenticity and Integrity Verification in Privacy-preserving Computing ffi ffi ff The Distributed Bloom Filter
CAR Mirror One-to-One
CAR Mirror Strategy
CAR Mirror Strategy Reduce graph scope Send index with request Use heuristics to find deduplication
CAR Mirror
CAR Mirror Balancing Factors
CAR Mirror Balancing Factors Latency Accuracy/Deduplication
CAR Mirror Balancing Factors Latency Accuracy/Deduplication
CAR Mirror Balancing Factors Latency Accuracy/Deduplication
CAR Mirror Balancing Factors Latency Equilibrium TL;DR We can a ord to be messy ff Accuracy/Deduplication
CAR Mirror First Reduce Scope
CAR Mirror First Reduce Scope AOT Mutable pointers (IPNS, DNSLink, ENS, di ed CID, etc) ff Previous CAR Mirror sessions
CAR Mirror First Reduce Scope AOT Mutable pointers (IPNS, DNSLink, ENS, di ed CID, etc) Previous CAR Mirror sessions Adaptive Optimization ff Previous CAR Mirror rounds
CAR Mirror First Reduce Scope AOT Mutable pointers (IPNS, DNSLink, ENS, di ed CID, etc) Previous CAR Mirror sessions Adaptive Optimization Previous CAR Mirror rounds No Overlap or Cold Start If the set is small, use random nodes ff “Worst case” looks very similar to Bitswap
CAR Mirror Back of the Napkin
CAR Mirror Back of the Napkin 500k nodes
CAR Mirror Back of the Napkin 500k nodes 46-59 chars + 1 delimiter each ~ average 53 chars each
CAR Mirror Back of the Napkin 500k nodes 46-59 chars + 1 delimiter each ~ average 53 chars each 53 ASCII chars x 500k nodes = 26.5MB
CAR Mirror Back of the Napkin 500k nodes 46-59 chars + 1 delimiter each ~ average 53 chars each 53 ASCII chars x 500k nodes = 26.5MB Gzipped ~ 11.5MB
CAR Mirror Back of the Napkin 500k nodes 46-59 chars + 1 delimiter each ~ average 53 chars each 53 ASCII chars x 500k nodes = 26.5MB Gzipped ~ 11.5MB
CAR Mirror Back of the Napkin 500k nodes 46-59 chars + 1 delimiter each ~ average 53 chars each 53 ASCII chars x 500k nodes = 26.5MB Gzipped ~ 11.5MB 🤔 ? r e t t e b o d e w Can
CAR Mirror Bloom Filter Primer
CAR Mirror Context and Heuristics
CAR Mirror Context and Heuristics 500k nodes @ FPP 1/1M = 1.71MB
CAR Mirror Context and Heuristics (Recommend +1 OOM) 500k nodes @ FPP 1/1M = 1.71MB
CAR Mirror Context and Heuristics (Recommend +1 OOM) 500k nodes @ FPP 1/1M = 1.71MB 93% savings! 👍
CAR Mirror Context and Heuristics (Recommend +1 OOM) 500k nodes @ FPP 1/1M = 1.71MB Gzipped ~ 896 KB 93% savings! 👍
CAR Mirror Context and Heuristics (Recommend +1 OOM) 500k nodes @ FPP 1/1M = 1.71MB 93% savings! 👍 Gzipped ~ 896 KB 92% savings! 👍
CAR Mirror Context and Heuristics (Recommend +1 OOM) 500k nodes @ FPP 1/1M = 1.71MB 93% savings! 👍 Gzipped ~ 896 KB 92% savings! 👍 AKA ~ 1 x OOM 🎉 Zero false positives on average
CAR Mirror Stages
CAR Mirror Stages Selection Narrowing Transmission Graph Status Cleanup
CAR Mirror Stages Selection Narrowing Transmission Graph Status Cleanup Next Round
CAR Mirror Over the Wire
CAR Mirror Over the Wire Bloom CID Roots CAR
CAR Mirror Over the Wire Requestor Pull Bloom CID Roots CAR
CAR Mirror Over the Wire Requestor Pull Bloom CID Roots CAR Requestor Push
Meta Pull Previous Round Bloom & Roots 🥺 🦸 📃🌸 Analyze New Roots New Bloom 📀📀📀📀📀 Updated Bloom & Roots Previous Round Hash Set Analyze & Fetch Response CAR Updated Hash Set
Meta Push Previous Round Bloom & Roots 🥺 🦸 Previous Round Hash Set 🥵 📀📀📀📀📀📃 Store & Analyze Request CAR DAG Bloom 🌸 📃 Updated Bloom & Roots Bloom & CID Roots Updated Hash Set
CAR Mirror Straggler Cleanup 🧹 🧹 🧹
CAR Mirror Graph Contraction
CAR Pool Many-to-One
CAR Pool Why
CAR Pool Why Recover multiple providers Stream in true parallel Work sharing Stepping stone to trustless network seeding (more later)
CAR Pool Requestor-Controlled Sharding A-H I-P Q-Z 🦸 🦸 🦸 📱
CAR Pool Invertible Bloom Filter (IBF) Primer
CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0
CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 (Not to scale 📏) 0 0 1 0 1 0 0
CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 (Not to scale 📏) XOR 3 XOR 2 XOR 6 XOR 4 XOR 7 XOR 5 XOR 2
CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 (Not to scale 📏) XORed CIDs XOR 3 XOR 2 XOR 6 XOR 4 XOR 7 XOR 5 XOR 2
CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 (Not to scale 📏) Counter XORed CIDs XOR 3 XOR 2 XOR 6 XOR 4 XOR 7 XOR 5 XOR 2
CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 (Not to scale 📏) Counter XORed CIDs XOR 3 XOR 2 XOR 6 XOR 4 XOR 7 XOR 5 XOR 2 XOR 1 XOR 4 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3
CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 (Not to scale 📏) Counter XORed CIDs XOR 3 XOR 2 XOR 6 XOR 4 XOR 7 XOR 5 XOR 2 XOR 1 XOR 4 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3 +
CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 (Not to scale 📏) Counter XORed CIDs XOR 3 XOR 2 XOR 6 XOR 4 XOR 7 XOR 5 XOR 2 XOR 1 XOR 4 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3
CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 (Not to scale 📏) Counter XORed CIDs XOR 3 XOR 2 XOR 6 XOR 4 XOR 7 XOR 5 XOR 2 XOR 1 XOR 4 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3 XOR 1 XOR 4 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3
CAR Pool Invertible Bloom Filter (IBF) Primer 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 (Not to scale 📏) Counter XORed CIDs XOR 3 XOR 2 XOR 6 XOR 4 XOR 7 XOR 5 XOR 2 XOR 1 XOR 4 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3
XOR 1 XOR 4 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3
CAR Pool Provider Coordinator 🦸 🌸🔁 🤹 📱 🌸🔁 🦸
CAR Pool Linear Network Coding
BONUS: Wild Ideas for Future Research PSI, PSU, NN Compression, XOR-Folding, etc
CAR Pool PSI youtube.com/watch?v=tsCD4i9SpxA
CAR Pool XOR-Folding https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3527984
An Eager Backbone 🦴 Content Addressed Alliance Teaser
🎉 Thank You, IPFS þing 🇮🇸 https://fission.codes ✨ github.com/fission-suite/spec ✨ {brooklyn,justin}@fission.codes @expede & @justincjohnson
