In this project, we implement yet another file system labs followed by course work. http://pdos.csail.mit.edu/6.824/labs/index.html
In consist of
- extent server (accessed from extent client) to store file system data.
- lock server (accessed from lock client) to manage locks
- We cache extent server and cache/replicate lock servers. Below gives some implementation details.
clientcacheMap: Stores the state of locks(as per below struct) in a Map.
struct lock_cache_value {
l_cache_state lock_cache_state; // State of the lock cache
thread_mutex_t client_lock_mutex; // To protect this structure
pthread_cond_t client_lock_cv; // CV to be notified of state chang
pthread_cond_t client_revoke_cv; // CV to be notified if lock is revoked
};
client_cache_mutex: To protect clientcacheMap
It supports acquire, release and listens on revoke and retry.
- On init, we spawn two threads, releaser and retryer (mutex and CVs are dedicated for each for synchronization)
- Releaser will listen on a list and release the lock if it is in FREE state or set the state to RELEASING and wait on client_revoke_cv to be set by the next release request from the client. Once it is released by the client, it sends release request to server
- Retryer will listen on a list and sends acquire request to server for each lockid. Upon successful response, it notifies threads that are waiting on client_lock_cv.
The course of action depends on the state of the lockid.
- NONE: We send acquire to server and set the state to ACQUIRING. On OK response, state is set to LOCKED. On RETRY response, we wait on client_lock_cv. Upon wakeup, if the state is not FREE, we loop back so that the next course of action depends on the current state
- FREE: State is set to LOCKED
- Otherwise: we wait on client_lock_cv. Upon wakeup, if the state is not FREE, we loop back so that the next course of action depends on the current state
If the state of lock is RELEASING, we signal client_revoke_cv. For LOCKED, we signal client_lock_cv.
Server is generally designed to be non-blocking and care is taken not to make RPC calls within acquire/release calls.
tLockMap: Stores the state of locks(as per below struct) in a Map:
struct lock_cache_value {
l_state lock_state;
std::string owner_clientid; // used to send revoke
std::string retrying_clientid; // used to match with incoming acquire request
std::list<std::string> waiting_clientids; // need to send retry
};
lmap_mutex: Global lock to synchronize
It supports acquire, release
- On init, we spawn two threads, releaser and retryer (mutex and CVs are dedicated for each for synchronization)
- Releaser will listen on a list and will send revoke RPC to client who owns the lock.
- Retryer will listen on a list and will send retry RPC to client who is scheduled to own next
Lock is granted only if current state is
- LOCKFREE (or) (RETRYING and incoming id matches the retrying_clientid so that it is granted to the appropriate client. Also, waiting_clientids is probed and if there is any client waiting, we schedule a revoke request to be sent by Releaser thread to avoid starvation
- LOCKED we schedule a revoke request to be sent by Releaser thread and client to added to waiting_clientids list
State is set to LOCKFREE and if there are clients waiting for this lock, then we schedule a retry request to be sent to the scheduled owner
This is to fix the solution that addresses atmost once delivery of RPC on server side. Essentially, we respond back with INPROGRESS if cb_present is false.
It passes all tests from lab3/lab4 scripts with/witout RPC LOSSY
In this exercise, we cache extent data/attributes at client end to avoid roundtrips to extent server. We use lock server/client to acquire locks before caching at the extent client side.
If the inode is not present in the hash map, then we invoke load which gets the attributes and data from extent server and populates struct extent_value { bool dirty; // To track puts std::string data; extent_protocol::attr ext_attr; };
If the inode is not present in extent server, we simply cache it in client and finally if the inode is still around, then we dump it back to server on flush() call.
We remove the inode from hash map
On release of lock from releaser thread in lock_client_cache, the hook dorelease invokes flush() in extent client. If the data is dirty, we "put" it to server, if not, we "remove" it from the server and delete the entry from client cache if needed.
- getattr on extent server was returning OK in all scenarios even if the inode is not in the system
- Out of Order revoke/retry messages. On lock client, dorelease will be called only "if" the locked has been acquired atleast "once". doflush flag is set to flag in NONE case when lock state is ACQUIRING. It is then set to true once the state changes to LOCKED state. This ensures that extent_client infact has acquired the lock and so it is valid to call doflush()
This script simply does regression test using all test scripts with LOSSY set to 0 and 5.
In this exercise, we implement PAXOS algorithm. The stack consists of RSM, Config and Paxos module. Config runs an heartbeat thread to monitor other nodes and invokes remove if necessary. One important convention that is used is that higher layers can hold mutex while calling down but not vice versa.
This consists of Proposer and Acceptor.
Implements below algorithm
n(prop_t): proposal number
v: value to be agreed on (list of alive nodes)
instance#: unique instance number
n_h: highest prepare seen (set during prepare and accept)
instance_h: highest instance accepted (set during decide)
n_a, v_a: highest accept seen
proposer run(instance, v):
choose n, unique and higher than any n seen so far
send prepare(instance, n) to all servers including self
if oldinstance(instance, instance_value) from any node:
commit to the instance_value locally
else if prepare_ok(n_a, v_a) from majority:
v' = v_a with highest n_a; choose own v otherwise
send accept(instance, n, v') to all
if accept_ok(n) from majority:
send decided(instance, v') to all
acceptor prepare(instance, n) handler:
if instance <= instance_h
reply oldinstance(instance, instance_value)
else if n > n_h
n_h = n
reply prepare_ok(n_a, v_a)
else
reply prepare_reject
acceptor accept(instance, n, v) handler:
if n >= n_h
n_a = n
v_a = v
reply accept_ok(n)
else
reply accept_reject
acceptor decide(instance, v) handler:
paxos_commit(instance, v)
In this exercise, we implement RSM version of lock service.
In this step, we ported the previous cache implementation. This guarantees there will not be any deadlock caused by RSM layer So, we dont hold locks across RPC calls. Use background threads with retryer/releaser threads to update state on server side that needs response from client
- The RSM client sends its request to the master by calling the invoke RPC.(handle if RSM is in view change undergoing paxos or if this is not primary anymore)
- The master assigns the client request the next viewstamp in sequence, and sends the invoke RPC to each slave
- If the request has the expected viewstamp, the slave executes the request locally and replies OK to the master.
- The master executes the request locally, and replies back to the client.
Only the primary lock_server_cache_rsm will communicate directly to clients.
Upon detecting failure(heartbeat thread in config layer)/addition of new node(recovery thread in rsm layer), paxos will be kicked off and once it settles, each replica should get state from new master. Master will hold still until all backups have synced (implemented with cond var).
- We serialize the state in master and implement marshal_state and unmarshal_state methods. This will be used on master and replica ends
- sync_with_backups in recovery thread in primary will wait for all replicas to sync up.
- sync_with_primary in recovery thread in backups will sync seperately to master.
- statetransferdone is called from backup to convey that sync is done
- transferdonereq is handler for above on primary
- Clients call init_members() if primary returns NOTPRIMARY response. this way we reinitialize the view
- If there is no response from primary at all, then, we assume the next member from the view as primary and try until succeeds.
- Master fails after 1 slave gets the request and second slave is in process of updating state.
- Fail one of slave before responding
With this, we conclude this series of exercises. Happy Coding!
Best, srned