Update

I have added a git repository where solutions to the different dojos will be. On the repository will also be what is needed for each challenge.
For this Code Dojo I will unfortunately not use C++ but Java instead. That is because this will be a microservice Code Dojo that will have some minimum CS in it. And right now I'm working on creating microservices in C++ I haven't gotten to the point where I run it with working requests.

Code Dojo

Category: Software Engineering and Computer science
Restriction: Non
Time: Small

You have a large set of data, represented by range.csv. The dataset has over 1 million rows. And data is stored in a database. The challenge is to retrieve the data with low latency as possible when a request comes in.

I had this problem at work. We had 500k rows of data in a database and the latency couldn't be slower than 500ms.

Solution

In the repository is a template Spring Boot microservice. Before diving into the code we need to discuss how to solve the problem.

Jeff Dean from Google visualize latency

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

This chart can give us some help how to minimize the latency for this problem. Comparing storing the data in a database to memory (or cache) we see a great increase in performance. But even if we can access the data from memory, it becomes a question how to get it fast. With that we need to look at algorithms. The one I shall implement is Binary Search which have a Big O notation of O(log(n)). And to Binary Search for us to use Binary Search, the data must be sorted which I will implement quicksort that has Big O notation of O(n log(n)).

There are many guides out there on how Spring Boot works, and how to get a service up-and-running so I will not go into that here.

To start with, a new Service will be created.

import ...

@Service
public class RangeService {

    private final List<RangeEntity> rangeList = new ArrayList<>();

    private final RangeRepository rangeRepo;

    private static final int BATCH_SIZE = 4000;

    private final Comparator<RangeEntity> compareRange = 
        Comparator.comparing(RangeEntity::getLowerBin);

    public RangeService(RangeRepository rangeRepo) {
        this.rangeRepo = rangeRepo;
    }

}

The important pieces of the service have been included here. The list will be our cache and contain the rows from the database. The RangeRepository will be the communication where the reading will happen. Not to read whole data at one go, it will be done in batches of 4000. And for later use when doing the binary search,

We can't start the loading from the database until it's up-and-running and we can't be sure that will happen when this constructor is called. We will use EventListener from Spring Framework to wait until the whole application is up before initiating the loading.

@EventListener(ApplicationReadyEvent.class)
public void handleApplicationStarup() {        
    initializeCache();
}

We can now implement initializeCache().

private void initializeCache() {
    Slice<RangeEntity> rangeOnPage;

    Pageable page = new PageRequest(0, BATCH_SIZE);
    while ( true ) {
        rangeOnPage = rangeRepo.findAll(page);
        rangeList.addAll(rangeOnPage.getContent());
        if (!rangeOnPage.hasNext() )
            break;
        page = page.next();
    }

    sortRange(rangeList, 0, rangeList.size());
}

A few bits here. Using pageable on findAll to get pages from the database. This means we get small batches, as we defined above the size, from the db without getting all of it and also keeping track of which data we have already retrieved and which data we have left. Slice works with pageable by saying if there is more data left or if we have reached the end. The while-loop will then request 4000 entries from the db each iteration and store them into our list. When there is no more data left to retrieve we break the loop and start sorting our list.

private void sortRange(List<RangeEntity> list, int start, int end) {
    if (start < end) {
        int pivot = pivot(list, start, end);
        sortRange(list, start, P - 1);
        sortRange(list, P + 1, end);
    }
}

Quicksort as we will implement it is a Divide and Conquer algorithm. It will pick a element from the list as a pivot, place the pivot in the middle while having all the element smaller as the pivot come earlier in the list and all the element larger being come later. Then it runs the algorithms on these two parts and continue until it's sorted.

There are different ways to choose the pivot element from the list. It could be the first, it could be the last or a random element. Or median from the list. I usually go for the last element on the list.

private int pivot(List<RangeEntity> list, int start, int end) {
    int pivot = list[end].getLow();
    int temp, p = start;

    for (int i = start; i < end; i++)
        if (v[i].getLow() <= pivot) {
            temp = v[i].getLow();
            v[i].setLow(v[p].getLow());
            v[p].setLow(temp);
            p++;
        }
    temp = v[end].getLow();
    v[end].setLow(v[p]);
    v[p].setLow(temp);
    return p;
}

As stated, I choose the last element as pivot here. As we need to keep track of where we are on moving element, we initiate p as our pointer where we are on the list. We then start a for-loop through the list. Each element we compare with our pivot. If they are larger we don't do anything about them. If they are smaller than the pivot we switch the value to the value our pointer is looking at. When we are done with this section of the list, section start to end, we switch the pivot value to the value we are currently looking at and return that value.

We have now implemented our quickSort for our list.

Next is the implementation if a request comes in and ask for the data in a specific range.

public RangeEntity findRange(int range) {
        return binarySearchRange(0, list.size(), range);
}

private RangeEntity binarySearchRange(int start, int end, int range) {
    if (end >= start) {
        int mid = start + (end - start) / 2;

        if (list[mid].getLow() < range && list[mid].getHigh() > range)
            return list[mid];

        if (list[mid].getLow() > range)
            return binarySearchRange(start, mid - 1, range);
        return binarySearchRange(mid + 1, end, range);
    }
    return null;
}

And here is the implementation of the binary search for our list. Binary search works that we compare our value with the element in the middle of the list. If our value is larger than the value in the middle, we search in the upper part. We do another call with the middle value as our starting point, the largest as our end and again compare our value with the value in this range.
If our value is smaller than the middle, we search for it in the lower part. As we can see, the binary search needs a sorted list to work.

Conclusion

We have now implemented all the parts needed for this microservice to be in use. We can have a large set of data in our db and have a minimum of latency for each request to retrieve the data. We have learned to implement two good algorithms that every engineers should know: quick sort and binary search. And we have worked with a microservice.

Next Code Dojo in December.