Decrementing money balance stored on master server from numerous backends? (distributed counter, eh?)

Question

I have some backend servers located in two differend datacenters (in USA and in Europe). These servers are just delivering ads on CPM basis.

Beside that I have big & fat master MySQL server serving advertiser's ad campaign's money balances. Again, all ad campaigns are being delivered on CPM basis.

On every impression served from any of backends I have to decrement ad campaign's money balance according to impression price.

For example, price per one impression is 1 cent. Backend A has delivered 50 impressions and will decrement money balance by 50 cents. Backed B has delivered 30 impressions and it will decrement money balance by 30 cents.

So, main problems as I see are:

• Backends are serving about 2-3K impressions every seconds. So, decrementing money balance on fly in MySQL is not a good idea imho.

• Backends are located in US and EU datacenters. MySQL master server is located in USA. Network latency could be a problem [EU backend] <-> [US master]

As possible solutions I see:

• Using Cassandra as distributed counter storage. I will try to be aware of this solution as long possible.

• Reserving part on money by backend. For example, backend A is connecting to master and trying to reserve $1. As $1 is reserved and stored locally on backend (in local Redis for example) there is no problem to decrement it with light speed. Main problem I see is returning money from backend to master server if backend is being disabled from delivery scheme ("disconnected" from balancer). Anyway, it seems to be very nice solution and will allow to stay in current technology stack.

• Any suggestions?

UPD: One important addition. It is not so important to deliver ads impressions with high precision. We can deliver more impressions than requested, but never less.

Answer 1

this may not be a detailed canonical answer but i'll offer my thoughts as possible [and at least partial] solutions. i'll have to guess a bit here because the question doesn't say much about what measurements have been taken to identify mysql bottlenecks, which imho is the place to start. i say that because imho 1-2k transactions per second is not out of range for mysql. i've easily supported volumes this high [and much higher] with some combination of the following techniques, in no particular order here because it depends on what measurements tell me are the bottlenecks: 0-database redesign; 1-tuning buffers; 2-adding ram; 3-solid state drives; 4-sharding; 5-upgrading to mysql 5.6+ if on 5.5 or lower. so i'd take some measurements and apply the foregoing as called for by the results of the measurements. hope this helps.

Answer 2

This is perhaps the most classical ad-serving/impression-counting problem out there. You're basically trying to balance a few goals:

1. Not under-serving ad inventory, thus not making as much money as you could.
2. Not over-serving ad inventory, thus serving for free since you can't charge the customer for your mistake.
3. Not serving the impressions too quickly, because usually customers want an ad to run through a given calendar time period, and serving them all in an hour between 2-3 AM makes those customers unhappy and doesn't do them any good.

This is tricky because you don't necessarily know how many impressions will be available for a given spot (since it depends on traffic), and it gets even more tricky if you do CPC instead of CPM, since you then introduce another unknowable variable of click-through rate.

There isn't a single "right" pattern for this, but what I have seen to be successful through my years of consulting is:

• Treat the backend database as your authoritative store. Partition it by customer as necessary to support your goals for scalability and fault tolerance (limiting possible outages to a fraction of customers). The database knows that you have an ad insertion order for e.g. 1000 impressions over the course of 7 days. It is periodically updated (minutes to hours) to reflect the remaining inventory and some basic stats to bootstrap the cache in case of cache loss, such as actual

• Don't bother with money balances at the ad server level. Deal with impression counts, rates, and targets only. Settle that to money balances after the fact through logging and offline processing.

• Serve ad inventory from a very lightweight and fast cache (near the web servers) which caches the impression remaining count and target serving velocity of an insertion order, and calculates the actual serving velocity.

• Log all served impressions with relevant data.

• Periodically collect serving velocities and push them back to the database.

• Periodically collect logs and calculate actual served inventory and push it back to the database. (You may need to recalculate from logs due to outages, DoSes, spam, etc.)

Answer 3

Create a service on your big & fat master MySQL server serving advertiser's ad campaign's money balances.

This service must implement a getCampaignFund(idcampaign, requestingServerId, currentLocalAccountBalanceAtTheRequestingServer) that returns a creditLimit to the regional server.

Imagine a credit card mechanism. Your master server will give some limit to your regional servers. Once this limit is decreasing, a threshold trigger this request to get a new limit. But to get the new credit limit the regional server must inform how much it had used from the previous limit.

Your regional servers might implement additionally these services:

1. currentLocalCampaignAccountBalance getCampaignAccountBalance(idcampaign): to inform the current usage of a specific campaign, so the main server might update all campaigns at a specific time.
2. addCampaign(idcampaign, initialBalance): to register a new campaign and it's start credit limit.
3. supendCampaign(idcampaign): to suspend the impressions to a campaign.
4. resumeCampaign(idcampaign): to resume impression to a campaign.
5. currentLocalCampaignAccountBalance finishCampaign(idcampaign): to finish a campaign and return the current local account balance.
6. currentLocalCampaignAccountBalance updateCampaignLimit(idcampaign, newCampaignLimit): to update the limit (realocation of credit between regional servers). This service will update the campaign credit limit and return the account balance of the previous credit limit acquired.

Services are great so you have a loosely coupled architecture. Even if your main server goes offline for some time, your regional servers will keep running until they have not finished their credit limits.

Answer 4

I assume

• Ads are probably bought in batches of at least a couple of thousands
• There are ads from several different batches being delivered at the same time, not all of which be near empty at the same time
• It is OK to serve some extra ads if your infrastructure is down.

So, here's how I would do it.

The BigFat backend has these methods

• getCurrentBatches() that will deliver a list of batches that can be used for a while. Each batch contains a rate with the number of ads that can be served each second. Each batch also contains a serveMax; how many ads might be served before talking to BigFat again.
• deductAndGetNextRateAndMax(batchId, adsServed) that will deduct the number of ads served since last call and return a new rate (that might be the same) and a new serveMax.

The reason to have a rate for each batch is that when one batch is starting to run out of funds it will be served less until it's totally depleted.

If one backend doesn't connect to BigFat for a while it will reach serveMax and only serve ads from other batches.

The backends could have a report period of seconds, minutes or even hours depending on serveMax. A brand new batch with millions of impressions left can run safely for a long while before reporting back.

When BigFat gets a call to deductAndGetNextRateAndMax it deducts the number of served ads and then returns something like 75% of the total remaining impressions up to a configured max. This means that at the end of batch, if it isn't refilled, there will be some ads delivered after the batch is empty but it's better that the batch is actually depleted rather than almost depleted for a long time.

Answer 5

How about instead of decrementing balance, you keep a log of all reported work from each backend, and then calculate balance when you need it by subtracting the sum of all reported work from the campaign's account?

Tables:

campaign (campaign_id, budget, ...)
impressions (campaign_id, backend_id, count, ...)

Report work:

INSERT INTO impressions VALUES ($campaign_id, $backend_id, $served_impressions);

Calculate balance of a campaign only when necessary:

SELECT campaign.budget - impressions.count * $impression_price AS balance
FROM campaign INNER JOIN impressions USING (campaign_id);