The primary input on weather.bingo is a search box with autocomplete. In this article I’ll cover how I built it to be globally fast without relying on a third-party API.
Requirements
Users of weather.bingo need a way to select which city’s weather to display. Since there are a large number of cities in the world, I thought a free-form text input with autocomplete would by a great way for a user to select their desired location.
A good autocomplete responses quickly to user input. If suggestions appear slowly the experience feels laggy and the user might be confused. To best serve world-wide users, it helps to generate the suggestions locally or from a low-latency API.
The Edgiest Approach?
Could the autocomplete suggestions be generated from the client in this case? How many cities are there in the world?
I found a city data set at geonames.org. There are about 200,000 cities in this data with a population greater than 500, which seemed a reasonable size cutoff.
Even if I use only 20 bytes per city on average, that would be at least 4 MiB of data. Since this search is the first thing that needs to respond, this is too heavy for device-based search.
An Edge Over the Competition
The next best thing to on-device search is a low-latency server near the user. With weather.bingo I’m targeting an audience all over the world. The only cost-effective way to have a server presence close to everyone is to use an edge network like the kind offered by Vercel Edge Functions or CloudFlare Workers (perhaps they are still the same thing).
These edge functions have strict size requirements, especially on the hobby plan: they need to fit in 1 MiB.
How can our city data set fit into such a small space?
It’s a Small World, After All
What data do we need for autocomplete? At a minimum, the city name, and associated country information. After some iteration on the experience, I ended up also including the log of the population and some abbreviations for some administrative district names.
I also wanted to include the latitude and longitude of the city as a natural key used throughout the site. For weather purposes, identifying a location roughly is fine. So, I transformed the latitude and longitude to within 1/100th of a degree, which at its coarsest near the equator is about a kilometer. The transformed coordinates easily pack into a 32-bit integer.
Math.round((lat + 90) * 100) << 16) | (Math.round((lon + 180) * 100) & 0xffff)
I was surprised that a 32-bit integer could identify locations with such a fine granularity (and other schemes are even more effective). Earth isn’t actually all that big — in fact, the MineCraft world is bigger.
Altogether my raw data set came to 6 MiB compressed. Not enough to need a database, but too big for an edge function. But not too big for… ten edge functions!
To divide the work into multiple edge functions, I implemented range-based sharding on the first two characters of the city name. After the user has typed two characters, the particular edge function holding the data set for matching cities can be identified. The ranges for cities of the world ended up looking like this:
["bo", "cr", "gd", "k.", "lu", "nn", "ra", "sh", "ut", "’u"];
About 1/10th of cities start with characters lexically less than or equal to “bo”, another 1/10th are greater than “bo” and less than or equal to “cr”, etc. This mapping can be leveraged directly in the client — which you can see if you observe the network calls while typing “bo” vs. “br” for example. With this split I ended up with ten edge function each only about 0.5 MiB in size.
Will this type of sharding increase costs? I don’t think so - edge functions are charged per invocation, and in this case nothing is invoked before the correct function is identified. The total number of invocations should remain the same as if everything was backed by a single function.
Now that the data can fit, the actual search is simple - I used a library called FlexSearch to generate an index for each two-character prefix. The indexes are built on-demand and cached in memory; in practice this is very fast.
A 1997 Movie with Anthony Hopkins and Alex Baldwin
Try some searches on weather.bingo and see how fast the autocomplete is. Type two characters that seem unusual; note the time it takes for a response. Then erase the input and type those same characters again. This should be the difference between cold start (needing to load the edge function and build the index) and warm start. Cold start in this case is still only milliseconds.
Overall I was very pleased with the responsiveness I achieved for this autocomplete search. If you have any ideas on how to make it even faster, please let me know!.