Skip to main content

gen_id/
lib.rs

1use serde::Serialize;
2use std::sync::atomic::{AtomicU16, Ordering};
3use std::time::{SystemTime, UNIX_EPOCH};
4
5#[cfg(target_arch = "wasm32")]
6use wasm_bindgen::prelude::*;
7
8pub const DEFAULT_EPOCH: u64 = 1609459200000;
9
10#[repr(u8)]
11pub enum ConfigPreset {
12    ShortEpochMaxNodes = 0,
13    ShardedConfig = 1,
14    Custom(u64, u8, u8, u8, u8),
15}
16
17pub struct IdGenerator {
18    epoch: u64,
19    epoch_bits: u8,
20    node_bits: u8,
21    shard_bits: u8,
22    max_nodes: u16,
23    config_id: u8,
24    next_id: AtomicU16,
25}
26
27#[derive(Debug, Serialize)]
28pub struct DecodedId {
29    pub time: u64,
30    pub node_id: u64,
31    pub shard_id: u16,
32    pub incrementing_id: u64,
33    pub config_id: u8,
34}
35
36impl IdGenerator {
37    pub fn new(preset: ConfigPreset, epoch: u64) -> Self {
38        match preset {
39            ConfigPreset::ShortEpochMaxNodes => Self {
40                epoch,
41                epoch_bits: 37,
42                node_bits: 14,
43                shard_bits: 0,
44                max_nodes: 16384,
45                config_id: 3,
46                next_id: AtomicU16::new(0),
47            },
48            ConfigPreset::ShardedConfig => Self {
49                epoch,
50                epoch_bits: 32,
51                node_bits: 14,
52                shard_bits: 5, // upto 32 shards
53                max_nodes: 16384,
54                config_id: 1,
55                next_id: AtomicU16::new(0),
56            },
57            ConfigPreset::Custom(epoch, epoch_bits, node_bits, shard_bits, config_id) => Self {
58                epoch,
59                epoch_bits,
60                node_bits,
61                shard_bits,
62                max_nodes: (1 << node_bits) as u16,
63                config_id,
64                next_id: AtomicU16::new(0),
65            },
66        }
67    }
68
69    pub fn derive_sharded_id(&self, original_id: u64, shard: u16) -> u64 {
70        if self.shard_bits == 0 {
71            panic!("This configuration doesn't support sharding");
72        }
73
74        if shard as u64 >= (1 << self.shard_bits) {
75            panic!("Shard number exceeds maximum");
76        }
77
78        let shard_shift = 13;
79        let shard_width = self.shard_bits;
80
81        let shard_mask = ((1u64 << shard_width) - 1) << shard_shift;
82
83        let base_id = original_id & !shard_mask;
84
85        let shard_part = ((shard as u64) & ((1 << shard_width) - 1)) << shard_shift;
86
87        base_id | shard_part
88    }
89
90    pub fn decode_id(&self, id: u64) -> DecodedId {
91        let config_id = (id & 0b111) as u8;
92        let incrementing_id = (id >> 3) & ((1 << 10) - 1);
93
94        // Shard bits come after incrementing id
95        let shard_id = if self.shard_bits > 0 {
96            ((id >> (3 + 10)) & ((1 << self.shard_bits) - 1)) as u16
97        } else {
98            0
99        };
100
101        // Node id now comes after shard bits
102        let node_shift = 3 + 10 + self.shard_bits;
103        let node_id = (id >> node_shift) & ((1 << self.node_bits) - 1);
104
105        // Time comes after node id
106        let time_shift = node_shift + self.node_bits;
107        let time = (id >> time_shift) & ((1 << self.epoch_bits) - 1);
108
109        DecodedId {
110            time,
111            node_id,
112            shard_id,
113            incrementing_id,
114            config_id,
115        }
116    }
117
118    fn generate_id(&self, node_id: u16, incrementing_id: u16) -> u64 {
119        let now = SystemTime::now()
120            .duration_since(UNIX_EPOCH)
121            .expect("Time went backwards");
122        let millis = now.as_millis() as u64;
123        let time_since_epoch = millis.checked_sub(self.epoch).expect("Time went backwards");
124
125        // Start with config bits (lowest 3)
126        let config_part = (self.config_id as u64) & 0b111;
127
128        // Incrementing id next (10 bits)
129        let inc_part = ((incrementing_id as u64) & ((1 << 10) - 1)) << 3;
130
131        // Shard bits are 0 for non-sharded configs (comes after incrementing id)
132        let shard_shift = 3 + 10;
133
134        // Node id comes after shard bits
135        let node_shift = shard_shift + self.shard_bits;
136        let node_part = ((node_id as u64) & ((1 << self.node_bits) - 1)) << node_shift;
137
138        // Time is highest
139        let time_shift = node_shift + self.node_bits;
140        let time_part = (time_since_epoch & ((1u64 << self.epoch_bits) - 1)) << time_shift;
141
142        time_part | node_part | inc_part | config_part
143    }
144
145    pub fn next_id(&self, node_id: u16) -> u64 {
146        let incrementing_id = self.next_id.fetch_add(1, Ordering::SeqCst) & ((1 << 10) - 1);
147        self.generate_id(node_id, incrementing_id)
148    }
149}
150
151#[cfg(target_arch = "wasm32")]
152#[wasm_bindgen]
153pub struct WasmIdGenerator {
154    generator: IdGenerator,
155}
156
157#[cfg(target_arch = "wasm32")]
158#[wasm_bindgen]
159impl WasmIdGenerator {
160    #[wasm_bindgen(constructor)]
161    pub fn new(preset_type: u8, epoch: u64) -> Result<WasmIdGenerator, JsValue> {
162        let preset = match preset_type {
163            0 => ConfigPreset::ShortEpochMaxNodes,
164            1 => ConfigPreset::ShardedConfig,
165            _ => return Err(JsValue::from_str("Invalid preset type")),
166        };
167
168        Ok(WasmIdGenerator {
169            generator: IdGenerator::new(preset, epoch),
170        })
171    }
172
173    #[wasm_bindgen]
174    pub fn next_id(&self, node_id: u16) -> u64 {
175        self.generator.next_id(node_id)
176    }
177
178    #[wasm_bindgen]
179    pub fn decode_id(&self, id: u64) -> Result<JsValue, JsValue> {
180        let decoded = self.generator.decode_id(id);
181        serde_wasm_bindgen::to_value(&decoded).map_err(|e| JsValue::from_str(&e.to_string()))
182    }
183
184    #[wasm_bindgen]
185    pub fn derive_sharded_id(&self, original_id: u64, shard: u16) -> Result<u64, JsValue> {
186        if self.generator.shard_bits == 0 {
187            return Err(JsValue::from_str(
188                "This configuration doesn't support sharding",
189            ));
190        }
191
192        if shard as u64 >= (1 << self.generator.shard_bits) {
193            return Err(JsValue::from_str("Shard number exceeds maximum"));
194        }
195
196        Ok(self.generator.derive_sharded_id(original_id, shard))
197    }
198}
199
200#[cfg(test)]
201mod tests {
202    use super::*;
203
204    #[test]
205    fn test_initialization() {
206        let gen_short = IdGenerator::new(ConfigPreset::ShortEpochMaxNodes, DEFAULT_EPOCH);
207        assert_eq!(gen_short.epoch, DEFAULT_EPOCH);
208        assert_eq!(gen_short.epoch_bits, 37);
209        assert_eq!(gen_short.node_bits, 14);
210        assert_eq!(gen_short.max_nodes, 16384);
211        assert_eq!(gen_short.config_id, 3);
212        assert_eq!(gen_short.shard_bits, 0);
213
214        let custom_epoch = 1609459200000;
215        let custom_epoch_bits = 36;
216        let custom_node_bits = 13;
217        let custom_shard_bits = 2;
218        let custom_config_id = 1;
219        let gen_custom = IdGenerator::new(
220            ConfigPreset::Custom(
221                custom_epoch,
222                custom_epoch_bits,
223                custom_node_bits,
224                custom_shard_bits, // Add this parameter
225                custom_config_id,
226            ),
227            custom_epoch,
228        );
229        assert_eq!(gen_custom.epoch, custom_epoch);
230        assert_eq!(gen_custom.epoch_bits, custom_epoch_bits);
231        assert_eq!(gen_custom.node_bits, custom_node_bits);
232        assert_eq!(gen_custom.shard_bits, custom_shard_bits);
233        assert_eq!(gen_custom.max_nodes, 8192);
234        assert_eq!(gen_custom.config_id, custom_config_id);
235    }
236
237    #[test]
238    fn test_id_uniqueness_and_sequence() {
239        let gen = IdGenerator::new(ConfigPreset::ShortEpochMaxNodes, DEFAULT_EPOCH);
240        let mut last_id = 0;
241        for _ in 0..100 {
242            let new_id = gen.next_id(1);
243            assert!(new_id > last_id);
244            last_id = new_id;
245        }
246    }
247
248    #[test]
249    fn test_id_composition() {
250        let gen = IdGenerator::new(ConfigPreset::ShortEpochMaxNodes, DEFAULT_EPOCH);
251        let id = gen.next_id(1);
252        let decoded = gen.decode_id(id);
253        assert_eq!(decoded.config_id, 3);
254        assert!(
255            decoded.time
256                <= (SystemTime::now()
257                    .duration_since(UNIX_EPOCH)
258                    .unwrap()
259                    .as_millis() as u64
260                    - DEFAULT_EPOCH)
261        );
262        assert_eq!(decoded.node_id, 1);
263    }
264
265    #[test]
266    fn test_boundary_conditions() {
267        let gen = IdGenerator::new(ConfigPreset::ShortEpochMaxNodes, DEFAULT_EPOCH);
268        // Test maximum node ID
269        let max_node_id = gen.max_nodes - 1;
270        let id = gen.next_id(max_node_id);
271        let decoded = gen.decode_id(id);
272        assert_eq!(decoded.node_id, max_node_id as u64);
273
274        // Test maximum incrementing ID
275        let max_inc_id = (1 << 10) - 1; // 10 bits max
276        let id = gen.generate_id(1, max_inc_id as u16);
277        let decoded = gen.decode_id(id);
278        assert_eq!(decoded.incrementing_id, max_inc_id as u64);
279    }
280
281    #[test]
282    fn test_decode_correctness() {
283        let gen = IdGenerator::new(ConfigPreset::ShortEpochMaxNodes, DEFAULT_EPOCH);
284        let id = gen.next_id(1);
285        let decoded = gen.decode_id(id);
286        assert_eq!(decoded.node_id, 1);
287        assert_eq!(decoded.config_id, 3);
288    }
289
290    #[test]
291    #[should_panic(expected = "Time went backwards")]
292    fn test_time_travel_resilience() {
293        let gen = IdGenerator::new(ConfigPreset::ShortEpochMaxNodes, u64::MAX);
294        let _ = gen.next_id(1);
295    }
296
297    #[test]
298    fn test_node_id_encoding() {
299        let gen = IdGenerator::new(ConfigPreset::ShortEpochMaxNodes, DEFAULT_EPOCH);
300        let test_node_ids = [0, 1, 2, 3, 4, 5, 6, gen.max_nodes / 2, gen.max_nodes - 1];
301
302        for &node_id in &test_node_ids {
303            let id = gen.next_id(node_id);
304            let decoded = gen.decode_id(id);
305            assert_eq!(
306                decoded.node_id, node_id as u64,
307                "Node ID did not match for node_id {}",
308                node_id
309            );
310        }
311    }
312
313    #[test]
314    fn test_sharding_functionality() {
315        let gen = IdGenerator::new(ConfigPreset::ShardedConfig, DEFAULT_EPOCH);
316
317        let original_id = gen.next_id(1);
318        let original_decoded = gen.decode_id(original_id);
319        println!(
320            "Original ID: {}, node_id: {}",
321            original_id, original_decoded.node_id
322        );
323
324        for shard in 0..32 {
325            let sharded_id = gen.derive_sharded_id(original_id, shard);
326            let decoded = gen.decode_id(sharded_id);
327
328            println!(
329                "Shard {}: ID: {}, node_id: {}",
330                shard, sharded_id, decoded.node_id
331            );
332
333            assert_eq!(
334                decoded.time, original_decoded.time,
335                "Time component changed after sharding"
336            );
337            assert_eq!(
338                decoded.node_id, original_decoded.node_id,
339                "Node ID changed after sharding"
340            );
341            assert_eq!(
342                decoded.incrementing_id, original_decoded.incrementing_id,
343                "Increment changed"
344            );
345            assert_eq!(
346                decoded.config_id, 1,
347                "Config ID should be 1 for sharded config"
348            );
349            assert_eq!(decoded.shard_id, shard, "Shard ID not correctly set");
350        }
351    }
352}