I don't have any experience with such systems, just a few naive ideas:
- give every machine a local budget, and only talk to the central server when the local budget is exhausted. This shoudl reduce load and thus contention on the central server
- give every machine a local budget, and have it obtain budgets from other peers when its own budget is exhausted. If it can't do that (or can't do it fast enough), don't approve the transaction
- Make something home-grown, simple and very fast on the server side for querying and changing the available budget. You'll only need to support very few operations (query and decrease budgets), so something tailored specifically to that use case might well be faster than a generic solution like redis
- keep statistics about how many of your bids were successful, and use these stastistics to allocate local budgets
