Multi-Touch Attribution via Markov Chains on F# and Cloud Run

1. The Business Problem: When SQL Becomes an Anti-Pattern

In digital marketing, Multi-Touch Attribution (MTA) is the process of assigning credit to various touchpoints in a customer’s journey. Standard heuristic models, such as “Last-Click” or “Linear,” fail to capture the actual impact of each channel. To understand true marketing ROI, businesses require data-driven attribution.

When an architect receives this task, the default approach is often to build the entire logic directly inside the data warehouse (BigQuery). Engineers write complex SQL scripts using recursive Common Table Expressions (CTEs), window functions, and cross-joins to map user paths and calculate probabilities.

This approach reveals a fundamental architectural flaw: relational databases are not designed for matrix operations or graph traversals.

Attempting to solve sequence-based algorithmic problems in pure SQL leads to three critical failures:

1. Exponential Slot Consumption (Cloud Waste): Calculating transition probabilities across millions of dynamic user journeys requires heavy shuffling and self-joins. A single attribution query can consume thousands of BigQuery slots, leading to massive billing spikes.
2. Maintenance Nightmares: A 500-line SQL script calculating graph probabilities is nearly impossible to debug, test, or version-control effectively.
3. Algorithmic Limitations: SQL lacks native structures for linear algebra. Calculating the “Removal Effect” (a core component of advanced MTA) in SQL requires brute-forcing combinations, which eventually hits BigQuery’s Resources exceeded limits.

To solve this, we must shift the paradigm. We extract the heavy mathematics out of the warehouse, move it into a serverless compute engine (Google Cloud Run), and write it in a functional language (F#) optimized for algebraic data types. BigQuery returns to its primary role: fast data storage and retrieval.

2. Mathematical Abstraction: The Markov Chain Engine

Instead of treating the user journey as a set of relational tables, we translate the business problem into a mathematical algorithm: a Markov Chain.

A Markov Chain is a stochastic model describing a sequence of possible events. Its defining characteristic is the Markov Property: the probability of transitioning to the next state depends solely on the current state, not on the sequence of events that preceded it.

Step 2.1: Defining the State Space

First, we map the digital marketing reality to mathematical states in a directed graph.

• S (Start): The beginning of any user journey.
• C_1, C_2, … C_n (Channels): The marketing touchpoints (e.g., Organic Search, Paid Social, Email).
• V (Conversion): The absorbing state of success (e.g., a purchase).
• N (Null/Drop-off): The absorbing state of failure (user leaves without buying).

A user path like Start -> Social -> Search -> Conversion becomes a discrete walk through the graph.

Step 2.2: Building the Transition Matrix

By analyzing historical data extracted from BigQuery, the F# engine calculates the probability of moving from one state to another. This forms a Transition Matrix ($P$).

If a user is currently in the “Social” state, the matrix defines where they are mathematically most likely to go next.

Current State (i)	Next State: Social	Next State: Search	Next State: Conversion	Next State: Null
Start	0.60	0.40	0.00	0.00
Social	0.00	0.30	0.10	0.60
Search	0.15	0.00	0.35	0.50
Conversion	0.00	0.00	1.00	0.00
Null	0.00	0.00	0.00	1.00

Note: Conversion and Null are absorbing states. Once entered, the probability of remaining there is 1.00.

Step 2.3: Calculating the Removal Effect

The Transition Matrix alone does not assign marketing credit. To find the true value of a channel, the algorithm applies the Removal Effect.

1. Baseline Probability: Using linear algebra, the engine calculates the overall probability of a user reaching the Conversion state from the Start state across the entire network. Let’s assume this baseline is $25\%$.
2. Simulated Removal: We mathematically “remove” a channel from the graph (e.g., “Social”). All paths that previously went through “Social” are redirected strictly to the “Null” (Drop-off) state.
3. Recalculation: The engine recalculates the overall conversion probability on this modified graph. If the probability drops to $15\%$, the Removal Effect for “Social” is $0.40$ (a $40\%$ loss in total conversions).
4. Credit Distribution: This process is repeated for every channel. The resulting removal effects are normalized to $100\%$, distributing the exact fractional value of conversions to each marketing touchpoint.

By treating the problem as a graph simulation rather than a relational query, we reduce a multi-hour, expensive BigQuery workload into a matrix multiplication task that takes milliseconds in F#.

3. The Architecture on Google Cloud

To implement this mathematical engine effectively, we need a decoupled, event-driven architecture that minimizes total cost of ownership (TCO) while ensuring high performance. The architecture utilizes three primary Google Cloud services: BigQuery for storage, Cloud Run for serverless computation, and Eventarc (or Cloud Scheduler) for orchestration.

The Flow of Execution

1. Data Extraction (BigQuery Storage API): The user journey data is pre-aggregated into a lightweight view in BigQuery. Instead of writing complex SQL to calculate the probabilities, BigQuery simply outputs the raw sequences (e.g., User123: Start -> Social -> Search -> Conversion).
2. Trigger (Cloud Scheduler / Eventarc): Once the daily batch of raw data is ready, a trigger fires an HTTP request to the Cloud Run service.
3. Compute Engine (Cloud Run & F#):
   • The F# application spins up instantly.
   • It streams the data from BigQuery into memory. F# is highly efficient at handling large collections in memory using sequences (seq<'T>).
   • The algorithm calculates the Transition Matrix and processes the Removal Effect.
   • The engine generates a structured output (the final attribution weights for each channel).
4. Data Loading (BigQuery Storage Write API): The F# engine writes the final attribution matrix back to a target table in BigQuery.

Why Cloud Run is the Optimal Choice

For this specific workload, Cloud Run significantly outperforms alternative compute options (like GKE or Dataproc) in terms of FinOps efficiency:

• Scale-to-Zero: The attribution model only needs to run once a day (or several times a day in micro-batches). A GKE cluster would incur idle costs, whereas Cloud Run scales to zero and costs exactly $0.00 when not in use.
• Memory Efficiency: Matrix operations require memory. Cloud Run allows configuring up to 32 GB of RAM per instance, which is more than sufficient for processing transition matrices of millions of user journeys in F#.
• Execution Time: By removing the heavy lifting from BigQuery slots (which are expensive for complex iterative queries), we shift the cost to Cloud Run’s CPU seconds, which are fractions of a cent.

4. Engineering in F#: The Algorithmic Core

F# is the perfect language for this engine. Its functional nature, immutable data structures, and concise syntax allow us to express complex mathematics clearly without the boilerplate of C# or the potential runtime errors of Python.

Below is an abstract representation of the core algorithmic components written in F#.

4.1 Defining the Domain Model

We use F# Discriminated Unions to define the graph states. This ensures type safety; the compiler will not allow an invalid state transition.

F#

namespace MarkovAttribution

// Define the precise states of the user journey
type JourneyState =
    | Start
    | Channel of string // e.g., Channel("Paid Social")
    | Conversion
    | NullDropoff

// Represents a single transition from one state to another
type Transition = {
    FromState: JourneyState
    ToState: JourneyState
    Weight: float // Optional weight, usually 1.0 for a standard transition
}

4.2 Building the Transition Matrix

The engine must process the raw sequences and build the matrix. In F#, we can use a Map (dictionary) to store the probability of moving from state A to state B.

F#

module MatrixEngine =
    
    // Calculates the raw counts of transitions between states
    let calculateTransitionCounts (paths: JourneyState list list) =
        paths
        |> List.collect (fun path -> 
            // Pair each state with the next state in the sequence
            path |> List.pairwise
        )
        |> List.countBy id // Count occurrences of each (From, To) tuple
        |> Map.ofList

    // Normalizes counts into a probability matrix (rows summing to 1.0)
    let buildProbabilityMatrix (transitionCounts: Map<(JourneyState * JourneyState), int>) =
        // Group by the 'FromState'
        let groupedBySource =
            transitionCounts
            |> Map.toList
            |> List.groupBy (fun ((fromState, _), _) -> fromState)
            
        groupedBySource
        |> List.map (fun (fromState, transitions) ->
            let totalTransitions = 
                transitions |> List.sumBy (fun (_, count) -> count) |> float
            
            // Calculate probability for each destination
            let probabilities =
                transitions
                |> List.map (fun ((_, toState), count) -> 
                    toState, (float count) / totalTransitions)
                |> Map.ofList
                
            fromState, probabilities
        )
        |> Map.ofList

4.3 Implementing the Removal Effect Simulation

To calculate the removal effect, we mathematically “break” the graph by simulating the removal of a specific channel.

F#

    // Simulates the removal of a channel by redirecting its inbound traffic to NullDropoff
    let simulateRemoval (matrix: Map<JourneyState, Map<JourneyState, float>>) (channelToRemove: string) =
        let targetState = Channel(channelToRemove)
        
        matrix
        |> Map.map (fun fromState transitions ->
            if fromState = targetState then
                // If we are at the removed channel, all traffic goes to NullDropoff
                Map.ofList [ (NullDropoff, 1.0) ]
            else
                transitions
                |> Map.map (fun toState prob ->
                    // If traffic was heading to the removed channel, redirect it
                    if toState = targetState then 0.0 else prob
                )
        )

Note: After applying simulateRemoval, the algorithm would then traverse the modified matrix (usually using absorbing Markov chain formulas involving the Fundamental Matrix) to calculate the new overall conversion probability.

By utilizing F#, we have translated a chaotic, resource-intensive BigQuery SQL script into a clean, strictly typed algorithmic engine that runs predictably and efficiently in a serverless container.

5. Handling Data I/O: The BigQuery Storage API

A common pitfall when extracting computations from the data warehouse to a microservice is the memory bottleneck. If an F# application attempts to load 10 million user journeys into memory using standard REST API calls, the Cloud Run container will crash due to Out-Of-Memory (OOM) errors.

To solve this, the engine must stream data rather than load it monolithically. In the Google Cloud ecosystem, this is achieved using the BigQuery Storage Read API.

Unlike the standard BigQuery API, which is designed for pagination and small result sets, the Storage API uses gRPC (Google Remote Procedure Call) to stream data directly from BigQuery’s underlying storage mechanism (Colossus) to the F# application. This allows the engine to process sequences lazily.

F# Data Streaming Implementation

By leveraging the Google.Cloud.BigQuery.Storage.V1 .NET library, we can iterate through the dataset efficiently. The functional nature of F# seq<'T> (which translates to IEnumerable<T> in .NET) is perfectly suited for lazy evaluation.

F#

// Pseudo-code for streaming BigQuery data efficiently
open Google.Cloud.BigQuery.Storage.V1

let streamUserJourneys (projectId: string) (datasetId: string) (tableId: string) =
    // Initialize the gRPC client
    let client = BigQueryReadClient.Create()
    let tableReference = sprintf "projects/%s/datasets/%s/tables/%s" projectId datasetId tableId
    
    // Create a read session requesting only the specific columns needed
    let session = new ReadSession()
    session.Table <- tableReference
    session.DataFormat <- DataFormat.Avro
    
    let readSession = client.CreateReadSession(
        sprintf "projects/%s" projectId, 
        session, 
        1 // Restrict to a single stream for simplicity, or scale for parallel processing
    )

    // The F# sequence expression yields rows lazily as they arrive over gRPC
    seq {
        for stream in readSession.Streams do
            let request = new ReadRowsRequest(ReadStream = stream.Name)
            let responseStream = client.ReadRows(request).GetResponseStream()
            
            while responseStream.MoveNextAsync().Result do
                let rowBatch = responseStream.Current
                // Parse Avro rows and yield them to the Matrix Engine
                yield! parseAvroBatch rowBatch
    }

After the Matrix Engine calculates the Removal Effects and assigns the final fractional attribution to each marketing channel, the results are written back using the BigQuery Storage Write API, which allows for high-throughput, exactly-once delivery into the final reporting tables.

6. Infrastructure Deployment

To ensure reproducibility, the entire engine is deployed using Terraform. The F# application is compiled ahead-of-time (AOT) or packed into a lightweight Alpine Linux Docker container to ensure cold start times remain under a few seconds.

Terraform

# infrastructure/cloudrun.tf
resource "google_cloud_run_v2_job" "markov_attribution_job" {
  name     = "mta-markov-engine"
  location = "europe-west1"

  template {
    template {
      containers {
        image = "europe-west1-docker.pkg.dev/my-project/repo/mta-fsharp-engine:latest"
        
        resources {
          limits = {
            cpu    = "4"
            memory = "8Gi" # Sufficient for in-memory matrix operations
          }
        }
        
        env {
          name  = "TARGET_DATASET"
          value = "marketing_features"
        }
      }
      # Maximum allowed execution time (Cloud Run Jobs support up to 24 hours)
      timeout = "3600s" 
    }
  }
}

Note: We use google_cloud_run_v2_job instead of a standard Cloud Run Service, because this is an asynchronous batch processing task, not a synchronous web request.

7. FinOps Impact and TCO Analysis

Migrating complex graph traversals from BigQuery SQL to an F# algorithmic engine on Cloud Run dramatically alters the financial profile of the data pipeline.

The SQL Approach (High Variable Cost)

When executing recursive CTEs and cross-joins in BigQuery to calculate Markov probabilities, the engine dynamically provisions hundreds or thousands of slots (compute units).

• Cost: Billed per terabyte scanned or via slot-hour consumption. A poorly optimized matrix calculation can easily scan terabytes of intermediate temporary tables, costing tens of dollars per run.
• Risk: Prone to “Resources Exceeded” errors during traffic spikes, requiring more expensive slot reservations to guarantee execution.

The Algorithmic Engine Approach (Low Fixed-Cap Cost)

• Cost: BigQuery is only billed for the initial read (Storage API is highly cost-effective) and final write. The computation happens in Cloud Run.
• Cloud Run Pricing: Billed only for the exact seconds the CPU and memory are allocated. A Cloud Run Job utilizing 4 CPUs and 8GB RAM costs roughly $0.0003 per second. If the F# engine processes the matrices in 5 minutes (300 seconds), the compute cost is less than $0.10 per run.
• Risk: Complete financial predictability. The maximum cost is hard-capped by the job timeout setting.

Conclusion

The “Modern Data Stack” often promotes the idea that everything should be expressed as SQL inside the data warehouse. However, true cloud architecture requires using the right tool for the job.

Relational databases are built for aggregations, filtering, and joining structured datasets. They are fundamentally not designed for algorithmic graph traversals, linear algebra, or stochastic simulations. By forcing BigQuery to perform these tasks, businesses incur massive FinOps penalties and create unmaintainable codebases.

Extracting mathematical business logic into a dedicated, strictly-typed functional language like F# and deploying it to a serverless container like Cloud Run provides the optimal balance. It reduces cloud waste, ensures deterministic and testable calculations, and restores BigQuery to its most efficient role: a highly scalable, low-latency storage layer.