Implement queue based sampling

[trivigy]

A part of the gossip sampling algorithm has not been implemented. Read section "2.4.2 sampling" in https://www.distributed-systems.net/my-data/papers/2007.tocs.pdf regarding a queue that ensures fair sampling.

[trivigy]

This is where --joins added as an argument parser. https://github.com/syncaide/backend/blob/master/src/server/options.cpp#L29

Entry point to the implementation of the gossip protocol. https://github.com/syncaide/backend/blob/master/src/server/server.cpp#L17

I had to write my own View and Peer classes. All the messages are sent using grpc so you will need to understand that.

[trivigy]

To connect syncaided to each other you have to pass at least one other address of another running syncaided. example:

./syncaided
./syncaided -b 127.0.0.1:8848 -j 127.0.0.1:8847

The first call starts syncaided with the default parameters including bind:127.0.0.1:8847 and no joins. Send starts on a different bind and points 1 join to the default node. Once the gossip starts they will exchange knowledge of the network topology by sending over views. You can start this way as large of a network as you want locally.

[BGZHU1]

Two questions : 1) where do you get current view? 2) where do you get view update notice?

[trivigy]

@bijiezhu The current view can either be empty or constructed from the --join parameters passed to syncaided. The view is updated through the gossip algorithm itself.

https://github.com/syncaide/backend/blob/v0.0.5/src/server/peering.cpp#L53-L66 - pushing the current view to a randomly selected peer. Notice that each view submission always adds one peer. Itself.

https://github.com/syncaide/backend/blob/v0.0.5/src/server/options.cpp#L166-L175 - parsing joins. All config data ends up being stored inside of server::Options class. The values inside are mutable so need to be careful to not create race conditions. (problem for another day)

All information is being sent via grpc. The services are defined here: https://github.com/syncaide/backend/tree/v0.0.5/src/rpc/services Imported here: https://github.com/syncaide/backend/blob/v0.0.5/src/server/peering.h#L5-L6 And registered to the grpc server here: https://github.com/syncaide/backend/blob/v0.0.5/src/server/peering.cpp#L27-L28

Let me know if you have more questions.

[BGZHU1]

if I want to start a third node, can I do ./syncaided -b 127.0.0.1:8849 -j 127.0.0.1:8847? which I bind with a different port but join the same address with the first node?

[BGZHU1]

notifier(bind(&server::Options::on_joins, this, _1)), what exactly do you mean "points 1 join to the default node" ? I assume under this context you mean the newly created node? And does it has anything to do with _1?

[trivigy]

@bijiezhu Here is an example how you can link 3 nodes. By the way, remember that the gossip protocol is responsible for exchanging peer views. That means that technically when we boot strap the network we can just do a star shaped start. Where every new node knows exactly the same address. After joining the nodes will exchange addresses.

As for the notifier(), it is just a function that binds a callback function. It makes it so that at some point when the application starts; if --join was passed, the information coming from args will pass inside of the binded function. Additionally I am using the bind function. This function is a special kind, it takes the function you pass as 1st argument, and binds to it's function parameters whatever you pass afterwards. In this case, bind just creates a new member function pointer to which it attaches this as its own this and a placeholder. The placeholder is like saying: some argument will be provided later. It allows to do bind() without having the actual variable ready yet.

Here are the docs for the different concepts: notifier: https://www.boost.org/doc/libs/1_67_0/doc/html/boost/program_options/typed_value.html#id-1_3_31_9_10_1_1_7_5_6-bb std::bind: http://en.cppreference.com/w/cpp/utility/functional/bind std::placeholder::_1 : http://en.cppreference.com/w/cpp/utility/functional/placeholders

[BGZHU1]

so The implementation should be inside

shared_ptr<server::Peering> server::Server::peering() {
   return _peering;
}

instead of just return a the private variable _peering. It needs to return a the one in the queue.

[trivigy]

no, the server::Server::peering() is really for external use. Inside of the server::Server class there are three main sections right now. Peering, Upstream, and Frontend. In order for those to communicate with each other, they all hold a pointer to the parent class server::Server. Since each of the instances of the sections are private, there is a function for each that returns a shared_ptr to that particular section.

So if Frontend code needs Peering, it can do something like:

auto peering = this->server->peering();

What you are implementing is related only to peering internals. When this function is called, it always returns a random peer. https://github.com/syncaide/backend/blob/master/src/server/peering.cpp#L56. The problem is that on every round the view is going to get reshuffled and so even though it is "random" the same peer may be selected multiple times. The paper, look at the reference at the top of this thread, talks about a queue to preserve fairness.

[BGZHU1]

So, I need to implement the queue based sampling inside/related to the view.cpp ? From my understanding, we creates view in peering.cpp. And we have peering.cpp interact with RPC to get the miners/peers message, and then the message is updated through _view->update(cfg.peers.c, cfg.peers.H, cfg.peers.S, pull.value()); in the peering class? Not sure I understand correctly, needs clarification.

[trivigy]

It would probably be it's own class that is instantiated inside of the view. I bet you will end up needing some sort of locking mechanism inside of the queue. Otherwise would there ever be a race condition? Are there any kind of other processes or threads that are touching it at the same time? I am just throwing ideas in the air. Let me know what you think in terms of the design and let me know when you think you will be able to implement it.

[BGZHU1]

How can I find any kind of other processes or threads that are touching the view at the same time? The only thing I googled out is top -H.

[trivigy]

https://github.com/syncaide/backend/blob/master/src/server/server.cpp#L17-L19 This chunk of code starts three threads. You will have to read through the code / do grep to find out if there are use cases. Don't remember. But it would be valuable to assume there might be in the future.

[BGZHU1]

So in the protos folder you have defined .proto. And in the rpc folder you have callers as client & service as server. And you passed in server.cpp class instance into the miners.cpp & peers.cpp inside the services folder. And inside your server folder, you also have miner.cpp[read messages through proto/ accept connections] & peering.cpp[implement gossip protocol/register with miners/peers]. My question is with in both peers.cpp & peering.cpp, they create channels. Does this part overlapping? And how exactly miners.cpp & peers.cpp & miner.cpp & peering.cpp communicate with each other? @trivigy

[BGZHU1]

what exactly does upstream.cpp and frontend.cpp do?

[trivigy]

Upstream is the program thread that deals with the cryptocurrency nodes (monero in this case). Peering is the program thread that deals with the other syncaide nodes. frontend is the program thread that deals with websockets and serving the files via http. view is the class representing the partial network topology. peer is just a class for representing an individual peer.

[BGZHU1]

From my understanding, does the exchange/update of view only related to view.cpp and peering.cpp class? (of course it is related to rpc(caller/services) and .proto for message passing)

[trivigy]

For now yes.

[BGZHU1]

And in the miner.cpp, I see you implemented methods for miner like read/write/login. Does that also related to view exchange and view update? Also, I think in server::Miner::on_read(error_code code, size_t bytes_transferred) it reads the message, where does it get the message? from the monero?