Posted on | In

本篇自我总结

有了本系列上篇文章中的分包和重组系统为何还要这个发送大块数据系统?是否是多余的?是雷同的吗?
请看总结概要理清思路, 再细看文章.

为什么需要做这个发送大块数据系统

第一眼看上去，这种替代性的技术似乎非常类似于数据包的分包和重组，但是它的实现是完全不同的。这种实现上的差异的目的是为了解决数据包分包和重组的一个关键弱点 : 一个片段的丢失就会导致整个数据包都要被丢弃掉然后重新分包重发。

你可能需要这样做的一些常见的例子包括：客户端在首次加入的时候，服务器需要下发一个大的数据块给客户端(可能是世界的初始状态)、一开始用来做增量编码的基线或者是在一个多人在线网络游戏里面客户端在加载界面所等待的大块数据。

在这些情况下非常重要的是不仅要优雅地处理数据包的丢失，还要尽可能的利用可用的带宽并尽可能快的发送大块数据。

这个发送大块数据系统大致可以理解为是一个在原来分包和重组系统的基础上增加了分包确认功能, 也就是说增加了可靠性的部分.

本篇基本术语

In this new system blocks of data are called chunks. Chunks are split up into slices. This name change keeps the chunk system terminology (chunks/slices) distinct from packet fragmentation and reassembly (packets/fragments).

  • 块 : 在这个新系统中，大块的数据被称为”块”(chunks)
  • 片段 : 而块被分成的分包被称为”片段”(slices)

数据包的结构设计

这个系统在网络上发送的数据包类型一共有两种类型：

  • Slice packet片段数据包 : 这包括了一个块的片段，最多大小为1k。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    const int SliceSize = 1024;
    const int MaxSlicesPerChunk = 256;
    const int MaxChunkSize = SliceSize  MaxSlicesPerChunk;
     
    struct SlicePacket : public protocol2::Packet
    {
        uint16_t chunkId;
        int sliceId;
        int numSlices;
        int sliceBytes;
        uint8_t data[SliceSize];
      
        template <typename stream> bool Serialize( Stream & stream )
        {
            serialize_bits( stream, chunkId, 16 );
            serialize_int( stream, sliceId, 0, MaxSlicesPerChunk - 1 );
            serialize_int( stream, numSlices, 1, MaxSlicesPerChunk );
            if ( sliceId == numSlices - 1 )
            {
                serialize_int( stream, sliceBytes, 1, SliceSize );
            }
            else if ( Stream::IsReading )
            {
                sliceBytes = SliceSize;
            }
            serialize_bytes( stream, data, sliceBytes );
            return true;
        }
    };

  • Ack packet确认数据包 : 一个位域bitfield指示哪些片段已经收到, we just send the entire state of all acked slices in each ack packet. When the ack packet is received (including the slice that was just received).

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    struct AckPacket : public protocol2::Packet 
    { 
        uint16_t chunkId; 
        int numSlices; 
        bool acked[MaxSlicesPerChunk]; 
     
        bool Serialize( Stream & stream )
        { 
            serialize_bits( stream, chunkId, 16 ); 
            serialize_int( stream, numSlices, 1, MaxSlicesPerChunk ); 
            for ( int i = 0; i < numSlices; ++i ) 
                serialize_bool( stream, acked[i] ); return true; } };
        }
    };

发送方的实现

与之前文章介绍的数据包的分包和重组系统不同，块系统在同一时间只能由一个块正在传输。
发送方的策略是：

  • 持续的发送片段数据包，直到所有的片段数据包都被确认。
  • 不再对已经确认过的片段数据包进行发送。

对于发送方而言有一点比较微妙，实现一个片段数据包重新发送的最小延迟是一个很棒的主意，如果不这么做的话，就可能会出现这种一样情况，对于很小的块数据或者一个块的最后几个片段数据包，很容易不停的发送它们把整个网络都塞满。正是因为这一原因，我们使用了一个数组来记录每个片段数据包的上一次发送时间。重新发送延迟的一个选择是使用一个估计的网络往返时延，或者只有在超过上一次发送时间网络往返时延*1.25还没有收到确认数据包的情况才会重新发送。或者，你可以说“这根本就无所谓”，只要超过上一次发送时间100毫秒了就重新发送。我只是列举适合我自己的方案！

我们使用以下的数据结构来描述发送方：

1
2
3
4
5
6
7
8
9
10
11
12
class ChunkSender
{
    bool sending;
    uint16_t chunkId;
    int chunkSize;
    int numSlices;
    int numAckedSlices;
    int currentSliceId;
    bool acked[MaxSlicesPerChunk];
    uint8_t chunkData[MaxChunkSize];
    double timeLastSent[MaxSlicesPerChunk];
};

接收方的实现思路

首先，接收方的设置会从块0开始。当一个片段数据包从网络上传递过来，并且能够匹配这个块id的话，“receiving”状态会从false翻转为true，第一个片段数据包的数据会插入” chunkData“变量的合适位置，片段数据包的数量会根据第一个片段数据包里面的数据进行正确的设置，已经接收到的片段数据包的数量会加一，也就是从0到1，针对每个片段数据包的接收标记里面对应这个片段数据包的项会变为true。

随着这个块数据的其他片段数据包的到来，会对每一个片段数据包进行检测，判断它们的id是否与当前块的id相同，如果不相同的话就会被丢弃。如果这个片段数据包已经收到过的话，那么这个包也会被丢弃。否则，这个片段数据包的数据会插入” chunkData“变量的合适位置、已经接收到的片段数据包的数量会加一、针对每个片段数据包的接收标记里面对应这个片段数据包的项会变为true。

这一过程会持续进行，直到接收到所有的片段数据包。一旦接收到所有的片段数据包（也就是已经接收到的片段数据包的数量等于片段数据包的数量的时候），接收方会把“receiving “状态改为false，而把”readyToRead“状态改为true。当”readyToRead”状态为true的时候，所有收到的片段数据包都会被丢弃。在这一点上，这个处理过程通常非常的短，会在收到片段数据包的同一帧进行处理，调用者会检查”我有一块数据要读取么？“并处理块数据。然后会重置数据块接收器的所有数据为默认值，除了块数据的id从0增加到1，这样我们就准备好接收下一个块了。

1
2
3
4
5
6
7
8
9
10
11
class ChunkReceiver
{
    bool receiving;
    bool readyToRead;
    uint16_t chunkId;
    int chunkSize;
    int numSlices;
    int numReceivedSlices;
    bool received[MaxSlicesPerChunk];
    uint8_t chunkData[MaxChunkSize];
};

防DDos

如果你对每个收到的片段数据包都会回复一个确认数据包的话，那么发送方能够构造一个很小的片段数据包发送给你，而你会回复一个比发送给你的片段数据包还大的确认数据包，这样你的服务器就变成了一个可以被人利用来进行DDos放大攻击的工具。

永远不要设计一个包含对接收到的数据包进行一对一的映射响应的协议。让我们举个简单例子来说明一下这个问题。如果有人给你发送1000个片段数据包，永远不要给他回复1000个确认数据包。相反只发一个确认数据包，而且最多每50毫秒或者100毫秒才发送一个确认数据包。如果你是这样设计的话，那么DDos攻击完全不可能的。

原文

原文出处

原文标题 : Sending Large Blocks of Data (How to send blocks quickly and reliably over UDP)

Introduction

Hi, I’m Glenn Fiedler and welcome to Building a Game Network Protocol.


In the previous article we implemented packet fragmentation and reassembly so we can send packets larger than MTU.


This approach works great when the data block you’re sending is time critical and can be dropped, but in other cases you need to send large blocks of quickly and reliably over packet loss, and you need the data to get through.


In this situation, a different technique gives much better results.


Background


It’s common for servers to send large block of data to the client on connect, for example, the initial state of the game world for late join.


Let’s assume this data is 256k in size and the client needs to receive it before they can join the game. The client is stuck behind a load screen waiting for the data, so obviously we want it to be transmitted as quickly as possible.


If we send the data with the technique from the previous article, we get packet loss amplification because a single dropped fragment results in the whole packet being lost. The effect of this is actually quite severe. Our example block split into 256 fragments and sent over 1% packet loss now has a whopping 92.4% chance of being dropped!


Since we just need the data to get across, we have no choice but to keep sending it until it gets through. On average, we have to send the block 10 times before it’s received. You may laugh but this actually happened on a AAA game I worked on!


To fix this, I implemented a new system for sending large blocks, one that handles packet loss by resends fragments until they are acked. Then I took the problematic large blocks and piped them through this system, fixing a bunch of players stalling out on connect, while continuing to send time critical data (snapshots) via packet fragmentation and reassembly.


Chunks and Slices


In this new system blocks of data are called chunks. Chunks are split up into slices. This name change keeps the chunk system terminology (chunks/slices) distinct from packet fragmentation and reassembly (packets/fragments).


The basic idea is that slices are sent over the network repeatedly until they all get through. Since we are implementing this over UDP, simple in concept becomes a little more complicated in implementation because have to build in our own basic reliability system so the sender knows which slices have been received.


This reliability gets quite tricky if we have a bunch of different chunks in flight, so we’re going to make a simplifying assumption up front: we’re only going to send one chunk over the network at a time. This doesn’t mean the sender can’t have a local send queue for chunks, just that in terms of network traffic there’s only ever one chunk in flight at any time.


This makes intuitive sense because the whole point of the chunk system is to send chunks reliably and in-order. If you are for some reason sending chunk 0 and chunk 1 at the same time, what’s the point? You can’t process chunk 1 until chunk 0 comes through, because otherwise it wouldn’t be reliable-ordered.


That said, if you dig a bit deeper you’ll see that sending one chunk at a time does introduce a small trade-off, and that is that it adds a delay of RTT between chunk n being received and the send starting for chunk n+1 from the receiver’s point of view.


This trade-off is totally acceptable for the occasional sending of large chunks like data sent once on client connect, but it’s definitely not acceptable for data sent 10 or 20 times per-second like snapshots. So remember, this system is useful for large, infrequently sent blocks of data, not for time critical data.


Packet Structure


There are two sides to the chunk system, the sender and the receiver.


The sender is the side that queues up the chunk and sends slices over the network. The receiver is what reads those slice packets and reassembles the chunk on the other side. The receiver is also responsible for communicating back to the sender which slices have been received via acks.


The netcode I work on is usually client/server, and in this case I usually want to be able to send blocks of data from the server to the client and from the client to the server. In that case, there are two senders and two receivers, a sender on the client corresponding to a receiver on the server and vice-versa.


Think of the sender and receiver as end points for this chunk transmission protocol that define the direction of flow. If you want to send chunks in a different direction, or even extend the chunk sender to support peer-to-peer, just add sender and receiver end points for each direction you need to send chunks.


Traffic over the network for this system is sent via two packet types:



  • Slice packet - contains a slice of a chunk up to 1k in size.

  • Ack packet - a bitfield indicating which slices have been received so far.


The slice packet is sent from the sender to the receiver. It is the payload packet that gets the chunk data across the network and is designed so each packet fits neatly under a conservative MTU of 1200 bytes. Each slice is a maximum of 1k and there is a maximum of 256 slices per-chunk, therefore the largest data you can send over the network with this system is 256k.


const int SliceSize = 1024;
const int MaxSlicesPerChunk = 256;
const int MaxChunkSize = SliceSize  MaxSlicesPerChunk;

struct SlicePacket : public protocol2::Packet
{
    uint16_t chunkId;
    int sliceId;
    int numSlices;
    int sliceBytes;
    uint8_t data[SliceSize];

    template &lt;typename Stream&gt; bool Serialize( Stream &amp; stream )
    {
        serialize_bits( stream, chunkId, 16 );
        serialize_int( stream, sliceId, 0, MaxSlicesPerChunk - 1 );
        serialize_int( stream, numSlices, 1, MaxSlicesPerChunk );
        if ( sliceId == numSlices - 1 )
        {
            serialize_int( stream, sliceBytes, 1, SliceSize );
        }
        else if ( Stream::IsReading )
        {
            sliceBytes = SliceSize;
        }
        serialize_bytes( stream, data, sliceBytes );
        return true;
    }
};

There are two points I’d like to make about the slice packet. The first is that even though there is only ever one chunk in flight over the network, it’s still necessary to include the chunk id (0,1,2,3, etc…) because packets sent over UDP can be received out of order.


Second point. Due to the way chunks are sliced up we know that all slices except the last one must be SliceSize (1024 bytes). We take advantage of this to save a small bit of bandwidth sending the slice size only in the last slice, but there is a trade-off: the receiver doesn’t know the exact size of a chunk until it receives the last slice.


The other packet sent by this system is the ack packet. This packet is sent in the opposite direction, from the receiver back to the sender. This is the reliability part of the chunk network protocol. Its purpose is to lets the sender know which slices have been received.


struct AckPacket : public protocol2::Packet
{
    uint16_t chunkId;
    int numSlices;
    bool acked[MaxSlicesPerChunk];

    bool Serialize( Stream &amp; stream )
    {
        serialize_bits( stream, chunkId, 16 );
        serialize_int( stream, numSlices, 1, MaxSlicesPerChunk );
        for ( int i = 0; i &lt; numSlices; ++i )
        {
            serialize_bool( stream, acked[i] ); return true; } };
        }
    }
};

Acks are short for ‘acknowledgments’. So an ack for slice 100 means the receiver is acknowledging that it has received slice 100. This is critical information for the sender because not only does it let the sender determine when all slices have been received so it knows when to stop, it also allows the sender to use bandwidth more efficiently by only sending slices that haven’t been acked.


Looking a bit deeper into the ack packet, at first glance it seems a bit redundant. Why are we sending acks for all slices in every packet? Well, ack packets are sent over UDP so there is no guarantee that all ack packets are going to get through. You certainly don’t want a desync between the sender and the receiver regarding which slices are acked.


So we need some reliability for acks, but we don’t want to implement an ack system for acks because that would be a huge pain in the ass. Since the worst case ack bitfield is just 256 bits or 32 bytes, we just send the entire state of all acked slices in each ack packet. When the ack packet is received, we consider a slice to be acked the instant an ack packet comes in with that slice marked as acked and locally that slice is not seen as acked yet.


This last step, biasing in the direction of non-acked to ack, like a fuse getting blown, means we can handle out of order delivery of ack packets.


Sender Implementation


Let’s get started with the implementation of the sender.


The strategy for the sender is:



  • Keep sending slices until all slices are acked

  • Don’t resend slices that have already been acked


We use the following data structure for the sender:


class ChunkSender
{
    bool sending;
    uint16_t chunkId;
    int chunkSize;
    int numSlices;
    int numAckedSlices;
    int currentSliceId;
    bool acked[MaxSlicesPerChunk];
    uint8_t chunkData[MaxChunkSize];
    double timeLastSent[MaxSlicesPerChunk];
};

As mentioned before, only one chunk is sent at a time, so there is a ‘sending’ state which is true if we are currently sending a chunk, false if we are in an idle state ready for the user to send a chunk. In this implementation, you can’t send another chunk while the current chunk is still being sent over the network. If you don’t like this, stick a queue in front of the sender.


Next, we have the id of the chunk we are currently sending, or, if we are not sending a chunk, the id of the next chunk to be sent, followed by the size of the chunk and the number of slices it has been split into. We also track, per-slice, whether that slice has been acked, which lets us count the number of slices that have been acked so far while ignoring redundant acks. A chunk is considered fully received from the sender’s point of view when numAckedSlices == numSlices.


We also keep track of the current slice id for the algorithm that determines which slices to send, which works like this. At the start of a chunk send, start at slice id 0 and work from left to right and wrap back around to 0 again when you go past the last slice. Eventually, you stop iterating across because you’ve run out of bandwidth to send slices. At this point, remember our current slice index via current slice id so you can pick up from where you left off next time. This last part is important because it distributes sends across all slices, not just the first few.


Now let’s discuss bandwidth limiting. Obviously you don’t just blast slices out continuously as you’d flood the connection in no time, so how do we limit the sender bandwidth? My implementation works something like this: as you walk across slices and consider each slice you want to send, estimate roughly how many bytes the slice packet will take eg: roughly slice bytes + some overhead for your protocol and UDP/IP header. Then compare the amount of bytes required vs. the available bytes you have to send in your bandwidth budget. If you don’t have enough bytes accumulated, stop. Otherwise, subtract the bytes required to send the slice and repeat the process for the next slice.


Where does the available bytes in the send budget come from? Each frame before you update the chunk sender, take your target bandwidth (eg. 256kbps), convert it to bytes per-second, and add it multiplied by delta time (dt) to an accumulator.


A conservative send rate of 256kbps means you can send 32000 bytes per-second, so add 32000 dt to the accumulator. A middle ground of 512kbit/sec is 64000 bytes per-second. A more aggressive 1mbit is 125000 bytes per-second. This way each update you accumulate a number of bytes you are allowed to send, and when you’ve sent all the slices you can given that budget, any bytes left over stick around for the next time you try to send a slice.


One subtle point with the chunk sender and is that it’s a good idea to implement some minimum resend delay per-slice, otherwise you get situations where for small chunks, or the last few slices of a chunk that the same few slices get spammed over the network.


For this reason we maintain an array of last send time per-slice. One option for this resend delay is to maintain an estimate of RTT and to only resend a slice if it hasn’t been acked within RTT * 1.25 of its last send time. Or, you could just resend the slice it if it hasn’t been sent in the last 100ms. Works for me!


Kicking it up a notch


Do the math you’ll notice it still takes a long time for a 256k chunk to get across:



  • 1mbps = 2 seconds

  • 512kbps = 4 seconds

  • 256kbps = 8 seconds :(


Which kinda sucks. The whole point here is quickly and reliably. Emphasis on quickly. Wouldn’t it be nice to be able to get the chunk across faster? The typical use case of the chunk system supports this. For example, a large block of data sent down to the client immediately on connect or a block of data that has to get through before the client exits a load screen and starts to play. You want this to be over as quickly as possible and in both cases the user really doesn’t have anything better to do with their bandwidth, so why not use as much of it as possible?


One thing I’ve tried in the past with excellent results is an initial burst. Assuming your chunk size isn’t so large, and your chunk sends are infrequent, I can see no reason why you can’t just fire across the entire chunk, all slices of it, in separate packets in one glorious burst of bandwidth, wait 100ms, and then resume the regular bandwidth limited slice sending strategy.


Why does this work? In the case where the user has a good internet connection (some multiple of 10mbps or greater…), the slices get through very quickly indeed. In the situation where the connection is not so great, the burst gets buffered up and most slices will be delivered as quickly as possible limited only by the amount bandwidth available. After this point switching to the regular strategy at a lower rate picks up any slices that didn’t get through the first time.


This seems a bit risky so let me explain. In the case where the user can’t quite support this bandwidth what you’re relying on here is that routers on the Internet strongly prefer to buffer packets rather than discard them at almost any cost. It’s a TCP thing. Normally, I hate this because it induces latency in packet delivery and messes up your game packets which you want delivered as quickly as possible, but in this case it’s good behavior because the player really has nothing else to do but wait for your chunk to get through.


Just don’t go too overboard with the spam or the congestion will persist after your chunk send completes and it will affect your game for the first few seconds. Also, make sure you increase the size of your OS socket buffers on both ends so they are larger than your maximum chunk size (I recommend at least double), otherwise you’ll be dropping slices packets before they even hit the wire.


Finally, I want to be a responsible network citizen here so although I recommend sending all slices once in an initial burst, it’s important for me to mention that I think this really is only appropriate, and only really borderline appropriate behavior for small chunks in the few 100s of k range in 2016, and only when your game isn’t sending anything else that is time-critical.


Please don’t use this burst strategy if your chunk is really large, eg: megabytes of data, because that’s way too big to be relying on the kindness of strangers, AKA. the buffers in the routers between you and your packet’s destination. For this it’s necessary to implement something much smarter. Something adaptive that tries to send data as quickly as it can, but backs off when it detects too much latency and/or packet loss as a result of flooding the connection. Such a system is outside of the scope of this article.


Receiver Implementation


Now that we have the sender all sorted out let’s move on to the reciever.


As mentioned previously, unlike the packet fragmentation and reassembly system from the previous article, the chunk system only ever has one chunk in flight.


This makes the reciever side of the chunk system much simpler:


class ChunkReceiver
{
    bool receiving;
    bool readyToRead;
    uint16_t chunkId;
    int chunkSize;
    int numSlices;
    int numReceivedSlices;
    bool received[MaxSlicesPerChunk];
    uint8_t chunkData[MaxChunkSize];
};

We have a state whether we are currently ‘receiving’ a chunk over the network, plus a ’readyToRead’ state which indicates that a chunk has received all slices and is ready to be popped off by the user. This is effectively a minimal receive queue of length 1. If you don’t like this, of course you are free to add a queue.


In this data structure we also keep track of chunk size (although it is not known with complete accuracy until the last slice arrives), num slices and num received slices, as well as a received flag per-slice. This per-slice received flag lets us discard packets containing slices we have already received, and count the number of slices received so far (since we may receive the slice multiple times, we only increase this count the first time we receive a particular slice). It’s also used when generating ack packets. The chunk receive is completed from the receiver’s point of view when numReceivedSlices == numSlices.


So what does it look like end-to-end receiving a chunk?


First, the receiver sets up set to start at chunk 0. When the a slice packet comes in over the network matching the chunk id 0, ‘receiving’ flips from false to true, data for that first slice is inserted into ‘chunkData’ at the correct position, numSlices is set to the value in that packet, numReceivedSlices is incremented from 0 -> 1, and the received flag in the array entry corresponding to that slice is set to true.


As the remaining slice packets for the chunk come in, each of them are checked that they match the current chunk id and numSlices that are being received and are ignored if they don’t match. Packets are also ignored if they contain a slice that has already been received. Otherwise, the slice data is copied into the correct place in the chunkData array, numReceivedSlices is incremented and received flag for that slice is set to true.


This process continues until all slices of the chunk are received, at which point the receiver sets receiving to ‘false’ and ‘readyToRead’ to true. While ‘readyToRead’ is true, incoming slice packets are discarded. At this point, the chunk receive packet processing is performed, typically on the same frame. The caller checks ‘do I have a chunk to read?’ and processes the chunk data. All chunk receive data is cleared back to defaults, except chunk id which is incremented from 0 -> 1, and we are ready to receive the next chunk.


Conclusion


The chunk system is simple in concept, but the implementation is certainly not. I encourage you to take a close look at the source code for this article for further details.

译文

译文出处

翻译：张华栋 (wcby) 审校：王磊(未来的未来)


大家好，我是格伦·菲德勒。欢迎大家阅读系列教程《构建游戏网络协议》的第四篇文章。在之前的文章中，我们讨论了如何在游戏协议这一层实现对数据包的分包和重组。

现在在这篇文章里面，我们将继续通过探索在UDP协议上发送大块数据的替代方案来继续我们构建一个专业级别的游戏网络协议的征程。


第一眼看上去，这种替代性的技术似乎非常类似于数据包的分包和重组，但是它的实现是完全不同的。这种实现上的差异的目的是为了解决数据包分包和重组的一个关键弱点-一个片段的丢失就会导致整个数据包都要被丢弃掉。这种行为是非常不好的，因为它会随着分包数量的增加而放大数据包丢失的概率。当你遇到大块数据包的时候，这种放大是如此的明显，加入256 k大小的分包丢失率是1%的话，那么原始数据包就有92.4%的概率被丢弃。平均来说，你需要发送原始数据包10次，它才能顺利的到达网络的另外一端！

如果你需要在一个可能会有数据包丢失的网络上比如说互联网，快速和可靠地发送大量的数据，很明显，这样的方法是完全不可接受的。你可能需要这样做的一些常见的例子包括：客户端在首次加入的时候，服务器需要下发一个大的数据块给客户端(可能是世界的初始状态)、一开始用来做增量编码的基线或者是在一个多人在线网络游戏里面客户端在加载界面所等待的大块数据。

在这些情况下非常重要的是不仅要优雅地处理数据包的丢失，还要尽可能的利用可用的带宽并尽可能快的发送大块数据。这正是我要在这篇文章里面告诉你该如何做的内容。


块和片段

让我们开始使用基本术语。在这个新系统中，大块的数据被称为”块“，而它们被分成的分包被称为”片段”。 这个名字上的改变使的块系统的术语(块和片段)不同于数据包分包和重组的术语(数据包和分包)。这是我认为很重要的一个事情，因为这些系统是在解决不同的问题，没有理由你不能在相同的网络协议中同时这两个系统。事实上，我经常把这两个结合起来，在时间比较关键的增量数据包里面使用数据包的分包和重组，当客户端加入游戏的时候，使用块系统来下发整个游戏世界的初始状态下(非常大的数据包)。


块系统的基本思想，真是一点都不复杂，是把块分成很多片段，然后通过网络多次发送片段，直到他们都顺利的到达网络的另外一端。当然，因为我们正在UDP协议上实现这个功能，同时还有可能数据包会丢失、数据包乱序到达以及数据包重复到达的情况，简单的概念在实现中也会变得非常复杂，因为我们必须在UDP协议上建立我们自己的具有基本可靠性的系统，这样发送方才能知道这个片段已经被网络的另外一端成功收到。


如果我们有一组不同的块正在传输过程中(就像我们在数据包的分包和重组中所做的那样)，那么可靠性的问题就会变得非常棘手，所以我们要做一个简化的假设。我们一次只会通过网络发送一个块的数据。这并不意味着发送者不能在本地有一个块的发送队列，这只是意味着在实际的网络传输中只有一个块的数据会正在传递。


这么做之所以有意义，是因为有了这一点假设以后就能保证块系统能够可靠有序的发送块。如果你因为某些原因在同一时间发送块0和块1，这会发生什么？你不能在块0到来之前处理块1，否则这个传输过程就不是有序可靠了。也就是说，如果你挖得深一些的话，你会发现一次只能发送一个块确实引入了一个小的权衡，它给正在接收的块Ｎ增加了一个网络往返延迟，以及从接收方的角度看块Ｎ＋１的发送开始时间也被延迟了一个网络往返延迟。


这个代价是完全可以接受的，因为发送大块数据是一个非常偶然的事情（举些简单的例子来说，当客户端连接上来的时候会发送大块数据，当新的关卡需要进行加载的时候才会发送大块数据。。。），但是如果1秒钟内10次或者20次发送块数据的话这就是绝对不能被接受的了。所以我希望你能看到这个系统是专为什么目的设计的以及不是为什么目的设计的。


数据包的结构

在块系统中有两方会参与，分别是发送方和接收方。

发送方是负责将块压入队列并通过网络发送片段。接收方是负责在网络的另外一端读取这些片段并进行重组。接收方还负责通过发送“确认”数据包给发送方来与发送方交流表明这个片段已经收到。


我工作过的网络模式通常是客户端与服务端之间的通信，在这种情况下，我通常希望能够从服务器往客户端发送大块数据，以及从客户端到服务器发送大块数据。所以在这种情况下，有两个发送方和两个接收方，一个发送方在客户端对应着在服务器那边有一个接收方，反过来也是如此。可以把发送方和接收方认为是块传输协议的终点，这样也就定义了网络流的方向。如果你想在不同的方向发送块，甚至是扩展块的发送方来支持点对点的发送，只需要在你需要发送块的每个方向添加一个发送方和一个接收方作为终点。

这个系统在网络上发送的数据包类型一共有两种类型：

1）片段数据包-这包括了一个块的片段，最多大小为1k。

2）确认数据包-一个位域指示哪些片段已经收到。


片段数据包是从发送方发送到接收器的。这是通过网络对块数据进行传递的有效载荷数据包，在设计的时候每个片段数据包的大小都贴近一个保守的最大传输单元的大小，也就是 1200字节。每个片段数据包最大是1 k，每个块最多有256个片段数据包，所以通过这个系统可以通过网络发送的最大的数据是256k（如果你愿意的话，你可以增加这个片段的最大数目）。我建议保持片段的大小为1k，这主要是基于最大传输单元方面的考虑。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const int SliceSize = 1024;
const int MaxSlicesPerChunk = 256;
const int MaxChunkSize = SliceSize MaxSlicesPerChunk;
struct SlicePacket : public protocol2::Packet
{
uint16_t chunkId;
int sliceId;
int numSlices;
int sliceBytes;
uint8_t data[SliceSize];
template <typename stream> bool Serialize( Stream & stream )
{
serialize_bits( stream, chunkId, 16 );
serialize_int( stream, sliceId, 0, MaxSlicesPerChunk - 1 );
serialize_int( stream, numSlices, 1, MaxSlicesPerChunk );
if ( sliceId == numSlices - 1 )
{
serialize_int( stream, sliceBytes, 1, SliceSize );
}
else if ( Stream::IsReading )
{
sliceBytes = SliceSize;
}
serialize_bytes( stream, data, sliceBytes );
return true;
}
};

在这里我想对片段数据包进行两点说明。第一点是即使只有一个块在网络上进行传输，仍然是有必要在数据包里面包含一个块的id(比如说，0、1、2、3、等等等)，这是,因为通过UDP协议发送的数据包可以是乱序到达的。通过这种方式的话，如果一个片段数据包到达的时候对应着一个已经接受过的块，举个简单的例子来说明，你正在接受块2的数据，但是块1的一个片段数据包现在到达了，你可以直接拒绝这个数据包，而不是接受它的数据包并把它的数据插入到块2从而把块2的数据给弄混了。

第二点。由于我们知道块分成片段的方法会把所有的片段除了最后一个以外都弄成必须SliceSize的大小(也就是1024字节)。我们利用这一点来节省一点带宽，我们只在最后一个片段里面发送片段的大小，但这是一种权衡:接收方不知道块的确切大小到底是多少字节，直到它接收到最后一个片段才能知道。

可以让这个系统继续往后发送新的数据包的机制是确认数据包。这个数据包是沿着另外一个方向进行发送的，也就是从接收方发回给发送方，这也是块网络协议中负责可靠性的部分。它存在的目的是让发送方知道这个片段已经被发送方收到。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct AckPacket : public protocol2::Packet
{
uint16_t chunkId;
int numSlices;
bool acked[MaxSlicesPerChunk];
bool Serialize( Stream & stream )
{
serialize_bits( stream, chunkId, 16 );
serialize_int( stream, numSlices, 1, MaxSlicesPerChunk );
for ( int i = 0; i < numSlices; ++i )
serialize_bool( stream, acked[i] ); return true; } };
}
};


ack是“确认”的缩写。所以一个对片段100的确认数据包意味着接收方确认它已经接收到了片段100。这对于发送方来说是一条关键信息，因为它不仅让发送方知道什么时候所有的片段都已经被成功接收，这样发送方就可以停止发送了，它还允许发送方只重发那些还没有被确认的片段，这样就能让发送方更有效率的利用带宽。


让我们对确认数据包再深入一点思考，似乎在一开始看上去对于每个数据包的所有分片都发送确认包似乎有点多余。我们为什么要这么做?是的，这是因为确认数据包是通过UDP协议发送的，所以没有办法保证所有的确认数据包都会成功的到达网络的另外一端，你当然不会希望发送方和接收方之间对于目前确认到那个片段的信息都是不同步的。


所以我们需要一些确认数据包传输的可靠性，但是我们不希望实现一个确认数据包的确认系统，因为这将会是一个非常痛苦和麻烦的过程。因为在最坏的情况下，确认数据包的大小是256位或32字节，最简单的方法是也是最好的。we just send the entire state of all acked slices in each ack packet. When the ack packet is received, we consider a slice to be acked the instant an ack packet comes in with that slice marked as acked and locally that slice is not seen as acked yet.



基本的发送方实现

现在我们已经了解了这个系统背后的基本概念，让我们从发送方的实现开始实现整个系统。

发送方的策略是：

1）持续的发送片段数据包，直到所有的片段数据包都被确认。

2）不再对已经确认过的片段数据包进行发送。

我们使用以下的数据结构来描述发送方：

?
1
2
3
4
5
6
7
8
9
10
11
12
class ChunkSender
{
bool sending;
uint16_t chunkId;
int chunkSize;
int numSlices;
int numAckedSlices;
int currentSliceId;
bool acked[MaxSlicesPerChunk];
uint8_t chunkData[MaxChunkSize];
double timeLastSent[MaxSlicesPerChunk];
};


正如之前提到的那样，一次只会发送一个块的数据，如果我们正在发送一个块的数据的时候，那么关于“发送”的状态是true，假如我们处于闲置状态、正在准备发送一个块的数据的时候，那么关于“发送”的状态是false。在这个实现中，如果当前有一个块的数据仍在通过网络进行发送的话，你不能发送另外一个块的数据。你必须等待当前块的数据发送完毕之后才可以发送另外一个块的数据。如果你不喜欢的话，在块的发送器的前端按照你的意愿可以放置一个发送队列。


接下来，我们有我们正在发送的块数据的id，或者如果我们没有在发送块数据的话，那么我们有要发送的下一个块数据的id、以及这个块所分成的片段数据包的数量。我们也会跟踪每个片段数据包，来记录这个片段数据包是否已经被确认，这可以让我们避免重发那些已经收到的片段数据包，并且我们还会记录迄今为止已经确认收到的片段数据包的数量，这个数量会去掉冗余的确认，也就是每个片段数据包的确认只算一次。从发送方的观点来看，只有当确认的片段数据包的数量等于这个块所分成的片段数据包的数量的时候才会这个块数据已经被完全收到了。


我们还需要为这个算法记录当前发送的片段数据包的id，因为这将决定了哪些片段数据包将被发送。它的工作机制大致是这样：一个块数据开始发送的时候，是从id为0的片段数据包开始发送的，然后依次从左到右开始发送直到经过最后一个片段数据包(也就是id为分包数量的大小-1)的时候会回头从id为0的片段数据包继续发送。最终，你会停止这个迭代因为发送的片段数据包已经耗尽了带宽。在这一点上，我们通过记录当前发送的片段数据包的id就能记住我们当前遍历的片段数据包的索引，这样在下一次开始遍历的时候你就可以继续从这个位置开始发送片段数据包。最后一部分是非常重要的，这是因为它可以把发送一个块数据所有的片段数据包这个事情是分散开，而不是在一起就全部发出去。


现在让我们讨论下带宽限制。显然你不能把所有的片段数据包一次全部发完，因为如果这么做的话，会把整个链接堵住，那么，我们该如何限制发送方所使用的带宽?我的实现机制大概是这样的：当你对全部的片段数据包进行遍历并且考虑你想要发送的每个片段数据包的时候，大概估计下这个片段数据包会需要占据多少字节，比如可以用这种估计算法：大概这个片段的字节数+一些协议的开销和UDP / IP的报头。然后用所需的字节数和你带宽预算里面可用来进行发送的字节数进行比较。如果带宽预算里面没有足够可用的字节数，那么就停止发送。否则的话，从带宽预算里面减去发送这个片段数据包所需的字节数，然后对于下个片段数据包重复整个过程。


带宽预算里面可用的字节发送预算是从哪里计算得来的？在每一帧更新块的发送方之前，把你的目标带宽（比如说每秒256KB）转换成每秒可以发送的字节数，然后用它乘以更新时间来把记过放到一个累加器里面。每秒256KB是一个比较保守的发送速率，这意味你可以每秒发送32000个字节，所以把32000 dt这个值添加到累加器里面。每秒512KB是一个比较适中的估计，意味你可以每秒发送64000个字节。每秒1MB是一个比较激进的估计，意味你可以每秒发送125000个字节。通过这种方法，在每次更新的时候你就可以累加你被允许发送的字节数了，这样当你可以按照预算来发送最大数量的片段数据包，如果还有数据没有发完的话，会等到下一帧的时候再尝试发送。


对于发送方而言有一点比较微妙，实现一个片段数据包重新发送的最小延迟是一个很棒的主意，如果不这么做的话，就可能会出现这种一样情况，对于很小的块数据或者一个块的最后几个片段数据包，很容易不停的发送它们把整个网络都塞满。正是因为这一原因，我们使用了一个数组来记录每个片段数据包的上一次发送时间。重新发送延迟的一个选择是使用一个估计的网络往返时延，或者只有在超过上一次发送时间网络往返时延*1.25还没有收到确认数据包的情况才会重新发送。或者，你可以说“这根本就无所谓”，只要超过上一次发送时间100毫秒了就重新发送。我只是列举适合我自己的方案！


把发送方实现的更完美一点

如果你仔细用数学计算一下的话，你会注意到对于一个256K 的数据块而言，它要在网络上发送完毕仍然需要发送很长的时间：

  • 如果网络速率是每秒1M的话，就需要2秒钟的时间。
  • 如果网络速率是每秒512KB的话，就需要4秒钟的时间。
  • 如果网络速率是每秒256KB的话，就需要8秒钟的时间。

这可有点糟糕。我们实现系统的重点是快速和可靠性。再次强调下需要能够快速传递。如果块系统的传输不能做到快速的话，这是不是会不太好？块系统的一些典型用例会支持这一点。举个简单的例子来说明，当客户端第一次连接上服务器的时候，一大块数据需要立刻发送给客户端，或者在客户端退出加载界面开始游戏的时候需要能够大量数据快速下发给客户端。你想要尽快的传递完需要的数据，而且在这两种情况下，用户对于自己的带宽并没有什么太多其他的用途，那么为什么不使用尽可能多的带宽?


在过去我曾经尝试过一个方法，就是在一开始的时候尽量传递，这取得了很好的效果。假设你的块大小并不是那么大，而且你的块发送频率并不那么频繁，我没找到什么理由为什么你不能在一开始就把所有的片段数据包都发送出去，填充满贷款，然后等待100毫秒，在恢复成正常的带宽受限的片段数据包发送策略。


为什么这样会取得良好的效果？如果用户有一个良好的网络连接（可以每秒发送超过10MB的数据甚至更多。。。），事实上，片段数据包在网络上的传输非常的快速。如果是连接的情况并不是那么好的情况下，大部分的片段数据包会得到缓冲，大部分的片段数据包受限于带宽但是会尽可能快的发送出去。处理完这些数据包之后，就会切换到常规的策略，从那些第一次没有发送出去的片段数据包选择合适的进行发送。


这似乎有点冒险，所以让我来解释一下。如果出现大量数据需要传输但是已经超过带宽限制的情况，互联网上的路由器会倾向于缓冲这些数据包，而不是不惜代价的抛弃它们。这就是TCP协议会做的事情。通常情况下，我讨厌这个机制因为它会诱发延迟而且会弄乱那些你想要尽快交付的游戏数据包，但在这种情况下它是一个非常好的行为，这是因为玩家真的没有其他事情可以做，智能等待你的块数据赶紧传输完毕。只是在你的块数据传输完毕以后，会有一些垃圾数据或者交通拥堵，它会影响你的游戏开始的几秒钟。另外，请确保你增加了网络两端的加操作系统的套接字缓冲区的大小，这样它们才可以比你最大的块数据的大小要大(我建议至少增加一倍)，否则在超过网络带宽的限制之前你就会出现丢弃段数据包的情况。


最后，我想成为一个负责任的网络公民，虽然在这里我推荐在最开始连接的时候一次发送所有的片段数据包，所以对我来说介绍下我认为这真的是适当的是非常非常重要的，在2016年的网络环境下，发送几百个KB量级的数据包是没什么大不了的行为，而且只会发生在没有其他关键数据同时发送的情况下。让我们举个简单的例子来说明，如果用户正在玩你的游戏，那么当你发送大块数据的时候，使用保守的策略。如果不这么做的话，就会冒影响用户游戏体验的风险，这是因为你的发送行为可能会诱导额外的网络延迟或者出现数据包丢失的情况。


同样，如果你的块数据非常大的情况下，比如说是十几MB的情况，那么请不要使用这种野蛮发送的策略，这是因为这种方法太过于依赖陌生人的仁慈，也就是在你和你的数据包目的地之间的路由器缓冲区。如果要持续发送非常大的数据块保持一个高吞吐量有必要实施一些更聪明的方法。这是某种自适应的方法，它会试图尽快发送数据，但是一旦检测到因为连接上有太多的数据在传输导致太多的延迟或者数据包的丢失，就能切换回一个低速的方式。这样一个系统超出了本文的范围。


接收方的实现

现在我们已经解决了发送方实现的所有细节和小问题，那么让我们开始实现接收方。正如之前提到的那样，与之前文章介绍的数据包的分包和重组系统不同，块系统在同一时间只能由一个块正在传输。

这使得块系统的接收方可以实现的更加简单，你可以看下面的实现:

?
1
2
3
4
5
6
7
8
9
10
11
class ChunkReceiver
{
bool receiving;
bool readyToRead;
uint16_t chunkId;
int chunkSize;
int numSlices;
int numReceivedSlices;
bool received[MaxSlicesPerChunk];
uint8_t chunkData[MaxChunkSize];
};


我们有一个状态来记录我们是否正在网络上“接收”一个块数据，加上“readyToRead’”状态来表明是否已经有一个块的所有片段数据包都已经收到、已经准备好被用户弹出进行读取处理了。接收队列的最小长度是1，这是非常有效的。如果你不喜欢这个的话，你当然可以立即从块数据接收器里面将这个数据弹出并把它插入实际的接收队列。


在这个数据结构中我们还记录了块数据的大小（尽管不是完全准确，直到收到最后一个片段数据包才能准确的计算块数据的大小）、片段数据包的数量、已经接收到的片段数据包的数量还有针对每个片段数据包的一个接收标记。针对每个片段数据包的接收标记可以让我们丢弃那些我们已经收到的片段数据包，并计算到目前为止我们已经收到的片段数据包的数量（因为我们可能会多次收到同一个片段数据包，但是我们只会在第一次收到这个片段数据包的才会增加计数器的值）。它也被用在生成确认数据包上。当已经接收到的片段数据包的数量等于片段数据包的数量的时候，从接收方的角度看这个块数据的接收才算完成。


首先，接收方的设置会从块0开始。当一个片段数据包从网络上传递过来，并且能够匹配这个块id的话，“receiving”状态会从false翻转为true，第一个片段数据包的数据会插入” chunkData“变量的合适位置，片段数据包的数量会根据第一个片段数据包里面的数据进行正确的设置，已经接收到的片段数据包的数量会加一，也就是从0到1，针对每个片段数据包的接收标记里面对应这个片段数据包的项会变为true。


随着这个块数据的其他片段数据包的到来，会对每一个片段数据包进行检测，判断它们的id是否与当前块的id相同，如果不相同的话就会被丢弃。如果这个片段数据包已经收到过的话，那么这个包也会被丢弃。否则，这个片段数据包的数据会插入” chunkData“变量的合适位置、已经接收到的片段数据包的数量会加一、针对每个片段数据包的接收标记里面对应这个片段数据包的项会变为true。


这一过程会持续进行，直到接收到所有的片段数据包。一旦接收到所有的片段数据包（也就是已经接收到的片段数据包的数量等于片段数据包的数量的时候），接收方会把“receiving “状态改为false，而把”readyToRead“状态改为true。当”readyToRead”状态为true的时候，所有收到的片段数据包都会被丢弃。在这一点上，这个处理过程通常非常的短，会在收到片段数据包的同一帧进行处理，调用者会检查”我有一块数据要读取么？“并处理块数据。然后会重置数据块接收器的所有数据为默认值，除了块数据的id从0增加到1，这样我们就准备好接收下一个块了。


浸泡测试的重要性和确认数据包

第一眼看上去，确认数据包这个系统似乎很简单：

1）记录已经接收到的片段数据包。

2）当一个片段数据包收到以后，回复一个包含所有确认收到的片段数据包信息的确认数据包。

这看上去实现起来似乎相当的简单，但是像大多数发生在UDP协议的事情一样，当涉及到数据包丢失的时候，就有一些微妙的点让它的处理有点棘手。

一个对于确认数据包比较天真的实现可能是这样子的。每次收到片段数据包，就回复一个包含所有确认收到的片段数据包信息的确认数据包（也会包括刚收到的片段数据包的信息）。这看上去非常符合逻辑，但是这使得块协议给恶意发送者一个漏洞使得它们可以块协议作为一个DDos的工具。如何作为一个DDos的工具?如果你对每个收到的片段数据包都会回复一个确认数据包的话，那么发送方能够构造一个很小的片段数据包发送给你，而你会回复一个比发送给你的片段数据包还大的确认数据包，这样你的服务器就变成了一个可以被人利用来进行DDos放大攻击的工具。


现在也许是因为我对DDos这个事情有一点偏执（我确实是有一点），但是一般来说你可以防止对DDos的放大，永远不要设计一个包含对接收到的数据包进行一对一的映射响应的协议。让我们举个简单例子来说明一下这个问题。如果有人给你发送1000个片段数据包，永远不要给他回复1000个确认数据包。相反只发一个确认数据包，而且最多每50毫秒或者100毫秒才发送一个确认数据包。如果你是这样设计的话，那么滥用你的UDP协议对DDos进行放大就是完全不可能的。


还有其他的方法让这个确认系统容易出错，而这些都往往表现为”发送挂起“。换句话说，接收方已经知道这个块已经发送完毕了，但是由于程序员的错误，发送方错过了一个确认数据包(可能是针对最后一个片段数据包的确认数据包)并且卡入到一个状态，会不停的反复重发这个片段数据包而没有得到一个确认数据包的响应。


在过去10年里，我可能至少5次从头开始实现这个块系统，每次我都找到新的和令人兴奋的方式来让发送方挂起。我开发和测试块系统的策略是首先进行编码确认它能够跑起来，然后设置一个测试工具在有大量的数据包丢失、数据包乱序和重复的情况下随机发送随机大小的块。这往往会清除任何挂起。我曾经实现过的块系统都至少有一个挂起存在，通常会有2到3个挂起。所以如果你是打算从头开始实现这个块系统的话，请不要轻敌。请设置一个浸泡测试。你会感谢我在这里的提醒的。


我通常遇到的第一次挂起是由于对同一个片段数据包的多次收到不会回复一个确认数据包。它有点像这样：” 哦，这个片段数据包已经收到过了么？已经收到过了就丢弃它”，然后忘记在确认数据包里面设置标记。这对于发送方来说是一个困扰，因为这样的话就不会有一个确认数据包，那么如果出现这种情况的话，又恰好遇到第一次收到这个片段数据包的时候发送的确认数据包出现丢包的情况，发送方根本就不知道这个他在反复发送的片段数据包其实已经被收到了。如果你就是这么不巧，遇上了第一次收到这个片段数据包的时候发送的确认数据包出现丢包的情况，那么就遇上了挂起的情况。如果你想在你的代码里面重现这个情况的话，可以在收到最后一个片段数据包的时候不发送确认数据包，那么出现的情况就是这种挂起了。


下一个挂起会发生在接收方在发送方知道之前就已经知道块发送完毕并切换它的状态变量“readyToRead”来丢弃后续传入的片段数据包。在这种状态下，即使接收方认为块已经完全接收完毕，但是发送方还不知道这一点，所以有必要设置确认数据包对应的标志位，即使块已经完全接收完毕，这样发送方才能一直接收到提示块已经全部发送完毕的确认数据包。


通常遇到的最后一个挂起情况是在读取完块数据以后的状态切换里面，那个时候状态变量“readyToRead”已经切回false而块的id也加一了。让我们举个简单例子来说明一下这个问题，块0已经完成接收，用户已经完成对块0的读取并且块id已经递增到1了，所以我们已经准备好接收块1的片段数据包了（我们会丢弃任何与我们当前正在接收块ID不同的片段数据包）。


再一次出现这种情况，就是这里的发送方因为确认数据包的丢失导致信息有一点滞后，可能是因为没有收到第一个确认数据包。在这种情况下，有必要关注片段数据包，如果我们正处于这么一个状态：我们尚未收到第n个片段数据包，但是前面n – 1个片段数据包都已经收到了，我们必须设置一个特殊的标记位然后我们会发送一个包含所有前面n – 1个片段数据包都已经收到信息的确认数据包，否则发送方不会意识到块数据已经收到并且发送方已经准备挂起了。


正如你所看到的那样，确认数据包的实现是有一点微妙的，这是一个有点奇怪的过程因为当片段数据包在网络的一端收到的时候，需要设置一个标记位来发送确认数据包直到发送方知道都有哪些发送的片段数据包被成功接收为止。如果你打破了片段数据包->确认数据包这个链接的话，那么整个系统就将挂起。我鼓励你仔细看看这篇文章的源代码搞清楚进一步的细节。



总结

块系统在概念上是很简单的，但是它的具体实现肯定不是微不足道的。在我看来，实现发送者设计这一块是一个很好的学习经验，当你从头开始实现这样的系统的时候一定有很多东西需要学习。

我希望你喜欢这个系统的设计，并试着自己动手从头开始实现它。这是一个很好的学习经历。此外，我鼓励你在patreon上支持我，作为回报，你会得到本文的示例源代码(以及本系列的其他文章的示例源代码)，还包括我在GDC 2015上关于网络物理的演讲的源代码。

如果你觉得这篇文章有价值的话，请在patreon上支持我的写作，这样我会写的更快。你可以在BSD 3.0许可下访问到这篇文章里面的代码。非常感谢你的支持！



【版权声明】

原文作者未做权利声明，视为共享知识产权进入公共领域，自动获得授权。


Posted on | In

本篇自我总结

本篇主要讲了数据包的分包和重组问题, 到底数据包多大才好呢?是不是越大越好呢?包太大了怎么办呢?
请看总结, 不明之处再看文中具体讲解.

为什么需要做这个分包和重组系统

每台计算机(路由器)会沿着路由强制要求数据包的大小会有一个最大的上限，这个上限就是所谓的最大传输单元MTU。如果任意一个路由器收到一个数据包的大小超过这个最大传输单元的大小，它有这么两个选择，a)在IP层对这个数据包进行分包，并将分包后的数据包继续传递，b)丢弃这个数据包然后告诉你数据包被丢弃了，你自己负责摆平这个问题。

实例 : 这儿有一个我会经常遇到的情况。人们在编写多人在线游戏的时候，数据包的平均大小都会非常的小，让我们假设下，这些数据包的平均大小大概只有几百字节，但时不时会在他们的游戏中同时发生大量的事情并且发出去的数据包会出现丢失的情况，这个时候数据包会比通常的情况下要大。突然之间，游戏的数据包的大小就会超过最大传输单元的大小，这样就只有很少一部分玩家能够收到这个数据包，然后整个通信就崩溃了。

本篇基本术语

  • 数据包packets
  • 分包fragments

分包的数据结构

我们将允许一个数据包最多可以分成256个数据包，并且每个分包后的数据包的大小不会超过1024个字节。这样的话，我们就可以通过这样一个系统来发送大小最大为256k的数据包

[protocol id] (32 bits)   // not actually sent, but used to calc crc32
[crc32] (32 bits)  
[sequence] (16 bits)  // 数据包序号
[packet type = 0] (2 bits)
[fragment id] (8 bits) // 分包ID
[num fragments] (8 bits)
[pad zero bits to nearest byte index] // 用于字节对齐的bits
<fragment data>

发送分包后的数据包

发送分包以后的数据包是一件非常容易的事情。如果数据包的大小小于保守估计的最大传输单元的大小。那么就按正常的方法进行发送。否则的话，就计算这个数据包到底该分成多少个1024字节的数据包分包，然后构建这些分包并按照之前发送正常数据包的方法进行发送。

发送出去以后也不记录发送的数据包的内容，这种发送以后不记录发送的数据包的内容的方法有一个后果，就是数据包的任意一个分包如果丢失的话，那么整个数据包就都要丢弃。随着分包数量的增加，整个数据包被丢弃的概率也随之增加.由此可见，当你需要发送要给256K的数据包的时候要发送256个分包，如果有一个分包丢失的话，你就要重新把这个256k的数据包再分一次包然后再发送出去。

什么时候用这个分包和重组系统呢

因为发送出去以后也不记录发送的数据包, 随着分包数量的增加，整个数据包被丢弃的概率也随之增加, 而一个片段的丢失就会导致整个数据包都要被丢弃掉.所以我建议你要小心分包以后的数量。

这个分包和重组系统最好是只对2-4个分包的情况进行使用，而且最好是针对那种对时间不怎么敏感的数据使用或者是就算分包lost了也无所谓的情况。绝对不要只是为了省事就把一大堆依赖顺序的事件打到一个大数据包里面然后依赖数据包的分包和重组机制进行发送。这会让事情变得更加麻烦。

数据包分包和重组系统的关键弱点是一个片段的丢失就会导致整个数据包都要被丢弃掉, 想要解决这个弱点得使用大块数据发送策略, 见下一篇文章 构建游戏网络协议四之发送大块数据.

接收分包后的数据包

之所以对分包后的数据包进行接收很困难的原因是我们不仅需要给缓冲区建立一个数据结构还要把这些分包重组成原始的数据包，我们也要特别小心如果有人试图让我们的程序产生崩溃而给我们发送恶意的数据包。

要非常小心检查一切可能的情况。除此之外，还有一个非常简单的事情要注意：让分包保存在一个数据结构里面，当一个数据包的所有分包都到达以后（通过计数来判断是否全部到达），将这些分包重组成一个大的数据包，并把这个重组后的大数据包返回给接收方。

什么样的数据结构在这里是有意义的?这里并没有什么特别的数据结构!我使用的是一种我喜欢称之为序列缓冲区的东西。我想和你分享的最核心的技巧是如何让这个数据结构变得高效：

1
2
3
4
5
6
7
8
const int MaxEntries = 256;
 
struct SequenceBuffer
{
    bool exists[MaxEntries];
    uint16_t sequence[MaxEntries];
    Entry entries[MaxEntries];
};

原文

原文出处

原文标题 : Packet Fragmentation and Reassembly (How to send and receive packets larger than MTU)

Introduction

Hi, I’m Glenn Fiedler and welcome to Building a Game Network Protocol.


In the previous article we discussed how to unify packet read and write into a single serialize function and added a bunch of safety features to packet read.


Now we are ready to start putting interesting things in our packets and sending them over the network, but immediately we run into an interesting question: how big should our packets be?


To answer this question properly we need a bit of background about how packets are actually sent over the Internet.


Background


Perhaps the most important thing to understand about the internet is that there’s no direct connection between the source and destination IP address. What actually happens is that packets hop from one computer to another to reach their destination.


Each computer along this route enforces a maximum packet size called the maximum transmission unit, or MTU. According to the IP standard, if any computer recieves a packet larger than its MTU, it has the option of a) fragmenting that packet, or b) dropping the packet.


So here’s how this usually goes down. People write a multiplayer game where the average packet size is quite small, lets say a few hundred bytes, but every now and then when a lot of stuff is happening in their game and a burst of packet loss occurs, packets get a lot larger than usual, going above MTU for the route, and suddenly all packets start getting dropped!


Just last year (2015) I was talking with Alex Austin at Indiecade about networking in his game Sub Rosa. He had this strange networking bug he couldn’t reproduce. For some reason, players would randomly get disconnected from the game, but only when a bunch of stuff was going on. It was extremely rare and he was unable to reproduce it. Alex told me looking at the logs it seemed like packets just stopped getting through.


This sounded exactly like an MTU issue to me, and sure enough, when Alex limited his maximum packet size to a reasonable value the bug went away.


MTU in the real world


So what’s a reasonable maximum packet size?


On the Internet today (2016, IPv4) the real-world MTU is 1500 bytes.


Give or take a few bytes for UDP/IP packet header and you’ll find that the typical number before packets start to get dropped or fragmented is somewhere around 1472.


You can try this out for yourself by running this command on MacOS X:


ping -g 56 -G 1500 -h 10 -D 8.8.4.4

On my machine it conks out around just below 1500 bytes as expected:


1404 bytes from 8.8.4.4: icmp_seq=134 ttl=56 time=11.945 ms
1414 bytes from 8.8.4.4: icmp_seq=135 ttl=56 time=11.964 ms
1424 bytes from 8.8.4.4: icmp_seq=136 ttl=56 time=13.492 ms
1434 bytes from 8.8.4.4: icmp_seq=137 ttl=56 time=13.652 ms
1444 bytes from 8.8.4.4: icmp_seq=138 ttl=56 time=133.241 ms
1454 bytes from 8.8.4.4: icmp_seq=139 ttl=56 time=17.463 ms
1464 bytes from 8.8.4.4: icmp_seq=140 ttl=56 time=12.307 ms
1474 bytes from 8.8.4.4: icmp_seq=141 ttl=56 time=11.987 ms
ping: sendto: Message too long
ping: sendto: Message too long
Request timeout for icmp_seq 142

Why 1500? That’s the default MTU for MacOS X. It’s also the default MTU on Windows. So now we have an upper bound for your packet size assuming you actually care about packets getting through to Windows and Mac boxes without IP level fragmentation or a chance of being dropped: 1472 bytes.


So what’s the lower bound? Unfortunately for the routers in between your computer and the destination the IPv4 standard says 576. Does this mean we have to limit our packets to 400 bytes or less? In practice, not really.


MacOS X lets me set MTU values in range 1280 to 1500 so considering packet header overhead, my first guess for a conservative lower bound on the IPv4 Internet today would be 1200 bytes. Moving forward, in IPv6 this is also a good value, as any packet of 1280 bytes or less is guaranteed to get passed on without IP level fragmentation.


This lines up with numbers that I’ve seen throughout my career. In my experience games rarely try anything complicated like attempting to discover path MTU, they just assume a reasonably conservative MTU and roll with that, something like 1000 to 1200 bytes of payload data. If a packet larger than this needs to be sent, it’s split up into fragments by the game protocol and re-assembled on the other side.


And that’s exactly what I’m going to show you how to do in this article.


Fragment Packet Structure


Let’s get started with implementation.


The first thing we need to decide is how we’re going to represent fragment packets over the network so they are distinct from non-fragmented packets.


Ideally, we would like fragmented and non-fragmented packets to be compatible with the existing packet structure we’ve already built, with as little overhead as possible in the common case when we are sending packets smaller than MTU.


Here’s the packet structure from the previous article:


[protocol id] (64 bits) // not actually sent, but used to calc crc32
[crc32] (32 bits)
[packet type] (2 bits for 3 distinct packet types)
(variable length packet data according to packet type)
[end of packet serialize check] (32 bits)

In our protocol we have three packet types: A, B and C.


Let’s make one of these packet types generate really large packets:


static const int MaxItems = 4096 * 4;

struct TestPacketB : public Packet
{
    int numItems;
    int items[MaxItems];

    TestPacketB() : Packet( TEST_PACKET_B )
    {
        numItems = random_int( 0, MaxItems );
        for ( int i = 0; i < numItems; ++i )
            items[i] = random_int( -100, +100 );
    }

    template <typename Stream> bool Serialize( Stream & stream )
    {
        serialize_int( stream, numItems, 0, MaxItems );
        for ( int i = 0; i < numItems; ++i )
        {
            serialize_int( stream, items[i], -100, +100 );
        }
        return true;
    }
};

This may seem somewhat contrived but these situations really do occur. For example, if you have a strategy where you send all un-acked events from server to client and you hit a burst of packet loss, you can easily end up with packets larger than MTU, even though your average packet size is quite small.


Another common case is delta encoded snapshots in a first person shooter. Here packet size is proportional to the amount of state changed between the baseline and current snapshots for each client. If there are a lot of differences between the snapshots the delta packet is large and there’s nothing you can do about it except break it up into fragments and re-assemble them on the other side.


Getting back to packet structure. It’s fairly common to add a sequence number at the header of each packet. This is just a packet number that increases with each packet sent. I like to use 16 bits for sequence numbers even though they wrap around in about 15 minutes @ 60 packets-per-second, because it’s extremely unlikely that a packet will be delivered 15 minutes late.


Sequence numbers are useful for a bunch of things like acks, reliability and detecting and discarding out of order packets. In our case, we’re going to use the sequence number to identify which packet a fragment belongs to:


[protocol id] (64 bits)   // not actually sent, but used to calc crc32
[crc32] (32 bits)
[sequence] (16 bits)
[packet type] (2 bits)
(variable length packet data according to packet type)
[end of packet serialize check] (32 bits)

Here’s the interesting part. Sure we could just add a bit is_fragment to the header, but then in the common case of non-fragmented packets you’re wasting one bit that is always set to zero.


What I do instead is add a special fragment packet type:


enum TestPacketTypes
{
    PACKET_FRAGMENT = 0,     // RESERVED
    TEST_PACKET_A,
    TEST_PACKET_B,
    TEST_PACKET_C,
    TEST_PACKET_NUM_TYPES
};

And it just happens to be free because four packet types fit into 2 bits. Now when a packet is read, if the packet type is zero we know it’s a fragment packet, otherwise we run through the ordinary, non-fragmented read packet codepath.


Lets design what this fragment packet looks like. We’ll allow a maximum of 256 fragments per-packet and have a fragment size of 1024 bytes. This gives a maximum packet size of 256k that we can send through this system, which should be enough for anybody, but please don’t quote me on this.


With a small fixed size header, UDP header and IP header a fragment packet be well under the conservative MTU value of 1200. Plus, with 256 max fragments per-packet we can represent a fragment id in the range [0,255] and the total number of fragments per-packet [1,256] with 8 bits.


[protocol id] (32 bits)   // not actually sent, but used to calc crc32
[crc32] (32 bits)
[sequence] (16 bits)
[packet type = 0] (2 bits)
[fragment id] (8 bits)
[num fragments] (8 bits)
[pad zero bits to nearest byte index]
<fragment data>

Notice that we pad bits up to the next byte before writing out the fragment data. Why do this? Two reasons: 1) it’s faster to copy fragment data into the packet via memcpy than bitpacking each byte, and 2) we can now save a small amount of bandwidth by inferring the fragment size by subtracting the start of the fragment data from the total size of the packet.


Sending Packet Fragments


Sending packet fragments is easy. For any packet larger than conservative MTU, simply calculate how many 1024 byte fragments it needs to be split into, and send those fragment packets over the network. Fire and forget!


One consequence of this is that if any fragment of that packet is lost then the entire packet is lost. It follows that if you have packet loss then sending a 256k packet as 256 fragments is not a very good idea, because the probability of dropping a packet increases significantly as the number of fragments increases. Not quite linearly, but in an interesting way that you can read more about here.


In short, to calculate the probability of losing a packet, you must calculate the probability of all fragments being delivered successfully and subtract that from one, giving you the probability that at least one fragment was dropped.


1 - probability_of_fragment_being_delivered ^ num_fragments

For example, if we send a non-fragmented packet over the network with 1% packet loss, there is naturally a 1⁄100 chance the packet will be dropped.


As the number of fragments increase, packet loss is amplified:


  • Two fragments: 1 - (99⁄100) ^ 2 = 2%

  • Ten fragments: 1 - (99⁄100) ^ 10 = 9.5%

  • 100 fragments: 1 - (99⁄100) ^ 100 = 63.4%

  • 256 fragments: 1 - (99⁄100) ^ 256 = 92.4%


So I recommend you take it easy with the number of fragments. It’s best to use this strategy only for packets in the 2-4 fragment range, and only for time critical data that doesn’t matter too much if it gets dropped. It’s definitely not a good idea to fire down a bunch of reliable-ordered events in a huge packet and rely on packet fragmentation and reassembly to save your ass.


Another typical use case for large packets is when a client initially joins a game. Here you usually want to send a large block of data down reliably to that client, for example, representing the initial state of the world for late join. Whatever you do, don’t send that block of data down using the fragmentation and re-assembly technique in this article.


Instead, check out the technique in next article which handles packet loss by resending fragments until they are all received.


Receiving Packet Fragments


It’s time to implement the code that receives and processed packet fragments. This is a bit tricky because we have to be particularly careful of somebody trying to attack us with malicious packets.


Here’s a list of all the ways I can think of to attack the protocol:



  • Try to send out of bound fragments ids trying to get you to crash memory. eg: send fragments [0,255] in a packet that has just two fragments.


  • Send packet n with some maximum fragment count of say 2, and then send more fragment packets belonging to the same packet n but with maximum fragments of 256 hoping that you didn’t realize I widened the maximum number of fragments in the packet after the first one you received, and you trash memory.


  • Send really large fragment packets with fragment data larger than 1k hoping to get you to trash memory as you try to copy that fragment data into the data structure, or blow memory budget trying to allocate fragments


  • Continually send fragments of maximum size (256⁄256 fragments) in hope that it I could make you allocate a bunch of memory and crash you out. Lets say you have a sliding window of 256 packets, 256 fragments per-packet max, and each fragment is 1k. That’s 64 mb per-client.


  • Can I fragment the heap with a bunch of funny sized fragment packets sent over and over? Perhaps the server shares a common allocator across clients and I can make allocations fail for other clients in the game because the heap becomes fragmented.



Aside from these concerns, implementation is reasonably straightforward: store received fragments somewhere and when all fragments arrive for a packet, reassemble them into the original packet and return that to the user.


Data Structure on Receiver Side


The first thing we need is some way to store fragments before they are reassembled. My favorite data structure is something I call a sequence buffer:


const int MaxEntries = 256;

struct SequenceBuffer
{
    uint32_t sequence[MaxEntries];
    Entry entries[MaxEntries];
};

Indexing into the arrays is performed with modulo arithmetic, giving us a fast O(1) lookup of entries by sequence number:


const int index = sequence % MaxEntries;

A sentinel value of 0xFFFFFFFF is used to represent empty entries. This value cannot possibly occur with 16 bit sequence numbers, thus providing us with a fast test to see if an entry exists for a given sequence number, without an additional branch to test if that entry exists.


This data structure is used as follows. When the first fragment of a new packet comes in, the sequence number is mapped to an entry in the sequence buffer. If an entry doesn’t exist, it’s added and the fragment data is stored in there, along with information about the fragment, eg. how many fragments there are, how many fragments have been received so far, and so on.


Each time a new fragment arrives, it looks up the entry by the packet sequence number. When an entry already exists, the fragment data is stored and number of fragments received is incremented. Eventually, once the number of fragments received matches the number of fragments in the packet, the packet is reassembled and delivered to the user.


Since it’s possible for old entries to stick around (potentially with allocated blocks), great care must be taken to clean up any stale entries when inserting new entries in the sequence buffer. These stale entries correspond to packets that didn’t receive all fragments.


And that’s basically it at a high level. For further details on this approach please refer to the example source code for this article.


Click here to get the example source code for this article series.


Test Driven Development


One thing I’d like to close this article out on.


Writing a custom UDP network protocol is hard. It’s so hard that even though I’ve done this from scratch at least 10 times, each time I still manage to fuck it up in a new and exciting ways. You’d think eventually I’d learn, but this stuff is complicated. You can’t just write low-level netcode and expect it to just work.


You have to test it!


My strategy when testing low-level netcode is as follows:



  • Code defensively. Assert everywhere. These asserts will fire and they’ll be important clues you need when something goes wrong.


  • Add functional tests and make sure stuff is working as you are writing it. Put your code through its paces at a basic level as you write it and make sure it’s working as you build it up. Think hard about the essential cases that need to be property handled and add tests that cover them.


  • But just adding a bunch of functional tests is not enough. There are of course cases you didn’t think of! Now you have to get really mean. I call this soak testing and I’ve never, not even once, have coded a network protocol that hasn’t subsequently had problems found in it by soak testing.


  • When soak testing just loop forever and just do a mix of random stuff that puts your system through its paces, eg. random length packets in this case with a huge amount of packet loss, out of order and duplicates through a packet simulator. Your soak test passes when it runs overnight and doesn’t hang or assert.


  • If you find anything wrong with soak testing. You may need to go back and add detailed logs to the soak test to work out how you got to the failure case. Once you know what’s going on, stop. Don’t fix it immediately and just run the soak test again.


  • Instead, add a unit test that reproduces that problem you are trying to fix, verify your test reproduces the problem, and that it problem goes away with your fix. Only after this, go back to the soak test and make sure they run overnight. This way the unit tests document the correct behavior of your system and can quickly be run in future to make sure you don’t break this thing moving forward when you make other changes.


  • Add a bunch of logs. High level errors, info asserts showing an overview of what is going on, but also low-level warnings and debug logs that show what went wrong after the fact. You’re going to need these logs to diagnose issues that don’t occur on your machine. Make sure the log level can be adjusted dynamically.


  • Implement network simulators and make sure code handles the worst possible network conditions imaginable. 99% packet loss, 10 seconds of latency and +/- several seconds of jitter. Again, you’ll be surprised how much this uncovers. Testing is the time where you want to uncover and fix issues with bad network conditions, not the night before your open beta.


  • Implement fuzz tests where appropriate to make sure your protocol doesn’t crash when processing random packets. Leave fuzz tests running overnight to feel confident that your code is reasonably secure against malicious packets and doesn’t crash.


  • Surprisingly, I’ve consistently found issues that only show up when I loop the set of unit tests over and over, perhaps these issues are caused by different random numbers in tests, especially with the network simulator being driven by random numbers. This is a great way to take a rare test that fails once every few days and make it fail every time. So before you congratulate yourself on your tests passing 100%, add a mode where your unit tests can be looped easily, to uncover such errors.


  • Test simultaneously on multiple platforms. I’ve never written a low-level library that worked first time on MacOS, Windows and Linux. There are always interesting compiler specific issues and crashes. Test on multiple platforms as you develop, otherwise it’s pretty painful fixing all these at the end.


  • This about how people can attack the protocol. Implement code to defend against these attacks. Add functional tests that mimic these attacks and make sure that your code handles them correctly.



This is my process and it seems to work pretty well. If you are writing a low-level network protocol, the rest of your game depends on this code working correctly. You need to be absolutely sure it works before you build on it, otherwise it’s basically a stack of cards.


In my experience, game neworking is hard enough without having suspicions that that your low-level network protocol has bugs that only show up under extreme network conditions. That’s exactly where you need to be able to trust your code works correctly. So test it!

译文

译文出处

译者：崔嘉艺(milan21) 审校：崔国军（星际迷航）

大家好，我是格伦·菲德勒。欢迎大家阅读系列教程《构建游戏网络协议》的第三篇文章。在之前的文章中，我们讨论了如何将数据包的读取和写入用一个单独的序列化函数来实现。


现在我们要开始把一些有趣的事情放到这些数据包中，,但正如你即将开始编码的令人惊叹的多人在线动作、第一人称射击、大型多人在线角色扮演游戏、多人在线战术竞技游戏会发生的那样，当你以每秒120次的频率发送8k大小的数据包，游戏网络中会传来一个声音呼喊着你:“不要发送超过1200字节大小的数据包!”

但是都已经2016年了，你真的要注意最大传输单元这个东西么?

不幸的是，答案是是的！


最大传输单元MTU

你可能已经听说过最大传输单元了。在网络程序员中流传着大量有关最大传输单元问题的故事。那么这到底是怎么回事呢？究竟什么是最大传输单元?为什么你要在乎最大传输单元这个事情？

当你通过互联网来发送数据包的时候到底背后发生了什么？这些数据包要从一台计算机(路由器)跳到另一个计算机(路由器)上，如此往复多次才能到达自己的目的地。这是一个分组交换网络具体如何运作的方式。在大部分时间里，它的工作方式不像是在源和目的地之间存在一条直接的连接。


但意外的是：每台计算机(路由器)会沿着路由强制要求数据包的大小会有一个最大的上限，这个上限就是所谓的最大传输单元。如果任意一个路由器收到一个数据包的大小超过这个最大传输单元的大小，它有这么两个选择，a)在IP层对这个数据包进行分包，并将分包后的数据包继续传递，b)丢弃这个数据包然后告诉你数据包被丢弃了，你自己负责摆平这个问题。


这儿有一个我会经常遇到的情况。人们在编写多人在线游戏的时候，数据包的平均大小都会非常的小，让我们假设下，这些数据包的平均大小大概只有几百字节，但时不时会在他们的游戏中同时发生大量的事情并且发出去的数据包会出现丢失的情况，这个时候数据包会比通常的情况下要大。突然之间，游戏的数据包的大小就会超过最大传输单元的大小，这样就只有很少一部分玩家能够收到这个数据包，然后整个通信就崩溃了。


就在去年(2015年)，我与亚历克斯·奥斯汀在Indiecade谈论他的游戏” Sub Rosa “中的网络部分。他遇到了一些奇怪的无法重现的网络bug。出于某种原因，一些客户端（在所有玩家里面总是有那么一个或者两个）会随机的从游戏中断开连接并且其他人都能够正常游戏。查看日志的话，亚历克斯又觉得一切都是正常的，只是看上去好像数据包突然停止进行传递了。


对我来说，这听上去就像是一个最大传输单元所引起的问题，并且我非常确信。当亚历克斯把他最大的数据包大小限制在一个合理的值之内，这个bug就再也没有出现了。



真实世界中的最大传输单元MTU

所以什么是“一个合理的数据包的大小”？

在今天的互联网上(2016年，还是基于IPv4)，典型的最大传输单元的大小是1500字节。在UDP/IP数据包的包头添加或者去掉几个字节，你会发现在数据包开始出现被丢弃或者被分包情况的一个典型的边界值是1472。

你可以自己在MacOS X尝试运行下下面这个命令：

ping-g 56 -G 1500 -h 10 -D 8.8.4.4

在我的机器上，这个结果在略微低于1500字节的大小上下浮动，符合预期：

1404bytes from 8.8.4.4: icmp_seq=134 ttl=56 time=11.945 ms

1414bytes from 8.8.4.4: icmp_seq=135 ttl=56 time=11.964 ms

1424bytes from 8.8.4.4: icmp_seq=136 ttl=56 time=13.492 ms

1434bytes from 8.8.4.4: icmp_seq=137 ttl=56 time=13.652 ms

1444bytes from 8.8.4.4: icmp_seq=138 ttl=56 time=133.241 ms

1454bytes from 8.8.4.4: icmp_seq=139 ttl=56 time=17.463 ms

1464bytes from 8.8.4.4: icmp_seq=140 ttl=56 time=12.307 ms

1474bytes from 8.8.4.4: icmp_seq=141 ttl=56 time=11.987 ms

ping:sendto: Message too long

ping:sendto: Message too long

Requesttimeout for icmp_seq 142

为什么是1500字节？这是MacOS X上默认的最大传输单元的大小。这也是Windows平台上默认的最大传输单元的大小。所以现在我们对数据包的大小有了一个上限（也就是不能超过这个默认的最大传输单元的大小），假如你真的关心数据包通过Windows平台或者Mac平台进行传播而不希望数据包在IP层进行分包或者有被丢弃的可能的话，那么就要保证数据包的大小不能超过这个上限：1472个字节。


那么这个最大传输单元的大小的下限是多少呢？MacOS X允许设置的最大传输单元的大小的值是在1280到1500，所以我对现在互联网上通过IPv4进行传播的数据包的最大传输单元的大小的下限有一个比较保守的估计，就是1200字节。如果是在通过IPv4进行传播的情况下这个比较保守的大传输单元的大小的下限也会是一个很好的估计值，任意数据包只要大小小于1280字节都能保证在没有IP层分包的情况下顺利的传播。


这个估计与我在职业生涯中感受到的情况是比较一致的。以我的经验来看，很少有游戏会试图做这些复杂的事情，诸如尝试发现路径上的最大传输单元的大小之类的，它们一般都是假定一个合理又保守的最大传输单元的大小然后一直遵循这个值。如果出现一个要发送的数据包比这个保守的最大传输单元的大小要大的情况，游戏协议会将这个数据包分成几个包然后在网络的另外一侧进行重组。

而这正是我要在这篇文章里面要向你传授的内容。


分包后的数据包的结构

让我们从决定该对网络上传输的数据分包后采用什么的结构进行表示来开始构建我们的数据包分包和重组机制。在理想状态下，我们希望分包以后的数据包和未分包的数据包兼容我们现在已经建立好的数据包结构，这样当我们发送小于最大传输单元的大小的数据包的时候，网络协议没有任何多余的负载。

下面是在前一篇文章结束的时候得到的数据包的结构：



[protocol id] (64 bits) // not actually sent, but used to calc crc32
[crc32] (32 bits)
[packet type] (2 bits for 3 distinct packet types)
(variable length packet data according to packet type)
[end of packet serialize check] (32 bits)


在我们这个例子之中，我们一共有三个数据包的类型，分别是Ａ、Ｂ和Ｃ。

让我们用这三个数据包类型中的一个制造一个比最大传输单元的大小还要大一些的数据包：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static const int MaxItems = 4096 * 4;
struct TestPacketB : public protocol2::Packet
{
int numItems;
int items[MaxItems];
TestPacketB() : Packet( TEST_PACKET_B )
{
numItems = random_int( 0, MaxItems );
for ( int i = 0; i < numItems; ++i )
items[i] = random_int( -100, +100 );
}
template <typename stream> bool Serialize( Stream & stream )
{
serialize_int( stream, numItems, 0, MaxItems );
for ( int i = 0; i < numItems; ++i )
serialize_int( stream, items[i], -100, +100 );
return true;
}
};


这可能看起来不怎么自然，但在现实世界中这些情况真的会发生。举个简单的例子来说，如果你有一个策略，这个策略是从服务器往客户端发送所有的未确认的事件，你会得到一组可信赖也有序的事件，但是也会遇到大量数据包的丢失的情况，你会轻易的遇到数据包比最大传输单元的大小还要大的情况，即使你的数据包的平均大小非常小。（译注：这是由于丢包重传导致的不停重发，而重发的数据包在UDP或者TCP上会进行合并。所以即使数据包的平均大小远小于最大传输单元的大小，但是由于大量这样的数据包的合并，还是很容易出现超过最大传输单元的大小的情况）。


在大多数的情况下，通过实现这么一个策略：在一个数据包里面只包含很少一组事件或者状态更新来避免数据包的大小超过最大传输单元的大小，采用这种策略以后可以有效的规避上面的那种情况。这种规划在很多情况下都工作的很棒。。。但是有一种情况下这种策略也是存在问题的，这种情况就是增量编码。


由一个增量编码器创建的数据包的大小是与当前状态与之前状态之间所发生的状态变化的数量成正比的。如果这两个状态之间有大量的不同的话，那么增量也将很大并且你对这种情况其实是没有什么办法的。如果出现一个增量恰好比最大传输单元的大小要大的情况，当然这是一个坏运气下才会出现的情况，但是你仍然要发送这个超过最大传输单元的大小的数据包！所以你可以看到，在增量编码的情况下，你真的不能限制数据包的最大大小一定小于最大传输单元的大小，在这种情况下，数据包的分包和重组策略就有了用武之地。


让我们回到数据包的结构上面来。在每个数据包的包头的地方添加一个序号是一种非常常见的做法。这并没有什么复杂的。这只是一个数据包的序号，会在每个数据包进行发送的时候依次加一。举个例子来说，就是0、1、2、3这么简单。我喜欢用16比特来表示这个序号，即使在每秒发送60个数据包的情况下，只要15分钟序号就会被用完一遍，需要再次从头开始重用，但是这么做也没有什么关系，主要是因为你在网络上收到一个15分钟之前发送出去的数据包是一个非常罕见的事情，所以你很少会有机会困惑这到底是一个新的数据包还是一个旧的数据包（因为IP层在包头的地方有个跳转计数，超出一定跳转次数的数据包会被丢弃掉，所以基本不用担心这种情况）。如果你确实关心这个问题的话，请使用32比特的序号进行代替。


无论你选择用多少比特来表示这个序号，它们对于很多事情都是有用的，比如说可依赖性、检测和丢弃乱序的数据包等等。除此之外，我们需要一个数据包序号的原因是在对数据包进行分包的时候，我们需要某个方法来确定这个数据包的分包到底是属于哪个数据包的。

所以，让我们在我们的数据包的结构里面加上序号这个东西：



[protocol id] (64 bits)   // not actually sent, but used to calc crc32
[crc32] (32 bits)
[sequence] (16 bits)
[packet type] (2 bits)
(variable length packet data according to packet type)
[end of packet serialize check] (32 bits)


这是最有趣的部分。我们可以在数据包的头部只添加一个比特的标识 is_fragment，但是对于通常情况下根本不需要分包的数据包来说，你就浪费了一个比特，因为它总是要被置为0。这不是很好。

相反，我的选择是在数据包的结构里面添加了一个特殊的”分包后的数据包“的类型：

?
1
2
3
4
5
6
7
8
enum TestPacketTypes
{
PACKET_FRAGMENT = 0, // RESERVED
TEST_PACKET_A,
TEST_PACKET_B,
TEST_PACKET_C,
TEST_PACKET_NUM_TYPES
};

这恰好不需要占据任何的空间，是因为四个数据包类型正好可以用两个比特来表示，而这两个比特的空间已经用于表示数据包类型了，我们只是在原来的枚举上新加了一个类型。这么处理以后，每次当我们读取一个数据包的时候，如果这个数据包的类型是0的话，我们就知道这个数据包是一个特殊的分包以后的数据包，它的内存布局可以通过数据包的类型得知，否则的话，我们就走回原来的通用的对非分包的数据包进行读取和处理的方法。

让我们设计下这个分包后的数据包看起来应该是什么样子的。我们将允许一个数据包最多可以分成256个数据包，并且每个分包后的数据包的大小不会超过1024个字节。这样的话，我们就可以通过这样一个系统来发送大小最大为256k的数据包，这对于任意系统任意情况来说都应该是足够的，但是这只是我个人的一个看法，如果有特殊的情况，还请结合实际情况进行具体分析。

有了这么一个不大的固定大小的数据包包头结构，再加上UDP的包头结构以及IP的包头结构，一个分包以后的数据包会小于之前我们保守估计的最大传输单元的大小：1200字节。除此之外，因为一个数据包最多可以分包成256个数据包，我们可以用【0，255】这个范围来表示分包的id和序号，这样每个分包里面还需要有8比特来表示这个序号。



[protocol id] (32 bits)   // not actually sent, but used to calc crc32
[crc32] (32 bits)
[sequence] (16 bits)
[packet type = 0] (2 bits)
[fragment id] (8 bits)
[num fragments] (8 bits)
[pad zero bits to nearest byte index]
<fragment data>


请注意，我们把这几个比特对齐到了下一个字节，然后才把对齐以后的数据写入到数据包里面。我们为什么要这么做？这么做其实是有两个原因的: 1) 这么处理以后可以通过memcpy函数更快的把分包的数据拷贝到数据包里面而不需要使用位打包器来对每个字节进行处理。2) 我们通过不发送分包数据的大小节省了一小部分带宽。我们可以通过从数据包的整体大小减去分包数据起始位置的字节序号来推断出这个分包的大小。


发送分包以后的数据包

发送分包以后的数据包是一件非常容易的事情。如果数据包的大小小于保守估计的最大传输单元的大小。那么就按正常的方法进行发送。否则的话，就计算这个数据包到底该分成多少个1024字节的数据包分包，然后构建这些分包并按照之前发送正常数据包的方法进行发送。发送出去以后也不记录发送的数据包的内容，这没什么困难的！

这种发送以后不记录发送的数据包的内容的方法有一个后果，就是数据包的任意一个分包如果丢失的话，那么整个数据包就都要丢弃。由此可见，当你需要发送要给256K的数据包的时候要发送256个分包，如果有一个分包丢失的话，你就要重新把这个256k的数据包再分一次包然后再发送出去。这绝对不是一个好主意。

这显然是一个很糟糕的办法，因为随着分包数目的增多，发生丢失的概率肯定是显著的增大。这种增长关系不是线性的，而是一种相当复杂的关系，如果你对这个计算感兴趣的话，你可以读下这篇文章。

简而言之，如果你要计算一个数据包会被丢弃的概率，你必须要计算所有分包被成功发送到目的地的概率，然后从1中减去这个概率，得到的结果就是至少有一个分包丢失的概率。

下面这个公式可以用来计算因为分包丢失导致整个数据包被丢弃的概率：

＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼

1- ( probability of fragment being delivered ) ^ num_fragments

＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼

让我们举个简单的例子对上面这个公式进行说明，如果我们发送的一个不需要分包的数据包，如果它在网络上传说的时候丢失的概率是1%，那么只有百分之一的概率会出现这个数据包被丢弃的情况，或者我们不要嫌麻烦，把这些数据代入到上面这个公式里面: 1 – (99/100) ^ 1 = 1/100 = 1%。

随着分包数量的增加，整个数据包被丢弃的概率也随之增加：

  • 两个分包的情况： 1 – (99/100) ^ 2 = 2%。
  • 十个分包的情况： 1 – (99/100) ^ 10 = 9.5%。
  • 一百个分包的情况： 1 – (99/100) ^ 100 = 63.4%。
  • 二百五十六个分包的情况： 1 – (99/100) ^ 256 = 92.4%。

所以我建议你要小心分包以后的数量。这个策略最好是只对2-4个分包的情况进行使用，而且最好是针对那种对时间不怎么敏感的数据使用或者是就算分包lost了也无所谓的情况。绝对不要只是为了省事就把一大堆依赖顺序的事件打到一个大数据包里面然后依赖数据包的分包和重组机制进行发送。这会让事情变得更加麻烦。

大数据包的另外一种典型的用途是当客户端新连入一个游戏服务器的时候。游戏服务器通常会把大块的数据以一种可靠的方式下发给客户端。对于后期才加入的客户端而言，这些大块的数据也许代表了世界的初始状态。无论这些数据包含了怎么样的信息，请不要使用本篇文章的分包技巧来给客户端下发大块的数据。相反，请查阅这个系列教程的下篇文章，在那篇文章里面将讲解如何在有数据包可能发生丢失的情况下，快速可靠的发送大块的数据直到这些大块的数据完全被确认接收。



对分包后的数据包的接收

尽管发送分包以后的数据包是一件相同简单的事情，但是对分包后的数据包进行接收就相对需要技巧了。

之所以对分包后的数据包进行接收很困难的原因是我们不仅需要给缓冲区建立一个数据结构还要把这些分包重组成原始的数据包，我们也要特别小心如果有人试图让我们的程序产生崩溃而给我们发送恶意的数据包。



[protocol id] (32 bits)   // not actually sent, but used to calc crc32
[crc32] (32 bits)
[sequence] (16 bits)
[packet type = 0] (2 bits)
[fragment id] (8 bits)
[num fragments] (8 bits)
[pad zero bits to nearest byte index]
<fragment data>


下面列出的是我能想到的如何攻击你的协议以便让你的服务器崩溃的所有方法：

  • 尝试发送分包ID在一个限制范围内的分包，看看能不能让你的程序崩溃。举个例子来说，也许这个数据包只有两个分包，但是我会发送多个分包ID在【０，２５５】之内的分包。
  • 发送一个数据包，让我们假设这个书包的最大分包数量是2，然后发送多个属于这个数据包的分包，但是在分包的数据包报头里面把最大分包的数量改为256，来希望你在接收完第一个分包以后，不会发现分包的最大数量信息被改变了，这样就有可能造成你的内存崩溃。
  • 发送非常大的分包，让分包里面的数据超过1k，测试下你在试图把分包数据拷贝到数据结构的时候是否有良好的判断，如果没有良好的判断的话，这也许会让你的内存崩溃，或者占用大量的内容让你在分配新的分包的时候没有空间。
  • 持续的给你的程序发送最大分包数目的分包（也就是如果最大分包数目是256的话，就持续不断的发送分包ID是256的数据包），希望你会分配大量的内容来容纳这些分包然后让你的内存崩溃。让我们假设你的程序中有一个滑动窗口，这个滑动窗口有256个数据包，每个数据包最多可以有256个分包，每个分包预留的空间是1k。那么也就是会给每个客户端预留67,108,864字节或者64mb的空间。我可以通过这种方法让服务器崩溃么？我能用一堆大小有趣的分包来耗尽的你地址空间的heap空间么？因为服务器的程序是你来设计实现的，所以只有你才知道这个问题的确切答案。它取决于你的内存预算以及如何分配内存来存储分包。如果你考虑过了觉得这会是一个问题，那么就限制下缓冲区中分包的数目或考虑减少每个数据包的分包的最大数目。考虑给每个分包静态分配数据结果或者使用一个内存池来减少内存碎片。


所以你可以看到，在接收端代码是非常脆弱的，要非常小心检查一切可能的情况。除此之外，还有一个非常简单的事情要注意：让分包保存在一个数据结构里面，当一个数据包的所有分包都到达以后（通过计数来判断是否全部到达），将这些分包重组成一个大的数据包，并把这个重组后的大数据包返回给接收方。


什么样的数据结构在这里是有意义的?这里并没有什么特别的数据结构!我使用的是一种我喜欢称之为序列缓冲区的东西。我想和你分享的最核心的技巧是如何让这个数据结构变得高效：

?
1
2
3
4
5
6
7
8
const int MaxEntries = 256;
struct SequenceBuffer
{
bool exists[MaxEntries];
uint16_t sequence[MaxEntries];
Entry entries[MaxEntries];
};


这里面有几件事情值得注意。首先，使用类似数组的结构可以允许对给定条目是否存在于一个序列缓冲区的存在性进行快速测试并且将测试结果进行缓存，即使每个数据包的条目结构是非常大的（而且这种结构对于数据包的分包和重组来说是非常棒的）。

那么我们该如何使用这个数据结构？当你接收到一个分包以后的数据包以后，这个数据包会携带一个序号指定它是属于哪个数据包的分包。这个序号会随着发送而不停的增大(所有序号全部用完导致发生环绕除外)， 所以最关键的技巧是你要对序号进行散列让散列后的序号进入一个数组中某个给定的位置，具体处理过程如下所示：

int index = sequence % MaxEntries;

现在你可以用O(1)的时间复杂度进行一个快速测试，来通过序号看下一个给定的条目是否存在，并且判断下这个条目是否和你想要读取或者写入的数据包序号相匹配。也就是说，你既需要测试存在性又需要测试序号是否是预期的序号，这是因为所有的序号都是有效的数字(比如说是0)，还有就是因为根据一个特定的数据包序号查找到的条目可能是存在的，但是它属于过去的一个序号（比如说，这是某个其他的序号，但是恰巧通过取模的计算得到相同的序号）。

所以当一个新的数据包的第一个分包到达的时候，你需要把数据包的序号散列成一个索引，如果发现这个索引对应的内容还不存在的话，你需要设置exists[index] = 1，并设置sequence[index]来匹配你正在处理的数据包，并把这个分包储存在序号缓冲区对应的条目里面。这样当下一次有分包实际到达的时候，你会得到相同的序号，然后得到一个相当的索引，在查找的时候会发现对应这个索引的内容已经存在了，并且这个条目的序号正好能和刚刚接收到的数据包的序号匹配，所以你就可以把这个分包累加到这个条目上，这个过程会一直重复直到这个数据包的所有分包都被接收到为止。

如果从比较抽象的层次来解释这个事情的话，基本原理大概就是这样的。这种方法的一个更完整的解释请参阅本文的示例源代码。在地址https://www.patreon.com/gafferongames可以获取本系列文章示例的源代码。


网络协议的测试驱动开发

还有一件事情我想在文章的末尾进行补充说明。我感觉如果我不向我的读者提及这个方法的话，就是对他们的一个伤害。

编写一个定制的网络协议是非常困难的。这个过程是如此的苦难以至于我从头开始至少编写了10次网络协议，但是每次我都觉得我在用一种全新的有趣的方法在做这个事情。也许你会认为是我在挑战自己，用一些新奇的方法来实现这个过程，但其实是这个过程太复杂了，完全没有办法按照预期的那样写完代码就期待它们能够正确的工作。你需要对写出来的代码进行测试！


当编写底层网络协议层的代码的时候，我的策略是:

1、防御性编程。在一切可能的地方进行断言。当某些地方出现错误的时候这些断言会起作用，并且将成为查找问题的重要线索。

2、添加函数的功能测试，确保它们是如你的预期那样工作的。把你的代码放到一个可以运行和测试的环境下，这样可以不时地对它们进行测试以便可以确保它一直会像你起初创建它们时候那样良好的工作。仔细考虑有哪些情况需要正确的处理并给这些情况添加测试。

3、虽然函数测试非常有必要，但是只是添加一些函数测试是远远不够的。无论如何都有遇到你没有预料到的情况! 现在你必须把它们放到一个真实的环境下看看到底会发生什么。我把这个称之为浸泡测试，并且在我之前编写网络协议的过程中还从来没有过在浸泡测试的过程中没有发现问题的情况。浸泡测试只是在不停的循环，并会随机的做一些事情让你的系统在它的空间中处理一些情况，让我们举些简单的例子对它进行一些简单的说明，比如说构造出随机长度的数据包，而且这些数据包有一个非常高的丢失率，通过数据包模拟器发出的大量乱序并且重复的数据包等等。如果你的程序能够在一晚上的时间里面不挂起或者遇到断言，那么就算你的程序通过了浸泡测试。

4、如果你的程序在浸泡测试的过程中发现了某些问题。你可能需要在代码里面添加一些详细的日志以便下次在浸泡测试的时候如果遇到了同样的问题你可以找到出现问题的原因。一旦你知道发生了什么，就可以停止了。不要立即的修复这个问题并且再次运行浸泡测试。这种做法非常的愚蠢。相反，利用单元测试来不停的重现你需要修复的问题，确保单元测试能够重现问题，而且这个问题因为你的修复已经彻底修好了。只有在这样的处理流程之后，才能回到浸泡测试并确保程序在浸泡测试能正常运转一整夜。通过这种方式，单元测试能够记录你的系统的正确的行为并且在以后需要的时候可以快速的运行起来，确保当你做其他改变的时候不会导致一些原来修过的问题重复的出现。


这就是我的数据包分包和重组的处理流程了，它似乎工作的不错。如果你在进行一些底层的网络协议的设计，你的游戏的其他的部分将依赖于底层的网络协议的设计。在你继续构建其他的功能之前，你需要绝对的确认底层的网络协议是否能够正常的工作，否则就像一堆胡乱堆积的卡片，很容易就散架了。多人在线游戏的网络部分是非常困难的，如果不小心设计的话，很容易就会出现底层网络协议可能无法正常的工作或者存在缺陷。所以请确保你是知道你的底层网络协议是如何工作的！

即将到来的文章的预告

下一篇文章是: 《发送大块的数据》

请继续阅读本系列的下一篇文章，在哪篇文章里面我将向你展示如何通过数据包快速可信赖的发送大块的数据，如果其中一块数据丢失了也不需要丢弃整个数据包！

如果你觉得这篇文章有价值的话，请在patreon上支持我的写作，这样我会写的更快。你可以在BSD 3.0许可下访问到这篇文章里面的代码。非常感谢你的支持！


【版权声明】

原文作者未做权利声明，视为共享知识产权进入公共领域，自动获得授权。


Posted on | In

自我总结本篇概要

  • 读取数据的时候要特别小心， 因为可能会有攻击者发送过来的恶意的数据包以及错误的包， 在写入数据的时候你可能会轻松很多，因为如果有任何事情出错了，那几乎肯定是你自己导致的错误

  • 统一的数据包序列化功能 ：诀窍在于让流类型的序列化函数模板化。在我的系统中有两个流类型：ReadStream类和WriteStream类。每个类都有相同的一套方法，但实际上它们没有任何关系。一个类负责从比特流读取值到变量中，另外一个类负责把变量的值写到流中。
    在模板里类似这样写, 通过 Stream::IsWriting 和 Stream::IsReading 模板会自动区分,然后帮你生产你想要的代码, 简洁漂亮

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    class WriteStream
    {
    public:

        enum { IsWriting = 1 };
        enum { IsReading = 0 };
        // ...
    };

    class ReadStream
    {
    public:

        enum { IsWriting = 0 };
        enum { IsReading = 1 };
        // ..
    }

    template <typename Stream>
    bool serialize( Stream & stream, float & value )
    {
       union FloatInt
       {
           float float_value;
           uint32_t int_value;
       };
      
       FloatInt tmp;
       if ( Stream::IsWriting )
           tmp.float_value = value;
      
       bool result = stream.SerializeBits( tmp.int_value, 32 );
      
       if ( Stream::IsReading )
           value = tmp.float_value;
      
       return result;
    }

  • 边界检查和终止读取 ： 把允许的大小范围也传给序列化函数而不仅仅是所需的比特数量。

  • 序列化浮点数和向量 ： 计算机根本不知道内存中的这个32位的值到底是一个整数还是一个浮点数还是一个字符串的部分。它知道的就是这仅仅是一个32位的值。代码如下(可以通过一个联合体来访问看上去是整数的浮点数).
    有些时候，你并不想把一个完整精度的浮点数进行传递。那么该如何压缩这个浮点值？第一步是将它的值限制在某个确定的范围内然后用一个整数表示方式来将它量化。
    举个例子来说，如果你知道一个浮点类型的值是在区间[-10,+10]，对于这个值来说可以接受的精确度是0.01，那么你可以把这个浮点数乘以100.0让它的值在区间[-1000,+1000]并在网络上将其作为一个整数进行序列化。而在接收的那一端，仅仅需要将它除以100.0来得到最初的浮点值. 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    union FloatInt
    {
       float float_value;
       uint32_t int_value;
    };
      
    FloatInt tmp;
    tmp.float_value= 10.0f;
    printf(“float value as an integer: %x\n”, tmp.int_value );

  • 序列化字符串和数组 : 为什么要费那么大精力把一个字节数组按比特打包到你的比特流里?为什么不在序列化写入之前进行按字节进行对齐？Why not align to byte so you can memcpy the array of bytes directly into the packet?
    如何将比特流按字节对齐？只需要在流的当前位置做些计算就可以了，找出还差写入多少个比特就能让当前比特流的比特数量被8整除，然后按照这个数字插入填充比特（比如当前比特流的比特数量是323，那么323+5才能被8整除，所以需要插入5个填充比特）。对于填充比特来说，填充的比特值都是0，这样当你序列化读取的时候你可以进行检测，如果检测的结果是正确的，那么就确实是在读取填充的部分，并且填充的部分确实是0。一直读取到下一个完整字节的比特起始位置（可以被8整除的位置）。如果检测的结果是在应该填充的地方发现了非0的比特值，那么就中止序列化读取并丢弃这个数据包。

  • 序列化数组的子集 : 当实现一个游戏网络协议的时候，或早或晚总会需要序列化一个对象数组然后在网络上传递。比如说服务器也许需要把所有的物体发送给客户端，或者有时候需要发送一组事件或者消息。如果你要发送所有的物体到客户端，这是相当简单直观的，但是如果你只是想发送一个数组的一个子集怎么办？
    最先想到也是最容易的办法是遍历数组的所有物体然后序列化一个bool数组，这个bool数组标记的是对应的物体是否通过网络发送。如果bool值为1那么后面会跟着物体的数据，否则就会被忽略然后下一个物体的bool值取决于流的下一个值。
    如果有大量的物体需要发送，举个例子来说，整个场景中有4000个物体，有一半的物体也就是2000个需要通过网络进行发送。每个物体需要一个序号，那么就需要2000个序号，每个序号需要12比特。。。。这就是说数据包里面24000比特或者说接近30000比特（几乎是30000，不是严格是，译注：原文如此）的数据被序号浪费掉了.
    可以把序号的编码方式修改下来节省数据，序号不再是全局序号，而是相对上一个物体的相对序号。
  • 如何应对恶意数据包和错误包 : 如果某些人发送一些包含随机信息的恶意数据包给你的服务器。你会不会在解析的时候把服务器弄崩溃掉？
    有三种技术应对 :
    • 协议ID : 在你的数据包里面包含协议ID。一般典型的做法是，头4个字节你可以设定一些比较罕见而且独特的值，你可以通过这３２比特的数据判断出来根本就不是你的应用程序的包，然后就可以直接丢弃了。
    • CRC32 : 对你的数据包整体做一个CRC32的校验，并把这个校验码放到数据包的包头。可以不发送这个协议ID，但是发送方和接收方提前确认过这个协议ID是什么，并在计算数据包CRC32值的时候装作这个数据包带上了这个协议ID的前缀来参与计算。这样如果发送方使用的协议ID与接收方不一致的时候，CRC32的校验就会失败，这将为每个数据包节省4个字节.
    • 序列化检测 : 是在包的中间，在一段复杂的序列化写入之前或者之后写上一个已知的32比特整数，并在另外一端序列化读取的时候用相同的值进行检测判断。如果序列化检查值是不正确的，那么就中止序列化读取并丢弃这个数据包。
      . . .

Posted on | In

自我总结

这篇文章只是介绍, 之后的文章才是正题. 此篇文章大体介绍了 :

  • 文本格式传输的低效率问题， 为了可读性而产生了太多冗余无用数据
  • 为什么不用目前已经有了的库比如Protocol Buffers：因为我们不需要版本信息，也不需要什么跨语言的支持。所以让我们直接忽略掉这些功能并用我们自己的不带属性的二进制流进行代替，在这个过程中我们可以获得更多的控制性和灵活性
  • 要注意大小端的问题
  • 实现一个位打包器， 工作在32位或者64位的级别， 而不是是工作在字节这个级别。因为现代机器对这个长度进行了专门的优化而不应该像1985年那样在字节的级别对缓冲区进行处理。
  • 要注意防止恶意数据包的问题 ：
    • 我们需要实现一个方法来判断整数值是否超出预期范围，如果超出了就要中止网络包的读取和解析，因为会有一些不怀好意的人给我们发送恶意网络包希望我们的程序和内存崩溃掉。网络包的读取和解析的中止必须是自动化的，而且不能使用异常处理，因为异常处理太慢了会拖累我们的程序。
    • 如果独立的读取和写入函数是手动编解码的，那么维护它们真的是一个噩梦。我们希望能够为包一次性的编写好序列化代码并且没有任何运行时的性能消耗（主要是额外的分支、虚化等等）。
  • 我们为了不想自己手动检查各种可能会被攻击的地方， 需要实现检查自动化， 在下一篇文章 构建游戏网络协议二之序列化策略 里将会说。
    . . .