优化paxos group内的成员节点遍历

优化paxos group内的成员节点遍历

paxos的proposer的prepare和accept阶段调用Communicate::BroadcastMessage向paxos group内的其他成员节点发送paxos消息，Communicate::BroadcastMessage处于热路径上。Communicate::BroadcastMessage需要从SystemVSM::GetMembershipMap获取paxos group内的成员节点，然后遍历成员节点。在微基准测试中，发现有更好的数据结构可以加速成员节点遍历，有必要优化paxos group内的成员节点遍历。

原代码路径：
src/communicate/communicate.cpp
```cpp
int Communicate :: BroadcastMessage(const int iGroupIdx, const std::string & sMessage, const int iSendType)
{
    // 在微基准测试中，发现有更好的数据结构可以加速成员节点遍历
    const std::set<nodeid_t> & setNodeInfo = m_poConfig->GetSystemVSM()->GetMembershipMap();
        
    for (auto & it : setNodeInfo)
    {   
        if (it != m_iMyNodeID)
        {   
            Send(iGroupIdx, it, NodeInfo(it), sMessage, iSendType);                                                                                                                    
        }   
    }   

    return 0;
}
```

目前SystemVSM通过std::set存储paxos group内的成员节点的nodeid。std::set的底层是红黑树，红黑树的节点不一定具有内存连续性，节点内存不连续时对遍历不友好。而且红黑树需要额外的指针维护树的结构，这意味比数组/vector需要更多的内存，有可能需要读取更多的cache line才能遍历完红黑树。

c++23已经发布了std::flat_set。这是一个默认以vector为底层的容器，每个元素的值唯一，元素在vector里连续存放，对遍历友好。而且std::flat_set的clear，insert，size，find接口(SystemVSM::m_setNodeID也使用了这些接口)的语义跟std::set一致，可以把std::flat_set列为备选的数据结构。

std::flat_set文档：
https://en.cppreference.com/cpp/container/flat_set

比较可惜的是，时至今日很多主流的编译器还没有支持std::flat_set。我使用的g++ 13和g++ 14都没有实现std::flat_set。幸好boost::container::flat_set能替代std::flat_set。

boost::container::flat_set文档：
https://www.boost.org/doc/libs/1_73_0/doc/html/boost/container/flat_set.html

为了对比更多可能的备选数据结构，微基准测试将会引入std::unordered_set。微基准测试将会对std::set，std::unordered_set和boost::container::flat_set的遍历操作和find接口操作进行测试。因为这两个操作在phxpaxos中被高频使用，且性能会因数据结构不同而不用。

微基准测试不会对clear，insert操作进行测试。因为paxos group内成员变更时才会使用这两个操作，然而paxos group内成员变更是非常低频的操作。

对遍历进行微基准测试：测试程序是test_set_iter.cpp，测试的paxos group内成员变节点的个数分别是3/4/5/6/7/8/9/10/11/12/13/14/15。

test_set_iter.cpp在各编译优化选项对应的编译产物的测试耗时对比：
无编译优化选项耗时：boost::container::flat_set < std::unordered_set < std::set 
-O1耗时：std::unordered_set < boost::container::flat_set < std::set
-O2耗时：boost::container::flat_set < std::unordered_set < std::set  (phxpaxos使用了-O2编译优化选项，按测试结果应该选择boost::container::flat_set，boost::container::flat_set的耗时是std::unordered_set的0.08-0.28)
-O3耗时：std::unordered_set < boost::container::flat_set < std::set

test_set_iter.cpp的代码：
```cpp
#include <stdint.h>
#include <time.h>

#include <set>
#include <unordered_set>
#include <unordered_map>

#include <benchmark/benchmark.h>

#include <boost/container/flat_set.hpp>

static std::unordered_map<int, std::unordered_set<uint64_t>> g_size2set;

static void Init(int n) {
    if (n <= 0) return;

    if (g_size2set.count(n) == 0) {
        srand(static_cast<unsigned int>(time(NULL)));
        std::unordered_set<uint64_t> s;
        while (s.size() < n) {
            s.insert((static_cast<uint64_t>(rand()) << 32) | static_cast<uint64_t>(rand()));
        } 
        g_size2set[n] = std::move(s);
    }
}

static void BM_SetInter(benchmark::State& state) {
    int n = state.range(0);
    Init(n);

    std::set<uint64_t> s(g_size2set[n].begin(), g_size2set[n].end());
    volatile uint64_t v = 0;
    for (auto _: state) {
        for (auto it = s.begin(); it != s.end(); ++it) {
            v = *it;
        }
        benchmark::ClobberMemory();
    }
}

BENCHMARK(BM_SetInter)->ArgsProduct({{3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}});

static void BM_UnorderedSetInter(benchmark::State& state) {
    int n = state.range(0);
    Init(n);

    std::unordered_set<uint64_t> s(g_size2set[n].begin(), g_size2set[n].end());
    volatile uint64_t v = 0;
    for (auto _: state) {
        for (auto it = s.begin(); it != s.end(); ++it) {
            v = *it;
        }
        benchmark::ClobberMemory();
    }
}

BENCHMARK(BM_UnorderedSetInter)->ArgsProduct({{3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}});

static void BM_BoostFlatSetInter(benchmark::State& state) {
    int n = state.range(0);
    Init(n);

    boost::container::flat_set<uint64_t> s(g_size2set[n].begin(), g_size2set[n].end());
    volatile uint64_t v = 0;
    for (auto _: state) {
        for (auto it = s.begin(); it != s.end(); ++it) {
            v = *it;
        }
        benchmark::ClobberMemory();
    }
}

BENCHMARK(BM_BoostFlatSetInter)->ArgsProduct({{3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}});

BENCHMARK_MAIN();
```

test_set_iter.cpp的编译命令：
```shell
# 加上对应的编译优化选项
g++ -std=c++11 test_set_iter.cpp -lbenchmark
```


对find进行微基准测试：测试程序是test_set_find.cpp，测试的paxos group内成员变节点的个数分别是3/4/5/6/7/8/9/10/11/12/13/14/15。

test_set_find.cpp在各编译优化选项对应的编译产物的测试耗时对比：
无编译优化选项耗时：boost::container::flat_set < std::unordered_set < std::set
-O1耗时：std::set < boost::container::flat_set < std::unordered_set
-O2耗时：std::set < boost::container::flat_set < std::unordered_set  (phxpaxos使用了-O2编译优化选项，按测试结果应该选择std::set)
-O3耗时：std::set < boost::container::flat_set < std::unordered_set

test_set_find.cpp的代码：
```cpp
#include <stdint.h>
#include <time.h>

#include <set>
#include <unordered_set>
#include <unordered_map>

#include <benchmark/benchmark.h>

#include <boost/container/flat_set.hpp>

static std::unordered_map<int, std::unordered_set<uint64_t>> g_size2set;

static void Init(int n) {
    if (n <= 0) return;

    if (g_size2set.count(n) == 0) {
        srand(static_cast<unsigned int>(time(NULL)));
        std::unordered_set<uint64_t> s;
        while (s.size() < n) {
            s.insert((static_cast<uint64_t>(rand()) << 32) | static_cast<uint64_t>(rand()));
        } 
        g_size2set[n] = std::move(s);
    }
}

static void BM_SetFind(benchmark::State& state) {
    int n = state.range(0);
    Init(n);

    const auto& set = g_size2set[n];
    std::set<uint64_t> s(set.begin(), set.end());
    volatile bool b = false;
    for (auto _: state) {
        for (auto it = set.begin(); it != set.end(); ++it) {
            b = (s.find(*it) != s.end());
        }
        benchmark::ClobberMemory();
    }
}

BENCHMARK(BM_SetFind)->ArgsProduct({{3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}});

static void BM_UnorderedSetFind(benchmark::State& state) {
    int n = state.range(0);
    Init(n);

    const auto& set = g_size2set[n];
    std::unordered_set<uint64_t> s(set.begin(), set.end());
    volatile bool b = false;
    for (auto _: state) {
        for (auto it = set.begin(); it != set.end(); ++it) {
            b = (s.find(*it) != s.end());
        }
        benchmark::ClobberMemory();
    }
}

BENCHMARK(BM_UnorderedSetFind)->ArgsProduct({{3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}});

static void BM_BoostFlatSetFind(benchmark::State& state) {
    int n = state.range(0);
    Init(n);

    const auto& set = g_size2set[n];
    boost::container::flat_set<uint64_t> s(set.begin(), set.end());
    volatile bool b = false;
    for (auto _: state) {
        for (auto it = set.begin(); it != set.end(); ++it) {
            b = (s.find(*it) != s.end());
        }
        benchmark::ClobberMemory();
    }
}

BENCHMARK(BM_BoostFlatSetFind)->ArgsProduct({{3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}});

BENCHMARK_MAIN();
```

test_set_find.cpp的编译命令：
```shell
# 加上对应的编译优化选项
g++ -std=c++11 test_set_find.cpp -lbenchmark
```

基于以上的测试结果，SystemVSM需要增加一个boost::container::flat_set数据成员用于存储paxos group内成员节点的nodeid，也需要增加一个接口用于返回新增的boost::container::flat_set数据成员，还需要增加boost::container::flat_set相应的逻辑代码。

修改后的代码路径：
src/config/system_v_sm.h
```cpp
class SystemVSM : public InsideSM
{
// ...
public:
    //this function only for communicate.
    const std::set<nodeid_t> & GetMembershipMap();

    // 新增代码
    const boost::container::flat_set<nodeid_t> & GetMembershipMapForInter();

private:
    int m_iMyGroupIdx;
    SystemVariables m_oSystemVariables;
    SystemVariablesStore m_oSystemVStore;

    std::set<nodeid_t> m_setNodeID;

    // 新增代码
    boost::container::flat_set<nodeid_t> m_setNodeID2;

    nodeid_t m_iMyNodeID;

    MembershipChangeCallback m_pMembershipChangeCallback;
};
```

src/config/system_v_sm.cpp
```cpp
void SystemVSM :: AddNodeIDList(const NodeInfoList & vecNodeInfoList)
{       
    if (m_oSystemVariables.gid() != 0)
    {
        PLG1Err("No need to add, i already have membership info.");
        return;
    }
    
    m_setNodeID.clear();
    m_setNodeID2.clear(); // 新增代码                                                                                                                                                               
    m_oSystemVariables.clear_membership();

    for (auto & tNodeInfo : vecNodeInfoList)
    {       
        PaxosNodeInfo * poNodeInfo = m_oSystemVariables.add_membership();
        //to do, what rid?
        poNodeInfo->set_rid(0);
        poNodeInfo->set_nodeid(tNodeInfo.GetNodeID());

        NodeInfo tTmpNode(poNodeInfo->nodeid());
    }

    RefleshNodeID();
}

void SystemVSM :: RefleshNodeID()
{
    m_setNodeID.clear();
    m_setNodeID2.clear(); // 新增代码

    NodeInfoList vecNodeInfoList;
    
    for (int i = 0; i < m_oSystemVariables.membership_size(); i++)
    {
        PaxosNodeInfo oNodeInfo = m_oSystemVariables.membership(i);
        NodeInfo tTmpNode(oNodeInfo.nodeid());

        PLG1Head("ip %s port %d nodeid %lu", 
                tTmpNode.GetIP().c_str(), tTmpNode.GetPort(), tTmpNode.GetNodeID());

        m_setNodeID.insert(tTmpNode.GetNodeID());
        m_setNodeID2.insert(tTmpNode.GetNodeID()); // 新增代码

        vecNodeInfoList.push_back(tTmpNode);
    }

    if (m_pMembershipChangeCallback != nullptr)
    {
        m_pMembershipChangeCallback(m_iMyGroupIdx, vecNodeInfoList);
    }
}

// 新增代码
const boost::container::flat_set<nodeid_t> & SystemVSM :: GetMembershipMapForInter()
{
    return m_setNodeID2;                                                                                                                                                                
}
```

src/communicate/communicate.cpp
```cpp
int Communicate :: BroadcastMessage(const int iGroupIdx, const std::string & sMessage, const int iSendType)
{
    // 修改代码
    // const std::set<nodeid_t> & setNodeInfo = m_poConfig->GetSystemVSM()->GetMembershipMap();
    const boost::container::flat_set<nodeid_t> & setNodeInfo  = m_poConfig->GetSystemVSM()->GetMembershipMapForInter();
    
    for (auto & it : setNodeInfo)
    {
        if (it != m_iMyNodeID)
        {
            Send(iGroupIdx, it, NodeInfo(it), sMessage, iSendType);
        }
    }

    return 0;
} 
```

Navigation Menu

Uh oh!

优化paxos group内的成员节点遍历 #287

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Uh oh!

优化paxos group内的成员节点遍历 #287

Description

Activity

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions