answer
Question 1
Overall code organization
interface directory contains the interface definition for Cart , CartItem , Item ,
Supermarket and SupermarketSerializer . Business directory contains the
implementation for the Cart and Supermarket interface. It also contains both mutable and
immutable version of CartItem and Item interfaces. The client directory contains client
HTTP proxy classes for Cart and Supermarket . The JUnit tests are in tests subdirectory.
The wordloads contains the code for experiment. Directory server contains HTTP Server
classes for Cart and Supermarket . The utils directory contains classes utility classes used
in implementation such as serializer classes, HTTP request and response class and exception
classes.
RPC semantics
At-most-once is imlemented between clients and the Cart or Supermarket, and between the
Cart and the Supermarket.
Failure containment
When supermarket fails, the exception is catched in the cart instance and the exception object
is stored in
the response class and sent to client. Thus when Supermarket instance fails, Cart instances
should still be able to respond to queries on the state of shopping carts, but will raise
exceptions when some operations, namely, item additions or checkout, are invoked.
All-or-nothing atomicity
Cart service
I achieve all-or-nothing atomicity in Cart by checking the error condition first in each method,
when there is error such as negative id, the exception is thrown. Only after checking, the real
operation is conducted. Thus, the all-or-nothing atomicity is achieved.
My implementation in cart also achieves all-or-nothing atomicity even when exceptions are
propagated from the Supermarket service. In method add , if the supermarket.getItems
throws error, which is before cart.put , the cart state doesn’t change, nothing happens. In
method checkout , when the supermarket.updateStocks throws error, the cart is already
cleared. Thus, in both cases, all-or-nothing atomicity is achieved.
Supermarket service
For getItems , the method doesn’t change the supermarket state. For updateStocks , I first
test whether each itemDelta has error (whether item id is negative and whether the item
exists). Only when all itemDelta is valid, the actual updation begins. Thus, all-or-nothing
atomicity is achieved.
Question 2
Method
In CartImp , I define following instance variables.
Each cart is a Hashmap mapping cart item id to cart item. Each cart has a corresponding
ReentrantReadWriteLock . In method add , remove , and checkout . I first acquire the
writeLock for the cart , do the processing and then release the writeLock . In method
getCartItems , I first acquire the readLock for the cart , do the processing and then
release the readLock .
Correctness
Each cart has a corresponding lock. In the method that changes the cart state, writelock is
first acquired and then released. In the method that reads the cart state, readLock is first
acquired and then released. In each case, no lock is acquired after a lock is released. This is
equivalent to two-phase locking.
Issue of reads on predicates vs. multi-granularity locking
We don’t need to consider multi-granularity locking. There are just two level of hierarchy: cart
contains items. It is not necessary to use the more complex multi-granularity locking. Predicates
locking is not considered either. Because it is expensive to implement.
Performance
Because in my implementation, one lock for each cart, thus different threads that process
different carts and don’t infere each other. getCartItems uses the readLock , thus different
threads can getCartItems of the same cart. My implementation has high concurrency as a
result.
Question 3
Method
private Map
();
private Map
1
2
In SupermarketImp , I define following instance variable which is a ReentrantReadWriteLock
for the Supermarket .
In method updateStocks , I first acquire the writeLock for the cart , do the processing
and then release the writeLock . In method getItems , I first acquire the readLock , do the
processing and then release the readLock .
Correctness
In both the method updateStocks and getItems , I both acquire the lock before processing
and release lock in the end. No lock is acquired after a lock is released. This is equivalent to
two-phase locking.
Issue of reads on predicates vs. multi-granularity locking
We don’t need to consider multi-granularity locking. There are just two level of hierarchy:
supermarket contains items. It is not necessary to use the more complex multi-granularity
locking. Predicates locking is not considered either. Because it is expensive to implement.
Performance
In method getItems , readLock is used which allows multiple threads to retrive the items at
the same time. My implementation has high concurrency as a result.
Question 4
There are two test classes CartTest and SupermarketTest to test for Cart and
Supermarket both for local test and RPC test. The localTest indicates which kind of test is
performed. There are two kind of tests. One kind is for testing the basic correctness of
implementation in single thread. It tests both the normal cases and cases where exceptions are
expected to be thrown.
Another is to test before-or-after atomicity. In the test testForConcurrency1 in
SupermarketTest , thread 1 repeatedly adds items to one cart and check out which will
update the corresponding items’ stock in the supermarket. thread 2 repeatedly calls the
updateStocks to replenish the corresponding items. The amount of stocks thread 1
consumes eqaul to the amount thread 2 increases. The test method runs the two threads at
the same time, when they finish, assert that the amount of stocks don’t change. In the test
testForConcurrency2 in SupermarketTest , thread 1 repeatedly call updateStocks
that increase the stocks and then updateStocks that decreases the stocks , thread 2
repeatedly call getItems , assert that the getItems returns the amount of stocks either after
decrease or after increase. In the test testForConcurrency1 in CartTest , thread 1
repeatedly adds items to one cart . thread 2 repeatedly remove the same items from the
private ReentrantReadWriteLock lock = new ReentrantReadWriteLock();1
same cart. The amount of items thread 1 adds eqaul to the amount thread 2 removes. The
test method runs the two threads at the same time, when they finish, assert that the quantity of
the item doesn’t change. In the test testForConcurrency2 in CartTest , thread 1
repeatedly call add and then remove , thread 2 repeatedly call getCartItems , assert that
the getCartItems returns the quantity of cart item either after add or after remove .
Question 5
Workload Design
There are two kinds of access to Supermarket service: one is by Cart and another is by
Admin Client . For Cart , the getItems call is invoked when Stock Client add a Cart
Item to the Cart and updateStocks is invoked when Mobile Client checkout. Assuming
on average, custom add 10 different items before checkout. Thus in runCartInteraction , it
calls updateStocks with probability of 0.1 and calls getItems with probability 0.9. For
Admin Client , it mainly uses updateStocks to replenish items. It calls updateStocks with
probability 0.8 and calls getItems with probability 0.2. Since Cart interaction is much more
frequent than Admin Client interaction. runAdminClientInteraction is called with
probability 0.01 and runCartInteraction is called with probability 0.99.
Experimental Setup
Hardware: MacBook Pro (15-inch, 2016) with processor 2.7 GHz Intel Core i7 and memory 16
GB 2133 MHz LPDDR3. With more powerful hardware, the throughput is expected to increase.
Data: 100000 items are generated in the supermarket initially.
Configuration: Use binary serialization in RPC. Worker with 5000 warm up runs and 20000
actual runs. Max thread pool set to 100 and min thread pool set to 10 in
SupermarketHTTPServer .
Each worker thread records the successful interactions and the time taken. Total successful
interactions divided by total time taken to get the throughput.
Discussion of Results
Above graph shows the throughput changes with number of client threads. We can see that the
throughput tends to decrease when we increase the number of clients. This maches my
expectations. More clients will compete for the computation resources, and each client will take
more time, thus the throughput decreases.
Question 1
Overall code organization
RPC semantics
Failure containment
All-or-nothing atomicity
Cart service
Supermarket service
Question 2
Method
Correctness
Issue of reads on predicates vs. multi-granularity locking
Performance
Question 3
Method
Correctness
Issue of reads on predicates vs. multi-granularity locking
Performance
Question 4
Question 5
Workload Design
Experimental Setup
Discussion of Results