Fast & Simple Foreign Exchange in Go

This is the latest article in a series on Personal Expenses With Go.

TL;DR

I wrote a commandline tool and Go library to efficiently look up foreign exchange rates between any two currencies. By keeping it simple with such modern technologies as .csv files and the occasional cached GET request, the tool outperforms microservice-based alternatives by many orders of magnitude.

Motivations

I recently wrote about trying to understand my personal expenses by parsing credit card statements, and the resulting PDF-related woes.

Today, I wanted to touch on the other hurdle I encountered: foreign exchange rates. Living in Switzerland, my bank account is in Swiss Francs, but I have expenses in Euros, Czech Crowns, US Dollars and Pounds. The daily exchange rates fluctuate wildly, so it’s not enough to hardcode some conversion rates - ideally my spreadsheet would contain daily exchange rates between all the currencies I need.

Alternatives Considered

My first attempt used the GOOGLEFINANCE function in Sheets, but a cursory internet search will reveal that it has problems. Even after I got it to work, the spreadsheet would randomly crash the browser, take a few minutes to reload and wouldn’t even open at all on mobile apps.

What’s odd is that converting between currencies really is an easy problem. In a funny twist, we expect people to solve this in a 40-minute coding interview. I can’t handle the irony of the same problem crashing Google Sheets.

Most programmatic solutions I could find to “how do I convert between currencies” involve calling a metered (often paid or at least subject to registration) API over HTTP, taking 5-200 ms per request.

Microservice noun

the software equivalent of being paid by the word.

I found (but forgot to write down where and since haven’t been able to find it again) a single Go library. Sadly I soon realized it’s intended to be used as a microservice, uses an unfortunate algorithm and can’t be extended to deal with more currecy data.

I decided to make a library whose complexity was more appropriate for the complexity of the problem.

Technical Design

Converting from currency to currency is the same problem as knowing the exchange rate on a specific day. Central banks publish, as a public service, exchange rates between their currency and all major currencies, as well as some minor currencies. For our purposes, we will call major those currencies, that appear in every central bank’s foreign exchange data, e.g. the USD or the EUR. Minor currencies are those that only appear in the data of some central banks, usually in the same region, e.g. the CZK or the TWD.

Converting between major currencies is easy:

Get the forex data from any central bank
Convert to the bank’s currency (the rate to and from your other major currency will be available)
Convert from the bank’s currency to the target

Converting between minor currencies requires finding a general-case path from starting currency to the target currency. We’re therefore looking for a pathfinding algorithm.

As an added complication, we want the rate for a specific day, so our algorithm must be date-aware.

Illustrative Example

For example, let’s say we want to convert from CZK to TWD, and we have access to the following rates:

EUR to USD
EUR to CZK
USD to TWD

We can express this visually. Each circle is a currency and each box represents the dates on which we know the conversion rate. The blue lines show the path we can take to convert from CZK to TWD in February.

digraph {
    graph [fontsize=9]
    node [fontsize=9]

    USD, EUR, CZK, TWD [shape=circle]
    EURUSD, EURCZK, USDTWD [shape=record]
    
    EURUSD [label="Jan 1: 1.13|Jan 2: 1.15|...|June 6: 1.08|June 7: 1.09"]
    EURCZK [label="Jan 1: 23.17|Jan 2: 23.19|...|June 6: 22.97|June 7: 22.95"]
    USDTWD [label="Jan 1: 28.68|Jan 2: 28.71|...|June 6: 27.50|June 7: 27.45"]

    EUR -> EURUSD -> USD [arrowhead=none]
    EUR -> EURCZK -> CZK [arrowhead=none]
    USD -> USDTWD -> TWD [arrowhead=none]

    CZK -> EURCZK -> EUR -> EURUSD -> USD -> USDTWD -> TWD [color=blue]
}

In a slightly more contrived example, let’s say the European Central Bank (ECB) also used to publish a EUR to TWD rate, but stopped last month. If we’re still looking for a February rate, then we cannot use this data, as shown below.

digraph {
    graph [fontsize=9]
    node [fontsize=9]

    USD, EUR, CZK, TWD [shape=circle]
    EURUSD, EURCZK, USDTWD, EURTWD [shape=record]
    
    EURUSD [label="Jan 1: 1.13|Jan 2: 1.15|...|June 6: 1.08|June 7: 1.09"]
    EURCZK [label="Jan 1: 23.17|Jan 2: 23.19|...|June 6: 22.97|June 7: 22.95"]
    USDTWD [label="Jan 1: 28.68|Jan 2: 28.71|...|June 6: 27.50|June 7: 27.45"]
    EURTWD [label="Jan 1: 31.68|Jan 2: 31.80|...|Jan 13: 32.03|Jan 14: 31.98"]

    EUR -> EURUSD -> USD [arrowhead=none]
    EUR -> EURCZK -> CZK [arrowhead=none]
    EUR -> EURTWD -> TWD [arrowhead=none]
    USD -> USDTWD -> TWD [arrowhead=none]

    CZK -> EURCZK -> EUR -> EURUSD -> USD -> USDTWD -> TWD [color=blue]

    EUR -> EURTWD [color=red constraint=false label="nope"]

    { rank=same USDTWD EURTWD }
}

But if we’re looking for a rate in January, then the older data is useful, because it lets us make the conversion in fewer steps and this is probably better.

digraph {
    graph [fontsize=9]
    node [fontsize=9]

    USD, EUR, CZK, TWD [shape=circle]
    EURUSD, EURCZK, USDTWD, EURTWD [shape=record]
    
    EURUSD [label="Jan 1: 1.13|Jan 2: 1.15|...|June 6: 1.08|June 7: 1.09"]
    EURCZK [label="Jan 1: 23.17|Jan 2: 23.19|...|June 6: 22.97|June 7: 22.95"]
    USDTWD [label="Jan 1: 28.68|Jan 2: 28.71|...|June 6: 27.50|June 7: 27.45"]
    EURTWD [label="Jan 1: 31.68|Jan 2: 31.80|...|Jan 13: 32.03|Jan 14: 31.98"]

    EUR -> EURUSD -> USD [arrowhead=none]
    EUR -> EURCZK -> CZK [arrowhead=none]
    EUR -> EURTWD -> TWD [arrowhead=none]
    USD -> USDTWD -> TWD [arrowhead=none]

    CZK -> EURCZK -> EUR -> EURTWD -> TWD [color=blue]

    EUR -> EURUSD [color=red constraint=false label="nope"]

    { rank=same USDTWD EURTWD }
}

Conversion Algorithm

From studying the example, it seems like a good algorithm will find the shortest path (fewest conversions) between currencies. The data is a cyclic graph, so we have a couple of options. The CS answer is probably to use Dijkstra’s Algorithm, because the edges have values (forex rates), however we only care about finding the shortest path, not the best path. (The best path is subjective: are you trying to charge the highest rate, or save money?)

When you ignore edge weights, Dijkstra’s is the same as Breadth-First Search (BFS), which most programmers are probably familiar with, so we’ll implement that.

The added complication is that only some edges are valid for each query, based on their date. It would be impractical to build a separate graph for each day, so we will instead store the edges in an array sorted by time, and find the right ones using binary search.

The BFS search can, in the worst case, traverse each edge and each vertex once, so its complexity is O(E + V). In a fully interconnected graph, E would be about V², but the whole point of this exercise is that the graph is not very interconnected. Filtering the edges will take O(E × log N) where N is the number of days of data. The overall complexity should then be O(V + E × log N).

It seems good practice to at least guess at the values of V, E and N.

V is the number of currencies. It’s 50 right now, and cannot be much higher than 200 in the extreme.
E is the number of rates between currencies. Each central bank publishes ~20-50 rates, so the current value is about 100.
N is the number of days of data. The published data go back a few years, so this value can be in the thousands.

Getting the Data

Three central banks offer convenient access to their forex data:

The ECB publishes a daily csv file with several years of forex data under a permissive license. It includes 42 currencies.
The Royal Bank of Australia publishes a similar csv file with 21 currencies.
The Bank of Canada similarly, with 27 currencies.

Because the lists overlap, the banks provide 50 currencies, which seems like a good start.

(Data from the Bank of England and the Fed are available through a web UI that seems intentionally hostile to automation, so let’s skip them for now.)

The library will download the csv files from their fixed URLs and process them locally. To avoid unnecessary IO, we’ll cache the files locally in ~./forex.

Limitations

Upstream changes – A bank could decide to stop publishing, or move the data. Supporting multiple overlapping sources of data should mitigate the impact of this until it can be fixed by adding new sources.

Offline operation – Since not all environments allow access to the internet, the library should ship with historical rates embedded.

Implementation & Performance

Here’s my implementation in Go, which is the language I like to use for data processing. It takes about 4000 ns to convert between currencies using cached forex rates from three large national banks. (The performance could be improved further if I could be arsed to fight with Go’s heap escape analyzer.)

The library downloads the data every 12 hours into ~/.forex, but also ships with an offline bundle of historical data in case connecting to the internet is an issue.

import "github.com/wowsignal-io/go-forex/forex"

// This is thread-safe. Data get cached in ~/.forex as CSV every 12 hours.
rate, err := forex.LiveExchange().Convert(
    "USD", "EUR",
    time.Date(2022, time.January, 4, 0, 0, 0, 0, time.UTC))

if err != nil { /* Handle your errors, y'all. */ }

fmt.Printf("The conversion rate from USD to EUR on January 4, 2022 was %f\n", rate.Rate)
// Output: The conversion rate from USD to EUR on January 4, 2022 was 0.886603.

It also comes with a commandline tool, in case a Go library isn’t what you want.

# This places forex-convert in $GOBIN.
> go install github.com/wowsignal-io/go-forex/cmd/forex-convert@latest

> forex-convert -from=PGK -to=INR -date=2021-03-01 -v
# Outputs:
# Conversion step 1/2: 1 PGK = 0.367985 AUD (source: RBA (inverse))
# Conversion step 2/2: 1 AUD = 56.850000 INR (source: RBA)
# Computed rate: 20.919963

Future Work

The initial version supports about 50 currencies. More can be added if I figure out how to reliably get data from the Fed and the Bank of England.
The commandline tool doesn’t support batch conversion, but it would be trivial to add.

I hope this turns out to be useful to somebody.