## 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
For `Cart` , only method `add` and `checkout` invoked the `supermarket` method. When `Supermarket` fails,
`add` will not add new item to cart, nothing happens. In `checkout` method, the `Cart` is cleared only when the invoke of `updateStocks` success. For `Supermarket`, the actual operations are conducted only when all the ids of the input are valid. Thus, if one of id is invalid, exception throwed and nothing happens.
## Question 2
### Method
In `CartImp`, I define following instance variable.
“`java
private Map
“`
Each cart is a `ConcurrentHashMap` mapping cart item id to cart item. The `ConcurrentHashMap` ensures the atomicity of adding or removing cart items. The atomicity of change cart item is achieved by using `ReentrantReadWriteLock` in `MutableCartItem` class. A single `ReentrantReadWriteLock` is used in the `MutableCartItem` class. When reading `quantity`, `readlock` is used. When chaning `quantity`, the `writelock` is used.
### Correctness
Hashmap level atomicity is achieved due to the fact of the implementation of `ConcurrentHashMap` in the library. `MutableCartItem` level atomicity is achieved using the `ReentrantReadWriteLock`. The overall effect is equivalent to a single global lock.
###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
My method will allow multiple threads to get the cart items. It even allows multiple threads to updates of different cart items. It has high concurrency.
## Question 3
### Method
In `SupermarketImp`, I define following instance variable.
“`java
ConcurrentHashMap
“`
It is a `ConcurrentHashMap` mapping item id to item. The `ConcurrentHashMap` ensures the atomicity of adding or removing items. The atomicity of updating item is achieved by using `ReentrantReadWriteLock` in `MutableItem` class. A single `ReentrantReadWriteLock` is used in the `MutableItem` class. When reading the fields, `readlock` is used. When chaning the fields, the `writelock` is used.
### Correctness
Hashmap level atomicity is achieved due to the implementation of `ConcurrentHashMap` is thread-safe. `MutableCartItem` level atomicity is achieved using the `ReentrantReadWriteLock`. The overall effect is equivalent to a single global lock.
###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
My method will allow multiple threads to retrive the items. It even allows multiple threads to updates of different items. It has high concurrency.
## 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 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.