Trimming through Paxos on the services is the way to go, no doubt. However, it's a whole world of pain when it comes to decisions.
Why?
Trimming through Paxos acts as a proposal. We must encode a transaction that will trim the service's state in all the services at the same time once the proposal goes through, much like a "pending changes" proposal.
Why is it a problem?
Not a problem per se, but we do have to decide when to perform the said proposal. Up to this point, we've been trimming during the last stages of the service's Tick, and it wouldn't clash with an on-going proposal, even if we had proposed a value, because it simply didn't have much to do with the proposal mechanism. So far, trimming has always been a process local to the service, despite what was going on in the cluster.
However, making it a proposal does pose a couple of issues regarding to when we manage to issue the trimming proposal.
What kind of issues are we talking about?
In a nutshell, should we propose a trim if there are no on-going proposals, or should we bundle the trim with the "pending changes" proposal.
The simplest approach here would be to propose a trim only when we have no pending changes to propose. This way we could simply issue a proposal with the trim transaction. However, this may make the trim susceptible to starvation if we have lots of changes to propose. This is an unlikely scenario, but we can easily grow to 'god-knows-how-many' versions before trimming if this happens -- although not sure, I believe this could happen with the PGMap, but confirmation is needed.
In any case, even this simple approach would require us to change the PaxosService's proposal-related functions, to allow us to propose from the 'trim_to()' function. So, if we are going to perform those changes, I can only wonder why not take the slightly-harder approach but obtain a fair and reliable trimming scheme.
This last approach would be to bundle the trim proposal in the same transaction as the "pending changes" proposal. However, it would require us to significantly change the PaxosService interface.
What kind of changes?
The most basic ones would simply consist of adding a 'bool should_trim()' function, and check it during the 'propose_pending()' function. We would have to guarantee that service re-implemented this function in case it needed to trim its state, as well as a 'void encode_trim(Transaction& t)' function to encode its trim operations onto the proposal's transaction.
Note:
Nope. No hard part. Just figured it out. Will update if that doesn't pan out (which I doubt). Leaving this here for future reference though. Have a good day.