Thursday 24 December 2020

Ordered data structure using B+Tree and Skip List

This post is based on rum-conjecture paper for data systems. This paper talks about read, update & memory overhead of data structure and gives some nice examples on how balancing 2 factors leaves 3rd one in bad shape. 

 
Source : http://daslab.seas.harvard.edu/rum-conjecture/



Some of the popular read optimized ordered Key-value data structure are BST , Skip List , Prefix Tree , B+ tree etc.

To make read fast it does some trade off on space. 

In this post I will share space(i.e memory) efficient data structure that takes ideas from B+Tree and Skip List to create a new ordered data structure. 

Quick recap before we build our own data structure. 

B+ Tree

B+Tree is variant BST, every node contains n children. Tree contains 2 types of nodes root, internal & leaves node(i.e external).

Leaves node contains all the entries. Root and internal nodes will contain just keys and pointers to the leaf node. 

Every node has some capacity and when it gets full then split process is used to create another node that will have half of the values from the original node. This splitting helps in keeping allocation in control and also reduces rebalancing overhead as compared to BST.


B+Tree. Source:Wikipedia

This is a very popular data structure for databases, all relational databases and many non relational databases provide indexes that are backed up by B+Tree. 

Its popularity has only increased over time.

Now some databases are built using Log structured merge tree that solves some of the issues with B+Tree.

One of the trade off with B+Tree is that keys are stored at multiple places(leaf & internal nodes) and splits of nodes can cause cascade effects.

Every value is wrapped up in some Node container and that causes extra 32 bit overhead per value and also extra indirection to get to value.

Extra indirection does not work well with current CPU that have big cache lines. 

Skip List

Skip list takes ideas from the ordered link list and to make read and write efficient it adds upper layer or lane of sorted link list that has fewer values and acts like a fast lane to get to value.  

 

Skip List. Source:Wikipedia

This type of structure helps with concurrency because installing new value can be done with lock free operation like CAS.

One of the big trade-offs in skip lists is many keys are duplicated and level for key is decided randomly due to which every time skip levels could be very different although input is the same.

This also has other memory overhead due to extra container objects required to hold the values like B+Tree.

Let's look at new data structures that can take some ideas from these 2 data structures and reduce memory overhead and still maintain performance. 

B+Skip List

I don't have any good name for this DS, so let's call it B+SkipList.

I will take few ideas 

- Ordered memory block

B+Tree allocate nodes that can hold n values in an array. These values are stored in order by using simple array manipulation. This gives the nice property that related values are close together and have good chances to be in the same cache line. 

- Split node when full

B+Tree split full node into 2 to balance level tree. 

- Skip Lanes

Although SkipList is just an ordered link list but skip lane idea makes linked list like array, lower level nodes can be accessed quickly by skip lanes.


Let's create something !

Ordered memory block is straightforward to implement. It will look something like below

Ordered Array



Code snippet for ordered collection. I will take an example of int value for simplicity but the same thing applies for any custom object also.  

public OrderedIntCollection(int maxElement) {
this.maxElement = maxElement;
this.members = new int[1 + maxElement];
this.members[0] = Integer.MAX_VALUE;
this.length = 0;
}

public void insert(int value) {
this.min = Math.min(min, value);
this.max = Math.max(max, value);

int offSet = offSet(value, members, length);

if (members[offSet] == value) {
return; //This will skip copy overhead
}

shiftFrom(offSet);
members[offSet] = value;
length++;
}


Our first building block is ready, let's move to split logic now.

- Capacity check. 

This is required to decide if split is required or not.

- Split logic.

This will do an actual split and return a new node.

- Additional metadata

Now nodes can be split so we need to track some meta data like min, max value.

Split process might look like below



Split is one way to handle when a node is full and it has some advantage but other options are also available like extending current nodes and it could be a useful strategy in some cases to reduce memory fragmentation. We will talk about this later.


Code snippet for split. It is simple array manipulation and makes sure that each node is independent and value can only contain 1 node. 


public boolean hasCapacity(int count) {
return length + count < members.length;
}
public OrderedIntCollection split() {
int half = members.length / 2;

//Split and allocate new
int[] copy = new int[1 + maxElement];
int newLength = this.length - half;
System.arraycopy(members, half, copy, 0, newLength);
copy[newLength] = Integer.MAX_VALUE;
OrderedIntCollection collection = new OrderedIntCollection(maxElement, copy, newLength);

//Update current
this.members[half] = Integer.MAX_VALUE;
this.length = half;
this.max = members[half - 1];
Arrays.fill(members, half + 1, members.length, 0);

return collection;

} 


Lets move to the final piece that is skip lanes.

With the split process now we can have multiple nodes and we have to keep track of all the nodes and maintain order of nodes.

Few things are required for lane data structure 

- Dynamic list that allows you to add elements at any position.

- Ordering info for comparing nodes to identify which node comes first.

- Some way of finding which node will contain value.

- Some efficient algorithm to search values in all the available nodes.


Let's enhance OrderedIntCollection to add ordering info

public int max() {
return max;
}

public int min() {
return min;
}

@Override
public int compareTo(Integer value) {
if (value < min) return 1;
else if (value > max) return -1;
return 0;
}

Min/Max and compareTo function will help in having all the ordering info.

compareTo function will be later used to find which node can contain value.

With help of compareTo now we can store all the nodes in some array based data structure.

At high level it might look at something like below

B+ Skip List




This layout has some nice property like

- Keys are not duplicated.

This is a big gain and helps in reducing memory requirements. Only additional memory allocation is for lists that maintain reference to nodes. 

- Child node are just at 2nd level

Child nodes can be always reached in just 2 hops, as compared to n ( tree depth) in b+tree or SkipList. 

- Fanout of node is good.

It gets fanout the same as B+Tree without overhead of additional internal nodes and it plays an important role in read/writes.

- Data locality in single node.

Some of the discussion after the RUM paper was published was to add Cache also as dimension to look at data structure, so it becomes CRUM.

Packing everything together helps with the "C" part as it provides better cache locality and this is one of the big gains because it can take some benefits of the cache line of the processors.

Since nodes reference is stored in List based structure and are in order, so binary search can be used to identify nodes that are target for read or write.

Read/Write can be done in Log N time. Once a node is identified then it is sequential scan to locate value and that can add some cost but it is possible to use binary search within the node also to reduce overhead.

Trade off

Some of the trade off

Binary search can't be used 100% for writing.

Read request can be always served by binary search but for writing we need a hybrid approach, for eg in above sample if value is inserted that does not fall in any range then sequential search is required to find right node. Some of the sample value that can trigger sequential search are 1 (i.e min value), 300(i.e max value),105 (i.e comes in between node 2 and 3) 

Fragmentation

Due to splitting rules we might see many nodes that are half filled but that issue can be solved by relaxing the splitting rule like allow to choose between split or extend based on data distribution. 

Compact nodes by merging content. 

Code snippet of Skip Lane.
public class OrderedInts {
private final List<OrderedIntCollection> values = new ArrayList<>();
private final int blockSize;
private final AtomicLong bsHit = new AtomicLong();
private final AtomicLong seqHit = new AtomicLong();

public OrderedInts(int blockSize) {
this.blockSize = blockSize;
}

public void insert(int value) {
OrderedIntCollection e = search(value);
e.insert(value);
}

private OrderedIntCollection search(int value) {
if (values.isEmpty()) {
OrderedIntCollection last = new OrderedIntCollection(blockSize);
values.add(last);
return last;
} else {
int position = binarySearch(values, value);
if (position >= 0) {
bsHit.incrementAndGet();
return splitIfRequired(value, position, values.get(position));
} else {
seqHit.incrementAndGet();
return sequentialSearch(value);
}
}
}
}

Conclusion

In computer science we only have trade off and nothing comes for free.
RUM way of looking at data structure provides key insights on trade-off and also provides some ideas around new data structure possibility.
 

22 comments:

  1. investment advice

    Welcome to Bulls & Bears, Get the latest trading news and investment advice in the UK. We deliver insight to trading professionals and retail investors.

    to get more -https://www.bullsandbears.co.uk/

    ReplyDelete
  2. I value the post. Really thank you! Keep writing.Tree Cutting Round Rock

    ReplyDelete
  3. It is moreover an outstanding release we actually liked going through. It isn't really day-to-day i develop the chance to discover anything. Emergency Tree Service Rancho Cucamonga

    ReplyDelete
  4. This comment has been removed by the author.

    ReplyDelete
  5. Pine trees have green to bluish grey leaves in the form of needles that are arranged in bundles of two to five or six to eight, depending on species. How long does it take a pine tree to grow

    ReplyDelete
  6. There will be times when your trees will get rotten. eliminate tree hazards Elk Grove

    ReplyDelete
  7. Tree removal companies are well versed in how to take down trees safely and quickly so that your property is returned to a safe and beautiful state as soon as possible. Emergency Tree Service Rancho Cucamonga

    ReplyDelete
  8. Tree removal starts with a tree assessment and the location of the tree. To ensure that the tree is taken out safely the tree trimmer needs to plan ahead. Tree removal Sanford NC

    ReplyDelete
  9. Thanks for the informative and helpful post, obviously in your blog everything is good..
    data scientist course in malaysia

    ReplyDelete
  10. atom coin price

    Cosmos current price is $35.11 with a marketcap of $9.82 B. Its price is -6.43% down in last 24 hours.

    Visit our website by just clicking on - atom coin price

    ReplyDelete
  11. You will then, at that point, need to find out if the assistance holds protection that ensures the two representatives and your home if there should be an occurrence of mishaps. tree removal

    ReplyDelete
  12. IT's very informative blog and useful article thank you for sharing with us , keep posting learn more about Product engineering services | Product engineering solutions.

    ReplyDelete
  13. You may likewise search for their confirmations which show that they have previously rehearsed the said administration and have proactively granted. tree surgeon dunstable

    ReplyDelete
  14. Educative Minds was established by a group of professionals with extensive backgrounds working in residential education and university administration in India. The parent community has benefited from the admissions counselor's over 15 years of experience in getting their children into top-tier local boarding schools and universities. Educative Minds Educative Minds

    ReplyDelete
  15. Boarding high school. We'd like to present ourselves as one of the country's premier K-12 and higher education advisory and Outsourcing marketing partnerships.
    Boarding high school

    ReplyDelete
  16. This blog information is very useful. Thanks for sharing such a great infomation. we are provide best data science course in Delhi. For more information click the link.we are provide best data science course in Delhi. For more information click the link.
    DATA SCIENCE COURSE

    ReplyDelete
  17. This blog information is very useful. Thanks for sharing such a great information. we are provide best data science course in Delhi. For more information click the link. we are provide best data science course in Delhi. For more information click the link.
    DATA SCIENCE TRAINING INSTITUTE IN INDIA

    ReplyDelete