[jira] [Comment Edited] (MESOS-993) Performance issue during replicated log catch-up when the initial log position is large

[Jie Yu (JIRA)]

    [ 
https://issues.apache.org/jira/browse/MESOS-993?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13899877#comment-13899877
 ] 

Jie Yu edited comment on MESOS-993 at 2/13/14 1:10 AM:
-------------------------------------------------------

We may wanna choose to use boost interval_set. I did a simple experiment:

{code}
#include <iostream>

#include <boost/icl/interval.hpp>
#include <boost/icl/interval_set.hpp>

#include <gtest/gtest.h>

using namespace boost::icl;

TEST(IntervalSet, Basic)
{
  interval_set<int> iset;

  iset.insert(42);
  iset.insert(interval<int>::closed(10, 1000000000));

  EXPECT_FALSE(contains(iset, 9));
  EXPECT_TRUE(contains(iset, 42));
  EXPECT_TRUE(contains(iset, 50));
  EXPECT_TRUE(contains(iset, 60));
  EXPECT_TRUE(contains(iset, 70));
  EXPECT_TRUE(contains(iset, 80));
  EXPECT_TRUE(contains(iset, 1000000000));
  EXPECT_FALSE(contains(iset, 1000000001));

  iset -= 50; 

  EXPECT_FALSE(contains(iset, 50));

  iset -= interval<int>::closed(60, 80);

  EXPECT_FALSE(contains(iset, 60));
  EXPECT_FALSE(contains(iset, 70));
  EXPECT_FALSE(contains(iset, 80));

  for (interval_set<int>::iterator it = iset.begin();
       it != iset.end(); ++it) {
    std::cout << *it << std::endl;
  }
}
{code}

{noformat}
[tw-mbp-jyu playground]$ ./main --gtest_filter=IntervalSet.*
Running main() from gtest_main.cc
Note: Google Test filter = IntervalSet.*
[==========] Running 1 test from 1 test case.
[----------] Global test environment set-up.
[----------] 1 test from IntervalSet
[ RUN      ] IntervalSet.Basic
[10,50)
(50,60)
(80,1000000000]
[       OK ] IntervalSet.Basic (0 ms)
[----------] 1 test from IntervalSet (0 ms total)

[----------] Global test environment tear-down
[==========] 1 test from 1 test case ran. (0 ms total)
[  PASSED  ] 1 test.
{noformat}


was (Author: jieyu):
We may wanna choose to use boost interval_set. I did a simple experiment:

{code:c++}
#include <iostream>

#include <boost/icl/interval.hpp>
#include <boost/icl/interval_set.hpp>

#include <gtest/gtest.h>

using namespace boost::icl;

TEST(IntervalSet, Basic)
{
  interval_set<int> iset;

  iset.insert(42);
  iset.insert(interval<int>::closed(10, 1000000000));

  EXPECT_FALSE(contains(iset, 9));
  EXPECT_TRUE(contains(iset, 42));
  EXPECT_TRUE(contains(iset, 50));
  EXPECT_TRUE(contains(iset, 60));
  EXPECT_TRUE(contains(iset, 70));
  EXPECT_TRUE(contains(iset, 80));
  EXPECT_TRUE(contains(iset, 1000000000));
  EXPECT_FALSE(contains(iset, 1000000001));

  iset -= 50; 

  EXPECT_FALSE(contains(iset, 50));

  iset -= interval<int>::closed(60, 80);

  EXPECT_FALSE(contains(iset, 60));
  EXPECT_FALSE(contains(iset, 70));
  EXPECT_FALSE(contains(iset, 80));

  for (interval_set<int>::iterator it = iset.begin();
       it != iset.end(); ++it) {
    std::cout << *it << std::endl;
  }
}
{code}

{noformat}
[tw-mbp-jyu playground]$ ./main --gtest_filter=IntervalSet.*
Running main() from gtest_main.cc
Note: Google Test filter = IntervalSet.*
[==========] Running 1 test from 1 test case.
[----------] Global test environment set-up.
[----------] 1 test from IntervalSet
[ RUN      ] IntervalSet.Basic
[10,50)
(50,60)
(80,1000000000]
[       OK ] IntervalSet.Basic (0 ms)
[----------] 1 test from IntervalSet (0 ms total)

[----------] Global test environment tear-down
[==========] 1 test from 1 test case ran. (0 ms total)
[  PASSED  ] 1 test.
{noformat}

> Performance issue during replicated log catch-up when the initial log 
> position is large
> ---------------------------------------------------------------------------------------
>
>                 Key: MESOS-993
>                 URL: https://issues.apache.org/jira/browse/MESOS-993
>             Project: Mesos
>          Issue Type: Bug
>    Affects Versions: 0.17.0
>            Reporter: Jie Yu
>            Assignee: Jie Yu
>             Fix For: 0.18.0
>
>
> Inside Replica::persist(const Action& action), we update the in-memory 
> 'holes' data structure
>   // Update holes if we just wrote many positions past the last end.
>   for (uint64_t position = end + 1; position < action.position(); position++) 
> {
>     holes.insert(position);
>   }
> During catch-up (starts with an empty log), if the 'position' is very large, 
> we may spend a lot of time in this loop. Also, the data structure 'holes' 
> might become extremely large.



--
This message was sent by Atlassian JIRA
(v6.1.5#6160)