Recently I did a Kata where I implemented an 'Auction' class which accepts bids by users on items for some price.
The requirements specified that we should be able to retrieve the following:
- all the items that a user has bid on
- all bids on an item
- and the current winning bid on an item.
This suggested to me that I should have two maps:
HashMap<Item, PriorityQueue<Bid>> bidsForItems;
HashMap<User, HashSet<Item>> itemsUsersHaveBidOn;
Easy so far.
Making it Thread Safe
So it was quite easy to make this thread safe. I simple utilised Concurrent collections.
ConcurrentHashMap<Item, PriorityBlockingQueue<Bid>> bidsForItems;
ConcurrentHashMap <User, CopyOnWriteSet<Item>> itemsUsersHaveBidOn;
The bid method was pretty much unchanged.
However, there is one problem with this implementation: the two maps can be out of sync.
Eg imagine two threads:
Thread 1: Updates bidsForItems saying that there is a new bid on Item Fridge which happens to be a winning bid by User Chris;
Thread 1: Updates itemsUsersHaveBidOn map saying that User Chris has placed a bid on Item Fridge.
Thread 2 wants to call GetWinningBid for Item Fridge, find out which User has placed the winning bid, and see what other items this user has bid on.
If Thread 2 executes between the two actions by thread 1 then Thread 2 might get inconsistent results.
To make it consistent I utilised the CopyOnWrite Pattern..
Firstly, I abstracted the two maps into a 'DataStore' class:
Then the 'Auction' class must hold an atomic reference to the DataStore:
Then the bid method looks like this:
We take a copy of the existing datastore and create a new one from it to include the new bid. Then we perform a compare and swap operation to update the AtomicReference to the datastore. The compare and swap method in the while condition will return true if the value is updated (and the loop with terminate) but false if the datastore that we copied has been modified since we took our copy.
The problem with this implementation is that we are creating a new HashMap every time there is a bid. There is one nice optimisation that can be done where instead of creating a new Map every time, we have an immutable wrapper class around it like this:
The bid method was pretty much unchanged.
However, there is one problem with this implementation: the two maps can be out of sync.
Eg imagine two threads:
Thread 1: Updates bidsForItems saying that there is a new bid on Item Fridge which happens to be a winning bid by User Chris;
Thread 1: Updates itemsUsersHaveBidOn map saying that User Chris has placed a bid on Item Fridge.
Thread 2 wants to call GetWinningBid for Item Fridge, find out which User has placed the winning bid, and see what other items this user has bid on.
If Thread 2 executes between the two actions by thread 1 then Thread 2 might get inconsistent results.
Making it Consistent
To make it consistent I utilised the CopyOnWrite Pattern..
Firstly, I abstracted the two maps into a 'DataStore' class:
Then the 'Auction' class must hold an atomic reference to the DataStore:
Then the bid method looks like this:
We take a copy of the existing datastore and create a new one from it to include the new bid. Then we perform a compare and swap operation to update the AtomicReference to the datastore. The compare and swap method in the while condition will return true if the value is updated (and the loop with terminate) but false if the datastore that we copied has been modified since we took our copy.
The problem with this implementation is that we are creating a new HashMap every time there is a bid. There is one nice optimisation that can be done where instead of creating a new Map every time, we have an immutable wrapper class around it like this:
No comments:
Post a Comment