Uploaded image for project: 'Blazegraph (by SYSTAP)'
  1. Blazegraph (by SYSTAP)
  2. BLZG-641 Improve load performance
  3. BLZG-1665

Reduce commit latency by parallel checkpoint by level of dirty pages in an index

    Details

    • Type: Sub-task
    • Status: Done
    • Priority: Medium
    • Resolution: Done
    • Affects Version/s: None
    • Fix Version/s: BLAZEGRAPH_2_2_0
    • Component/s: B+Tree, HTree
    • Labels:
      None

      Description

      The index flush to the write set is slower than the write cache flush to the disk. So index eviction is a bottleneck here. We might be able to do something more intelligent about gathering together the dirty pages to be flushed and organizing them in terms of index locality and even doing evictions by B+Tree level in parallel (we have to evict from the leaves up, but we could evict all leaves in parallel).

      Note: It might not be possible to parallelize this operation for the HTree in quite the same fashion. The HTree has a different concept of "depth" or "level" than the BTree. The requirement would be a means to identify dirty pages that are independent of one another. So first all leaf buckets, then all parents of those leaf buckets, and this continues recursively until we reach the top directory page.

      Note: The strategy described at BLZG-1664 is not likely to reduce the commit bottleneck. Instead it is focused on reducing the average latency of AbstractBTree.touch() during writes since touch() drives evictions.

      TODO This requires support for concurrent NodeSerializers. The existing class is only for a single writer. The code currently makes gratuitous NodeSerializer instances to support the parallelism and then drops them after each level. This is likely to create a lot of short term heap growth. This should be amortized by either having a pool for the life of the mutable index or some other technique such as only using multiple threads when we have a large number of pages being evicted at the same time (e.g., 10 or more).

      TODO The maximum parallelism should be configurable (it is currently hackable from the environment, but that is not a long term solution) - see the AbstractHTree and AbstractBTree constructors (bottom of these methods).

      TODO This also needs to be done for the HTree.

      See BLZG-1663 for more background on this.

        Activity

        Hide
        bryanthompson bryanthompson added a comment -

        PR: https://github.com/SYSTAP/bigdata/pull/233 is good. Change will go into 2.1.

        Show
        bryanthompson bryanthompson added a comment - PR: https://github.com/SYSTAP/bigdata/pull/233 is good. Change will go into 2.1.
        Hide
        bryanthompson bryanthompson added a comment - - edited

        This PR (https://github.com/SYSTAP/bigdata/pull/233) was left behind by accident. bradbebee has merged master into this branch. Per Beebs, am reviewing the following files:

        • AbstractHTree
        • AbstractBTree
        • BTreeCounters

        michaelschmidt We do need to benchmark this PR (potentially after pulling it into the release branch). This has changes related to the performance counters. We need to ensure that we are not imposing too much overhead in this part of the code.

        martyncutcher FYI. The parallel checkpoint by level set code.

        Note: Review of merge up is done. In CI.

        Note: Recommend benchmark of this branch before merging down (so please merge up master into it before benchmarking).

        Show
        bryanthompson bryanthompson added a comment - - edited This PR ( https://github.com/SYSTAP/bigdata/pull/233 ) was left behind by accident. bradbebee has merged master into this branch. Per Beebs, am reviewing the following files: AbstractHTree AbstractBTree BTreeCounters michaelschmidt We do need to benchmark this PR (potentially after pulling it into the release branch). This has changes related to the performance counters. We need to ensure that we are not imposing too much overhead in this part of the code. martyncutcher FYI. The parallel checkpoint by level set code. Note: Review of merge up is done. In CI. Note: Recommend benchmark of this branch before merging down (so please merge up master into it before benchmarking).
        Hide
        michaelschmidt michaelschmidt added a comment - - edited

        Benchmarked the branch itself (i.e., https://github.com/SYSTAP/bigdata/commit/fddde601aa64db7bc29eeb0d0bce5a5aed864882).

        Comparing to 2.1.0, the benchmark results all look good, everything is in the tolerance of [-0.7;0.7]%, sometimes a bit slower, sometimes a bit faster. Also loading times are stable. The only exception is LUBM, where we have 5% speedup due to Q2+Q9 -> note that we had an unexplainable regressions for exactly those two queries in 2.1.0, which now seems to be back to normal.

        So from a benchmarking perspective, nothing speaks against merging down this branch.

        Brad Bebee bryanthompson

        Show
        michaelschmidt michaelschmidt added a comment - - edited Benchmarked the branch itself (i.e., https://github.com/SYSTAP/bigdata/commit/fddde601aa64db7bc29eeb0d0bce5a5aed864882 ). Comparing to 2.1.0, the benchmark results all look good, everything is in the tolerance of [-0.7;0.7] %, sometimes a bit slower, sometimes a bit faster. Also loading times are stable. The only exception is LUBM, where we have 5% speedup due to Q2+Q9 -> note that we had an unexplainable regressions for exactly those two queries in 2.1.0, which now seems to be back to normal. SP2Bench: https://docs.google.com/spreadsheets/d/1xtOf9C-SycmynC8tZg6aDkjVWU0dcsj-l_da4o0gjtw/edit#gid=2083807769 BSBM: https://docs.google.com/spreadsheets/d/1i-JnEy_W5Pt4AWg87oxg564GYkz3zaxxmIS9H4OKssE/edit#gid=1221709459 LUBM: https://docs.google.com/spreadsheets/d/12rbe77GOqnRmi4yFjWE1D1hXnd2jB-WPUV2uVJZEmwE/edit#gid=153334433 Govtrack: https://docs.google.com/spreadsheets/d/1MFF3kQmzQv7LzBFjbNX7bhc1eLgCVPQH0vQA6SxeHuQ/edit#gid=1870917767 So from a benchmarking perspective, nothing speaks against merging down this branch. Brad Bebee bryanthompson
        Hide
        bryanthompson bryanthompson added a comment -

        Assigned to brad to bring in for master and 2.1.1

        Show
        bryanthompson bryanthompson added a comment - Assigned to brad to bring in for master and 2.1.1
        Hide
        bryanthompson bryanthompson added a comment -

        Brad Bebee I have merged https://github.com/SYSTAP/bigdata/pull/233 into master.

        Brad Bebee I have assigned https://github.com/SYSTAP/bigdata/pull/233 to you to merge into 2.1.1. This needs to be done for a release.

        Show
        bryanthompson bryanthompson added a comment - Brad Bebee I have merged https://github.com/SYSTAP/bigdata/pull/233 into master. Brad Bebee I have assigned https://github.com/SYSTAP/bigdata/pull/233 to you to merge into 2.1.1. This needs to be done for a release.

          People

          • Assignee:
            beebs Brad Bebee
            Reporter:
            bryanthompson bryanthompson
          • Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved: