New

Our landmark annual report is here.Read the State of Payment Operations 2022

Journal|||Behind The Scenes

How We Built Virtual Accounts

Image of Matt McFarland
Matt McFarlandEngineering

Introduction

From its outset, Modern Treasury solved the payment origination problem. We made it easy for customers to send money to recipients across a matrix of payment rails, currency and countries.

On Tuesday, we announced our Virtual Accounts product, which solves the other side of the payment operations problem: inbound payment attribution. As customers grow and receive more payments originated by external parties, the reconciliation of those payments to their senders becomes increasingly complex and burdensome.

Our Virtual Accounts Product

Modern Treasury’s Virtual Accounts can automatically reconcile and tag inbound payments with their sender by allocating a unique account number to which each external originating party can send payments. Customers can designate one—or more—virtual accounts per counterparty to handle received funds, which makes tracking the payments from each of those individuals unambiguous. Payments sent to a virtual account appear in the physical Internal Account that the virtual account range is mapped to (the bank owns this mapping process).

Types of Virtual Account Allocations

The banks that provide virtual accounts expose a wide range of virtual account implementations, which can be represented by:

  • A common prefix (“123456XXXX”)
  • A common suffix (“XXXX123456”)
  • A range (“12345[1111-9999]”)
  • A bank-determined list of reserved numbers (“123450”, “123455”, “123459”, etc…)

Our Virtual Accounts API unifies how a customer can create virtual accounts in any of these schemes by handling the account allocation logic in each scenario.

How It Works

When we were designing the Virtual Accounts API, we knew that the API would need to handle the variety of virtual account allocation schemes offered within the banking ecosystem. Customers needed the virtual account creation API to pick a free virtual account number within the range defined by their bank. Banks offering virtual accounts have various allocation types, so we needed our implementation to abstract away the complexity of those types, and identify a usable account virtual number if the customer does not specify one.

The API requires the minimum information we need to attribute a virtual account to which a counterparty can send payments. The following example shows how to create a virtual account and the response.

In this example, let’s say that the Bank of MT provided a virtual account range 1234XXXXXX [1] attached to the Internal Account for Sesame Inc.’s ID: “56324045-5eeb-49b0-8714-c3a1f48884a1.”

That virtual account range would include all account numbers ranging from 1234000000 - 1234999999, giving us 100,000 possible virtual account numbers.

1POST /api/virtual_accounts
2{
3    name: "Sesame Inc.",
4    # Sesame Inc's Counterparty Id
5    counterparty_id: "24d77ddf-b13d-4c84-abc1-4d7ca671bd9a",
6    # Internal Account mapped to the virtual account range.
7    internal_account_id: "56324045-5eeb-49b0-8714-c3a1f48884a1" 
8}
1Returns 201 OK
2‍(some fields omitted for concision)
3{
4    "id": "2e0296c1-1daf-4b3e-954d-fb9ec7be56f6",
5    "object": "virtual_account",
6    "name": "Sesame Inc.",
7    "counterparty_id": "24d77ddf-b13d-4c84-abc1-4d7ca671bd9a",
8    "internal_account_id": "56324045-5eeb-49b0-8714-c3a1f48884a1",
9    "account_details": [
10      {
11       "id": "5668c0cf-972d-49c6-970f-b32591f3e8a6",
12       "object": "account_detail",
13       "account_number": "1234111111",
14       "account_number_type": "other"
15      }
16     ],
17    "routing_details": [
18      {
19       "id":"5ceb251f-0235-48a2-81cb-0c668f5ee81b",
20       "object": "routing_detail",
21       "payment_type": null,
22       "routing_number": "121141822",
23       "routing_number_type": "aba",
24       "bank_name": "BANK OF MT",
25       "bank_address": <address_object>,
26       ...
27      }
28     ],
29     ...
30}

Payments can be sent to the Sesame Inc.’s virtual account by specifying the routing number 121141822 and account number 1234560000. In this API call, Modern Treasury found a free account number within the virtual account allocation and claimed it for Sesame Inc.’s virtual account.

How We Built It

Defining the logic to identify and claim account numbers within an allocation ended up being an interesting problem to solve. We needed this process to be performant and correct. The rest of this blog post discusses our journey to finding a solution that fit both criteria.

The Naive / Brute-Force Approach

In the first Virtual Account implementation at Modern Treasury, we wrote the following algorithm to find an unassigned account number in a prefix range.

This simple algorithm repeatedly pulls random account numbers out of the range, determines if a collision exists for that customer’s allocation, and then re-rolls if there is one.

1def virtual_account_number_taken?(account_number)
2    # Returns true if the account number has been allocated
3    # within the customer's virtual account range.
4end
5
6def find_free_account_number_in_range(prefix, range_width: 10)
7    range_digits = range_width - prefix.length
8    allowable_range = 10 ** range_digits # 10^(range_digits)
9
10    allocated = nil
11    while !allocated do
12      # find a random number between 0 and the limit
13      random = Random.rand(allowable_range)
14      # 0-pad to fit the desired width
15      random = random.to_s.rjust(range_digits, "0") 
16      random_account_number = "#{prefix}#{random}"
17
18      next if virtual_account_number_taken?(random_account_number)    
19      allocated = random_account_number
20    end
21
22   allocated
23end

After a moment's thought, it became clear this algorithm had a major flaw. If every possible account had been provisioned in the range, this algorithm would loop endlessly.

Brute Force, Version 2

We tried our hand again with an implementation that capped attempts so the algorithm wouldn’t be recursive.

We can at least complain loudly and abort if an allocation finding exceeds a certain number of attempts, but even then, if a successful and growing customer starts to allocate a significant portion of their allowed range, we might run into collision exceptions as the norm.

1MAX_ATTEMPTS = 100
23def virtual_account_number_taken?(account_number)
4    # Returns true if the account number has been allocated
5    # within the customer's virtual account range.
6end
7
8def find_free_account_number_in_range!(prefix, range_width: 10)
9    range_digits = range_width - prefix.length
10    allowable_range = 10 ** range_digits # 10^(range_digits)
11
12    allocated = nil
13    i = 0
14    while !allocated do
15      raise "Exceeded maximum iterations!" if i >= MAX_ATTEMPTS
16      # find a random number between 0 and the limit
17      random = Random.rand(allowable_range) 
18      # 0-pad to fit the desired width
19      random = random.to_s.rjust(range_digits, "0") 
20      random_account_number = "#{prefix}#{random}"
21
22      i += 1
23      next if virtual_account_number_taken?(random_account_number)    
24
25      allocated = random_account_number
26    end
27
28   allocated
29end

Though this implementation will not infinitely spin, it has another problem. Since this allocation algorithm is run synchronously during the API call (without a given account number), these API calls could grow increasingly expensive as the number of expected iterations to find a free account number rises. This didn’t sit right with us, and we rethought our approach again.

Queues and Asynchronous Processing

After reviewing our initial implementation and realizing that we needed to find a sturdier and more performant virtual account number search strategy. We started by reviewing our requirements:

  1. The algorithm needed to be able to find a free account number in constant O(1) time.
  2. The solution also needed to handle the real-world constraint that an allocation might become exhausted.

We realized we could satisfy both requirements by separating the calculation of free account numbers from allocating those numbers to virtual accounts during virtual account creation. We decided to add a queue data structure for each customer's virtual account allocation range. Each queue contained a list of unallocated account numbers found by a background processing job. It turned the synchronous provisioning logic into a much simpler process.

1def find_free_account_number_in_range!(internal_account)
2    # find the virtual account range from the requested internal account
3    virtual_account_range = internal_account.virtual_account_range 
4
5    # get the queue structure for the virtual account range
6    queue = virtual_account_range.allocation_queue
7
8    # throw if the account range is exhausted
9    random_virtual_account_number = queue.pop!
10
11    if queue.length < minimum
12      # start the asynchronous process to fill 
13      # the queue with more unallocated account numbers
14      refill_queue_asnchronously(queue)
15    end
16
17   random_virtual_account_number
18end

The background processor would periodically scan all of the virtual account ranges for queues that had been depleted below our desired threshold.

1MINIMUM_THRESHOLD = 100
2
3def fill_queue(virtual_account_range, queue)
4    return if queue.length > MINIMUM_THRESOLD
5    return if range_exhausted?(virtual_account_range)
6
7    loop do
8      random_account_number = find_free_account_number_in_range(range.prefix)
9      queue.push(random_account_number)
10
11      # Add some overhead when refilling the queues
12      break if queue.length > MINIMUM_THRESOLD * 2
13    end
14end
15
16def virtual_account_number_taken?(account_number)
17    # Returns true if the account number has been allocated
18    # within the customer's virtual account range.
19end
20
21def range_exhausted?(virtual_account_range)
22    # Returns true if all possible virtual accounts within the
23    # range have been allocated to virtual accounts in Modern Treasury.
24end
25
26def find_free_account_number_in_range(prefix, range_width: 10)
27    range_digits = range_width - prefix.length
28    allowable_range = 10 ** range_digits # 10^(range_digits)
29
30    allocated = nil
31    while !allocated do
32      # find a random number between 0 and the limit
33      random = Random.rand(allowable_range) 
34      # 0-pad to fit the desired width
35      random = random.to_s.rjust(range_digits, "0") 
36      random_account_number = "#{prefix}#{random}"
37
38      next if virtual_account_number_taken?(random_account_number)    
39
40      allocated = random_account_number
41    end
42
43   allocated
44end

Extending the Solution

By separating how Modern Treasury identifies available virtual accounts from the allocation of those virtual account numbers, we were able to abstract over the various types of virtual account products offered by banks. The Virtual Account creation API retains a simple and performant interface, while our background processors handle the complexity of enforcing uniqueness across virtual accounts within a customer's allocated range.

If you have any questions or feedback, feel free to reach out to support@moderntreasury.com. Likewise, if you enjoy designing well-abstracted APIs, Modern Treasury is hiring software engineers.

Try Modern Treasury

See how smooth payment operations can be.

Talk to Us
  1. This type of range allocation is something we call “prefix” range allocation. In the virtual account product landscape, banks are also suffix allocations, range allocations, and reserved allocations, all of which can be handled with a similar provisioning strategy.

Share

Copied!