1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228
#![cfg_attr(feature="clippy", feature(plugin))] #![cfg_attr(feature="clippy", plugin(clippy))] //! # Ditto //! //! Ditto is a library for using [CRDTs](https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type), //! or conflict-free replicated data types. CRDTs are data structures //! which can be replicated across multiple sites, edited concurrently, //! and merged together without leading to conflicts. Ditto provides //! a number of commonly used data types: //! //! * **[Register\<T\>](register/Register.t.html):** A replaceable value //! * **[Counter](counter/Counter.t.html):** An i64 value that increments //! * **[Set\<T\>](set/Set.t.html):** A HashSet-like collection of unique values //! * **[Map\<K, V\>:](map/Map.t.html)** A HashMap-like collection of key-value pairs //! * **[List\<T\>:](list/List.t.html)** A Vec-like ordered sequence of elements //! * **[Text:](text/Text.t.html)** A String-like container for mutable text //! * **[Json:](json/Json.t.html)** A JSON value //! //! Ditto's goal is to be fast, correct, and easy to use. If you have any //! questions, suggestions, or other feedback, feel free to open an issue //! or a pull request or contact the Ditto developers directly. //! //! ## Example //! //! ```rust //! extern crate ditto; //! extern crate serde_json; //! use ditto::List; //! //! fn main() { //! // Create a List CRDT. The site that creates the CRDT //! // is automatically assigned id 1. //! let mut list1 = List::from(vec![100,200,300]); //! //! // Send the list's state over a network to a second site with id 2. //! let encoded_state = serde_json::to_string(&list1.state()).unwrap(); //! let decoded_state = serde_json::from_str(&encoded_state).unwrap(); //! let mut list2 = List::from_state(decoded_state, Some(2)).unwrap(); //! //! // Edit the list concurrently at both the first and second site. //! // Whenever you edit a CRDT, you receive an op that can be sent //! // to other sites. //! let op1 = list1.insert(0, 400).unwrap(); //! let op2 = list2.remove(0).1.unwrap(); //! //! // Each site sends its op to the other site for execution. //! // The encoding and decoding has been left out for brevity. //! list1.execute_op(op2); //! list2.execute_op(op1); //! //! // Now both sites have the same value: //! assert_eq!(list1.state(), list2.state()); //! assert_eq!(list1.local_value(), vec![400, 200, 300]); //! } //! ``` //! //! You can find more examples in the examples and tests directories in the //! crate repo. //! //! ## Using CRDTs //! //! Ditto CRDTs are designed to mimic standard data type APIs as much //! as possible. You can `insert` and `remove` list and map //! elements, `replace` text elements, etc. Each edit generates an op //! that can be sent to other sites for execution. When you execute an //! op sent from another site, you receive a `LocalOp` that shows //! exactly how the CRDT's value has changed. //! //! The two complications of CRDTs that users have to worry about are: //! //! * How to send ops/state from one site to another //! * How to assign a site id to each site. //! //! Ditto does not include a networking layer. However, you can find //! info on how to send changes and assign site IDs in the docs below. //! //! ### Sending ops and state //! //! CRDTs and ops are serializable with [Serde](https://serde.rs). //! Serialization is tested against [`serde_json`](https://github.com/serde-rs/json) //! (`JSON`) and [`rmp-serde`](https://github.com/3Hren/msgpack-rust) //! (`MsgPack`) but may work with other formats as well. //! //! Ops must be sent in the order they were generated. That is, if //! a site performs edit A and then edit B, it must send op A before //! it sends op B. State can be sent in any order. //! //! Similarly, ops must be sent over a network that guarantees in-order //! delivery. TCP fits this requirement, so any protocol sitting atop //! TCP (HTTP, WebSockets, SMTP, XMPP, etc.) will work as a transport //! layer for op-based replication. State can be sent via a protocol //! that does not guarantee in-order delivery. //! //! In general, when replicating a CRDT state you should send its //! state struct, not the CRDT struct, because the CRDT struct includes //! the site ID. For example, to replicate a `Json` CRDT you should //! send the serialized `JsonState`, which can be created by calling //! `json_crdt.state()`. //! //! ### Assigning Site IDs //! //! A CRDT may be distributed across multiple *sites*. A site is //! just a fancy distributed systems term for "client". Each //! site that wishes to edit the CRDT must have a unique `u32` //! identifier. //! //! The site that creates the CRDT is automatically assigned to //! ID 1. ***You*** are responsible for assigning all other sites; //! Ditto will not do it for you. //! //! Here are some strategies for assigning site identifiers: //! //! * Reuse existing site identifiers (e.g. numeric client ids) //! * Use a central server to assign site ids on a per-CRDT basis //! * Use a consensus algorithm like Raft or Paxos to determine a new site's ID //! //! Site IDs can be assigned lazily. If a site only needs read access //! to a CRDT, it doesn't need a site ID. If a site without an ID edits //! the CRDT, the CRDT will update locally but ops will be cached and //! unavailable to the user. When the site receives an ID, that ID //! will be retroactively applied to the site's edits, and the cached ops //! will be returned to be sent over the network. //! //! ### Do I need a centralized server to maintain consistency? //! //! CRDTs do not require a central server to ensure eventual //! consistency; you can use them in peer-to-peer protocols, //! client-server applications, federated services, or any other //! environment. However you *do* need a way to assign unique site //! identifiers, as explained in the section [Assigning Site IDs](#assigning-site-ids). //! A centralized server is one way to do that, but not the only way. //! //! A server may also be useful as an op cache for unavailable //! clients. If you are using CRDTs in an application where sites are //! often offline (for instance, a mobile phone app), you can use //! the server to store ops and state changes until they have been //! received by all sites. //! //! ### Duplicate ops //! //! Ditto CRDTs are *idempotent* — executing an op twice //! has no effect. As long as ops from a site are executed in //! the order they were generated, the CRDT will maintain consistency. //! //! ### Sending ops vs. sending state //! //! Usually, the most compact way to send a change between sites //! is to send an *op*. An op is just a fancy distributed systems //! term for "change". Each time you edit a CRDT locally, you generate //! an op that can be sent to other sites and executed. //! //! However, there may be times when it is faster and more compact //! to send the whole CRDT state (e.g. if you're sending 100 or 1000 //! edits at once). You should replicate exclusively via state if you //! cannot guarantee in-order op delivery. //! //! ### Other Notes //! //! Collection CRDTs are inherently larger than their native equivalents //! because each element must have a unique id. Overhead is most //! significant when storing a collection of very small values — a `List<u8>` //! will be many times larger than a `Vec<u8>`. If the collection itself //! is immutable, you can significantly reduce overhead by switching from //! a `List<T>` or `Map<K,V>` to a `Register<Vec<T>>` or `Register<Map<K,V>>`. //! //! ## License //! //! Ditto is licensed under either of //! //! * [Apache License, Version 2.0](https://www.apache.org/licenses/LICENSE-2.0) //! * [MIT license](https://opensource.org/licenses/MIT) //! //! at your option. //! //! ### Contribution //! //! Unless you explicitly state otherwise, any contribution intentionally //! submitted for inclusion in Ditto by you, as defined in the Apache-2.0 //! license, shall be dual licensed as above, without any additional terms //! or conditions. extern crate base64; #[macro_use] extern crate lazy_static; extern crate num; extern crate rand; extern crate serde; #[macro_use] extern crate serde_derive; #[cfg(test)] #[macro_use] extern crate serde_json; #[cfg(not(test))] extern crate serde_json; #[cfg(test)] #[macro_use] extern crate assert_matches; #[cfg(test)] extern crate rmp_serde; #[macro_use] mod traits; pub mod dot; pub mod counter; pub mod json; pub mod list; pub mod map; pub mod register; pub mod set; pub mod text; mod error; mod map_tuple_vec; mod sequence; mod tree; mod vlq; pub use error::Error; pub use counter::{Counter, CounterState}; pub use json::{Json, JsonState}; pub use list::{List, ListState}; pub use map::{Map, MapState}; pub use register::{Register, RegisterState}; pub use set::{Set, SetState}; pub use text::{Text, TextState};