Lecture
In my mind, I have always viewed computer science as the study of computational trade-offs. Representing ordered sets and maps with finite state machines is a shining beam of that study. Given that we have devoted most of this article to discussing the benefits of FSTs, we will now devote a small section to their drawbacks.
Despite the many interesting things you can do with FSTs, they are simply not suitable as a general-purpose data structure. When writing code, if you need an unordered map or an ordered map, you should immediately reach for a HashMap or a BTreeMap. An FST-based data structure has a number of hurdles you must overcome before it becomes useful.
First of all, how many keys do you expect to have? If you are unlikely to see more than a few hundred thousand keys, then it is almost certainly better to use a simpler data structure. To support queries like fuzzy search or regular expressions, a simple linear scan over the keys is probably enough, since there are not that many of them.
Second, what do your keys look like? What do your values look like? In this article I presented an FST-based data structure that knows how to store only keys that are sequences of bytes, and knows only how to store values that are 64-bit unsigned integers. If it is hard to bring your keys and values into this format, then using an FST may not pay off. (That said, I note that it is usually possible with some work. For example, if your keys are 32-bit integers, then encoding them in big-endian byte order, so that each number takes 4 bytes, will work fine with FSTs, because big-endian preserves the natural ordering of integers under lexicographic ordering. Notably, little-endian encoding will not work! Here is a small toy example that stores a set of simple integers.)
Third, is a reasonable order defined on your keys? Can they be sorted? In particular, although it is usually possible to come up with an order, you need to make sure that it is preserved lexicographically after conversion to bytes (otherwise range queries will not work). Sorting the keys is also usually not a showstopper, since you can batch the keys, sort them, and build intermediate FSTs that can be merged afterward. But that is an additional cost; in your case it may or may not be worth it.
Fourth, do you need regular mutation? Standard data structures such as HashMap and BTreeMap allow the caller to freely add, remove, or modify keys and their values. The FST-based data structure presented in this article has no such capability. Namely, once produced, it cannot be changed. Like the other hurdles, this one can also be overcome, but it requires building a new FST for each mutation. Whether this is feasible depends on whether you can batch your mutations, which lets you build new FSTs periodically instead of a new FST for every change.
Another important caveat about using the fst crate presented in this article is that it is more robust on 64-bit systems. Namely, because the fst crate strongly favors the use of memory maps, it must access the contents of a file through a pointer. If you are using a 32-bit system, then the pointer type can address at most 4 GB of data, which means your FSTs are limited to that size (but probably less, depending on the availability of virtual memory on your system). For example, this would make it impossible to both build and search the Common Crawl FST. (If you built it on a 64-bit system, moved it to a 32-bit system, and tried to search it, the fst crate would panic, which usually results in the program aborting.)
On a 64-bit system, the size of your FST is effectively limited by the available virtual memory. A 64-bit system has a large amount of virtual memory.
Consequently, if you use FSTs on a 32-bit system, you need to take care to limit the size of the FSTs you create. This is a bit tricky, since there is no way to know how large an FST will be until it has been built. It also means that any process that wants to search an FST will need to search all the FST's components in a way that does not exhaust the available virtual memory.
The in-memory and on-disk FST format depends heavily on being able to quickly access any particular byte of the FST. Unfortunately, there is little locality of reference here. (There may be some, but confirming it requires additional analysis, and it probably depends heavily on how the redundancy in the keys is exploited.) This means that if your FST is on a mechanical disk and not already in memory, then a query could potentially be quite slow. This is mostly mitigated by using an SSD, which has zero seek latency and obviously supports the random-access use case well.
If your FSTs are really large, then SSDs can be prohibitively expensive. But as we showed in the experiments above, even with more than 1 billion keys the FST grew to only 27 GB. In such a case, using an SSD seems quite cost-effective. In fact, even using RAM at that level of memory usage may be cost-effective. For example, a machine with 61 GB of RAM currently costs $0.0961/hour as an Amazon EC2 spot instance (r3.2xlarge).
The "keep the FST in RAM" use case is well supported by the fst crate. Although I insist on using memory maps, it is of course also possible to store an FST directly on the heap, which means you will not be susceptible to the operating system's page cache. (Of course, you may still be susceptible to swapping, but as I understand it, most people disable that these days.)
Thank you for sticking with me this far! I hope this article has taught you something about using finite state machines as a data structure that allows you to store a large number of keys in a small space while remaining easily searchable.
We also briefly looked at an efficient implementation of the ideas in this article. This implementation is provided as part of the fst crate, written in Rust. It comes with full API documentation and examples.
Finally, you may be interested in other work I have done in Rust with strings:
Comments