Bidding Credit Systems
Written by , February 28, 2016 The project I work on at AdRoll is mature. In a mature project the economics of software flip around to where doing something right is more desirable that doing something quickly. In 2015 we invested a lot of effort in resolving long-tail issues with the bidder system, issues we’d recognized in our failure-mode conversations but had left unresolved pending future work. Sometimes, a system will evolve away from such things and sometimes you’ll have to put in the time and energy to, not repair, but mitigate. Long-tail issues are often intrinsic, those fun little sideshows Charles Perrow called Normal Accidents, failures inherent to a system that can’t be removed but must be lived with. It’s good times.
This blog post details one of my favorite resolutions in 2015, the bidding credit system.
A brief run-down of the bidders. A bid comes in from an “exchange”–these are companies like Google, AppNexus or OpenX–and we’re obligated to reply. Replies can be either a “no bid”, essentially a bid of $0, or a “bid”, a bid of greater than $0. If we win the auction the exchange sends us a specially coded additional request, called a “win”. When this arrives, we reduce the amount of money the system as a whole has to spend. If a “win” doesn’t arrive, we assume that there’s still money to spend and the system does its best to do so.
Here’s a fun question: what happens if an actual win gets decoupled from “win” events? By protocol contract with the exchanges they’re not supposed to be but, you know, things go wrong. What happens?
The bidder used to simply assume, without a “win” that it had money to spend and would continue to do so. This meant that it would continue to spend money, money it may, were the “wins” arriving appropriately, have not spent. Worse, the bidders might erroneously spend more money that in its budget, a worst-case scenario we call “overspend”. Overspends are potentially catastrophic as there’s no fixed upper bound.
Win decoupling took us by surprise in early 2015. Alarms fired alerting us that the system’s rate of win had dropped below normal bounds but a side-channel in a more delayed notification informed us that the system was still spending money. Oops! Manual intervention killed all bidding and communication with the exchange in question informed us that a bug in their latest release caused a failure of win notifications. This was… not cheap.
In the lifetime of the system this decoupling had only been seen just the once but it was bad enough to need a safety system to stop it from happening again. My colleague Mike and I kicked around ideas and settled on a take off a classic feedback control system.
The algorithm is this:
Grant a “bidding credit pool” of some initial capacity C, maximally bounded at Cm, some bid rate Br (per second) and some win rate Wr (per second):
- Each bid issued by the system to an exchange decrements C by B.
- Each win received by the system from an exchange increases C by W.
- If at bid time C =< L a no-bid is automatically issued.
- Every X seconds Bmp credits are added to the pool.
The first two points decide for the system how much a losing bid costs. Combine that with the third point, it’s possible to set values such that a losing streak will cause the pool to exhaust, shutting off bidding. The fourth point protects against losing streaks and allows for automatic recovery in the event of pool exhaustion.
It seemed to Mike and me that the algorithm would work. Say you have Cm = 100, C = 100, Br = 100, Wr = 0.1, B = 1, W = 1, L = 0, X = 5 and Bmp = 100. Then you’ll find that per second Br*Wr = 10 and so every second you’ll remove 90 credits from C, or, C(t1) = C(t0) - Br(1-Wr).
C(0) = 100
C(1) = 100 - 100(1-0.1) = 90
C(2) = 90 - 100(1-0.1) = 0
C(3) = 0
C(4) = 0
C(5) = 0 + 100 - 100(1-0.1) = 90 = C(0).
It’s a loop. In reality there’d be some variation as Br won’t always be a constant but notice that for 3/5 of the time the system is in a state where it can’t bid. That’s not good: the whole purpose of the system is to make bids.
Charles Perrow’s analysis in Normal Accidents argued that by attempting to resolve failure in one subsystem with the addition of another you introduce new failures elsewhere. Well, check it out, the bidding credit system can be configured to cause a worse problem than the one we’re attempting to fix.
Clearly, the trick here is finding the right parameters for the system. By team consensus we wanted something that would be slow to shut off bidding, something with a gradual wind-down, and quick to start bidding again, something with “get up and go”. This bidding credit system is dangerous enough that it can’t be released into the world behind a feature gate and fiddled with but we also must have operational experience with it.
What to do?
We modeled it! What we had on our hands was a simple-to-understand system and a search space for ideal configuration parameters. A small bit of python:
import argparse
import math
import random
import sys
ONE_DAY_MS = 86400
def tri(mode):
return random.triangular(max(0.0, mode-0.3),
mode,
max(1.0, mode+0.3))
def log(n):
if not n:
return 0
else:
return math.log(n)
class World:
def __init__(self,
seed,
initial_credits=1000,
win_kill_point=43200,
win_recover_point=53200,
credit_cap=1000,
time_step=10,
time_end_lower_limit=86400,
bid_request_rate_per_second=100,
win_rate=0.10,
bid_rate=0.10,
decriment_per_bid=1,
incriment_per_win=10,
periodic_credit_bump=100,
periodic_credit_bump_amount=10
):
self.time_step = time_step
self.time_end_lower_limit = time_end_lower_limit
self.bid_request_rate_per_second = bid_request_rate_per_second
self.win_rate = win_rate
self.bid_rate = bid_rate
self.decriment_per_bid = decriment_per_bid
self.incriment_per_win = incriment_per_win
self.periodic_credit_bump = periodic_credit_bump
self.periodic_credit_bump_amount = periodic_credit_bump_amount
self.credit_cap = credit_cap
self.win_kill_point = win_kill_point
self.win_recover_point = win_recover_point
self.current_time = 0
self.outbound_bids = 0
self.credits = initial_credits
self.total_bids = 0
self.total_wins = 0
random.seed(seed)
return None
def step(self):
if self.current_time >= self.time_end_lower_limit:
return None
instantaneous_max_bids = int(self.bid_request_rate_per_second * self.time_step)
time_of_day_adjustment = (math.sin(self.current_time * (1.0/(ONE_DAY_MS/8)))+1)/2.0
instantaneous_bids = int(instantaneous_max_bids * time_of_day_adjustment)
# Determine how many bids we can make given our credit pool and the
# bids coming into the system. Can't bid more than we get traffic!
free_bids = math.ceil(self.credits / (self.decriment_per_bid*1.0))
bids_submitted = math.ceil(min(instantaneous_bids, free_bids) * tri(self.bid_rate))
# Based on the outbound bids, determine how many of those signal back as
# wins. (We fake the delay to be one tick. Not realistic but I don't
# think it matters.)
#
# If we're past the kill point, we have no wins coming into the system.
if self.win_kill_point <= self.current_time <= self.win_recover_point:
dead_air = True
instantaneous_wins = 0
else:
dead_air = False
instantaneous_wins = math.ceil(self.outbound_bids * tri(self.win_rate))
# Queue up our current bids to be outbound for the next tick.
self.outbound_bids = bids_submitted
self.total_wins += instantaneous_wins
self.total_bids += bids_submitted
# Credit adjustments
#
# Remove credits per bid. I don't _think_ order of this matters in the
# context of simulation, whether we incriment or decriment first.
self.credits -= bids_submitted * self.decriment_per_bid
# Account for wins. We done good and deserve some credit.
self.credits += instantaneous_wins * self.incriment_per_win
# Every fixed period we get an automatic credit bump.
if (self.current_time % self.periodic_credit_bump) == 0:
self.credits += self.periodic_credit_bump_amount
if self.credits > self.credit_cap:
self.credits = self.credit_cap
assert self.credits <= self.credit_cap
self.current_time += self.time_step
return [self.current_time, self.credits, free_bids, bids_submitted, self.outbound_bids, instantaneous_wins, instantaneous_bids, time_of_day_adjustment, self.total_bids, self.total_wins, dead_air]
if __name__ == '__main__':
parser = argparse.ArgumentParser(description='Simulate the "bidding credits" constrol system')
parser.add_argument('--time_step', type=int, default=10,
help='integer, unit in seconds: time simulation steps forward per tick')
parser.add_argument('--time_end_lower_limit', type=int, default=86400,
help='integer, unit in seconds: time simulation will not cease before; default 1 day')
parser.add_argument('--win_kill_point', type=int, default=(86400/2),
help='integer, unit in seconds: point in time when all win notifications will fail; default 1/2 day')
parser.add_argument('--win_recover_point', type=int, default=(86400/2)+10,
help='integer, unit in seconds: point in time when all win notifications will recover; default 1/2 + 10000 day')
parser.add_argument('--seed', dest='seed',
default="""I went to the woods because I wished to live deliberately, to front only the
essential facts of life, and see if I could
not learn what it had to teach, and not, when
I came to die, discover that I had not lived.
I did not wish to live what was not life,
living is so dear; nor did I wish to practice
resignation, unless it was quite
necessary.""",
help='hashable: seed for the simulation random number')
parser.add_argument('--initial_credits', type=int, default=1000,
help='integer: total number of credits available to the system on startup'),
parser.add_argument('--credit_cap', type=int, default=1000,
help='integer: maximum number of credits the system can accumulate'),
parser.add_argument('--bid_request_rate_per_second', type=int, default=100,
help='integer, units in bid/sec: total number of requests per second in the simulation')
parser.add_argument('--win_rate', type=float, default=0.10,
help='float, [0,1.0]: The percentage of time a bid wins.')
parser.add_argument('--bid_rate', type=float, default=0.10,
help='float, [0,1.0]: The percentage of time we make a bid.')
parser.add_argument('--decriment_per_bid', type=int, default=1,
help='integer: total credits a single bid consumes')
parser.add_argument('--incriment_per_win', type=int, default=10,
help='integer: total credits a single win provides')
parser.add_argument('--periodic_credit_bump', type=int, default=100,
help='integer, units in seconds: periodicity of automatic credit replenishment')
parser.add_argument('--periodic_credit_bump_amount', type=int, default=10,
help='integer: amount of credits per replenishment cycle')
args = parser.parse_args()
w = World(args.seed,
initial_credits=args.initial_credits,
win_kill_point=args.win_kill_point,
win_recover_point=args.win_recover_point,
credit_cap=args.credit_cap,
time_step=args.time_step,
time_end_lower_limit=args.time_end_lower_limit,
bid_request_rate_per_second=args.bid_request_rate_per_second,
win_rate=args.win_rate,
bid_rate=args.bid_rate,
decriment_per_bid=args.decriment_per_bid,
incriment_per_win=args.incriment_per_win,
periodic_credit_bump=args.periodic_credit_bump,
periodic_credit_bump_amount=args.periodic_credit_bump_amount
)
sep = '\t'
print sep.join(['# ', 'current_time', 'credits', 'free_bids', 'bids_submitted', 'outbound_bids', 'instantaneous_wins', 'instantaneous_bids', 'time_of_day_adjustment', 'total_bids', 'total_wins', 'dead_air'])
step = w.step()
while step:
print sep.join([str(x) for x in step])
step = w.step()and an even smaller bit of gnuplot:
#!/usr/bin/env gnuplot
#
# Plotting data about the credit model (see credit_model.dat)
reset
# png
set terminal png size 2560,1440 enhanced font 'Verdana,10'
set output 'credit_model.png'
set xlabel 'Time (seconds)'
set tics scale 0.75
plot 'credit_model.dat' using 1:2 smooth acsplines with lines title 'Credits Available', \
'credit_model.dat' using 1:4 smooth acsplines with lines title 'Bids Submitted', \
'credit_model.dat' using 1:5 smooth acsplines with lines title 'Outbound Bids', \
'credit_model.dat' using 1:6 smooth acsplines with lines title 'Instantaneous Wins'
let the team understand how the system would behave in a no-risk manner. You’ll notice that the python code is simulating more than the brief sketch above: waning traffic through the day, random fluctuation around rates. Here’s a similar periodic crash scenario graphed:
blt> python credit_model.py --time_end_lower_limit=1800
--bid_request_rate_per_second=1000 --initial_credits=1000 --time_step=1
--credit_cap=1000 --periodic_credit_bump=60
--periodic_credit_bump_amount=1000 --decriment_per_bid=1
--incriment_per_win=1 --bid_rate=1.0 --win_rate=0.1 > credit_model.dat &&
./credit_model.gnu
Crummy, right?
Here’s another scenario with W = 10, effectively canceling out all the losing bids to get to a win.
blt> python credit_model.py --time_end_lower_limit=1800
--bid_request_rate_per_second=1000 --initial_credits=1000 --time_step=1
--credit_cap=1000 --periodic_credit_bump=60
--periodic_credit_bump_amount=1000 --decriment_per_bid=1
--incriment_per_win=10 --bid_rate=1.0 --win_rate=0.1 > credit_model.dat &&
./credit_model.gnu
Configured well, the system is stable in normal operation. Good! What about if there’s a win decoupling event? The careful reader will have noticed that the python script has the ability to simulate a decoupling. Here’s the stable system with a decouple thrown in:
blt> python credit_model.py --time_end_lower_limit=1800
--bid_request_rate_per_second=1000 --initial_credits=1000 --time_step=1
--credit_cap=1000 --periodic_credit_bump=60 --periodic_credit_bump_amount=1000
--decriment_per_bid=1 --incriment_per_win=10 --bid_rate=1.0 --win_rate=0.1
--win_kill_point=900 --win_recover_point=1200 > credit_model.dat &&
./credit_model.gnu
You’ll note it’s got the properties we desire, a clamping of bidding and a rapid jump back to full capacity once wins start entering the system again. At no point do bids ever permanently drop to zero–the periodic credit bump keeps us issuing a moderate number bid submissions–but the fall-off is drastic enough to put the loss in the realm of pennies.
And it turns out, it works well in practice, too:
