https://gafferongames.com/post/deterministic_lockstep/

本文主要講了3方面

1.使用UDP而不是TCP去實現 input sync

2.接收方實現Delay Buffer去避免接受不及時導致的抖動問題

3.冗余發送去解決 input sync丟包問題

Deterministic lockstep is a method of networking a system from one computer to another by sending only the inputs that control that system, rather than the state of that system. In the context of networking a physics simulation, this means we send across a small amount of input, while avoiding sending state like position, orientation, linear velocity and angular velocity per-object.

The benefit is that bandwidth is proportional to the size of the input, not the number of objects in the simulation. Yes, with deterministic lockstep you can network a physics simulation of one million objects with the same bandwidth as just one.

While this sounds great in theory, in practice it’s difficult to implement deterministic lockstep because most physics simulations are not deterministic. Differences in floating point behavior between compilers, OS’s and even instruction sets make it almost impossible to guarantee determinism for floating point calculations.

確定性鎖步（Deterministic Lockstep） 是一種網絡同步方法，它通過僅發送控制系統的輸入，而不是整個系統的狀態，實現從一臺計算機到另一臺計算機的同步。

在物理模擬的網絡同步中，這意味著我們只需要傳輸少量的輸入數據，而無需發送每個物體的狀態數據（例如位置、方向、線速度和角速度）。

優點：

這樣做的好處是，所需帶寬與輸入數據的大小成正比，而不是與模擬中的物體數量成正比。
換句話說，使用確定性鎖步，即使是100 萬個物體的物理模擬，其網絡帶寬消耗也可以和單個物體相同！

挑戰：

雖然理論上聽起來很棒，但實際實現確定性鎖步卻非常困難，因為大多數物理模擬并不是完全確定性的。
由于不同編譯器、操作系統甚至CPU 指令集在浮點運算上的行為存在差異，幾乎不可能確保浮點計算的完全確定性。

Determinism

Determinism means that given the same initial condition and the same set of inputs your simulation gives exactly the same result. And I do mean exactly the same result.

Not close. Not near enough. Exactly the same. Exact down to the bit-level. So exact, you could take a checksum of your entire physics state at the end of each frame and it would be identical.

確定性（Determinism） 指的是，在相同的初始條件和相同的輸入下，模擬的結果必須完全一致。

我指的是真正的完全一致。

不是接近，不是“差不多”，而是 精確到每一位（bit-level） 的相同。

精確到什么程度？
你可以在每一幀結束時，對整個物理狀態進行校驗和（checksum），結果都必須完全一致。

https://gafferongames.com/videos/deterministic_lockstep_desync.mp4

Above you can see a simulation that is almost deterministic. The simulation on the left is controlled by the player. The simulation on the right has exactly the same inputs applied with a two second delay starting from the same initial condition. Both simulations step forward with the same delta time (a necessary precondition to ensure exactly the same result) and both simulations apply the same inputs. Notice how after the smallest divergence the simulation gets further and further out of sync. This simulation is non-deterministic.

上方的示例展示了一個幾乎確定性的模擬。

• 左側的模擬由玩家控制。

• 右側的模擬使用完全相同的輸入，但延遲 2 秒，并從相同的初始狀態開始。

兩次模擬都以相同的時間步長（delta time） 前進（這是確保結果完全一致的必要前提），并且兩者都應用了相同的輸入。

然而，請注意：即使是最微小的偏差，也會導致模擬逐漸失去同步。

這說明，這個模擬并不是確定性的（non-deterministic）。

What’s going on is that the physics engine I’m using (Open Dynamics Engine) uses a random number generator inside its solver to randomize the order of constraint processing to improve stability. It’s open source. Take a look and see! Unfortunately this breaks determinism because the simulation on the left processes constraints in a different order to the simulation on the right, leading to slightly different results. Luckily all that is required to make ODE deterministic on the same machine, with the same complied binary and on the same OS (is that enough qualifications?) is to set its internal random seed to the current frame number before running the simulation via dSetRandomSeed. Once this is done ODE gives exactly the same result and the left and right simulations stay in sync.

問題出在物理引擎（Open Dynamics Engine，簡稱 ODE）。

ODE 的求解器在處理約束時，會使用隨機數生成器來隨機化約束處理的順序，以提高穩定性。
（它是開源的，你可以自行查看！）

然而，這破壞了確定性，因為左側和右側的模擬以不同的順序處理約束，最終導致結果出現細微差異。

解決方案：
幸運的是，要讓 ODE 在同一臺機器、相同的編譯二進制文件和相同的操作系統（這夠多限定條件了吧？??）下保持確定性，我們只需要在運行模擬前，使用 dSetRandomSeed 將 ODE 的內部隨機種子設置為當前幀編號。

一旦完成這個步驟，ODE 就會給出完全相同的結果，使得左側和右側的模擬保持同步。

And now a word of warning. Even though the simulation above is deterministic on the same machine, that does not necessarily mean it would also be deterministic across different compilers, a different OS or different machine architectures (eg. PowerPC vs. Intel). In fact, it’s probably not even deterministic between debug and release builds due to floating point optimizations.

Floating point determinism is a complicated subject and there’s no silver bullet.

For more information please refer to this article.

現在要提醒你一點注意事項。

即使上面的模擬在同一臺機器上是確定性的，但這并不意味著它在不同的編譯器、不同的操作系統，甚至不同的 CPU 架構（例如 PowerPC vs. Intel）上也能保持確定性。

事實上，由于浮點數優化的原因，甚至在Debug 版和 Release 版之間，模擬結果很可能也不是確定性的。

浮點數的確定性是一個復雜的問題，并不存在萬能的解決方案。

想了解更多信息，請參考這篇文章。

Networking Inputs

Now let’s get down to implementation.

Our example physics simulation is driven by keyboard input: arrow keys apply forces to make the player cube move, holding space lifts the cube up and blows other cubes around, and holding ‘z’ enables katamari mode.

How can we network these inputs? Must we send the entire state of the keyboard? No. It’s not necessary to send the entire keyboard state, only the state of the keys that affect the simulation. What about key press and release events then? No. This is also not a good strategy. We need to ensure that exactly the same input is applied on the right side, at exactly the same time, so we can’t just send ‘key pressed’, and ‘key released’ events over TCP.

What we do instead is represent the input with a struct and at the beginning of each simulation frame on the left side, sample this struct from the keyboard:

   struct Input
    {
        bool left;
        bool right;
        bool up;
        bool down;
        bool space;
        bool z;
    };

接下來，我們需要將左側模擬的輸入發送到右側模擬，同時確保右側模擬知道這些輸入屬于第 n 幀。

關鍵點：

右側模擬只有在收到第 n 幀的輸入后，才能模擬第 n 幀。
如果它沒有收到該幀的輸入，它就必須等待。

舉個例子，如果使用 TCP 進行數據傳輸，你可以簡單地只發送輸入數據，然后在另一端讀取收到的數據包，每個接收到的輸入對應一幀模擬的前進。
但如果某一幀的輸入數據沒有到達，右側模擬就無法繼續前進，而是必須等待下一次輸入的到來。

基于 TCP 傳輸輸入：

假設我們使用 TCP 進行傳輸，并且：

• 禁用了 Nagle 算法（防止小數據包延遲）。

• 每幀發送一次輸入（60 次/秒）。

這里會出現一個問題：網絡傳輸的輸入數據并不會總是均勻分布，每 1/60 秒精準到達，這會導致模擬變得非常抖動（jittery）。
因此，我們不能僅僅按照數據到達的順序立即運行模擬，否則效果會很糟糕。

如果你想要穩定的輸入間隔，你必須自己實現這種行為。

Playout Delay Buffer

Such a device is called a playout delay buffer.

Unfortunately, the subject of playout delay buffers is a patent minefield. I would not advise searching for “playout delay buffer” or “adaptive playout delay” while at work. But in short, what you want to do is buffer packets for a short amount of time so they appear to be arriving at a steady rate even though in reality they arrive somewhat jittered.

What you’re doing here is similar to what Netflix does when you stream a video. You pause a little bit initially so you have a buffer in case some packets arrive late and then once the delay has elapsed video frames are presented spaced the correct time apart. If your buffer isn’t large enough then the video playback will be hitchy. With deterministic lockstep your simulation behaves exactly the same way: showing hitches when the buffer isn’t large enough to smooth out the jitter. Of course, the cost of increasing the buffer size is additional latency, so you can’t just buffer your way out of all problems. At some point the user says enough! That’s too much latency added. No sir, I will not play your game with 1 second of extra delay :)

播放延遲緩沖區（Playout Delay Buffer）

這樣的方式被稱為播放延遲緩沖區（Playout Delay Buffer）。

它的作用是什么？

簡而言之，你需要對數據包進行短暫緩沖，以便讓它們看起來是穩定到達的，盡管它們實際上可能存在抖動（Jitter）。

這種技術類似于 Netflix 在播放視頻時的緩沖機制：

1. 開始播放前先進行一點點緩沖，確保有足夠的數據可用，以防某些數據包延遲到達。

2. 等到緩沖時間過去后，視頻幀會以正確的時間間隔呈現，保證播放流暢。

3. 如果緩沖區不夠大，視頻就會卡頓（Hitchy）。

在確定性鎖步中的作用

在**確定性鎖步（Deterministic Lockstep）**中，模擬的行為與視頻播放類似：

• 如果緩沖區不足，模擬就會出現卡頓，因為它無法填補網絡數據傳輸的抖動。

• 增大緩沖區可以平滑模擬，但代價是增加額外的延遲（Latency）。

然而，你不能無限制地增加緩沖區大小來解決問題。
因為玩家最終會忍受不了過大的延遲！
“1 秒額外延遲？不行！我拒絕玩你的游戲！”

My playout delay buffer implementation is really simple. You add inputs to it indexed by frame, and when the very first input is received, it stores the current local time on the receiver machine and from that point on delivers packets assuming they should play at that time + 100ms. You’ll likely need to something more complex for a real world situation, perhaps something that handles clock drift, and detecting when the simulation should slightly speed up or slow down to maintain a nice amount of buffering safety (being “adaptive”) while minimizing overall latency, but this is reasonably complicated and probably worth an article in itself

我的播放延遲緩沖區實現

我的播放延遲緩沖區實現非常簡單：

• 輸入數據按幀索引存入緩沖區。

• 當接收到第一個輸入時，記錄當前接收端機器的本地時間。

• 之后，每個輸入都假定應在 （記錄的時間 + 100ms） 時刻播放。

更復雜的實際應用

在實際應用中，你可能需要一個更復雜的方案，例如：

1. 處理時鐘漂移（Clock Drift），確保不同設備之間的時鐘同步。

2. 檢測何時需要調整模擬的速度，讓它稍微加快或減慢，以維持合理的緩沖區安全值。

3. 做到“自適應”（Adaptive），在盡量減少整體延遲的同時，保持平穩的模擬體驗。

不過，這些優化相當復雜，可能值得單獨寫一篇文章來深入探討！

The goal is that under average conditions the playout delay buffer provides a steady stream of inputs for frame n, n+1, n+2 and so on, nicely spaced 1/60th of a second apart with no drama.

In the worst case the time arrives for frame n and the input hasn’t arrived yet it returns null and the simulation is forced to wait.

If packets get bunched up and delivered late, it’s possibly to have multiple inputs ready to dequeue per-frame.

In this case I limit to 4 simulated frames per-render frame so the simulation has a chance to catch up, but doesn’t simulate for so long that it falls further behind, aka. the “spiral of death”.

目標是，在平均條件下，播放延遲緩沖區能夠提供一個穩定的輸入流，按照1/60秒的間隔依次提供第n幀、第n+1幀、第n+2幀，并且無卡頓。

在最壞情況下，當第n幀的時間到達時，如果輸入還沒有到達，則返回null，并且模擬會被迫等待。

如果數據包出現堆積并且延遲到達，可能會有多個輸入可以在每一幀進行出隊處理。
在這種情況下，我會限制每渲染幀最多模擬4幀，這樣可以讓模擬有機會趕上進度，但不會模擬太長時間，以至于進一步落后，避免出現所謂的**“死亡螺旋”（Spiral of Death）**。

Is TCP good enough?

Using this playout buffer strategy and sending inputs across TCP we ensure that all inputs arrive reliably and in-order. This is convenient, and after all, TCP is designed for exactly this situation: reliable-ordered data.

In fact, It’s a common thing out there on the Internet for pundits to say stuff like:

• If you need reliable-ordered, you can’t do better than TCP!

• Your game doesn’t need UDP (yet)

But I’m here to tell you this kind of thinking is dead wrong.

https://gafferongames.com/videos/deterministic_lockstep_tcp_100ms_1pc.mp4

Above you can see the simulation networked using deterministic lockstep over TCP at 100ms latency and 1% packet loss. If you look closely on the right side you can see hitches every few seconds. What’s happening here is that each time a packet is lost, TCP has to wait RTT*2 while it is resent (actually it can be much worse, but I’m being generous…). The hitches happen because with deterministic lockstep the right simulation can’t simulate frame n without input n, so it has to pause to wait for input n to be resent!

That’s not all. It gets significantly worse as latency and packet loss increase. Here is the same simulation networked using deterministic lockstep over TCP at 250ms latency and 5% packet loss:

https://gafferongames.com/videos/deterministic_lockstep_tcp_250ms_5pc.mp4

Now I will concede that if you have no packet loss and/or a very small amount of latency then you very well may get acceptable results with TCP. But please be aware that if you use TCP it behaves terribly under bad network conditions.

Can we do better than TCP?

Can we beat TCP at its own game. Reliable-ordered delivery?

The answer is an emphatic YES. But only if we change the rules of the game.

Here’s the trick. We need to ensure that all inputs arrive reliably and in order. But if we send inputs in UDP packets, some of those packets will be lost. What if, instead of detecting packet loss after the fact and resending lost packets, we redundantly include all inputs in each UDP packet until we know for sure the other side has received them?

這里有一個訣竅。我們需要確保所有輸入都可靠且按順序到達。但是，如果我們通過 UDP 發送輸入，一些數據包可能會丟失。

那么，如果我們不等到檢測到丟包后再重傳，而是在每個 UDP 數據包中冗余地包含所有輸入，直到確認對方已經接收到它們，會怎么樣呢？

Inputs are very small (6 bits). Let’s say we’re sending 60 inputs per-second (60fps simulation) and round trip time we know is going the be somewhere in 30-250ms range. Let’s say just for fun that it could be up to 2 seconds worst case and at this point we’ll time out the connection (screw that guy). This means that on average we only need to include between 2-15 frames of input and worst case we’ll need 120 inputs. Worst case is 120*6 = 720 bits. That’s only 90 bytes of input! That’s totally reasonable.

輸入數據非常小（僅 6 比特）。假設我們每秒發送 60 個輸入（對應 60fps 的模擬），而已知的往返時間（RTT） 介于 30-250ms 之間。

再假設，為了好玩，我們把最壞情況設為 2 秒，超過這個時間就直接超時斷開連接（反正那家伙也玩不了）。這意味著，平均情況下，我們只需要在每個數據包中包含 2-15 幀 的輸入，而最壞情況下，需要存儲 120 幀的輸入。

最壞情況下：
120 幀 × 6 比特 = 720 比特，也就是 90 字節 的輸入數據！

這完全可以接受。

We can do even better. It’s not common for inputs to change every frame. What if when we send our packet instead we start with the sequence number of the most recent input, and the 6 bits of the first (oldest) input, and the number of un-acked inputs. Then as we iterate across these inputs to write them to the packet we can write a single bit (1) if the next input is different to the previous, and (0) if the input is the same. So if the input is different from the previous frame we write 7 bits (rare). If the input is identical we write just one (common). Where inputs change infrequently this is a big win and in the worst case this really isn’t that bad. 120 bits of extra data sent. Just 15 bytes overhead worst case.

我們還能做得更好！輸入并不會每一幀都發生變化。

如果我們在發送數據包時，先包含最新輸入的序列號、最早（最舊）的 6 位輸入，以及未被確認的輸入數量，然后在遍歷這些輸入并寫入數據包時，添加一個單比特標記：

• 如果下一個輸入與前一個不同，則寫入 1 并存儲 6 位新輸入（共 7 位，但這很少發生）。

• 如果下一個輸入與前一個相同，則只寫入 0（只需 1 位，而這通常是主要情況）。

這樣，當輸入變化不頻繁時，我們可以大幅減少數據量。即使在最壞情況下，額外發送的數據也只有 120 位（15 字節），這點開銷完全可以接受。

Of course another packet is required from the right simulation to the left so the left side knows which inputs have been received. Each frame the right simulation reads input packets from the network before adding them to the playout delay buffer and keeps track of the most recent input it has received and sends this back to the left as an “ack” or acknowledgment for inputs.

When the left side receives this ack it discards any inputs older than the most recent received input. This way we have only a small number of inputs in flight proportional to the round trip time between the two simulations.

當然，右側模擬還需要發送一個數據包回到左側，以便左側知道哪些輸入已經被接收。

每一幀，右側模擬會從網絡中讀取輸入數據包，在將其添加到播放延遲緩沖區之前，跟蹤它接收到的最新輸入，并將這個信息作為**“ack”（確認）** 發送回左側。

當左側收到這個 ack 時，它會丟棄比最新接收輸入更早的所有輸入。

這樣，我們在網絡中傳輸的輸入數量始終保持在一個與往返時間（RTT）成比例的較小范圍，避免了不必要的冗余數據。

Flawless Victory

We have beaten TCP by changing the rules of the game.

Instead of “implementing 95% of TCP on top of UDP” we have implemented something totally different and better suited to our requirements. A protocol that redundantly sends inputs because we know they are small, so we never have to wait for retransmission.

So exactly how much better is this approach than sending inputs over TCP?

Let’s take a look…

完美勝利！
我們通過改變游戲規則，徹底擊敗了 TCP。

我們并沒有在 UDP 之上實現 95% 的 TCP，而是創造了一種完全不同、更加符合我們需求的協議。

這個協議通過冗余發送輸入（因為我們知道它們很小），使得我們永遠不需要等待重傳。

那么，這種方法相比通過 TCP 發送輸入，究竟能好多少呢？

讓我們來看看吧……

https://gafferongames.com/videos/deterministic_lockstep_udp_2sec_25pc.mp4

The video above shows deterministic lockstep synchronized over UDP using this technique with 2 seconds of latency and 25% packet loss. Imagine how awful TCP would look under these conditions. So in conclusion, even where TCP should have the most advantage, in the only networking model that relies on reliable-ordered data, we can still easily whip its ass with a simple protocol built on top of UDP.

上面的視頻展示了使用這種技術在2秒延遲和25%丟包率的情況下，通過 UDP 實現的確定性鎖步同步。想象一下，在這種情況下，如果使用 TCP 會變得多么糟糕。

總之，即使在 TCP 應該具有最大優勢的地方——即在唯一依賴于可靠有序數據的網絡模型中，我們仍然能夠輕松擊敗它，使用一個簡單的基于 UDP 的協議。