Global counter conflict resolution

[joshmh]

Currently, Merrimack is not designed for more than ~100 incoming messages per second. In order to remove this limitation, we need to limit global counter incrementation. Here's an idea:

• Record key is [globalCounter, randomNonce]
• globalCounter is not required to be unique per record
• Each Merrimack client keeps a local counter and a local divisor n
• Initialize n = 1
• If a conflict occurs when incrementing globalCounter (retriable FDBError), the divisor n is doubled
• globalCounter is only increased when counter % n === 0
• Once a second, n is halved (if n === 1 we just keep it there)
• Only records strictly less than globalCounter are consumed. This is because we can't guarantee that a new record with the current globalCounter but a lower randomNonce won't appear later on.
• Backoff period (once a second, above) is configurable, and will depend on traffic bursting patterns. Eventually, this parameter could be adaptive.
• If n is currently high and traffic slows abruptly, it will take a few seconds for n to get back to 1. In this case, it's possible there would be a few seconds when consuming is slow, because the globalCounter is not being incremented fast enough. In fact, consuming could stop altogether if traffic stops completely and globalCounter isn't subsequently incremented. This is probably a pretty weird edge case, though.

[joshmh]

Improved periodic global counter increment logic in a client could work as follows:

Trigger maintainCounter every k milliseconds, where a reasonable value would be 20ms.

function maintainCounter() {
  if (noNewRecordsSinceLastCheck) return;
  if (localCounter % n === 0 && noRecordsWithCurrentGlobalCounter())
    incrementGlobalCounter();
  localCounter++;
}

[joshmh]

The problem with maintainCounter is that it's sensitive to event traffic patterns, which could change abruptly. Instead it should be dependent on number of clients connected, which shouldn't change abruptly. The solution is for maintainCounter to have its own mLocalCounter and backoff regime.

function maintainCounter() {
  if (noNewLocalRecordsSinceLastCheck) return;
  if (mcLocalCounter % mcn === 0 && noRecordsWithCurrentGlobalCounter())
    incrementGlobalCounter();
  if (conflictDetected) mcn <<= 1;
  if (mcLocalCounter % 100 === 0 && mcn > 1) mcn >>= 1;
  mcLocalCounter++;
}

For simplicity, we can dispense entirely with globalCounter incrementing while publishing, and therefore with backoff managing for publishing. Then, consuming latency will depend entirely on maintainCounter.

[joshmh]

See also: http://community.foundationdb.com/questions/3221/message-store-pubsub-signalr-scaleout-layer.html