Home

Awesome

YFS

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

Caching Locks

Design

Lock Client Cache

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.

Releaser, Retryer Threads

Acquire

The course of action depends on the state of the lockid.

Release

If the state of lock is RELEASING, we signal client_revoke_cv. For LOCKED, we signal client_lock_cv.

Lock Server Cache

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

Releaser, Retryer Threads

Acquire

Lock is granted only if current state is

Release

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

Changes to rpc/rpc.cc

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.

Validation

It passes all tests from lab3/lab4 scripts with/witout RPC LOSSY

Caching Extent

Caching at Extent Client

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.

get()

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; };

put()

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.

remove()

We remove the inode from hash map

flush()

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.

BUGS FIXED

test.sh

This script simply does regression test using all test scripts with LOSSY set to 0 and 5.

Paxos

Design

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.

Paxos Module

This consists of Proposer and Acceptor.

Proposer

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

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)

RSM

Design

Replicated State Machine (RSM)

In this exercise, we implement RSM version of lock service.

1) Replicable caching lock server

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

2) RSM without failures

Only the primary lock_server_cache_rsm will communicate directly to clients.

3) Cope with Backup Failures and Implement state transfer

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).

4) Cope with Primary Failures

5) Complicated Failures

Conclusion

With this, we conclude this series of exercises. Happy Coding!

Best, srned