add pipelining for AppendEntries RPCs

[ongardie]

This would help log replication performance. I started to implement this for my dissertation (see #95 / a7ce12d / nasty-thesis-wip tag for code) but never cleaned it up. See the log replication performance chapter in my dissertation for more thoughts.

[nhardt]

After doing a lot of testing on SATA disks under extreme and persistent load, I think I'm going to need to pick up this ticket. i've gathered my thoughts on what I believe to be happening and what I think would be a more optimized way to handle things in my use case. Posting here early in the process just to get early feedback in case I'm missing something. (Feedback welcome!)

In looking at logs and code, it looks like the current implementation does the following:

  per peer thread (Leader)
    while not exiting
      if peer is behind then
        send all new entries
        wait for response
      else
        sleep until heartbeat timeout or new entries

  per peer thread (Follower)
    on append entries
      write new entries to stable storage
      respond

At a high level, what i think needs to happen is:

  Leader
    on new log entry:
      send to followers
    on heartbeat timeout:
      send no op append entries
    on follower response:
      move guaranteed commit index pointer as appropriate
      respond to clients as appropriate

  Follower:
    on append entries:
      update leader election timeout // a crucial part for me
      add new entries to incoming queue

  Follower Write thread:
    while not exiting
      copy items from incoming queue to write queue
      write entire queue to disk (no fsyncs)
      fsync  // hoping that 1 fsync is fine after a series of entries
      send latest commit index to leader

Have read through 10.2.2 and have some thoughts. At a high level, I'm expecting that writes will still be linear, and my hope and assumption with this plan is that several ordered append entry writes with one fsync doesn't break anything fundamental about raft. The extra bookkeeping doesn't seem overwhelming, but I do need to think through failure scenarios wrt exactly how log replication works, which is my next task on this.

Hopefully I'm not horribly off base here, or if I am, that it's correctable! Once again, feedback welcome!

[ongardie]

@nhardt I think what you're describing is related to pipelining, but the issue you're trying to solve is different. I think you're worried about a follower timing out because it's taken too long to write to its own disk. If so, can we solve that by simply moving the setElectionTimeout() call in handleAppendEntries() lower, past the disk write? Meanwhile the follower holds a mutex the entire time, so it won't start an election.

[nhardt]

That's interesting, definitely less work and worth testing. I'll give it a shot.