Matthias: Here's Rust in production, a podcast about companies who use Rust to shape the
Matthias: future of infrastructure.
Matthias: My name is Matthias Endler from corrode, and today we talk to Jeff Kao from Radar
Matthias: about building a high-performance geocoding platform with Rust.
Matthias: Jeffrey, thanks a lot for taking the time today for the interview.
Matthias: Can you say a few words about yourself and about Radar?
Jeff: Yeah, happy to be on this podcast. So my name is Jeff, and I'm a principal engineer at Radar Labs.
Jeff: We are an enterprise geolocation tech company.
Jeff: So that's a variety of things, spanning from maps and routing to search and
Jeff: geocoding and geofencing, as well as fraud detection.
Jeff: And a bit more about myself, I've been programming for quite some time now.
Jeff: I've worked at a variety of different startups. I've been a freelancer before
Jeff: as well, and even started my own small indie company a while ago.
Jeff: But these days, most of my engineering focus, I would say, is largely on backend
Jeff: and data infrastructure engineering.
Matthias: What's your programming background? What other languages do you know besides Rust?
Jeff: Yeah, so I would say, actually, it's kind of funny.
Jeff: When I first graduated from university, I joined a company called Foursquare.
Jeff: And I think at that time, it was maybe around the 2010s, where there were a
Jeff: lot of companies that were moving from Ruby,
Jeff: because Ruby on Rails, I think at the time was like, and it still is,
Jeff: you know, but I think like, it was almost like peak Ruby on Rails.
Jeff: And then there's the peak migrating from Ruby on Rails to something more quote
Jeff: unquote scalable by companies like Twitter and like Foursquare and like SoundCloud.
Jeff: So it's funny because I worked at two of those companies. And so I've done a lot of work in Scala.
Jeff: You know, in university, I prototyped and I was doing freelancing.
Jeff: And then I used a lot of Ruby on Rails at that time.
Jeff: And so, you know, a lot of like web technology is involved with that as well.
Jeff: So I did a lot of JavaScript.
Jeff: And even at that time, there wasn't TypeScript, but I think people were using
Jeff: CoffeeScript at that time. So I played around with that quite a bit.
Jeff: We actually, it's funny, we migrated when I worked at PagerDuty,
Jeff: we moved some workloads from JavaScript to actually CoffeeScript.
Jeff: But I think it's pretty much defunct now. Nobody really uses it.
Jeff: So those are probably my main languages, you know, dabbled in Python and some
Jeff: C and C++, but never in like a really full-time sort of manner.
Jeff: And so these days at Radar, mostly working with TypeScript, some Scala for some
Jeff: Spark pipelines, of course, a lot of Rust.
Jeff: And yeah, what else? Maybe some python as well that's the matter in the face.
Matthias: That's pretty impressive ruby scala javascript coffee script python type scripts
Matthias: that's a lot and now Rust what could people learn from the philosophy of ruby.
Jeff: I think this is sort of like an interesting question because technology comes in cycles, I would say.
Jeff: And that's definitely something I learned with some of the more senior principal
Jeff: engineers at companies I've worked at before,
Jeff: where really having an understanding and appreciation of things that are old
Jeff: really gives you insight onto what's coming next because technology really is cyclical.
Jeff: So I think there's a lot to learn and like about Ruby.
Jeff: And usually, I would say the entry point for most people with Ruby is really Rails.
Jeff: So it's really that concept of making programming languages work for you, in some sense.
Jeff: And so what does that entail? It's almost like, especially in modern languages.
Jeff: A lot of us have come to really be spoiled with these concepts of very powerful
Jeff: list collections that you see from functional languages.
Jeff: So mapping and filtering and reducing.
Jeff: And even these concepts you can see are applied to things that aren't even just
Jeff: programming languages, even in like distributed computation frameworks,
Jeff: like literally MapReduce is that concept and you see that in Spark and with
Jeff: all the new sort of data infrastructure that's written in Rust or even like SQL,
Jeff: because if you think about, you know, like the where clause in SQL is like a filter or,
Jeff: you know, you can do reductions with grouping,
Jeff: like there are all sort of these ways to express, It's, you know,
Jeff: how you process data in a way that's like very elegant and like it's commonly
Jeff: used throughout all these different paradigms.
Jeff: So I really think that, you know, on the Ruby side, for me, when I first started,
Jeff: I was like, wow, this is like Python, but better.
Jeff: But, you know, that's that's going to make some people angry, obviously.
Jeff: And that was me being a naive college student looking at languages and seeing
Jeff: like, oh, where's the sort of trend going? And why is everybody using Ruby on Rails?
Jeff: And it's really just understanding that it's a very pleasant experience and
Jeff: very expressive language.
Jeff: And having all of those sort of batteries built in gives you a lot of productivity
Jeff: and almost brings more joy to programming. Yeah.
Jeff: For really expressing like your ideas because
Jeff: really at the end of the day programming is about creating things
Jeff: and almost it's almost like a creative profession that i think most people don't
Jeff: really assume is creative from the outside but you're you're trying to solve
Jeff: problems and build things and being able to express things in in a very i guess
Jeff: like terse manner is is is very,
Jeff: conducive to you sort of getting into the flow state as a programmer yeah.
Matthias: When i think of ruby i think of elegance i
Matthias: think of the joy of programming expressiveness where
Matthias: would you see yourself more on the programming is a craft it's or an art or
Matthias: would it be more like discipline of engineering where would you see yourself on that scale.
Jeff: I think it's a mix of the two
Jeff: things you have the tools but it shouldn't necessarily be like you know the
Jeff: tools help you express something so maybe like as as like drawing parallels
Jeff: to maybe some other hobbies i have like say you're a musician right um,
Jeff: Especially like in jazz music, you know, like jazz musicians spend a lot of
Jeff: time practicing because they want to express like, oh, I want to play the chord
Jeff: changes in certain ways and like work on that. Or I want to learn these certain skills.
Jeff: And, you know, at the end of the day, music isn't about scales or chords,
Jeff: but those are the tools you use to express yourself.
Jeff: And once you sort of have those tools ingrained, then they get out of the way,
Jeff: they come natural to you. Then you can express, you know, your music,
Jeff: how you, you know, write music and, and add these things.
Jeff: So it's, it's, it's sort of like a mix of the two things, right?
Jeff: You want to understand the tools and what's out there and they should help you
Jeff: really ship the thing you're trying to do.
Jeff: And the thing you're trying to do can be very technical. So in a lot of cases,
Jeff: you can get really down like deep into the foundation, depending on what you're
Jeff: doing. a lot of systems programming, you know, and this is a Rust podcast,
Jeff: right? So there's that side of things.
Jeff: But on the other hand, there's a whole, you know, ecosystem of digital products
Jeff: that don't necessarily need, you know, the best tooling or anything like that.
Jeff: I think, you know, back to when, you know, in college,
Jeff: like I remember just creating some small websites by uploading
Jeff: things to like an ftp server from
Jeff: some of these like you know hosting companies that
Jeff: just give you a box and it's like here you go upload like index.php and then
Jeff: wow suddenly you you have something that's connected to the internet like it
Jeff: can be something as simple as that so i i can see their appreciation for for
Jeff: tools but i i really don't think it's necessarily going to,
Jeff: I don't think it's necessarily productive to just focus on it,
Jeff: but it's a mix. It's a mix.
Matthias: Coming back to Rust, with your background, Ruby, Scala, and so on, you have a lot of,
Matthias: functional part down. You have the expressiveness down. That part must have
Matthias: been really easy for you to learn.
Matthias: Algebraic data types do exist in Scala. And now you come to Rust.
Matthias: How was that first impression to you?
Jeff: Yeah, it was very refreshing. Rust really feels modern.
Jeff: And there are so many things to like coming from. I guess at Radar,
Jeff: our main programming language which is TypeScript.
Jeff: We actually migrated to TypeScript from JavaScript a couple of years ago.
Jeff: But looking at the JavaScript ecosystem where essentially there's a library
Jeff: for everything. There's a joke even on Stack Overflow.
Jeff: It's like, how do you add two plus two? Just add this NPM package to add two numbers.
Jeff: So there's having really, even at the time where we first started building this
Jeff: and we're definitely not early adopters.
Jeff: We started building our Rust project maybe two and a half years ago or so.
Jeff: There's a rich cargo crate ecosystem. There's a formatter,
Jeff: flame graphs, and the paradigms are very functional, but you're not forced to use those either.
Jeff: So having a rich data structure ecosystem in the standard library,
Jeff: being able to process vectors with all of the functions that many developers
Jeff: are used to these days really felt refreshing.
Jeff: And when we were starting to build out HorizonDB, our Rust geo service project,
Jeff: Those were some of the characteristics we were really looking for,
Jeff: especially for a team with, like, largely a background in writing, you know, TypeScript.
Matthias: Take us back to that time. What was the tech stack like before you started HorizonDB?
Matthias: What was the team like, the team dynamics?
Matthias: I guess most of them would be TypeScript developers, but there might be other people in the team.
Jeff: I guess at that time, maybe to give some background on maybe the business side
Jeff: of things, we're sort of tasked to build essentially an address validation API.
Jeff: And so that's slightly different from geocoding. And we can talk about these two things.
Jeff: So geocoding, or generally it's synonymous with for geocoding,
Jeff: that's what most people assume what geocoding is, is essentially searching for
Jeff: any geo entity. Whether that's an address, that can be a place or a region.
Jeff: So those tend to be, you know, more specifically called as like a course geocode.
Jeff: So for an address code, say I live at, you know, 123 Broadway.
Jeff: The task is then to understand this query, to know that this is an address,
Jeff: and you're looking for the number 123 and the street Broadway,
Jeff: and then return a latitude and longitude.
Jeff: And with our APIs, we offer like some other metadata such as,
Jeff: oh, this is in New York in this postal code and things like that.
Jeff: And so for address validation, there's a slight difference.
Jeff: Address validation is more about understanding the deliverability of mail rather
Jeff: than being focused on, you know, here's the latitude and longitude.
Jeff: It's more like, does this address exist in the post office's database?
Jeff: And so for us to accomplish that, the data format that we got from the post
Jeff: office, essentially they give you ranges of addresses. So Broadway goes from,
Jeff: let's say, 1 to 100, and it has this postal code.
Jeff: Or 841 Broadway has floor 1 to floor 12, and they have these specific postal codes.
Jeff: And it gets even more pedantic with a post office.
Jeff: And the rabbit hole goes very deep with address validation.
Jeff: So at that time, we didn't really, we were using an open source service for
Jeff: geocoding, but there wasn't really a way for us to essentially ingest these
Jeff: ranges and validate addresses.
Jeff: So that was sort of the main motivation for us to come up with something new. And so...
Jeff: Our tech stack, you know, at that time didn't have any Rust.
Jeff: We have some front-end, you know, services written with React and Next and JavaScript.
Jeff: And then our API server was written in TypeScript.
Jeff: We had some, like, data processing jobs in Spark and Scala.
Jeff: And then we used Airflow, so some Python as well. But nothing really,
Jeff: you know, statically compiled or...
Jeff: I mean, there's TypeScript, but more in the sense of like, you know,
Jeff: these things translate into some bytecode, sort of like a JVM or into native instructions.
Jeff: And we were sort of expecting, we had more constraints about like, oh,
Jeff: if we want to build a service that does things like this and it overlaps so much with geocoding,
Jeff: we might as well just sort of replace the service because we had some operational
Jeff: issues with our existing geocoder, which we can talk about later. And so...
Jeff: There was sort of a motivation to use something that, whether it's like an external
Jeff: service, like something like Elasticsearch or, you know, having something like all in one.
Jeff: Operationally, like we sort of got burnt by like having so many like external
Jeff: services that we were almost sort of motivated to have something that would
Jeff: just let us do everything on almost one package almost.
Matthias: Was Rust the only language that you considered for that project?
Jeff: So we were considering a couple of different options. And it's funny because at our company,
Jeff: we write like tech specs or essentially design documents before we sort of go
Jeff: into building some, you know, larger projects or like features or things that
Jeff: will have like big downstream impacts.
Jeff: So actually, looking back at the doc, we were considering a couple of languages,
Jeff: and we sort of discussed the trade-offs there.
Jeff: So we were thinking about Kotlin, and the thinking around there is that the
Jeff: Java and JVM ecosystem is very rich.
Jeff: From my personal experience, I think Scala is very complicated.
Jeff: And you know onboarding the whole team to that might have been a little tricky
Jeff: but Kotlin is a little bit more closer to like you know it's sort of in between
Jeff: and I do feel like there's a little bit more of a backing around it now in you
Jeff: know the 2020s versus Scala.
Jeff: Scala really just seems like a little bit more niche and like sort of Spark
Jeff: and even then like I think with Spark I I have some opinions about that and
Jeff: like how Rust might play into a world like that.
Jeff: So Kotlin felt like a good in between. And there was just a whole ton of, of these sort of,
Jeff: interesting ecosystem aspects such as you know
Jeff: elastic search is written in java and you
Jeff: know essentially elastic search is just a distributed wrapper around lucene
Jeff: i mean obviously it's much more than that you know entire company so
Jeff: it's a very broad stroke but you know there's a whole ton of work around like
Jeff: text processing which is essentially a lot of this this and we felt like okay
Jeff: that is a very rich ecosystem that we could potentially use with the trade-off
Jeff: of we know We're probably going to have to store large text indexes and all of these things,
Jeff: even synonyms or different spellings or spell correction.
Jeff: A lot of this is like dictionary lookups of strings and things like that.
Jeff: So you can imagine, even from the onset, we're probably going to store giant
Jeff: hash maps or a lot of things in memory.
Jeff: And we'll have to deal with a garbage collector. and one of the motivating factors
Jeff: from something like that as well, I guess before I talk about that,
Jeff: we're also considering Golang,
Jeff: which is sort of similar about it's garbage collected.
Jeff: And we've seen that a lot of companies
Jeff: have adopted it because it's really trivial to write web services,
Jeff: and it's relatively simple in the sense that There's not a whole lot of different
Jeff: ways to do something versus something like a Scala.
Jeff: You can express your problem, how to do it in many ways.
Jeff: So those were sort of the two biggest contenders.
Jeff: And that was largely because we didn't feel too comfortable of transitioning
Jeff: some JavaScript developers to something like CRC++.
Jeff: And I think the hurdle around like setting up like C and C++ projects,
Jeff: I know there's been so much innovation around, especially C++,
Jeff: but it just didn't seem like such a natural transition for our developers.
Jeff: And sort of similar with Golang, you know, like I think Golang was sort of evolved
Jeff: from Google from like their large C++ monorepo.
Jeff: And so a lot of these things that I mentioned about that make programming enjoyable
Jeff: is things like mapping and filtering and all of these sort of expressive aspects.
Jeff: We felt like because we had a bit of a short timeline, it almost felt like a
Jeff: step back in terms of the joy of programmer being able to express,
Jeff: especially concepts where you have to process strings in very precise ways.
Jeff: In a lot of ways, a lot of searches is... If you ever do these leak code problems,
Jeff: there's so much string processing.
Jeff: And having more expression really helps you to make the code very clear about
Jeff: some very potentially complicated ways that you process strings.
Matthias: Which leaves us with Kotlin versus Rust.
Jeff: Right, right. And so...
Jeff: We saw, like, there was this, I think there's a very famous blog post.
Jeff: If you go on Hacker News and look up, like, Rust or migrating to Rust,
Jeff: I think the first result is always this one about Discord moving from Golang to Rust.
Matthias: Yeah.
Jeff: And so we, it almost sort of motivated us to see, like, oh, they had occasional
Jeff: garbage collecting issues.
Jeff: And even working at like other companies where we use Scala and the JVM,
Jeff: like there was consistently like issues with like the JVM and like the garbage collector.
Jeff: And, you know, there's so much innovation around the garbage collector.
Jeff: But we knew like for a lot of what we were doing, text processing and indexing,
Jeff: things like that, we're going to store large data structures just in memory.
Jeff: I know there's like these concepts of like off heap memory, but that's already
Jeff: sort of off the happy path of the language we're using. So we're almost like
Jeff: putting a barrier or like something impeding us before we even got started.
Jeff: So we really did want to have something where we had a lot more control over the memory.
Jeff: But we also didn't want a language like C or C++ where you sort of have to expect
Jeff: developers to understand these like concepts.
Jeff: Like they still need to understand these concepts to some extent.
Jeff: But it's you have to be really really up front and like be very almost very
Jeff: very strict about these things so that would require significant like senior
Jeff: engineering talent within that had like c and c++ knowledge which we didn't have.
Matthias: There's a lot of ceremony around allocating and deallocating memory and in c
Matthias: not so much in c++ nowadays but definitely in c still and when you say garbage
Matthias: collectors yeah that is also true for both go and kotlin or java to a wider extent,
Matthias: I remember that in the past, we ran a very large Elasticsearch cluster,
Matthias: and those were different times.
Matthias: We tried to migrate that to containers, and it wasn't really easy because operationally,
Matthias: Java had some unfortunate default decisions where it would try to allocate as
Matthias: much memory as it could possibly get on the machine.
Matthias: And if it's co-hosted with a lot of other services on the same machine,
Matthias: that sometimes caused some problems.
Matthias: So did you also run into, or did you also consider these kind of concerns,
Matthias: the operational part of it, the deployment process?
Jeff: I guess specifically for, you know, how you mentioned Elasticsearch,
Jeff: actually one of the things that, you know,
Jeff: also sort of bit us and also why we decided not to use a JVM language was the
Jeff: fact that we did have to maintain an Elasticsearch cluster to power geocoding
Jeff: with our, you know, old iteration.
Jeff: Of the geocoder.
Jeff: And we realized we just had to put everything on one machine,
Jeff: which is still the case, but we didn't even use really the sort of distributed
Jeff: aspect of Elasticsearch because of the nature of the workload.
Jeff: It would just end up, you know, essentially fanning out all the queries to all
Jeff: the nodes, even though they're sharded.
Jeff: So at that point, we just essentially just got one really like fat box and...
Jeff: All the shards of the Elasticsearch cluster just lived on one box.
Jeff: So it almost defeated the purpose of that.
Jeff: And so, you know, maybe this is more of a design thing, more so than Rust.
Jeff: But, you know, that motivation of, you know, Elasticsearch was,
Jeff: you know, contains, let's say,
Jeff: a bunch of geodata and like addresses and places and things like that.
Jeff: And there were a couple of other microservices that we had powering our old geocoder.
Jeff: What we really wanted was not just like a deployment story that was simple for
Jeff: essentially the binary, but our data assets as well.
Jeff: And so what that meant was that,
Jeff: It would be much simpler where the old world is essentially,
Jeff: oh, hey, I want to do a migration.
Jeff: And, you know, developers deal with this all the time. If you want to do a database
Jeff: migration, you essentially have to reason about what's the existing state of your database.
Jeff: You know, do I want to introduce a column? You know, can my or you can't you
Jeff: got to make sure that maybe everything can handle null to begin with.
Jeff: And then, you know, maybe you have like a state change. Maybe you want to increment something.
Jeff: So you have to understand that the state of your database looks like this.
Jeff: You're going to apply this operation. What happens if your database script fails?
Jeff: Then you've got to code in this concept of idempotency where you can rerun the
Jeff: script many times. And that's a lot of things to reason about.
Jeff: So in terms of a deployment story, for sure, we wanted something that was very simple to deploy.
Jeff: And Rust just gives you a simple binary. And, you know, we essentially compile
Jeff: it in CI and essentially ship up the binary to our servers.
Jeff: But also the data assets, we wanted it all to be, you know, self-contained within the same server.
Jeff: And even the way that we process it, actually, we rebuild the data sets from scratch.
Jeff: We never backfill anything. We just take all the raw sources and then,
Jeff: you know, distribute the compute with something like Spark.
Jeff: And essentially compile it to, you know, some data assets.
Jeff: And there are some things that are more specific to, you know,
Jeff: the data formats that we use on our server.
Jeff: So we process those later and then we ship those data assets to all of these boxes.
Jeff: And so, you know, what that means is because everything is self-contained,
Jeff: it's actually very trivial to roll back, which is something that you might not
Jeff: be able to do if you had, say, like a third, you know, like if very simple,
Jeff: like two-tier architecture, even a web app and a, say, SQL Server.
Jeff: If you do a data migration...
Jeff: That you have to reason about the data migration roll back and forward,
Jeff: as well as the binary data roll back and forward.
Jeff: But with our new service, it all sort of goes in one package and lockstep.
Jeff: So if you need a rollback, you just switch everything over and all the data
Jeff: pointers also switch back.
Jeff: And so that's a way to roll back. And you don't have to reason about these many
Jeff: states. It's just one self-contained thing.
Jeff: And for that to work, you really do need something that's like very efficient,
Jeff: essentially both in because they're shipping such you know so many data assets and.
Matthias: I see that's an aspect that i never heard before you because Rust is so fast
Matthias: you can afford to simplify operations by doing more at startup but it's still
Matthias: performing so you can cut some corners thanks to Rust.
Jeff: Right, because it's almost like, hey, you don't even need an external database
Jeff: for something like you would typically grab for in web apps like a Postgres or MySQL.
Jeff: It's, hey, I'm going to use an embedded database or have a large in-memory index,
Jeff: and that's your sort of state.
Jeff: And so all that ships together in one whole unit or package.
Matthias: What do you use for the storage layer?
Jeff: So we use a couple of things. And so we talk about this in the blog post that describes Verizon DV.
Matthias: And we link to it in the show notes. It's a really, really nice write-up.
Jeff: Yeah. I would say our primary storage mechanism is this thing called RocksDB,
Jeff: which is an embedded storage or embedded database.
Jeff: And the way people think about it is it's essentially the database that you use to build databases.
Jeff: So, for example, Facebook or Meta,
Jeff: they originally used this to power the storage layer of MySQL for them.
Jeff: And I think there's a project called MyRocks, MongoDB, for example.
Jeff: They actually used RocksDB for some time. If you look at CockroachDB,
Jeff: their storage layer for a long time was also RocksDB.
Matthias: Same for InfluxDB.
Jeff: Right. There's so many projects around there and so much community backing that
Jeff: we felt it was such a mature project that we could use it for our purposes.
Jeff: I know for sure there are a lot of Rust crates now, things like,
Jeff: I believe, SLED, stuff like that.
Jeff: There's many people who write these sort of embedded databases.
Jeff: And essentially, RocksDB is this data structure called a log structure merge tree.
Jeff: And it's really designed for high write throughput, which is sort of different from our use case.
Jeff: But as I mentioned before, technology is so cyclical where, you know,
Jeff: if somebody builds a database that's like high write throughput,
Jeff: well, they actually adopt a lot of these concepts and ways to tune it so that,
Jeff: you know, it's also very well tuned for read throughputs.
Jeff: And so we just felt that, yeah, that, you know, community backing and the sort
Jeff: of, and it's a project that's written not in Rust, right? So that was a sort of another nice thing.
Jeff: We had all the Rust bindings to RocksDB. and it
Jeff: was very simple like integration to be
Jeff: able to just pull in that project and that
Jeff: is our sort of primary storage layer for you
Jeff: know all of our entities so addresses places and
Jeff: different regions and so it serves you know a number of different purposes so
Jeff: obviously like primary key fetches so when our services have say like an event
Jeff: and they have an id for a place They'll fetch that from our service,
Jeff: but we also index it in a way that makes it really easy to do geo lookups.
Jeff: So given this lat long, I want to
Jeff: be able to fetch all the relevant geo entities. So am I inside the city?
Jeff: Am I inside this country? Things like that.
Matthias: RocksDB is very fast and very write
Matthias: focused but also it's effective in
Matthias: terms of storage and i guess that plays in your favor because if you try to
Matthias: geocode the world you need a lot of storage and on top of it once the storage
Matthias: is quite optimized you get really decent cache locality on top of it for free,
Matthias: So it might have been a really great choice.
Jeff: Yeah, there are a lot of nice aspects about a log structure merge tree.
Jeff: And I think most modern database implementations use that in some shape or another.
Jeff: And it's largely this concept of, obviously, there's so much engineering around
Jeff: it, but everything is sorted.
Jeff: So that gives you a huge advantage. And like that is something that many people take advantage of.
Jeff: So in our blog post, we talk about, you know, very fast geo lookups using this
Jeff: library called S2, which is essentially a geo hashing library.
Jeff: And so what that means is you have a latitude and you have a longitude.
Jeff: That's two dimensions. Right.
Jeff: And so it's not clear at first how you can use sorting to help you make lookups faster.
Jeff: And so, I mean, there is literally a thing called geo hashing.
Jeff: And there are other like implementations such as from Uber, there's this thing
Jeff: called H3. Ffrom Google, there's this thing called S2.
Jeff: And essentially it collapses, you know, the latitude and longitude into a single
Jeff: 64 bit or a U64, I guess, in Rust terms.
Jeff: And it has many nice properties because it tends to be the case,
Jeff: obviously there's boundary conditions because latitude and longitude and they
Jeff: go from negative 180 to 180 and negative 90 to 90.
Jeff: So there are some boundary conditions to take into account. But for the most part.
Jeff: You maintain because of like, you know, somebody who's smarter than me who came
Jeff: up with this thing called like using a Hilbert curve, you have a locality with adjacent IDs,
Jeff: which means that things that are close to each other will be,
Jeff: you know, if you sort it will be next to each other.
Jeff: Obviously, you know, barring some some boundary conditions, but that fits really
Jeff: well into a system that has, you know, things sorted like a log structure merge tree.
Jeff: So you're able to make very efficient range and geo queries from from something like that.
Matthias: And all of that combines into a very efficient single binary lookup service
Matthias: what do you use for the fuzzy searching part that you mentioned.
Jeff: Right so this is more related to the forward geocoding side which is you know
Jeff: essentially translating your text query into some sort of, you know, geo entity.
Jeff: And so one of the requirements we had to deal with was essentially being able
Jeff: to handle a little bit of typo tolerance from our address validation service.
Jeff: And that comes in many different forms. Like there's so many like sort of failure
Jeff: cases for search, which is a little bit different from like more typical web applications.
Jeff: It's like you click through a couple of things and that you expected this
Jeff: really like all the different use cases are
Jeff: literally every type of single character that a user can type those are all
Jeff: the potential use case so the cardinality is is is extremely high and essentially
Jeff: the number of failure cases is is almost unbounded in some sense there's there's
Jeff: just so many combinations that at that point like there's so many ways to to type something in,
Jeff: So we deal with fuzzy search in a couple of ways.
Jeff: We use a library called FST. And I remember there's an episode you had with
Jeff: Charlie Marsh from UV. And I think...
Jeff: There's an engineer who works there now. I only remember his GitHub name because
Jeff: it's very memorable, like burntsushi.
Jeff: But he works at UV, if I remember correctly.
Jeff: And he's come up with a lot of really interesting Rust crates.
Jeff: And I think he even implemented the regex or did the regex implementation of Rust.
Matthias: Yeah, exactly. Jonathan Gallant.
Jeff: Right. And yeah, so we make a lot of use of his libraries. but FST is essentially a character graph.
Jeff: And so there's this concept of like a try that's very typically used for prefix queries.
Jeff: And so you can sort of think of an FST as like a try where all the prefixes
Jeff: that are shared compress, but it also compresses the suffixes.
Jeff: So now you have almost like double compression, right? And essentially...
Jeff: Doing text lookups is a traversal of the graph.
Jeff: And you can see how that sort of primitive lets you do many things.
Jeff: It lets you implement like a regex because the regex sort of works the same way.
Jeff: And so for fuzzy search, you can implement like Levenstein distance by essentially
Jeff: keeping a way of dropping or like if you type something incorrectly.
Jeff: You can have like certain thresholds that, We use an edit distance of one because
Jeff: more than that, it's essentially combinatorially expensive.
Jeff: And we have other techniques for typotolerance.
Jeff: But we use this library essentially for, one, obviously prefix search.
Jeff: But then two, it does have some built-in ways to do 11 sign distance,
Jeff: which we're actually starting to move off of a little bit.
Jeff: Because now we're actually, as the project is starting to succeed,
Jeff: we're getting more queries.
Jeff: And so because you know what users typed and what their end result actually
Jeff: was, we're able to, at scale, sort of figure out, oh, these typos actually map
Jeff: to this type of, this actual correct spelling.
Jeff: And so we're able just to do those lookups much quicker. But the funny part
Jeff: is for some of these cases, we actually also indexed that into the FST.
Jeff: So in a lot of ways, the FST is almost like You can almost think of it as a
Jeff: hash map or maybe even a B-tree map of a string to a U64.
Jeff: It's maybe a compressed version of that. But more than that,
Jeff: it's really just a way to cache high cardinality text in a very compressed way.
Matthias: Yeah. The way I always think of an FST, and I might be wrong here,
Matthias: is it's a very fast state machine for looking up,
Matthias: the existence of words very efficiently and very quickly.
Matthias: So you mentioned the tri-data structure that is similar where it stores all of the inputs in a tree,
Matthias: but it knows when there is no possible way for a word to exist in the data storage
Matthias: because you reached a leaf node in the tree and there are no child nodes.
Matthias: So you know, for example, but this is not a hit in your data structure.
Matthias: And in your blog post, you mentioned a few other crates.
Matthias: We just wanted to quickly do a quick shout out here.
Matthias: 10TV would be one, LightGBM, and FastText. What are these?
Jeff: Right, so I'll give a quick rundown of these. So for any sort of search system,
Jeff: the most fundamental data structure is this thing called an inverted index.
Jeff: So that implies like a forward index. So maybe I'll explain what that is first.
Jeff: And so forward index is more like a traditional database. So record one maps
Jeff: to Broadway, record two maps to Prince Street.
Jeff: The inverted index sort of switches that around. So you first tokenize,
Jeff: and that is its own whole topic.
Jeff: People research on how to tokenize text, especially with all AI and machine learning trend now.
Jeff: But you can then say, oh, Broadway, the token maps to ID one and then prints
Jeff: maps to document two and street maps to document two.
Jeff: So when you type in prints, then it's a I mean, it's not a hash map in these
Jeff: implementations, but essentially you just look up the word prints and then you
Jeff: get all the documents that are related.
Jeff: And so there's, once you have these documents, you can sort of perform these
Jeff: set operations to essentially narrow down which documents are relevant.
Jeff: And then there's, you know, Tantibi offers this thing called BM25,
Jeff: which you can think of it as like TFIDF.
Jeff: But essentially, once you have these documents.
Jeff: And this is the difference between a database and a search engine.
Jeff: How do you essentially rank which of these documents is most relevant?
Jeff: I mean, that is its own, you know, that is its own, like, sort of,
Jeff: there's a lot of work around figuring out what is the most relevant.
Jeff: I mean, it's different for every company and every use case.
Jeff: So Tantivy, you know, that's a library that came from, I think,
Jeff: these people from France.
Jeff: And they were building essentially, it's funny, it's an Elasticsearch replacement,
Jeff: which is, we've been talking a little bit about that, called QuickWit.
Jeff: And so there's just a lot of primitives that, you know, that came along with
Jeff: this sort of Rust ecosystem. And that was one of the libraries that really drew us to using Rust.
Jeff: We're actually using, we're migrating to a different implementation that doesn't
Jeff: use any of these libraries now.
Jeff: We use this thing called Roaring Bitmap, but it's the same concept.
Jeff: And we're doing that largely because of sort of the more structured nature of
Jeff: some of the geoentities we have.
Jeff: You know, we have addresses and regions and people tend to type addresses in
Jeff: a certain way. So we can take more advantage of that and fine tune how we do our search workloads.
Jeff: But at the core of it really is this concept of an inverted index.
Jeff: So that is, I would say, the core of geoconing.
Jeff: And then we can talk a little bit about light GBM and fast text.
Jeff: And these things always move very quickly.
Jeff: So we're actually considering moving off of these libraries,
Jeff: but we're still doing, you know, doing something that would serve what these libraries do.
Jeff: And so light GBM is a gradient boosted tree.
Jeff: I think if you take any basic machine learning courses, you'll learn about decision
Jeff: trees. So the concepts are really the same.
Jeff: And essentially, it's a way to do a couple of different functions versus classification.
Jeff: So if I receive an email, does it seem like a positive sentiment or a negative
Jeff: sentiment or a neutral sentiment?
Jeff: It does interpolation.
Jeff: So given the name and the country and I don't know, the sports that somebody
Jeff: does, try and guess their height. You know, it's like, you know,
Jeff: four feet to, I don't know, seven feet, something like that.
Jeff: And that's interpolation.
Jeff: It does learn to rank, which is particularly interesting.
Jeff: And as I mentioned, we do, you know, from the inverted index,
Jeff: we do ranking, which in some sense is like really just a primitive of classification.
Jeff: But essentially what it's saying is like, given this list of entities,
Jeff: which one has the highest rank and which one has the lowest rank?
Jeff: And you can really just think of that as like pairwise comparisons.
Jeff: So like if I'm given, if I type in 841 Broadway and I'm in this latitude and
Jeff: longitude, is it referring to 841 Broadway in Brooklyn or 841 Broadway in Manhattan?
Jeff: And so that is essentially what
Jeff: Learn to Rank is, but you can apply it to more entities than just two.
Jeff: But really it is just sort of classification if you think about it.
Matthias: There's a Broadway in Brooklyn? Yeah.
Jeff: Yes, there is. I think when you start to learn about the world,
Jeff: I don't think people are really all that creative with naming things.
Jeff: So it's not just programmers that have problems with naming things.
Jeff: Everybody has those issues.
Matthias: Nice. Well, it's just a wide way. It's just a wide street, so it totally makes sense. Right.
Jeff: It is also a very wide street in Brooklyn, so we consistently have issues with
Jeff: people trying to figure out which Broadway we're talking about.
Matthias: Okay, we have all of those libraries. Just to recap that part,
Matthias: when the service boots up, it starts to ingest all of that data that is more
Matthias: or less stored in some flat storage.
Matthias: You start to ingest it, you start to build your, let's say, understanding your
Matthias: model of the world, quite literally.
Matthias: And then you have that highly efficient lookup functionality.
Matthias: And through the API, then you can find addresses really quickly and map addresses
Matthias: to certain geolocations and maybe even vice versa if you needed to.
Jeff: Right.
Jeff: Yeah, and you can already see that because there are so many of these assets,
Jeff: the startup time does take a little bit of a hit.
Matthias: Can you roughly tell us how long it takes?
Jeff: So we download all these assets in parallel from S3, and we do actually try
Jeff: and sort of cache these assets.
Jeff: So we deploy in Kubernetes, and generally when we're making new releases,
Jeff: only a couple of things change, like, oh, maybe you only updated places.
Jeff: So we only need to pull those changes from S3.
Jeff: And so it's maybe like, couple minutes
Jeff: but really like the future of this is we want
Jeff: to get it to you know less than a minute or or even
Jeff: like in in like 30 seconds or so and so
Jeff: this is another area where i think Rust and like having and like all the work
Jeff: around the data infrastructure area where like a lot of like before it was like
Jeff: a lot of these java services from all the apache projects they're all using
Jeff: java we're seeing like a whole ecosystem of these data infrastructure pieces
Jeff: is being moved to Rust or like.
Jeff: And so one of those things is we do want to start to separate the storage and
Jeff: compute in a way that our database can start to come up right away or download
Jeff: the minimum amount of assets.
Jeff: And the fact that we almost like memory map some of these like assets,
Jeff: you can actually translate, you know, that pretty, in a pretty straightforward
Jeff: way with S3 because it offers like a range API.
Jeff: And because like people have built libraries to essentially cache S3 on disk,
Jeff: what we're thinking about is we're going to build a storage layer that almost caches S3.
Jeff: And then while the surface is booting up and hasn't pulled in the assets to the local NVMe disk.
Jeff: It can temporarily sort of pull in ranges of bytes from these storage services
Jeff: so it can immediately start serving queries.
Jeff: Obviously, there's going to be a latency hit, but in terms of being able to
Jeff: deal with things like, oh, we have a traffic spike, that's sort of one of the
Jeff: problems we're trying to solve.
Jeff: And I think the fact that there's so much development around data infrastructure
Jeff: projects and we use Spark at Radar and so many companies use Radar.
Jeff: Just this whole concept of data infrastructure in the cloud and using object storage.
Jeff: We're seeing new streaming frameworks written in Rust or a lot of these new
Jeff: iceberg tools in Rust and that's going to help us a lot for building something
Jeff: where we want to separate.
Jeff: Or it's going to accelerate essentially what we want to build where we separate storage and compute.
Matthias: How long did it take you to build and ship the first version of HorizonDB?
Jeff: Right. So as I mentioned before, like our first use case was address validation.
Jeff: We had a customer who was asking for it, like, and we built it in.
Jeff: About a month actually i think less than that like
Jeff: to actually get something working but to get it closer to like full production
Jeff: with this customer maybe it was like two months but it was like with a lot of
Jeff: qa and like a lot of feedback things like that but i would say it took about like two months did.
Matthias: You have a lot of outages due to Rust production outages.
Jeff: Not really one was because we were only onboarding a single customer and like
Jeff: the qps wasn't like that high to begin with and two because we had this property
Jeff: of everything was sort of self-contained,
Jeff: it was very trivial for us to do blue green deploys which also includes the
Jeff: data as well so like hey you process the string in in a wrong way and you're
Jeff: starting to see that you just flip it back to the the previous service and it's
Jeff: all self-contained whereas that might be the harder to do with like a single
Jeff: like backing database or things like that can.
Matthias: You even remember a single outage or a single error or a panic in production with with Rust.
Jeff: Yes so i i will say there's we do make use of this geo library from Rust which
Jeff: is very popular um and one of the top issues is that it panics and doesn't handle,
Jeff: It doesn't handle errors, which is like unrest-like, I guess.
Jeff: We have this service called Sentry that we use for error logging.
Jeff: And there's essentially no exceptions normally apart from that library.
Jeff: But typically, we don't see stack traces.
Jeff: We do see outages. And that's just due to spikes or essentially queries of death.
Jeff: And there you know we can there's a
Jeff: whole podcast to talk about like reliability and things like that but
Jeff: the service itself is pretty efficient and our our
Jeff: rewrite of of the search indexes is going to make the service even faster and
Jeff: as i mentioned with like the you know storage and compute separation that's
Jeff: going to introduce like another level of scalability and like being able to
Jeff: handle like spikes in a way that yeah generally i would say like if we're looking at the proportion,
Jeff: and really there's two main backend servers.
Jeff: There's our API server, and then HorizonDB.
Jeff: I would say there are not significant amount of outages from that.
Matthias: And talking about scale, can you give us a few numbers, number of requests,
Matthias: number of notes, et cetera?
Jeff: Right. So at a steady state, we're looking at about 18,000 queries per second.
Jeff: That's a lot of queries. Yeah, I would say it's a lot.
Jeff: Maybe it's at other companies, it's not super high because there are some cases
Jeff: where things will fan out and suddenly you get hundreds of thousands of TPS.
Jeff: But yeah, it's enough to know that like if you made like a certain optimization,
Jeff: like you can quickly tell if things went right or went horribly wrong.
Matthias: How many nodes do you need to handle that traffic?
Jeff: Right. So we have 30 nodes. It's significantly over provision now,
Jeff: which is why we're looking into like how we can be more efficient about dealing with spikes.
Jeff: We already actually shard out the database servers by different use cases and
Jeff: by different tiers of customers because we are a SaaS company just to reduce
Jeff: or essentially just to isolate certain workloads and prevent outages from bad
Jeff: query from one customer affecting others.
Jeff: So all that's to say is we are quite over provisioned there, but we're working on it.
Matthias: Well, it's great. You could do with less. That's always a good thing that managers
Matthias: want to hear because saving costs becomes much easier if you can't just shut
Matthias: down some of those nodes if you don't need them at the moment.
Jeff: Yeah, that's right. Cost cutting is like a, I wouldn't say it was the primary
Jeff: thing for getting this started, but we did see a lot of benefit from that.
Jeff: So even running 30 nodes, we're able to replace a number of Elasticsearch instances.
Jeff: And we represented geoqueries in many different ways, like denormalized across
Jeff: different stores like Redis and Mongo as well.
Jeff: And then in total, I would say actually even with the 30 nodes and the over-provisioning,
Jeff: we probably saved maybe...
Jeff: Mid to high five-figure monthly spending for some of these things.
Matthias: Impressive. How many queries per second does one box do, and how much CPU does it use, roughly?
Jeff: Right, so on average, which is a misleading metric, because for geocoding,
Jeff: which is search, is a very different workload from reverse geocoding.
Jeff: We do 600 queries per second per box, And it's about 20 to 30% CPU at the steady
Jeff: state, which means it can go higher.
Jeff: And I would say that, you know, our search workloads are probably like a 10x,
Jeff: sometimes even 100x of like reverse lookups as well as like primary key lookups.
Matthias: Would you say it's a rather CPU or compute bound problem or a storage or IO bound problem?
Matthias: Because on one side you have hashing which can
Matthias: be very expensive but maybe that's just a thing that you do at the beginning
Matthias: when you boot up and then it's not really as compute intense later on during
Matthias: operations or would you say well no actually that is kind of the bottleneck
Matthias: or would you say no the storage part is the bottleneck right.
Jeff: So i you know breaking it down into like the different use cases for geocoding
Jeff: which is search query reverse geocoding which is like a lat-long lookup and
Jeff: then maybe even like primary key lookups.
Jeff: I would say the latter two are more IO bound.
Jeff: Maybe you pay some cost of serialization, deserialization from some of the storage
Jeff: systems, which will change soon because there's a lot of very nice zero copy
Jeff: libraries from Rust. And so.
Jeff: The CPU-intensive queries tend to be of search.
Jeff: I would say it's actually both, because if you think about it,
Jeff: as I mentioned, this inverted index structure, you have to do many key lookups, right?
Jeff: You tokenize your query, 123 fake street, Brooklyn, New York.
Jeff: And in fact, there's many ways to express it in synonyms. Maybe you expand the
Jeff: query, and maybe instead of 123 fake ST, it could be street.
Jeff: Or if you know the users in Germany, it's Straße. and we haven't indexed or
Jeff: normalized everything in a certain way.
Jeff: So we do expand the queries and you can see how it can fan out to many keys being pulled back.
Jeff: And once you have all these candidates, you essentially have to rank them.
Jeff: And so there is a little bit of CPU intensiveness in that, but we're working
Jeff: on optimizing these things.
Jeff: And I will say that if you do decide to build this sort of analytics or search
Jeff: system, We're very big fans of this new approach with drawing bitmap,
Jeff: which is, it's actually an implementation that you see across many different languages.
Jeff: But we found, at least from the sort of candidate fetching, where we're essentially
Jeff: in the inverted index and trying to pull out which candidates match a criteria,
Jeff: those tend to be like microsecond operations for most of our geocoding queries.
Jeff: So that's why we're sort of moving over to a more like dedicated and specific system for our use case.
Matthias: Yeah. You said it yourself, lots of moving parts.
Matthias: What's the median latency of a forward geocoding request and maybe a reverse
Matthias: geocoding request in comparison?
Jeff: Yeah, so the median latency is about 50 milliseconds.
Jeff: And that's because when we were building this system, and we were seeing customer queries,
Jeff: we're seeing that most customers tend to enter the right thing more or less,
Jeff: like they tend to enter their address correctly,
Jeff: even if there's like some spelling
Jeff: mistakes, but they tend to have a more predictable sort of query pattern.
Jeff: And that's sort of why I describe the FST as a high cardinality text cache.
Jeff: Because almost everything, I would say 70% to 80% of the queries,
Jeff: especially for US and Canada addresses, will just hit the FST.
Jeff: And all of that, we have the sort of generosity of being able to store all of
Jeff: that in memory because it's so compressed.
Jeff: And Rust, we're writing in a way that's a single process and multi-threading
Jeff: for concurrency versus something like Node, which, you know,
Jeff: concurrency or like Python, where, I mean, there are starting to be thread concepts,
Jeff: but the classical way is just to have multiple processes.
Jeff: And then that means you need multiple copies of the data structure and memory.
Jeff: And so oftentimes we're hitting that. And those, at least that side of things,
Jeff: those operations are usually at most single-digit milliseconds.
Jeff: Depends on the query, but a lot of times we will see things show up in less
Jeff: than a millisecond for that side of things.
Jeff: For reverse geocoding, as I mentioned, we sort of.
Jeff: And to speed up your algorithms, oftentimes it's like, can you sort it or can you hash it?
Jeff: And essentially, we have hashed it by taking the S2 library where we convert
Jeff: the latitude and longitude, two dimensions, into one dimension.
Jeff: And that's essentially just a key that you look up in RocksDB.
Jeff: So many of our workloads look like that. And once it's like that,
Jeff: it's almost no different from a primary key lookup.
Jeff: It's just a key value lookup. So we're seeing less than a millisecond for those types of workloads.
Matthias: Nice. And all of that with how many lines of Rust code in total for the server
Matthias: implementation at the moment?
Jeff: Right. So in terms of our code base, it's about 150,000 lines,
Jeff: which I would say is actually not very much.
Jeff: And I haven't taken the time to analyze which code line is serving which use case.
Jeff: But I will also say, like, there is like a good percentage of stuff that's like
Jeff: kind of hard coded right now that we could probably, I think,
Jeff: to get like a minimal implementation, maybe like you could,
Jeff: when we first started doing address validation, it was like a couple thousand
Jeff: lines. It wasn't anything too big.
Jeff: So and that sort of speaks to like how expressive, you know,
Jeff: being able to express certain concepts in Rust is.
Matthias: Are there any tips and tricks
Matthias: that you could share with people who are planning
Matthias: to build a larger Rust application i'm
Matthias: thinking of composition patterns usage of traits how you structure your data
Matthias: data objects immutability anything that comes to mind that that you learned
Matthias: maybe that is uncommon in Ruby or Scala or any other language that you knew before?
Jeff: I would almost like take the approach of almost, especially when you're starting
Jeff: out, not to overthink these things.
Jeff: I do think that Rust still has like so many different concepts.
Jeff: And we're always like, honestly, as we're writing, I don't even feel like I'm
Jeff: an expert in Rust at all. Like I always learn something new.
Jeff: So with that in mind, especially like if you're first starting out with Rust,
Jeff: just try and get something to work and then sort of optimize after.
Jeff: Because I guess they always say like premature optimization, you know, is, is.
Matthias: It's the root of all evil.
Jeff: Basically, yeah. So try and get the simplest thing to work and then only apply
Jeff: design patterns if you're starting to find you're really repeating yourself
Jeff: or it becomes very finicky.
Jeff: I will say that, especially in this age of AI editors that will essentially
Jeff: copy and paste everything for you, I don't know.
Jeff: But yeah, that's the way to think about it is really just to,
Jeff: rather than take very high-level approaches where it can actually sort of inhibit
Jeff: or prevent you from being able to do the thing you want it to do,
Jeff: just do the simplest thing and then apply more optimizations or introduce more
Jeff: sort of design patterns as you start to see the problems arise.
Jeff: And then you really do get a sense of what problem you're trying to solve.
Matthias: Yeah, perfect. That's right down my alley. even in
Matthias: a geocoding sense because i recently wrote an article called be simple and i'm
Matthias: very much in favor of that unfortunately we're getting close to the end we had
Matthias: a blast so the time flew by the last question is what's your message to the Rust community i.
Jeff: Would say obviously keep doing what you're doing. I think the Rust ecosystem is very vibrant.
Jeff: And like, I think there's an interesting trend that I've seen where,
Jeff: and it's almost like hacker news driven, where it's like, oh,
Jeff: I built this service and it's written in Rust.
Jeff: But we're actually even seeing in not even like a,
Jeff: We're seeing that in almost a marketing approach for real businesses.
Jeff: There are so many new, interesting pieces of infrastructure that are becoming
Jeff: businesses that are open core.
Jeff: I wouldn't say it's fully open source because I think the open source peers
Jeff: would be, it really depends on licenses.
Jeff: But I think it's such a flexible programming language and it's very modern that
Jeff: you get a lot of these sort of productivity or enjoyment aspects that you would
Jeff: get from maybe some other like scripting languages traditionally that I would love to see, you know,
Jeff: more of these like businesses that are really like open source and open core
Jeff: to really inspire what you can really do with the language.
Jeff: And I would also love to just see more...
Jeff: More work around even just doing the sort of 80% of things that most developers
Jeff: are doing these days, which is really just having a nice web app experience.
Jeff: I think there's still a lot to do there.
Jeff: I know people brand it as an infrastructure or systems language,
Jeff: but it really is a very enjoyable language to use for many different use cases.
Jeff: Even like, I think, so not this instrument,
Jeff: but I know Electron, they're in sweden and they
Jeff: make like a lot of music production equipment and a lot of their code is written
Jeff: in Rust so like you you really see like all these like different aspects because
Jeff: like it's such a it's a language that's very expressive but on the other hand
Jeff: it lets you get really deep in the weeds and so it lets you do so many things
Jeff: so i i would love to see like more,
Jeff: you know support and work around even just like basic things like wet like a
Jeff: lot of like web apps like who knows maybe there will be like a rails for Rust
Jeff: in the future that would be super interesting there's loco rs yeah i guess that's true
Matthias: Jeff,
Matthias: that was amazing thanks so much for taking the time today.
Jeff: Yeah likewise it was a very fun chat
Matthias: Rust
Matthias: in production is a podcast by corrode it is hosted by me Matthias Endler and
Matthias: produced by Simon Brüggen for show notes transcripts and to learn more about
Matthias: how we can help your company make the most of Rust, visit corrode.dev.
Matthias: Thanks for listening to Rust in Production.