lab/lab3/
mod.rs

1//! Welcome to Lab 3! The goal of this lab is to take the bin storage that we
2//! implemented in Lab 2 and make it fault-tolerant.
3//!
4//! Lab 3 can be submitted in teams of **up to** 3 people.
5//!
6//! ## Get Your Repo
7//!
8//! This is the the first assignment you will complete in groups. As a team you
9//! will create a shared Github repository. Have one group member follow the
10//! GitHub classroom link available through the Lab 3 class announcement. Once
11//! one group member has made the group the others can select it. **Choose your
12//! teammates carefully prior to accepting a Github group**, the choice is
13//! binding. Once you have a repo select one of your group members to push their
14//! code from lab2 to the freshly created lab3 starter repo for your team. See
15//! this [Github
16//! Documentation](https://docs.github.com/en/github/getting-started-with-github/managing-remote-repositories)
17//! for how to perform the push.
18//!
19//! Note that we don't provide great unit tests to test fault tolerance (as it's
20//! hard to spawn and kill processes from within unit tests). Make sure you test
21//! this sufficiently using a testing mechanism of your own design.
22//!
23//! ## System Scale and Failure Model
24//!
25//! There could be up to 300 backends. Backends may join and leave at will, but
26//! you can assume that at any time there will be at least one backend online
27//! (so that your system is functional). Your design is required to be
28//! fault-tolerant where if there are at least three backends online at all
29//! times, there will be no data loss. You can assume that each backend
30//! join/leave event will have a time interval of at least 30 seconds in
31//! between, and this time duration will be enough for you to migrate storage.
32//!
33//! There will be at least 1 and up to 10 keepers. Keepers may join and leave at
34//! will, but at any time there will be at least 1 keeper online. (Thus, if
35//! there is only one keeper, it will not go offline.) Also, you can assume that
36//! each keeper join/leave event will have a time interval of at least 1 minute
37//! in between. When a process 'leaves', assume that the process is killed--
38//! everything in that process will be lost, and it will not have an opportunity
39//! to clean up.
40//!
41//! When keepers join, they join with the same
42//! [index](tribbler::config::KeeperConfig::this) as last time, although they've
43//! lost any other state they may have saved. Each keeper will receive a new
44//! [id](tribbler::config::KeeperConfig::id) in the
45//! [KeeperConfig](tribbler::config::KeeperConfig).
46//!
47//! Initially, we will start at least one backend, and then at least one keeper.
48//! At that point, the keeper should send `true` to the [ready
49//! channel](tribbler::config::KeeperConfig::ready) and a frontend should be
50//! able to issue BinStorage calls.
51//!
52//! ## Consistency Model
53//!
54//! To tolerate failures, you have to save the data of each key in multiple
55//! places. To keep things achievable, we have to slightly relax the consistency
56//! model, as follows.
57//!
58//! [`clock()`](tribbler::storage::Storage::clock) and the key-value calls
59//! ([`set()`][s], [`get()`][g], and [`keys()`][k]) will keep the same semantics
60//! as before.
61//!
62//!
63//! When concurrent [`list_appends()`s][la] happen, calls to [`list_get()`][lg]
64//! might result in values that are currently being added, and may appear in
65//! arbitrary order. However, after all concurrent [`list_append()`s][la]
66//! return, [`list_get()`][lg] should always return the list with a consistent
67//! order.
68//!
69//! Here is an example of a valid call and return sequence:
70//!
71//! - Initially, the list "k" is empty.
72//! - A invokes `list_append("k", "a")`
73//! - B invokes `list_append("k", "b")`
74//! - C calls `list_get("k")` and gets `["b"]`. Note that `"b"` appears first in
75//!   the list here.
76//! - D calls `list_get("k")` and gets `["a", "b"]`, note that although `"b"`
77//!   appeared first last time, it appears at the second position in the list
78//!   now.
79//! - A's `list_append()` call returns
80//! - B's `list_append()` call returns
81//! - C calls `list_get("k")` again and gets `["a", "b"]`
82//! - D calls `list_get("k")` again and gets `["a", "b"]`
83//!
84//! [`list_remove()`][lr] removes all matched values that are appended into the
85//! list in the past, and returns number properly. When (and only when)
86//! concurrent [`list_remove()`s][lr] on the same key and value is called, it is
87//! okay to 'double count' elements being removed.
88//!
89//! [`list_keys()`][lk] keeps the same semantics.
90//!
91//! [s]: tribbler::storage::KeyString::set
92//! [g]: tribbler::storage::KeyString::get
93//! [k]: tribbler::storage::KeyString::keys
94//! [la]: tribbler::storage::KeyList::list_append
95//! [lg]: tribbler::storage::KeyList::list_get
96//! [lr]: tribbler::storage::KeyList::list_remove
97//! [lk]: tribbler::storage::KeyList::list_keys
98//!
99//! ## Entry Functions
100//!
101//! The entry functions will remain exactly the same as they are in Lab
102//! 2. The only thing that will change is that there may be multiple keepers
103//! listed in the [KeeperConfig](tribbler::config::KeeperConfig::addrs).
104//!
105//! ## Additional Assumptions
106//!
107//! - No network errors; when a TCP connection is lost you can assume that the
108//!   RPC server crashed.
109//! - When a bin-client, backend, or keeper is killed, all data in that process
110//!   will be lost; nothing will be carried over a respawn.
111//! - It will take less than 20 seconds to read all data stored on a backend and
112//!   write it to another backend.
113//!
114//! ## Requirements
115//!
116//! - Although you might change how data is stored in the backends, your
117//!   implementation should pass all past test cases, which means your system
118//!   should be functional with a single backend.
119//! - If there are at least three backends online, there should never be any
120//!   data loss. Note that the set of three backends might change over time, so
121//!   long as there are at least three at any given moment.
122//! - Assuming there are backends online, storage function calls always return
123//!   without error, even when a node and/or a keeper just joined or left.
124//!
125//! ## Building Hints
126//!
127//! - You can use the logging techniques described in class to store everything
128//!   (in lists on the backends, even for values).
129//! - Let the keeper(s) keep track on the status of all the nodes, and do the
130//!   data migration when a backend joins or leaves.
131//! - Keepers should also keep track of the status of each other.
132//!
133//! For the ease of debugging, you can maintain some log messages (by using the
134//! [log] crate, or by writing to a TCP socket or a log file). However, for the
135//! convenience of grading, please turn them off by default when you turn in
136//! your code.
137//!
138//! ## RPCs Between Keepers
139//!
140//! While not necessary to complete the lab, you may wish to implement an RPC
141//! service so that keepers can communicate with one another.
142//!
143//! You are allowed to define an RPC interface that is used between the keepers.
144//! Use protobuf syntax to define the messages and RPC calls that your keepers
145//! will use. Refer to the [protobuf language
146//! guide](https://developers.google.com/protocol-buffers/docs/proto3) for
147//! information on how to write protobuf specifications. You can also reference
148//! the `tribbler/proto/rpc.proto` file to see how the storage RPC interface is
149//! specified.
150//!
151//! A blank `proto` file is provided to you in `lab/proto/keeper.proto`. When
152//! building your project with `cargo build` this proto file will get compiled
153//! into the `lab/src/keeper.rs` module, which you can then use to implement
154//! your RPCs
155//!
156//! ## `Report.md`
157//!
158//! Similar to in Lab 2, please include a report file. See the [description in
159//! Lab 2](crate::lab2) for more details.
160//!
161//! ## Turning In
162//!
163//! Each student must submit their own version of the group repository to
164//! Gradescope by the deadline (+their individual late hours). Every member of
165//! the team can submit the exact same repository commit. Individual submissions
166//! are being used to allow individual teammates to make use of their late hours
167//! if they feel the need.
168//!
169//! Happy Lab 3. :-)