Is a tree the correct structure for the payment flow?

[cdecker]

@ZmnSCPxj raised some good points in the MPP fixup discussion. I'd like to address these and maybe discuss this independently of a fixup PR. I'll report the comment here for context:

Perhaps late to bring this up, but: do we need to actually arrange payments in a tree as opposed to a flat array of sub-payments?

The reason I bring this up is because we might want to merge sub-payments. For example, consider the case where the only viable paths for two sub-payments cost too much (i.e. fee budget is violated), but if we merge them (and their fee budgets) we could succeed.

But if the sub-payments we want to merge are cousins instead of siblings in the tree of payments, how do we viably merge them? For example, consider the case below:

        0
       / \
      /   \
     1     2
    / \   / \
   3   4 5   6

Suppose 4 and 6 are currently ongoing (possibly because they reached the destination, so the destination is waiting on the other parts). And 3 and 5 are failing getroute because the viable routes are too expensive (e.g. 4 and 6 have locked up funds on cheaper routes). However, if we merge 3 and 5, it may be feasible (because they would pool their fee budgets together).

As each subpayment needs a unique numeric id, we could use a monotonically-increasing counter and add an explicit field. Merged payments can get any of the ids of the merged payments.

And of course modules have to handle merges as well, if their data structures are not void.

I'm pretty happy with the tree structure since it describes the lineage of a payment attempt, and the reason it was initiated (just follow the links up the tree), though we currently don't make good use of that debuggability (might be an idea for a plugin that walls us through each step and prints nice lineage and routing graphviz graphs).

I do share your concerns that splitting might get us into a dead-end, however I don't think that the tree structure is to blame here, since we can still implement work-stealing across the tree branches, similar to how process and task schedulers work in operating systems. But let's first consider if the dead end is even likely to happen:

• If they happen we can detect these situations in the pay plugin, since the getroute call doesn't specify a fee and just returns a route, independently of whether we then consider it to be too expensive.
• At the size where splitting becomes relevant it is very likely that the fee_proportional dominates the routing costs, and the fee_base becomes negligible. This means that the fee is dependent mostly on the amount that is being transferred and the type of merge you mention doesn't really change that: 2x the amounts ~~~> 2x the fees. The adaptive splitter stops splitting at a size that is imho above the point where fee_base become relevant again, so we should not end up in a situation in which the fees for a route are dominated by fee_base.
• Fee stealing from completed payments looks like a more promising idea: if we have some parts that have been pending for some time we can tap into their fee-budget to pay for the payments we don't have sufficient budget for. Splitting the fee along with the amount really is just a guideline of what we expect to be sufficient.

What do you think? Is there something that I'm missing?

[ZmnSCPxj]

Perhaps the "history" of a payment can be a singly-linked list (actually a DAG to get structure sharing; just allocate all history nodes off the struct command).

So for example we start with a progenitor payment

  "payment started"
       ^
       |
       0

Then we split it:

  payment started
       ^
       |
     split
      ^ ^
      | |
   +--+ +--+
   |       |
   0       1

Now suppose in parallel, sub-payments 0 and 1 each have events happen to them.

  payment started
       ^
       |
     split
      ^ ^
      | |
   +--+ +--+
   |       |
 some0   some1 
   ^       ^
   |       |
   0       1

Now suppose we decide to split sub-payment 1:

  payment started
       ^
       |
     split
      ^ ^
      | |
   +--+ +--+
   |       |
 some0   some1
   ^       ^
   |       |
   |     split1
   |      ^ ^
   |      | |
   |    +-+ +-+
   |    |     |
   0    1     2

And then later, we decide to merge 0 and 2 together:

  payment started
       ^
       |
     split
      ^ ^
      | |
   +--+ +--+
   |       |
 some0   some1
   ^       ^
   |       |
   |     split1
   |      ^ ^
   |      | |
   +-+  +-+ |
     |  |   |
    merge   |
      ^     |
      |     |
      0     1

The actual subpayments are strictly an array of subpayments, but they can store a history with shared history, history-sharing discoverable by known sharing of allocated log nodes. You know, like having all branches of a git repo as a single array, but with each branch having its own history, and often having some shared history, including merge commits, something like that.

Note that when stealing fee budget from existing payments, we need to very careful, as payment modules may individually maintain budgets, most famously shadow_route, but future modules might themselves add new budgets, and stealing budgets may need to handle the budgets maintained by individual modules. So you might want to start looking into event systems, where you broadcast a "payment X steals budget from payment Y" event, and the shadow_route module registers to that event and adjusts the shadow route budgets in proportion to the amount stolen, to retain invariants. All the events you plan should probably be registered on by modules that are affected by them.

With a flat array of payments, as well as modules that touch the data structures of other modules, and events, your system is starting to look more and more like an Entity-Component-System, so you might consider that style as well. Entity == payment, Component == data structure (e.g. those currently registered on a per-module basis), System == code that reacts to events (e.g. including transitions of a payment from one state to another). But maybe some other day.

[ZmnSCPxj]

In addition: your observations may be correct for fee_proportional and fee_base today, but we have no assurances that those parameters, and their relative strengths, will not change tomorrow. So I think it is best if we have some facility to merge payments, so that later, in case of future changes in the forwarding fee market, our code adapts as well. Though of course, testing is a problem. Sigh.

[ZmnSCPxj]

Another thing to consider is that the test in #3913 sometimes fails when the paymod machine has split up the payment into very tiny amounts. While adaptive splitter does not split if there are too many HTLCs in our local channels, it also does not consider the possibility that another node might be paying or receiving near us and also taking up HTLC space in the public network, leading to WIRE_TEMPORARY_CHANNEL_FAILUREs on remote hops that are not due to capacity, but HTLC exhaustion, exacerbated by our splitting up into more parts. This makes the estimated capacity of channels lower than they actually are

By the time some of the HTLCs are cleared, we have not only split our payments into so many tiny amounts below the adaptive splitter limit, we have also advanced the routehints pointer (due to the previous failures), and in test_mpp_interference_2 of #3913 the payee is unpublished so overadvancing the routehints pointer will lead to inevitable failure since routehints are the only way to get to the payee.

Which is why I propose:

• Periodically clear our channel hints except for local channel hints, say every 10 seconds or so.
• Periodically reset our routehints pointer somehow.
• Periodically opportunistically merge the smallest failing splits.

[ZmnSCPxj]

Rather than budget-stealing, maybe just have a single fee budget? Sure, this now serializes payments around that single budget, but getroute is single-threaded anyway and leads to serialization at another part of our code. We might as well have controlled serialization inside libplugin-pay since getroute is single-threaded, which would work better as well with asymmetric splits (we can prioritize shorter/cheaper routes on the larger side of the split) a la Fibonacci sequence.

[ZmnSCPxj]

Now that I have thought about it more.... splitting the budget now elicits a facepalm from me.

Nothing in our interface requires that maxfeepercent/exemptfee budgets be split according to the size of the split. Just because a split is large does not mean it should have larger fee budget. Earlier (and most likely larger) splits tend to have lower fees because they are more likely to take the shorter paths, because there are fewer exclusions present in the channel hints.

On a (deliberately? lol) badly-connected node I have to bump up maxfeepercent to ridiculous values of 5% or 10%, and when I look at the listpays report the actual fee paid is less than 1% (around 0.6%), that seems like a massive mismanagement of our fee budget, since in principle the algorithm should have found the same payment solution with a lower maxfeepercent setting, but failed to do so.