raft: always keep un-applied logs in memory

[Fullstop000]

In the current version of implementation, if we want to apply committed entries, we will try to retrieve them from raft_log first. At that time, it's very likely that the entries we want are stored in the Storage, which might be insufficient to get them ( especially when the Storage is based on something like rocksDB).

Generally, the issue described above often occurs when the updating speed of committed_index is not as fast as raft log growing so I think it's a common situation we need to improve.

Therefore, we can always keep un-applied logs in memory ( the unstable ) even after we store them into the Storage.

[siddontang]

@Fullstop000

In TiKV, we use a cache outside to avoid fetching logs from Storage. But if we can do it in raft lib directly, maybe it is more common.

Here the think we need to care is the memory usage of this cache, we can't save a lot to avoid OOM.

[Fullstop000]

Avoiding OOM is exactly what I'm considering about. I notice there is a #131 which describes a protection mechanism for the leader to prevent unlimited raft logs growth and it inspires me a little.

An intuitive approach to solve the issue for me is to have some configurations for limitation e.g. max_entry_count_in_memory and max_entry_size_in_memory. But I start to realize that there might be a more attractive feature we can have: a throttle for the leader.

When the follower's in-memory raft logs reach the memory limit, it should send a msg (e.g MsgMemoryLimit) back to the leader to indicate that the applying speed could not be as fast as network transfers. And once the leader receives a MsgMemoryLimit from a follower, the leader should throttle the appending speed to the follower back.

For a detailed design of leader throttle:

1. The MsgMemoryLimit includes the last index of a follower to help the leader throttling it back ( just like the reject_hint).
2. Once the leader receives MsgMemoryLimit, it records the follower in memory who needs to be throttled. Therefore, the leader checks whether it needs to pause the log replication for a follower each Tick and the unit of pausing is the times of Tick ( should be able to be configured e.g throttle_pausing_ticks).
3. After the pausing, the leader starts sending raft logs to the follower.

The leader throttle approach might be somewhat aggressive here. For a succinct solution, we can just use configures. And if in-memory raft logs reach the limit, the unstable should be compacted. @siddontang

/cc @Hoverbear

[BusyJay]

This can be implemented in storage instead of the raft library. It's better to keep the library simple.

[Hoverbear]

@Fullstop000 Maybe you and I could make a new more sophisticated storage module crate for Raft that does this? :)

[Fullstop000]

@Hoverbear if you have any idea to improve this, I'd like to help with it.

[Hoverbear]

@Fullstop000 Do you think we could come up with a simple file based storage for demonstration purposes? Or maybe use something like SLED?

[Fullstop000]

@Hoverbear I prefer that we start this with file-based storage from scratch so that we can later easily add some best practices about how to use the raft lib. For now, the two examples might not be enough for some 'real-world' situations.

[Hoverbear]

That sounds great, @Fullstop000 . :) Do you think you can take care of an initial PR and I will make myself available to help how I can?

[Fullstop000]

@Hoverbear somewhat busy recently 😢. Maybe I could commit an initial PR for some ideas about the Storage on mid-June