Investigate what diagnostic correctness checking could be added to the skip list and other lock free data structures. This is time-boxed to five days. Some initial suggestions (thanks chenhao.qu@mongodb.com!) that would make for a good starting point:

For the skip list, I have some initial thoughts. If the search result is valid, the next_stack structure should have insert_list entries with lower level key larger than or equal to the higher level key and all the keys in the next_stack should be smaller than or equal to the search key.

We can also verify that the next key of the first key in the next_stack should be larger than the search key. If it is smaller, we should verify that the insert that follows the search should do a retry as we race with another insert to the same position.

In addition, we can walk every level of the insert list to verify the keys are in order. It is not enough to only walk the first level as the out of order key errors on the higher level may lead to future out of order keys in the lower level. In reconciliation, we have code to verify the first level is in order and we can extend that to the entire insert list.