Rewrite gossip to use UDP instead of TCP

[anton-k]

We need to rewrite gossip to use UDP, test with xenochain that transition is reliable and estimate
performance gains.

[thesz]

I think I'll take on this.

I've found the places where to look at and copy from. The code looks like connection-oriented, mostly: NetworkAPI is connection oriented (connect, listenOn, etc). But P2PConnection is not - it provides for just send, receive and close actions that are relatively easy to implement with UDP. I will closely look at the use of NetworkAPI to decide how to deal with it.

The main concern here is that message may exceed UDP datagram limit (about 64K for IPv4 which is itself split into Ethernet frames) and we have to assembly things back. I would like to approach that with adding two fields to an UDP payload: a "front index" field and an offset within the front. The "front index" is equal for all UDP packets of a bigger message and allows to identify what we have to assembly. It will increase monotonically (modulo, say, 256). The offset within the front is where this concrete UDP payload (minus front index and offset field) must be put.

If message has to be split into several UDP payloads, all payloads before last one must have size bigger than some limit (say, 65000 - or close to Ethernet frame size if we don't trust underlying protocol suite). The last one must have size less or equal to the limit.

The offset of UDP payload to be added to a message must be equal to the sum of UDP payloads with offsets smaller than current - a sanity check. This way we can randomize sizes of parts to some extent and (probabilistically) prevent parts from older fronts to be part of the current message we receive.

[thesz]

While I am at it, please look at https://github.com/jepsen-io/jepsen - this thing allows to test distributed systems by injecting faults. It also reports on the issues found and allows to test performance in the presence of faults at different rates.

[Shimuuar]

I caught a cold and cannot think straight. I'll reply when I feel better

[voidlizard]

We should not literally rewrite GOSSIP for using UDP instead of TCP. We should keep a possibility to use TCP or UDP depending on application / situation.

[Shimuuar]

Actually TCP is baked into current network implementation very deeply and switching to UDP will take a lot of work.

Small datagrams

One problems is practical limit on UDP datagram is rather small 512B or so. Otherwise it could be fragmented, dropped, or fragmented and then dropped. This is rather tight limit

So here is list of messages that we need to exchange

• Signed vote: ~200B
• Block - possibly large.
• Signed proposal, unknown. It depends on how we gossip blocks. But possibly largish
• Transaction - smallish but not guaranteed to fit into 512B
• Announcements, internal gossip messages, small

So we have two problems with large messages: 1) blocks/proposals 2) transactions. There're gossiped in different way and probably should be dealed in different way as well.

Blocks/proposals

General idea about block is that want transmit them in chunks where we could get different parts from different peers. It's not implemented at the moment although it's been planned for long time (#21). Also node should only accept blocks which it know either because it have correct proposal or b

We can have malicious nodes as well. The can transmit invalids parts of block. So it's highly desirable to be able to check whether part block is valid without assembling whole block. One approach is to build merkle tree from block and send it as proposal. It however brings another problem: we probably don't want to store full merkle tree since it's rather large. And this will create problems for node catchup. We don't store proposals, so node will only get commit which contains only top level hash. It's unclear how to transmit full merkle tree to lagging node.

Transactions

They are smaller and we don't assemble them from different peers. So simpler setup will suffice

Other considerations

Small datagram size is not only consideration. We need to do other things:

1. Track whether peer is still alive. (heartbeat?)

2. Implement some measure for controlling message flood. Peers can send messages faster than we can process them. At the momemnt we have queue for incoming messages when it's full network thread blocks as well. With TCP other side blocks too. With UDP we will probably lose packets.

[Shimuuar]

Also one of reasons for rewrite to UDP is efficiency. There're much lower hanging fruits for improving gossip efficiency.

1. Thundermint.Crypto.Containers.ValidatorISet is set of numbers from 0 to N. At the moment it's an IntSet. Since N is relatively small it could be replaced with something more efficient.

2. Selection of votes to gossip in Thundermint.P2P is written in really inefficient way

[thesz]

The packet size for UDP is, at the very least, as big as TCP packet size. Most often it is about 1500 bytes or so. There is a way to transmit bigger UDP packets, up to 65536 bytes for IPv4 and up to 4G bytes for IPv6. They will be split into smaller packets and reassembled if possible at the network protocol level. In that case it is kernel's work to wait for all parts, assemble them, etc.

My current plan is to have UDP implementation of what TCP implementation does right now. Basically, you will have (almost) same functionality with different transport. Except there will be lost messages and other corruptions. ;)

Given that, we can experiment with, say, typed messages - e.g., extend P2PConnection with the ability to extract, possible out-of-order, messages of different types. This is, basically, functionality of Cloud Haskell from which we can borrow parts.

[Shimuuar]

I no expert on network matter but quick search suggest that UDP fragmentation doesn't work reliably.

Also I'm afraid that trying to implement current abstract API in UDP will result in suboptimal reimplementation TCP in UDP. Anyway it's probably better to discuss on tomorrow call

[thesz]

There is a thing that is Lustre cluster file system. It works for hundreds of machines. The author once told me that they had a bug lurking in their code for several years - they haven't tested UDP resend, because, as it appear, they haven't lost a single UDP packet in more than seven years of active use of Lustre in various environments.

Lustre implements Paxos for highly loaded environments, so it is quite close to what we are doing here.

No, it will not result of reimplementation of TCP in UDP. The logic to work with UDP will be different. What if you lost some of messages? With UDP you have to think about it.

I also think that we can discuss by voice but discussion conclusion must be written here.

[Shimuuar]

Thing is nodes (if all is going well) won't be sitting in single data center with well configured network. They will be scattered all over the globe and will communicate over whatever is between them. Especially light nodes if we ever get them

I also think that we can discuss by voice but discussion conclusion must be written here.

Sure!

[thesz]

There is a thing that is Lustre cluster file system. It works for hundreds of machines. The author once told me that they had a bug lurking in their code for several years - they haven't tested UDP resend, because, as it appear, they haven't lost a single UDP packet in more than seven years of active use of Lustre in various environments.

Lustre implements Paxos for highly loaded environments, so it is quite close to what we are doing here.

No, it will not result of reimplementation of TCP in UDP. The logic to work with UDP will be different. What if you lost some of messages? With UDP you have to think about it.

I also think that we can discuss by voice but discussion conclusion must be written here.

[thesz]

There is a thing that is Lustre cluster file system. It works for hundreds of machines. The author once told me that they had a bug lurking in their code for several years - they haven't tested UDP resend, because, as it appear, they haven't lost a single UDP packet in more than seven years of active use of Lustre in various environments.

Lustre implements Paxos for highly loaded environments, so it is quite close to what we are doing here.

No, it will not result of reimplementation of TCP in UDP. The logic to work with UDP will be different. What if you lost some of messages? With UDP you have to think about it.

PS
The size of Ethernet frame is 1522 octets: https://en.wikipedia.org/wiki/Ethernet_frame

IP header takes 20 bytes, UDP header takes 16 bytes, the remaining data size is 1486.

[thesz]

It looks like AF_NET6-bound socket unable to receive AF_NET4 produced datagrams, even when it is allowed to do so (by setting appropriate socket option).

The branch is here: https://github.com/hexresearch/thundermint/tree/225-adding-UDP-transport

Also take a look here: https://docs.google.com/document/d/1QXXoQCxVOE6wSKPzbDeZu1aL0PIJGdrEz3OtjkX0lrw/edit?usp=sharing (Russian) A proposal on how to use BitTorrent-like functionality for message exchange.