bsv_overlay_engine/
node_batch.rs

1//! A batched node request between peers that both answer it (engine 0.2.1,
2//! bsv-overlay-cloudflare #58).
3//!
4//! `POST /requestForeignGASPNodes` takes up to [`NODE_BATCH_MAX_OUTPOINTS`]
5//! outpoints and answers their nodes in one body of at most
6//! [`NODE_BATCH_MAX_BYTES`]. Each entry names its outpoint and carries either
7//! the node, as `/requestForeignGASPNode` answers it, or a refusal word. The
8//! route is ours: a reference peer answers it 404 and is asked one node at a
9//! time, as before (`overlay-services@480d77a src/GASP/OverlayGASPRemote.ts`
10//! has the single request only).
11//!
12//! What the sync does with an answer is in `GASPSync::prefetched_root`:
13//! every entry feeds the same code a single answer feeds.
14
15use crate::types::GASPNode;
16use serde::{Deserialize, Serialize};
17
18/// The most outpoints one batch request may name; a request over it is
19/// answered 400 with this number in the body.
20///
21/// 100: the engine's page ([`crate::gasp::ENGINE_GASP_SYNC_PAGE_LIMIT`]), so
22/// one body answers a page. The answering Worker reads one D1 row per
23/// outpoint (`find_output`, one statement), so a full request costs 100 of
24/// the 1,000 D1 queries a paid invocation allows (`backfill.rs`, the
25/// platform's limits as cited there).
26pub const NODE_BATCH_MAX_OUTPOINTS: usize = 100;
27
28/// The most bytes one batch answer may carry, its JSON envelope included.
29///
30/// 4 MiB (4,194,304). A Worker's answer has no size limit of its own short
31/// of the isolate's 128 MiB of memory (`backfill.rs`, the platform's limits
32/// as cited there); both ends hold the body, its parse and the nodes made
33/// from it at once, about three copies, so 4 MiB keeps one answer under a
34/// tenth of the isolate. A `tm_uhrp` node is a raw transaction (the one
35/// whose size is written down, 483 bytes: the 0.1.9 lane's brief) and at most a peer
36/// proof of [`crate::beef_limits::PEER_PROOF_MAX_BYTES`] (4,095 bytes), in
37/// hex with its keys about 9.4 KB, so a full request of 100 such nodes is
38/// about 0.94 MB and the count binds; the bytes bind only for nodes above
39/// about 41 KB on average. A node larger than the whole budget is answered
40/// [`refusal::OVER_BUDGET`] and asked alone on the single route.
41pub const NODE_BATCH_MAX_BYTES: usize = 4 * 1024 * 1024;
42
43/// The words of a per-entry refusal.
44pub mod refusal {
45    /// The peer does not hold the outpoint: its word, counted by the absence
46    /// rule exactly as a single request's `NodeNotFound` (an HTTP 400).
47    pub const NOT_FOUND: &str = "not_found";
48    /// The node alone is larger than [`super::NODE_BATCH_MAX_BYTES`].
49    pub const OVER_BUDGET: &str = "over_budget";
50    /// Anything else the single route would answer outside 2xx.
51    pub const ERROR: &str = "error";
52}
53
54/// One outpoint of a batch request.
55#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
56pub struct BatchOutpoint {
57    pub txid: String,
58    pub vout: u32,
59}
60
61impl BatchOutpoint {
62    /// The `txid.vout` form the sync keys outputs by.
63    pub fn key(&self) -> String {
64        format!("{}.{}", self.txid, self.vout)
65    }
66}
67
68/// The body of `POST /requestForeignGASPNodes`.
69#[derive(Debug, Clone, Default, Serialize, Deserialize)]
70#[serde(deny_unknown_fields)]
71pub struct NodeBatchRequest {
72    pub outpoints: Vec<BatchOutpoint>,
73}
74
75/// One entry of a batch answer: the node, or a refusal word.
76#[derive(Debug, Clone, Serialize, Deserialize)]
77pub struct NodeBatchEntry {
78    pub txid: String,
79    pub vout: u32,
80    #[serde(default, skip_serializing_if = "Option::is_none")]
81    pub node: Option<GASPNode>,
82    #[serde(default, skip_serializing_if = "Option::is_none")]
83    pub refused: Option<String>,
84}
85
86impl NodeBatchEntry {
87    pub fn key(&self) -> String {
88        format!("{}.{}", self.txid, self.vout)
89    }
90}
91
92/// The answer of `POST /requestForeignGASPNodes`. An outpoint the byte
93/// budget left out has no entry; the asker names it again in its next body.
94#[derive(Debug, Clone, Default, Serialize, Deserialize)]
95pub struct NodeBatchAnswer {
96    pub nodes: Vec<NodeBatchEntry>,
97}
98
99/// What a remote received for one batch request: the answer and the bytes
100/// of its body, which the sync holds to [`NODE_BATCH_MAX_BYTES`].
101#[derive(Debug, Clone, Default)]
102pub struct NodeBatch {
103    pub answer: NodeBatchAnswer,
104    pub bytes: usize,
105}
106
107/// The bytes of `{"nodes":[]}`, the envelope of an answer.
108const ENVELOPE_BYTES: usize = 12;
109
110/// The answer's packer: entries in the asked order while they fit in
111/// `budget` bytes, the commas between them counted. An entry larger than the
112/// whole budget on its own is replaced by its `over_budget` refusal; the
113/// entry that does not fit ends the answer, and the outpoints from it
114/// on are left out.
115pub(crate) struct Packer {
116    budget: usize,
117    used: usize,
118    pub(crate) answer: NodeBatchAnswer,
119}
120
121impl Packer {
122    pub(crate) fn new(budget: usize) -> Self {
123        Self {
124            budget,
125            used: ENVELOPE_BYTES,
126            answer: NodeBatchAnswer::default(),
127        }
128    }
129
130    fn size(entry: &NodeBatchEntry) -> usize {
131        serde_json::to_string(entry).map_or(usize::MAX, |s| s.len())
132    }
133
134    /// Add `entry`; `false` when the answer is full and packing must stop.
135    pub(crate) fn push(&mut self, entry: NodeBatchEntry) -> bool {
136        let comma = usize::from(!self.answer.nodes.is_empty());
137        let mut entry = entry;
138        let mut size = Self::size(&entry);
139        if ENVELOPE_BYTES.saturating_add(size) > self.budget {
140            entry = NodeBatchEntry {
141                txid: entry.txid,
142                vout: entry.vout,
143                node: None,
144                refused: Some(refusal::OVER_BUDGET.into()),
145            };
146            size = Self::size(&entry);
147        }
148        if self.used.saturating_add(comma).saturating_add(size) > self.budget {
149            return false;
150        }
151        self.used += comma + size;
152        self.answer.nodes.push(entry);
153        true
154    }
155}
156
157#[cfg(test)]
158mod tests {
159    use super::*;
160
161    fn node(hex_len: usize) -> GASPNode {
162        GASPNode {
163            graph_id: "aa.0".into(),
164            raw_tx: "0".repeat(hex_len),
165            output_index: 0,
166            proof: None,
167            tx_metadata: None,
168            output_metadata: None,
169            inputs: None,
170        }
171    }
172
173    fn entry(vout: u32, hex_len: usize) -> NodeBatchEntry {
174        NodeBatchEntry {
175            txid: "aa".into(),
176            vout,
177            node: Some(node(hex_len)),
178            refused: None,
179        }
180    }
181
182    #[test]
183    fn batch_021_the_packer_never_crosses_its_budget() {
184        let budget = 1_000;
185        let mut packer = Packer::new(budget);
186        let mut count = 0;
187        while packer.push(entry(count, 200)) {
188            count += 1;
189        }
190        let body = serde_json::to_string(&packer.answer).unwrap();
191        assert_eq!(body.len(), packer.used);
192        assert!(body.len() <= budget, "{}", body.len());
193        assert_eq!(count as usize, packer.answer.nodes.len());
194        assert!(count >= 3, "{count}");
195    }
196
197    #[test]
198    fn batch_021_a_node_over_the_whole_budget_is_refused_by_name() {
199        let mut packer = Packer::new(1_000);
200        assert!(packer.push(entry(0, 5_000)));
201        assert!(packer.push(entry(1, 10)));
202        let alone = &packer.answer.nodes[0];
203        assert!(alone.node.is_none());
204        assert_eq!(alone.refused.as_deref(), Some(refusal::OVER_BUDGET));
205        assert!(packer.answer.nodes[1].node.is_some());
206        let body = serde_json::to_string(&packer.answer).unwrap();
207        assert_eq!(body.len(), packer.used);
208    }
209
210    #[test]
211    fn batch_021_the_wire_shape() {
212        let request: NodeBatchRequest =
213            serde_json::from_str(r#"{"outpoints":[{"txid":"aa","vout":1}]}"#).unwrap();
214        assert_eq!(request.outpoints[0].key(), "aa.1");
215        assert!(serde_json::from_str::<NodeBatchRequest>(r#"{"outpoints":[],"x":1}"#).is_err());
216        let refused = NodeBatchEntry {
217            txid: "aa".into(),
218            vout: 1,
219            node: None,
220            refused: Some(refusal::NOT_FOUND.into()),
221        };
222        assert_eq!(
223            serde_json::to_string(&refused).unwrap(),
224            r#"{"txid":"aa","vout":1,"refused":"not_found"}"#
225        );
226        let served = serde_json::to_value(entry(0, 2)).unwrap();
227        assert_eq!(served["node"]["graphID"], "aa.0");
228        assert_eq!(served["node"]["rawTx"], "00");
229    }
230
231    /// The derivation's arithmetic, so a change to either bound is seen: a
232    /// full request of the largest `tm_uhrp` node the derivation names fits.
233    #[test]
234    fn batch_021_a_full_request_of_proven_uhrp_nodes_fits_the_budget() {
235        let mut node = node(483 * 2);
236        node.proof = Some("0".repeat(crate::beef_limits::PEER_PROOF_MAX_BYTES * 2));
237        let mut packer = Packer::new(NODE_BATCH_MAX_BYTES);
238        for vout in 0..NODE_BATCH_MAX_OUTPOINTS as u32 {
239            assert!(packer.push(NodeBatchEntry {
240                txid: "ab".repeat(32),
241                vout,
242                node: Some(node.clone()),
243                refused: None,
244            }));
245        }
246        let body = serde_json::to_string(&packer.answer).unwrap().len();
247        assert!(body < 1_000_000, "{body}");
248    }
249}
bsv_overlay_engine/node_batch.rs

bsv_overlay_engine/
node_batch.rs
