diff options
| -rw-r--r-- | Cargo.lock | 75 | ||||
| -rw-r--r-- | Cargo.toml | 3 | ||||
| -rw-r--r-- | Justfile | 6 | ||||
| -rw-r--r-- | unique_ids/Cargo.toml | 12 | ||||
| -rw-r--r-- | unique_ids/src/main.rs | 83 |
5 files changed, 177 insertions, 2 deletions
@@ -3,6 +3,12 @@ version = 3 [[package]] +name = "cfg-if" +version = "1.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd" + +[[package]] name = "common" version = "0.1.0" dependencies = [ @@ -20,12 +26,35 @@ dependencies = [ ] [[package]] +name = "getrandom" +version = "0.2.10" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "be4136b2a15dd319360be1c07d9933517ccf0be8f16bf62a3bee4f0d618df427" +dependencies = [ + "cfg-if", + "libc", + "wasi", +] + +[[package]] name = "itoa" version = "1.0.9" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "af150ab688ff2122fcef229be89cb50dd66af9e01a4ff320cc137eecc9bacc38" [[package]] +name = "libc" +version = "0.2.147" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b4668fb0ea861c1df094127ac5f1da3409a82116a4ba74fca2e58ef927159bb3" + +[[package]] +name = "ppv-lite86" +version = "0.2.17" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5b40af805b3121feab8a3c29f04d8ad262fa8e0561883e7653e024ae4479e6de" + +[[package]] name = "proc-macro2" version = "1.0.66" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -44,6 +73,36 @@ dependencies = [ ] [[package]] +name = "rand" +version = "0.8.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "34af8d1a0e25924bc5b7c43c079c942339d8f0a8b57c39049bef581b46327404" +dependencies = [ + "libc", + "rand_chacha", + "rand_core", +] + +[[package]] +name = "rand_chacha" +version = "0.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e6c10a63a0fa32252be49d21e7709d4d4baf8d231c2dbce1eaa8141b9b127d88" +dependencies = [ + "ppv-lite86", + "rand_core", +] + +[[package]] +name = "rand_core" +version = "0.6.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ec0be4795e2f6a28069bec0b5ff3e2ac9bafc99e6a9a7dc3547996c5c816922c" +dependencies = [ + "getrandom", +] + +[[package]] name = "ryu" version = "1.0.15" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -96,3 +155,19 @@ name = "unicode-ident" version = "1.0.11" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "301abaae475aa91687eb82514b328ab47a211a533026cb25fc3e519b86adfc3c" + +[[package]] +name = "unique_ids" +version = "0.1.0" +dependencies = [ + "common", + "rand", + "serde", + "serde_json", +] + +[[package]] +name = "wasi" +version = "0.11.0+wasi-snapshot-preview1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9c8d87e72b64a3b4db28d11ce29237c246188f4f51057d65a7eab63b7987e423" @@ -1,5 +1,6 @@ [workspace] members = [ + "common", "echo", - "common" + "unique_ids" ] @@ -1,3 +1,7 @@ test-echo: cargo build --bin echo - maelstrom test -w echo --bin target/debug/echo --node-count 1 --time-limit 10
\ No newline at end of file + maelstrom test -w echo --bin target/debug/echo --node-count 1 --time-limit 10 + +test-unique-ids: + cargo build --bin unique_ids + maelstrom test -w unique-ids --bin target/debug/unique_ids --time-limit 30 --rate 1000 --node-count 3 --availability total --nemesis partition diff --git a/unique_ids/Cargo.toml b/unique_ids/Cargo.toml new file mode 100644 index 0000000..e7424bf --- /dev/null +++ b/unique_ids/Cargo.toml @@ -0,0 +1,12 @@ +[package] +name = "unique_ids" +version = "0.1.0" +edition = "2021" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] +serde = { version = "1.0.185", features = ["derive"] } +serde_json = "1.0.105" +common = { path = "../common/" } +rand = "0.8.5" diff --git a/unique_ids/src/main.rs b/unique_ids/src/main.rs new file mode 100644 index 0000000..3787033 --- /dev/null +++ b/unique_ids/src/main.rs @@ -0,0 +1,83 @@ +use std::{ + io, + time::{SystemTime, UNIX_EPOCH}, +}; + +use common::{run_with, Handler}; +use rand::{rngs::StdRng, Rng, SeedableRng}; +use serde::{Deserialize, Serialize}; + +fn main() { + run_with::<UniqueIdsHandler>(io::stdin(), io::stdout()) +} + +#[derive(Debug, Serialize, Deserialize)] +#[serde(tag = "type")] +enum UniqueIdsBody { + #[serde(rename = "generate")] + Generate { msg_id: usize }, + + #[serde(rename = "generate_ok")] + GenerateOk { + msg_id: usize, + in_reply_to: usize, + id: u128, + }, +} + +type RngMethod = StdRng; + +struct UniqueIdsHandler { + rng: RngMethod, + next_msg_id: usize, +} + +impl Handler for UniqueIdsHandler { + type Body = UniqueIdsBody; + + fn init(_node_id: String, _node_ids: Vec<String>, _msg_id: usize) -> Self { + Self { + rng: RngMethod::from_entropy(), // TODO: This could be seeded from the node ID + next_msg_id: 1, + } + } + + fn handle( + &mut self, + header: common::msg::MessageHeader, + body: Self::Body, + writer: &mut common::MsgWriter<impl std::io::Write>, + ) -> () { + match body { + UniqueIdsBody::Generate { msg_id } => { + let id = self.gen_id(); + writer.write( + header.src, + &UniqueIdsBody::GenerateOk { + msg_id: self.next_msg_id, + in_reply_to: msg_id, + id, + }, + ); + + self.next_msg_id += 1; + } + UniqueIdsBody::GenerateOk { .. } => (), + }; + } +} + +impl UniqueIdsHandler { + fn gen_id(&mut self) -> u128 { + // Time since UNIX epoch in milliseconds + let now = SystemTime::now(); + let time_millis: u128 = now.duration_since(UNIX_EPOCH).unwrap().as_millis(); + + // 80 bits of randomness + let rand1: u16 = self.rng.gen(); + let rand2: u64 = self.rng.gen(); + let rand: u128 = rand1 as u128 | ((rand2 as u128) << 64); + + (time_millis << 80) | rand + } +} |