promotions-engine

How it is built

Architecture overview

A promotions engine decides, for a basket of items and a customer, which discounts apply, in what order, and how much each line is reduced; it also issues and redeems coupon codes and enforces limits such as "one per customer" or "first 1,000 redemptions". It sits in the checkout path of retailers, marketplaces, subscription businesses and booking sites, so it is read on every cart change and must answer in milliseconds, while a marketer can add a new rule at any time without a deployment.

The idea that makes it work is to separate three questions that are easy to mix up. Eligibility asks which promotions could apply to this basket; it is a rule-matching problem over changing facts. Selection and stacking asks which of the eligible ones to apply, given exclusivity and priority; it is a small optimisation problem. Redemption asks whether the shared limit still has room and records the use; it is a concurrency problem on a counter that many carts hit at once. Each has a different data shape and failure mode, and the engine stays understandable only if the contract between them is explicit: eligibility returns a set, selection returns an ordered plan with amounts, redemption commits the plan or refuses it.

Parts:

• Rule store and distribution — versioned promotion definitions, published to many readers without locks — RCU, Fast hash functions, CPU caches and the memory hierarchy
• Eligibility matcher — finds the promotions that match a basket and customer — Rete rules engine, Swiss table, Hash join, Arena allocator, Interval tree
• Code service — generates, validates and looks up coupon codes — csprng (no page yet), Cryptographic hashes (SHA-2, BLAKE3), Bloom filter
• Selection and stacking — chooses the best compatible set and its order — Mixed-integer programming, Cutting planes, Presolve reductions, Linear programming (simplex), D-ary heap, Sparse matrices (CSR), LU and Cholesky factorisation
• Pricing arithmetic — exact amounts, allocation of an order-level discount to lines — Money representation, largest-remainder-rounding (no page yet), Floating-point error, interval-arithmetic (no page yet)
• Redemption ledger — enforces limits and records use exactly once — Sharded counters, Optimistic concurrency control, Idempotency keys, Leases, Fencing tokens, Exponential backoff with jitter, False sharing, Memory ordering
• Experiments — tests whether a promotion pays for itself — A/B testing, Hypothesis testing, Sequential probability ratio test, sequential-hypothesis-testing (no page yet), Deterministic bucketing, Experiment layering, CUPED variance reduction, Bayesian rate estimation, PCG and xoshiro generators, bootstrap-confidence-intervals (no page yet), wilson-score-interval (no page yet)

 marketing UI --> rule store (versioned) --publish--> RCU snapshot per node
                                                         |
 cart / checkout --basket, customer, code-->  +----------v-----------+
                                              | eligibility matcher  |  Rete / hash lookups
                                              +----------+-----------+
                                                         | eligible set
                                              +----------v-----------+
                                              | selection + stacking |  priority, exclusivity,
                                              | (greedy or MIP)      |  best-for-customer
                                              +----------+-----------+
                                                         | plan: per-line amounts (integer cents)
                                              +----------v-----------+
 order placed --idempotency key-------------->| redemption ledger    |  limits, per-customer,
                                              | (counters, OCC)      |  global budget
                                              +----------------------+

How the parts fit together

Rule store and distribution

A promotion is data: a condition on the basket and customer, an effect, a validity window, a priority, an exclusivity group, and limits. Marketers change it daily, the checkout path reads it thousands of times a second, so the pattern is read-mostly. RCU gives readers a pointer to an immutable snapshot with no lock and no atomic write; a publisher builds the new rule set, swaps the pointer with release semantics, and frees the old one after a grace period. The cost of this is that a cart in progress may finish on the old version, so the plan records the rule-set version it used, and a redemption refuses a plan older than the one stored for a promotion that was just paused. Lookups by promotion id and code hash use Fast hash functions on a table sized to stay inside the CPU caches and the memory hierarchy (the whole active rule set is small, tens of thousands of rules at most, order of).

Eligibility matcher

Naively, evaluate every promotion against every cart. With a few hundred active rules that is fine; with many thousands and rules like "buys 2 of category A and at least 50 in total, and is a member" it wastes time because most conditions are shared. A Rete rules engine compiles the conditions into a network and caches partial matches, so a cart change re-evaluates only the affected parts. Its internal joins are the Hash join pattern on the smaller side, with Swiss table for the memories and an Arena allocator so the per-cart working set is freed in one step. The graph lists event-condition-action rules as the alternative: for a small, flat rule set that just says "when this event, if this predicate, do that", the simple loop is easier to audit and often faster. Pick Rete when rules are many and share patterns; pick the loop when they are few.

Time windows ("Black Friday, 00:00 to 23:59 in the shop's timezone") sit in an Interval tree keyed by validity range so "which promotions are active now" is a stabbing query instead of a scan. The contract with selection is a set of match records: each carries the promotion id, the lines it matched (with quantities), and its declared effect. Eligibility does not compute amounts.

Code service

Single-use and personal codes must be unguessable, otherwise a bot can enumerate them. Codes come from a csprng (no page yet) with enough entropy and a checksum character to catch typos, and the system stores a hash (Cryptographic hashes (SHA-2, BLAKE3)) rather than the code itself, so a database leak does not reveal live codes. The most common request is an invalid code, either a typo or a guess; a Bloom filter over valid code hashes answers "definitely not a code" without a database read, which also blunts guessing traffic. The graph names cuckoo hashing and xor filters as alternatives; the Bloom filter wins when the set is updated in place and a small false-positive rate (which only costs a database lookup) is acceptable. Rate-limit code attempts per customer and per address, with Exponential backoff with jitter on the client side for retries.

Selection and stacking

Eligible promotions interact. "10 % off the order" and "free shipping over 50" may stack; "20 % off shoes" and "buy one get one half off shoes" are in one exclusivity group and the customer should get the better one. Most shops resolve this with an ordered pass: sort by priority, apply, mark the exclusivity group consumed, continue. That is a greedy algorithm over a heap (D-ary heap) and it is predictable, which merchants like.

Greedy is not optimal. When a coupon can attach to different lines, or the discount base changes with order (percent off after a fixed-amount off is different from before it), the best plan for the customer, or the plan with the lowest cost to the shop under a budget, is a combinatorial choice: binary variables for "apply promotion p to line l", linear constraints for quantities, exclusivity and caps. That is Mixed-integer programming, solved by branch and bound over Linear programming (simplex) relaxations that factor basis matrices with LU and Cholesky factorisation over Sparse matrices (CSR). Cutting planes and Presolve reductions shrink the search; baskets are small, so these models usually solve in a few milliseconds, but the worst case is exponential, so the call has a time limit and falls back to the greedy plan. In practice most systems keep greedy as the default and call the MIP only for cart shapes where the two can differ, or offline to audit how much greedy leaves on the table.

The output contract is a plan: promotion applications with, per line, an amount in integer minor units.

Pricing arithmetic

Amounts are integers in minor units with a stated rounding rule, per Money representation; never binary floats. An order-level discount (5 off the whole basket) has to be allocated to lines for tax and returns, and the line amounts must sum to the total exactly; largest-remainder-rounding (no page yet) distributes the leftover cents. Percentages are applied to the right base (before or after other discounts) and rounded once per line, a decision recorded as a rule, since Floating-point error shows how an intermediate float can flip a cent. Solvers compute in floating point, so the MIP's answer is turned into integers and verified by recomputing in exact arithmetic; interval-arithmetic (no page yet) is the tool when a solver's bound must be certified rather than trusted.

Redemption ledger

A limit such as "first 1,000 redemptions" or "one per customer" is a shared counter touched by many carts at once, and a launch-day promotion makes it a hot key. A single atomic counter on one cache line suffers False sharing and cache-line bouncing between cores; Sharded counters split it into cells and sum them for reading, with the budget divided across cells in advance (each cell holds a slice of the remaining allowance, and slices are rebalanced when one runs dry). The per-customer limit is cheap because it is keyed by customer and rarely contended.

Redemption is committed with Optimistic concurrency control: read the promotion's used count and version, check the limit, write with "if version unchanged"; on conflict re-read and retry with backoff. Each commit carries an Idempotency keys value (the cart or order id), so a client retry after a timeout does not redeem twice. Between "check at cart time" and "commit at payment time" the system may place a reservation, a Leases style hold that expires on its own if the shopper abandons, so abandoned carts do not eat the budget. A pause by the lease holder (a long GC) is the classic hazard, and Fencing tokens on the ledger reject a late commit from an expired holder. In-process counters need correct Memory ordering when they publish "budget exhausted" to other threads.

The contract: the ledger returns committed, refused (limit reached), or duplicate (already committed with this key); checkout turns "refused" into a visible message and removes the discount.

Experiments

A promotion costs margin; whether it pays back is an experiment question. A/B testing assigns customers by Deterministic bucketing, keeps promotion tests in their own Experiment layering layer, and compares incremental margin, not just redemptions (a coupon used by people who would have bought anyway is a cost). CUPED variance reduction and Hypothesis testing give the interval, a Sequential probability ratio test (with sequential-hypothesis-testing (no page yet)) allows early stops when a coupon is losing money fast, and bootstrap-confidence-intervals (no page yet) handle ratio metrics. Redemption rates on small segments use Bayesian rate estimation or the wilson-score-interval (no page yet) so a 2-out-of-2 does not look like 100 %. Randomised choices (which of two offers a visitor sees) use PCG and xoshiro generators seeded from the bucket.

Data and control flow

Pricing one cart (milliseconds, order of).

1. The cart service sends basket lines, customer id and any entered codes to the engine.
2. The engine reads the current rule snapshot (one pointer load) and resolves entered codes: Bloom filter, then hash lookup to the promotion.
3. The matcher computes the eligible set: automatic promotions through the Rete network or hash lookups by category and customer segment, code promotions directly.
4. Selection orders and filters the set; for risky shapes it runs the MIP with a time limit.
5. Pricing computes per-line integer amounts and allocates order-level discounts.
6. The response lists applied promotions with amounts and reasons ("rejected: exclusive with X"), plus the rule-set version; nothing is redeemed yet.

Placing the order.

1. Checkout sends the plan with the order id as the idempotency key.
2. The ledger checks the per-customer limit and takes from the global counter cell; on conflict it retries.
3. If any promotion is refused, the engine re-prices the cart without it and returns the new total for the shopper to confirm; if all succeed, the redemptions are committed with the order in one transaction.
4. If payment later fails, a compensating release returns the counts, again idempotent.

Launching a new promotion.

1. The marketer drafts it; validation checks the rule compiles, the dates make sense and the budget is set.
2. A dry-run replays recent carts and reports how often it fires and the discount volume.
3. The rule set is published as a new snapshot, optionally behind an experiment layer.

Scaling

1. Hot counters. The first real limit is the global redemption counter during a launch. Shard it, pre-allocate slices, and accept that the limit may be exceeded by at most the unspent slices unless the budget is a hard legal cap.
2. Read volume. The cart path is pure reads on a small snapshot; replicate the snapshot to every service node and scale horizontally.
3. Rule count. Grows with marketing activity. Index rules by the cheapest discriminating attribute (code, category, segment) before any rule network runs.
4. MIP time. Cap baskets and models, warm-start from the greedy plan, and cache plans keyed by basket shape.
5. Hotspots in the data store. Campaign-start spikes hit a few keys. Use per-key batching, and run the ledger on its own store so that checkout reads do not compete.
6. Experiments. More concurrent promotion tests need more layers or more traffic; use variance reduction first.

Failure modes

Real implementations

Retailers' promotion engines (the Examples line names Shopify discounts, and the impact estimate lists Talon.One and Voucherify) are proprietary and are not listed. The open-source items implement the rule engine, the commerce-platform promotion model and the solver parts.

Sources

• Drools rule engine documentation (Phreak, Rete lineage): https://docs.drools.org/latest/drools-docs/drools/rule-engine/index.html
• Clara Rules: https://github.com/cerner/clara-rules
• Saleor promotions: https://docs.saleor.io/developer/discounts/promotions
• Medusa Promotion module: https://docs.medusajs.com/resources/commerce-modules/promotion
• Spree promotions: https://spreecommerce.org/docs/developer/core-concepts/promotions
• OR-Tools: https://github.com/google/or-tools
• HiGHS: https://github.com/ERGO-Code/HiGHS