khepri_tx_adv: Prefer list prepending to build side effect lists

[the-mikedavis]

This is an optimization for functions in the transaction APIs. Specifically this should be very noticeable when any command from the khepri_tx or khepri_tx_adv API (delete, put, etc.) is used with a pattern that affects very many nodes (10,000 or more). The gist is that we can get surprisingly nice speed ups for some functions by building our side effect lists with [Effect | Effects] rather than ++/2.

For background: I have WIP changes to simplify the exchange deletion part of vhost deletion in RabbitMQ by using a transaction (commit). It deletes all exchanges and bindings in a single command without adding/removing runtime parameters and returns the combined rabbit_bindings:deletions() dict. It also changes the way we delete bindings in a transaction to use khepri_tx_adv:delete_many/1 (which returns a map of the deletions) rather than khepri_tx:get_many/1 plus khepri_tx:delete/1 for each binding. Against a stress test of deleting a vhost with 50,000 exchanges with no bindings or queues, I expected the deletion to be almost instant but rabbitmqctl delete_vhost myvhost took around 500s.

A flamegraph points to the BIF behind erlang:'++'/2 (and allocation functions associated with list appending) dominating the time taken to execute a khepri_tx_adv:delete_many/1 call in this block: https://github.com/rabbitmq/khepri/blob/be71afe3eff3cbb6b055372ced587aa63d0f4276/src/khepri_tx_adv.erl#L997-L1006

Flamegraph...

Zoomed in on this function in particular:

perf.data.zip

---

That is most expensive when deleting bindings which is odd since this test vhost only has these 50,000 exchanges - no queues or bindings or anything else.

List ++ [] is not optimized in Erlang/OTP (see https://github.com/erlang/otp/pull/8743): erlang:'++'/2 clones the left-hand-side unless it is [] which spends time and also introduces a lot of garbage. The reason that the reproduction case is slow is that we basically call List ++ [] twice for the non-existent bindings of each exchange we delete which is O(n^2) behavior (n being the number of exchanges) since cloning the list takes O(n) time and memory. List prepending is O(1) but even better we don't need to pay any cost when we don't end up prepending a new element.

Regardless of whether List ++ [] is optimized in Erlang/OTP we should switch to prepending: a large transaction that issues many individual commands will also cause many appends and the right-hand side of that append might be non-empty.

Reproduction steps in RabbitMQ...

With the RabbitMQ repository checked out at branch md/simplify-vhost-exchange-deletion or the linked commit above:

1. Start a single-node broker with make run-broker.
2. Add a blank vhost: sbin/rabbitmqctl add_vhost myvhost.
3. Enable Khepri: sbin/rabbitmqctl enable_feature_flag --experimental khepri_db.
4. Create many exchanges. For example [rabbit_exchange:declare({resource,<<"myvhost">>,exchange,erlang:list_to_binary(lists:flatten(io_lib:format("e~b", [N])))},topic,true,false,false,[],<<"rmq-internal">>) || N <- lists:seq(1,50_000)] in the the shell or an eval command.
5. Delete the vhost: time sbin/rabbitmqctl delete_vhost myvhost --timeout 10000.

When the server is running with this branch the deletion takes around 12s. Before this change the deletion takes around 500s.

---

[codecov[bot]]

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 89.23%. Comparing base (be71afe) to head (b750381). Report is 6 commits behind head on main.

Additional details and impacted files

@@            Coverage Diff             @@
##             main     #291      +/-   ##
==========================================
- Coverage   89.55%   89.23%   -0.33%     
==========================================
  Files          21       21              
  Lines        3130     3380     +250     
==========================================
+ Hits         2803     3016     +213     
- Misses        327      364      +37     

Flag	Coverage Δ
erlang-25	88.49% <100.00%> (-0.20%)	:arrow_down:
erlang-26	89.05% <100.00%> (-0.41%)	:arrow_down:
erlang-27	88.99% <100.00%> (-0.44%)	:arrow_down:
os-ubuntu-latest	89.20% <100.00%> (-0.36%)	:arrow_down:
os-windows-latest	89.05% <100.00%> (-0.38%)	:arrow_down:

Flags with carried forward coverage won't be shown. Click here to find out more.

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[the-mikedavis]

Forgot to clean up and makes sure things were wrapped properly, whoops!

I've also added a test case to assert that we handle the effects in the proper order.