nautilus_model/orderbook/
aggregation.rs

1// -------------------------------------------------------------------------------------------------
2//  Copyright (C) 2015-2026 Nautech Systems Pty Ltd. All rights reserved.
3//  https://nautechsystems.io
4//
5//  Licensed under the GNU Lesser General Public License Version 3.0 (the "License");
6//  You may not use this file except in compliance with the License.
7//  You may obtain a copy of the License at https://www.gnu.org/licenses/lgpl-3.0.en.html
8//
9//  Unless required by applicable law or agreed to in writing, software
10//  distributed under the License is distributed on an "AS IS" BASIS,
11//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12//  See the License for the specific language governing permissions and
13//  limitations under the License.
14// -------------------------------------------------------------------------------------------------
15
16//! Functions related to normalizing and processing top-of-book events.
17
18use crate::{
19    data::order::BookOrder,
20    enums::{BookType, RecordFlag},
21};
22
23/// Generates a stable order ID from a price value.
24///
25/// # High-Precision Safety
26///
27/// Under the `high-precision` feature, `PriceRaw` is `i128` (up to ~1.7e29).
28/// Casting to `u64` would truncate the upper bits, causing distinct prices to
29/// collide on the same synthetic `order_id`, breaking L2/MBP aggregation.
30///
31/// This function uses deterministic `AHash` to compress i128 into u64:
32/// - **Deterministic**: Fixed seeds (0,0,0,0) ensure the same price always maps to the same `order_id`.
33/// - **Collision-resistant**: `AHash` provides high-quality 1-in-2^64 collision probability.
34/// - **Correct**: No structural weaknesses; handles all i128 values uniformly.
35/// - **Fast**: `AHash` is optimized for performance while maintaining hash quality.
36///
37/// # Collision Characteristics
38///
39/// By the pigeonhole principle, any i128→u64 mapping must have theoretical collisions.
40/// However, `AHash` with fixed seeds ensures:
41/// - Truly random 1-in-2^64 collision probability (no systematic patterns).
42/// - For realistic orderbooks with ~1000 price levels: collision probability < 10^-15.
43/// - No structural weaknesses at edge cases.
44///
45/// Order-book correctness is binary, so we use a high-quality deterministic hash to
46/// push collision probability effectively to zero at negligible performance cost.
47#[inline]
48fn price_to_order_id(price_raw: i128) -> u64 {
49    let build_hasher = ahash::RandomState::with_seeds(0, 0, 0, 0);
50    build_hasher.hash_one(price_raw)
51}
52
53/// Returns a price-based order ID for MBP aggregation.
54#[inline]
55fn price_based_order_id(order: &BookOrder) -> u64 {
56    #[cfg(feature = "high-precision")]
57    {
58        price_to_order_id(order.price.raw)
59    }
60    #[cfg(not(feature = "high-precision"))]
61    {
62        price_to_order_id(i128::from(order.price.raw))
63    }
64}
65
66pub(crate) fn pre_process_order(book_type: BookType, mut order: BookOrder, flags: u8) -> BookOrder {
67    match book_type {
68        BookType::L1_MBP => order.order_id = order.side.map_or(0, |side| side as u64),
69        BookType::L2_MBP => order.order_id = price_based_order_id(&order),
70        BookType::L3_MBO => {
71            if RecordFlag::F_TOB.matches(flags) {
72                order.order_id = order.side.map_or(0, |side| side as u64);
73            } else if RecordFlag::F_MBP.matches(flags) || order.order_id == 0 {
74                // An ID of zero carries no identity (for example, MBP-style data),
75                // so key by price hash to keep every level addressable.
76                order.order_id = price_based_order_id(&order);
77            }
78        }
79    }
80    order
81}
82
83#[cfg(test)]
84mod tests {
85    use ahash::AHashSet;
86    use rstest::rstest;
87
88    use super::*;
89
90    #[rstest]
91    fn test_price_to_order_id_deterministic() {
92        let price1 = 123_456_789_012_345_678_901_234_567_890_i128;
93        let price2 = 987_654_321_098_765_432_109_876_543_210_i128;
94
95        // Same price should always produce same order_id
96        let id1_a = price_to_order_id(price1);
97        let id1_b = price_to_order_id(price1);
98        assert_eq!(id1_a, id1_b, "Same price must produce same order_id");
99
100        // Different prices should produce different order_ids
101        let id2 = price_to_order_id(price2);
102        assert_ne!(
103            id1_a, id2,
104            "Different prices should produce different order_ids"
105        );
106    }
107
108    #[rstest]
109    fn test_price_to_order_id_no_collisions() {
110        // Test that similar prices don't collide
111        let base = 1_000_000_000_i128;
112        let mut seen = AHashSet::new();
113
114        for i in 0..1000 {
115            let price = base + i;
116            let id = price_to_order_id(price);
117            assert!(seen.insert(id), "Collision detected for price {price}");
118        }
119    }
120
121    #[rstest]
122    fn test_price_to_order_id_no_collision_across_64bit_boundary() {
123        // Test the specific collision case: price_raw = 1 vs price_raw = 1 << 64
124        let price1 = 1_i128;
125        let price2 = 1_i128 << 64; // This is 2^64
126
127        let id1 = price_to_order_id(price1);
128        let id2 = price_to_order_id(price2);
129
130        assert_ne!(
131            id1, id2,
132            "Collision detected: price 1 and price 2^64 must have different order_ids"
133        );
134    }
135
136    #[rstest]
137    fn test_price_to_order_id_handles_negative_prices() {
138        let mut seen = AHashSet::new();
139
140        // Test negative prices including edge case of -2
141        let negative_prices = vec![
142            -1_i128,
143            -2_i128,
144            -100_i128,
145            -1_000_000_000_i128,
146            i128::MIN,
147            i128::MIN + 1,
148        ];
149
150        for &price in &negative_prices {
151            let id = price_to_order_id(price);
152            assert!(
153                seen.insert(id),
154                "Collision detected for negative price {price}"
155            );
156        }
157
158        // Also verify negative prices don't collide with positive ones
159        let positive_prices = vec![1_i128, 2_i128, 100_i128, 1_000_000_000_i128, i128::MAX];
160
161        for &price in &positive_prices {
162            let id = price_to_order_id(price);
163            assert!(
164                seen.insert(id),
165                "Collision detected between negative and positive price: {price}"
166            );
167        }
168    }
169
170    #[rstest]
171    fn test_price_to_order_id_handles_large_values() {
172        let mut seen = AHashSet::new();
173
174        // Test values that exceed u64::MAX
175        // Note: (u64::MAX + 1) and (1 << 64) are the same value (2^64)
176        let large_values = vec![
177            i128::from(u64::MAX), // 2^64 - 1
178            1_i128 << 64,         // 2^64 (same as u64::MAX + 1)
179            i128::from(u64::MAX) + 1000,
180            1_i128 << 65,  // 2^65
181            1_i128 << 100, // 2^100
182            i128::MAX - 1,
183            i128::MAX,
184        ];
185
186        for &price in &large_values {
187            let id = price_to_order_id(price);
188            assert!(
189                seen.insert(id),
190                "Collision detected for large price value {price}"
191            );
192        }
193    }
194
195    #[rstest]
196    fn test_price_to_order_id_multiples_of_2_pow_64() {
197        let mut seen = AHashSet::new();
198
199        // Test that multiples of 2^64 don't collide
200        // These would all collapse to the same value with naive XOR folding
201        for i in 0..10 {
202            let price = i * (1_i128 << 64);
203            let id = price_to_order_id(price);
204            assert!(
205                seen.insert(id),
206                "Collision detected for price {price} (multiple of 2^64)"
207            );
208        }
209    }
210
211    #[rstest]
212    fn test_price_to_order_id_realistic_orderbook_prices() {
213        let mut seen = AHashSet::new();
214
215        // Test realistic order book scenarios with fixed precision (9 decimals)
216        // BTCUSD at ~$50,000 with 9 decimal precision
217        let btc_base = 50_000_000_000_000_i128;
218        for i in -1000..1000 {
219            let price = btc_base + i; // Prices from $49,999 to $50,001
220            let id = price_to_order_id(price);
221            assert!(
222                seen.insert(id),
223                "Collision detected for BTC price offset {i}"
224            );
225        }
226
227        // EURUSD at ~1.1000 with 9 decimal precision
228        let forex_base = 1_100_000_000_i128;
229        for i in -10000..10000 {
230            let price = forex_base + i; // Tight spreads
231            let id = price_to_order_id(price);
232            assert!(
233                seen.insert(id),
234                "Collision detected for EURUSD price offset {i}"
235            );
236        }
237
238        // Crypto with high precision (e.g., DOGEUSDT at $0.10)
239        let doge_base = 100_000_000_i128; // $0.10 with 9 decimals
240        for i in -100_000..100_000 {
241            let price = doge_base + i;
242            let id = price_to_order_id(price);
243            assert!(
244                seen.insert(id),
245                "Collision detected for DOGE price offset {i}"
246            );
247        }
248    }
249
250    #[rstest]
251    fn test_price_to_order_id_edge_case_patterns() {
252        let mut seen = AHashSet::new();
253
254        // Test powers of 2 (common in binary representations)
255        // Note: 1 << 127 produces i128::MIN (sign bit set), so this covers both positive and negative extremes
256        for power in 0..128 {
257            let price = 1_i128 << power;
258            let id = price_to_order_id(price);
259            assert!(
260                seen.insert(id),
261                "Collision detected for 2^{power} = {price}"
262            );
263        }
264
265        // Test negative powers of 2
266        // We stop at 126 because -(1 << 127) would overflow (can't negate i128::MIN)
267        for power in 0..127 {
268            let price = -(1_i128 << power);
269            let id = price_to_order_id(price);
270            assert!(
271                seen.insert(id),
272                "Collision detected for -2^{power} = {price}"
273            );
274        }
275    }
276
277    #[rstest]
278    fn test_price_to_order_id_sequential_negative_values() {
279        let mut seen = AHashSet::new();
280
281        // Test sequential negative values (important for spread instruments)
282        for i in -10000..=0 {
283            let price = i128::from(i);
284            let id = price_to_order_id(price);
285            assert!(seen.insert(id), "Collision detected for price {i}");
286        }
287    }
288
289    #[rstest]
290    fn test_price_to_order_id_extreme_values_no_collision() {
291        let prices = [
292            i128::MAX,
293            i128::MAX - 1,
294            i128::MIN,
295            i128::MIN + 1,
296            i128::from(u64::MAX),
297            i128::from(u64::MAX) - 1,
298            i128::from(u64::MAX) + 1,
299            -i128::from(u64::MAX),
300            -i128::from(u64::MAX) - 1,
301            -i128::from(u64::MAX) + 1,
302            0,
303            1,
304            -1,
305        ];
306        let mut seen = AHashSet::new();
307
308        for price in prices {
309            let id = price_to_order_id(price);
310            assert!(
311                seen.insert(id),
312                "Collision detected for extreme value: {price} (order_id: {id})"
313            );
314        }
315    }
316
317    #[rstest]
318    fn test_price_to_order_id_avalanche_effect() {
319        // Test that small changes in price produce large changes in hash
320        // (avalanche property)
321        let base_price = 1_000_000_000_000_i128;
322        let id1 = price_to_order_id(base_price);
323        let id2 = price_to_order_id(base_price + 1);
324
325        // Count differing bits
326        let xor = id1 ^ id2;
327        let differing_bits = xor.count_ones();
328
329        // With good avalanche, ~50% of bits should differ for a 1-bit input change
330        // We'll be lenient and require at least 20% (12 out of 64 bits)
331        assert!(
332            differing_bits >= 12,
333            "Poor avalanche: only {differing_bits}/64 bits differ for adjacent prices"
334        );
335    }
336
337    #[rstest]
338    fn test_price_to_order_id_comprehensive_collision_check() {
339        let mut prices = AHashSet::new();
340
341        for i in -100_000..100_000 {
342            prices.insert(i128::from(i));
343        }
344
345        for power in 0..64 {
346            for offset in -10..=10 {
347                prices.insert((1_i128 << power) + offset);
348            }
349        }
350
351        for base in [100, 1000, 10000, 100_000, 1_000_000, 10_000_000] {
352            for i in 0..1000 {
353                prices.insert(base * 1_000_000_000_i128 + i);
354            }
355        }
356
357        let mut seen = AHashSet::with_capacity(prices.len());
358
359        for price in prices {
360            let id = price_to_order_id(price);
361            assert!(seen.insert(id), "Collision detected for price {price}");
362        }
363    }
364}
nautilus_model/orderbook/aggregation.rs

nautilus_model/orderbook/
aggregation.rs
