Lesson 12.4• 9 min read

Categories, budgets and monthly spending

The primer’s seller map and crowd overrides, income-based budget templates, monthly spending by SQL or MapReduce, and caching reads.

What you will learn

  • Categorize transactions with a seller map and crowd-sourced overrides.
  • Recommend budgets from an income template and store only the overrides.
  • Compute monthly spending, and serve reads from a cache, replicas and a warehouse.

Categorizing transactions (the primer's Category Service)

Seed a seller-to-category map with the most popular sellers. The primer estimates 50,000 sellers at under 255 bytes each, so "the dictionary would only take about 12 MB of memory". That easily fits in memory on every server.

seller_category_map['Exxon'] = DefaultCategories.GAS
seller_category_map['Target'] = DefaultCategories.SHOPPING

For sellers not in the map, use the crowd. Users can override a transaction's category, and each override is a vote for that seller. The primer keeps a heap per seller, so the most common override can be read in O(1)O(1)what its symbols mean time, the same however many votes there are, and then caches it in the map:

def categorize(self, transaction):
    if transaction.seller in self.seller_category_map:
        return self.seller_category_map[transaction.seller]
    elif transaction.seller in self.seller_category_crowd_overrides_map:
        self.seller_category_map[transaction.seller] = \
            self.seller_category_crowd_overrides_map[transaction.seller].peek_min()
        return self.seller_category_map[transaction.seller]
    return None

The seed map wins whenever it has an answer. The primer's use cases also rule out automatic re-categorization: a user's override changes their own transaction, and does not rewrite history.


Recommending a budget (the primer's Budget Service)

Start from a template based on income, for example housing 40%, food 20%, gas 10% and shopping 20%. Then you only store the categories a user overrides, in a budget_overrides table, not all 100 million budget items.

The Budget Service notifies a user when they approach or exceed a category's budget. The primer says these notifications "don't need to be instant". What counts as "approaching" is a product choice, such as 80%.


Computing monthly spending

The primer offers two ways to compute monthly_spending:

  1. SQL queries on transactions. The aggregate table "would likely have much fewer rows than the total 5 billion transactions".
  2. MapReduce over the raw transaction files in the object store. Categorize each transaction and sum by (user_id, month, category). "Running analyses on the transaction files could significantly reduce the load on the database." The Budget Service can re-run the analysis when a user changes a category.
def mapper(self, _, line):
    user_id, timestamp, seller, amount = line.split('\t')
    category = self.categorizer.categorize(seller)
    period = self.extract_year_month(timestamp)
    if period == self.current_year_month:
        yield (user_id, period, category), amount

If you want spending to update as transactions arrive instead, consume the outbox events (lesson 2) and add each amount to a per-user, per-month, per-category counter. Use integer cents (Redis HINCRBY), not floating point. The batch job can then reconcile the counters, the way chapter 15 checks a stream against a batch.


Serving reads

The primer adds a use case for users viewing summaries and transactions:

  • Put user sessions, aggregate stats by category and recent transactions in a memory cache such as Redis or Memcached. Read them cache-aside: check the cache, and on a miss read the SQL database and fill the cache.
  • Serve static content from an object store behind a CDN.
  • Read replicas handle cache misses, as long as they are not bogged down replicating writes.
  • Consider a separate analytics database, a data warehouse such as Amazon Redshift or Google BigQuery, for monthly_spending. Keep only about a month of transactions in the database and the rest in the warehouse or object store. S3 "can comfortably handle" 250 GB of new content a month.

Categorizing transactions and tracking budgets

The primer’s design: a seeded seller-to-category map, crowd overrides for sellers it does not know, and an income-based budget template. Amounts are kept in integer cents.

Would be: uncategorized (no data)
A user recategorizes Corner Cafe as:
Housing0.00 USD of
Food0.00 USD of
Gas0.00 USD of
Shopping0.00 USD of
Uncategorized: 0.00 USD
Budgets start from the primer’s income template for a 5,000 USD monthly income.
Users1× instanceCDN1× instanceObject store (staticcontent)1× instanceLoad balancer2× instancesRead API2× instancesMemory cache2× instancesRead replicas2× instancesSQL database2× instancesData warehouse2× instancesUsers1× instanceCDN1× instanceObject store (staticcontent)1× instanceLoad balancer2× instancesRead API2× instancesMemory cache2× instancesRead replicas2× instancesSQL database2× instancesData warehouse2× instancesUsers1× instanceCDN1× instanceObject store (staticcontent)1× instanceLoad balancer2× instancesRead API2× instancesMemory cache2× instancesRead replicas2× instancesSQL database2× instancesData warehouse2× instances
Figure 4

Serving reads: summaries from a memory cache, misses from read replicas, older transactions from a data warehouse, and static content from a CDN.

Follow one dashboard view. The page’s static content comes from the CDN, which fetches it from the object store. The request for the user’s summaries goes through the load balancer to the read API, which reads the cache first: user sessions, spending by category and recent transactions. On a miss it reads a read replica and fills the cache. Transactions older than about a month are read from the data warehouse, which also holds monthly spending. The replicas copy every write from the SQL database’s leader, so they serve reads only while they keep up with 2,000 writes a second. At 200 reads a second on average, one server of each kind is enough at the lab’s figures, plus a spare.

  • Users: 1 × Users
  • CDN: 1 × CDN
  • Object store (static content): 1 × Object store
  • Load balancer: 2 × Load balancer
  • Read API: 2 × App server
  • Memory cache: 2 × Cache
  • Read replicas: 2 × Read replica
  • SQL database: 2 × Relational database
  • Data warehouse: 2 × Relational database
  • Users sends requests to CDN
  • CDN sends requests to Object store (static content)
  • Users sends requests to Load balancer
  • Load balancer sends requests to Read API
  • Read API sends requests to Memory cache
  • Read API sends requests to Read replicas
  • Read replicas keeps a copy of SQL database
  • Read API sends requests to Data warehouse

Key takeaways

  • A 50,000-seller map fits in about 12 MB; for unknown sellers, users' overrides vote, and an override changes only the user's own transaction.
  • Store only the budget categories users change, not 100 million budget items.
  • Compute monthly spending with SQL or MapReduce over the raw files, or update counters in integer cents from the outbox events.
  • Serve summaries cache-aside, misses from read replicas, and older transactions from a data warehouse.
Sources4