Behold! Big Data at Fast Speed!
<p><i>Oak0.2 Release: Significant Improvements to Throughput, Memory Utilization, and User Interface</i></p><p>By <a href="https://www.linkedin.com/in/braginskyanastasia/">Anastasia Braginsky</a>, Sr. Research Scientist, Verizon Media Israel<br/></p><figure data-orig-width="186" data-orig-height="148"><img src="https://64.media.tumblr.com/f1b228f30567f7bb9da82dd124973cfe/813196bd531067cb-f0/s540x810/a6c449d21e0a6588bf547c58f3db63fa4a313a2b.png" alt="image" data-orig-width="186" data-orig-height="148"/></figure><p>Creating an open source software is an ongoing and exciting process. Recently, <a href="https://github.com/yahoo/oak">Oak open-source library</a> delivered a new release: <a href="https://github.com/yahoo/Oak/blob/master/release-notes.md">Oak0.2,</a> which summarizes a year of collaboration. Oak0.2 makes significant improvements in throughput, memory utilization, and user interface. <b><br/></b></p><p>OakMap is a highly scalable Key-Value Map that keeps all keys and values off-heap. The <a href="https://yahoodevelopers.tumblr.com/post/178045146133/introducing-oak-an-open-source-scalable-key-value">Oak project is designed for Big Data</a> real-time analytics. Moving data off-heap, enables working with huge memory sizes (above 100GB) while JVM is <a href="http://minborgsjavapot.blogspot.com/2019/07/java-chroniclemap-part-1-go-off-heap.html">struggling</a> to manage such heap sizes. OakMap implements the industry-standard Java8 ConcurrentNavigableMap API and more. It provides strong (atomic) semantics for read, write, and read-modify-write, as well as (non-atomic) range query (scan) operations, both forward and backward. OakMap is optimized for big keys and values, in particular, for incremental maintenance of objects (update in-place). It is <a href="https://github.com/yahoo/Oak/wiki/Performance-Evaluation">faster and scales better</a> with additional CPU cores than the popular Java’s ConcurrentNavigableMap implementation<a href="https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentSkipListMap.html"> ConcurrentSkipListMap</a>. </p><p>Oak data is written to the off-heap buffers, thus needs to be serialized (converting an object in memory into a stream of bytes). For retrieval, data might be deserialized (object created from the stream of bytes). In addition, to save the cycles spent on deserialization, we allow reading/updating the data directly via <a href="https://github.com/yahoo/Oak#oak-buffers">OakBuffers</a>. Oak provides this functionality under the <a href="https://github.com/yahoo/Oak#data-retrieval">ZeroCopy API</a>.</p><p>If you aren’t already familiar with Oak, this is an excellent <a href="https://github.com/yahoo/Oak#install">starting point to use it</a>! Check it out and <a href="mailto:firstname.lastname@example.org">let us know</a> if you have any questions.</p><p><b>Oak keeps getting better: Introducing Oak0.2</b><br/></p><p>We have made a ton of great improvements to Oak0.2, adding a new stream scanning for improved performance, releasing a ground-up rewrite of our Zero Copy API’s buffers to increase safety and performance, and decreasing the on-heap memory requirement to be less than 3% of the raw data! As an exciting bonus, this release also includes a new version of our off-heap memory management, eliminating memory fragmentation. </p><p>Below we dive deeper into sub-projects being part of the release.<br/></p><p><b><b>Stream Data Faster</b><br/></b></p><p>When scanned data is held by any on-heap data structures, each next-step is very easy: get to the next object and return it. To retrieve the data held off-heap, even when using Zero-Copy API, it is required to create a new OakBuffer object to be returned upon each next step. Scanning Big Data that way will create millions of ephemeral objects, possibly unnecessarily, since the application only accesses this object in a short and scoped time in the execution. </p><figure data-orig-width="588" data-orig-height="394" class="tmblr-full"><img src="https://64.media.tumblr.com/dd176d139314d78adde6910009efef78/813196bd531067cb-8e/s540x810/1a552e24e022eb6a97c675939465e7f5da971b59.png" alt="image" data-orig-width="588" data-orig-height="394"/></figure><figure data-orig-width="1014" data-orig-height="670" class="tmblr-full"><img src="https://64.media.tumblr.com/8ba19cb1b9e3dd7db75968b58b66367a/813196bd531067cb-3d/s540x810/0b5e8bd85d895709fce2f0d6be608a66cec91f3a.png" alt="image" data-orig-width="1014" data-orig-height="670"/></figure><p>To avoid this issue, the user can use our new <a href="https://github.com/yahoo/oak#data-retrieval">Stream Scan API</a>, where the same OakBuffer object is reused to be redirected to different keys or values. This way only one element can be observed at a time. Stream view of the data is frequently used for flushing in-memory data to disk, copying, analytics search, etc. </p><p>Oak’s Stream Scan API outperforms CSLM by nearly 4x for the ascending case. For the descending case, Oak outperforms CSLM by more than 8x even with less optimized non-stream API. With the Stream API, Oak’s throughput doubles. More details about the performance evaluation can be <a href="https://github.com/yahoo/Oak/wiki/Performance-Evaluation">found here</a>.</p><figure data-orig-width="605" data-orig-height="418" class="tmblr-full"><img src="https://64.media.tumblr.com/231775d7d9c634282649ca965c756c8f/813196bd531067cb-2e/s540x810/f56f4dcea32986c3265a2483a275c5e82cd5c8bc.png" alt="image" data-orig-width="605" data-orig-height="418"/></figure><figure data-orig-width="605" data-orig-height="418" class="tmblr-full"><img src="https://64.media.tumblr.com/40171de0fbd887ec7046b5cf106a7186/813196bd531067cb-b2/s540x810/053a440e53678d0011899cd3584e6fd14744d27c.png" alt="image" data-orig-width="605" data-orig-height="418"/></figure><p><b><br/><br/></b><b>Safety or Performance? Both!</b><b><br/></b></p><p>OakBuffers are core ZeroCopy API primitives. Previously, alongside with OakBuffers, OakMap exposed the underlying ByteBuffers directly to the user, for the performance. This could cause some data safety issues such as an erroneous reading of the wrong data, unintentional corrupting of the data, etc. We couldn’t choose between safety and performance, so strived to have both!</p><p>With Oak0.2, ByteBuffer is never exposed to the user. Users can choose to work either with OakBuffer which is safe or with OakUnsafeDirectBuffer which gives you faster access, but use it carefully. With OakUnsafeDirectBuffer, it is the user’s responsibility to synchronize and not to access deleted data, if the user is aware of those issues, OakUnsafeDirectBuffer is safe as well.</p><p>Our safe OakBuffer works with the same, great and known, OakMap performance, which wasn’t easy to achieve. However, if the user is interested in even superior speed of operations, any OakBuffer can be cast to OakUnsafeDirectBuffer. </p><figure data-orig-width="442" data-orig-height="387" class="tmblr-full"><img src="https://64.media.tumblr.com/8e05052b8398d65ae55c3ca9ee93be76/813196bd531067cb-59/s540x810/7069582b6c8a98baa9c47d77491dade45904a060.png" alt="image" data-orig-width="442" data-orig-height="387"/></figure><p><b>Less (metadata) is more (data)</b><br/></p><p>In the initial version of OakMap we had an object named handler that was a gateway to access any value. Handler was used for synchronization and memory management. Handler took about 256 bytes per each value and imposed dereferencing on each value access. </p><p>Handler is now replaced with an 8-bytes header located in the off-heap, next to the value. No dereferencing is needed. All information needed for synchronization and memory manager is kept there. In addition, to keep metadata even smaller, we eliminated the majority of the ephemeral object allocations that were used for internal calculations.</p><p>This means less memory is used for metadata and what was saved goes directly to keep more user data in the same memory budget. More than that, JVM GC has much less reasons to steal memory and CPU cycles, even when working with hundreds of GBs.</p><figure data-orig-width="600" data-orig-height="371" class="tmblr-full"><img src="https://64.media.tumblr.com/738f186c7d50388f1018c965e3cb714e/813196bd531067cb-74/s540x810/b2fcb61b0d3cd6682cf615c07e0f0bd0395ba668.png" alt="image" data-orig-width="600" data-orig-height="371"/></figure><p><b><br/>Fully Reusable Memory for Values<br/></b></p><p>As explained above, 8-byte off-heap headers were introduced ahead of each value. The headers are used for memory reclamation and synchronization, and to hold lock data. As thread may hold the lock after a value is deleted, the header’s memory couldn’t be reused. Initially the header’s memory was abandoned, causing a memory leak. </p><p>The space allocated for value is exactly the value size, plus header size. Leaving the header not reclaimed, creates a memory “hole” where a new value of the same size can not fit in. As the values are usually of the same size, this was causing fragmentation. More memory was consumed leaving unused spaces behind.</p><p>We added a possibility to reuse the deleted headers for new values, by introducing a sophisticated memory management and locking mechanism. Therefore the new values can use the place of the old deleted value. With Oak0.2, the scenario of 50% puts and 50% deletes is running with a stable amount of memory and performs twice better than CSLM.</p><p>We look forward to growing the Oak community! We invite you to explore the project, use OakMap in your applications, raise issues, suggest improvements, and contribute code. If you have any questions, please feel free to send us a <a href="mailto:email@example.com">note</a>. It would be great to hear from you!</p><p><b>Acknowledgements:</b></p><p><a href="https://www.linkedin.com/in/liran-funaro-6752a737/">Liran Funaro</a>, <a href="https://www.linkedin.com/in/eshcar/">Eshcar Hilel</a>, <a href="https://www.linkedin.com/in/eranmeirsw/">Eran Meir</a>, <a href="https://www.linkedin.com/in/yoavzuriel/">Yoav Zuriel</a>, <a href="https://www.linkedin.com/in/ebortnik/">Edward Bortnikov</a>, <a href="https://www.linkedin.com/in/yonigottesman/">Yonatan Gottesman</a></p>