Our solution was to design something we call an "adaptive batch". These are more-or-less normal Batchables (extending an abstract class of our own that itself is a Batchable) that have a built-in chaining that uses a System.scheduleBatch call to ensure there is a 1 minute gap between invocations (so as to avoid exhausting async executions in a day).
These adaptive batches are "kicked" via use of a Platform Event (ensuring they all run as the Automated Process user, since we have a trigger-based consumer, which suits our needs) that are published on the event bus when their data condition is detected (e.g. in a trigger or process builder flow etc.). This invocation is also designed to ensure that only a single instance of the adaptive batch implementation can execute at any one time. This is achieved in two parts:
- By using a given job name for the System.scheduleBatch (you cannot schedule more than one batch at a time with a given name) and
- By checking the Async Apex Jobs to see if there is an instance already going.
The latter can be done as a pre-condition before scheduling a new batch, though must also be done in the Batchable's start method in order to avoid race conditions; you are guaranteed that only one batch start method is invoked at any one time on your org (one of the few "synchronization" points on the platform).
If a new platform event is raised (and processed by the trigger-based consumer) we do these tests and if they pass we have the "adaptive batch" ready to roll. Since only one instance can exist there's no worries about the sort of clash you are seeing. If new records would match the criteria after the batch has started, these get processed by us determining (with a COUNT query) that there are records matching the data condition when finish is called. If there are matching records (a non-zero count) here, we schedule the batch again (thereby chaining the batch execution with a slight pause).
The benefits of this approach are:
- Never have a worry about race conditions, with two instances of the batch competing against the same data
- Reduce the number of batch executions, since they are only actually executed when we know there is some data to process (rather than running the batch on a strict schedule)
- For us, ensure the batch runs against a different user than the one that caused the data conditions to be met.
(There are some "delay optimizations" done in our framework too so we don't always have a 1 minute pause before we run the batch, but rather simply ensure that the previous execution was at least 1 minute prior. This allows immediate processing when data infrequently matches the data conditions.)
You can read a little more about some of these points in this answer and this one too.