Product for Engineers is PostHog’s newsletter dedicated to helping engineers improve their product skills. Subscribe for free to get curated advice on building great products, lessons (and mistakes) from building PostHog, deep dives on top startups, and very cute hedgehog illustrations.
A cross-platform library that commands the GPU. It encapsulates common GPU functionality with a low-level cross-platform interface. IGL is designed to support multiple backends implemented on top of graphics APIs like OpenGL and Vulkan with a common interface.
Valhalla is an open source routing engine and accompanying libraries for use with OpenStreetMap data. It also includes tools like time+distance matrix computation, isochrones, elevation sampling, map matching and tour optimization.
Join thousands of other open-source enthusiasts and developers in the Open Source Hub Discord server to continue the discussion on the projects in this week's email!
🎙️ Interview With Kevin and David of Valhalla - Open source routing engine for OSM
Kevin Kreiser and David Nesbitt
Hey Kevin and David! Thanks for joining us! Let us start with your backgrounds
Kevin: I’m from a tiny village called East Hanover in Pennsylvania. I got interested in programming and started learning it seriously in 2000 when I was in 11th grade thanks to a teacher who happened to also be a graduate professor at Penn State. Fresh out of a comp-sci undergrad program at Millersville, I started out in graphics programming building “video games for surgeons”. From there I went into a PhD program at the University of Delaware but dropped out of that to join Dave at MapQuest. Since then I’ve been working on mapping as a sub-genre of comp-sci ever since. Over the years I’ve worked at Mapzen (where we created Valhalla), Mapbox and now at Snapchat. C++ was my first language, has been my primary language throughout my (15 year) career and is still my favorite language by far though I like to use python and bash when the situation calls for it.
David: I am from Lancaster, Pennsylvania and now live near Port Deposit, Maryland. I’ve been in the software industry for over 40 years. I started at The Johns Hopkins University Applied Physics Laboratory doing mapping and computer graphics work while developing prototype naval command and control systems for nearly 18 years. I also taught Computer Graphics for the Johns Hopkins University Engineering for Professionals masters program for over 20 years. I spent nearly 15 years at MapQuest leading development of their driving directions software. I then moved to Mapzen, which is where we started Valhalla, and then to Mapbox (which uses Valhalla). I now work at Hammerhead Navigation (part of SRAM), developing mapping and navigation systems for bicycle head units - also using Valhalla.
I have worked with C++ for most of my career, and it is by far my favorite development language. Python is quite useful as well.
What happened to the video games for surgeons?
Kevin: It was a start-up called verify technologies. It was mildly successful in the US for a while, but eventually wasn't able to compete with other US companies that not only had the software but also had hardware patents on the bits you needed for simulating the instruments the surgical residents used to train with.
What’s your most controversial programming opinion?
Kevin: node.js is a psyop
David: I’m not sure it is controversial, but event driven software is difficult for me. No matter how hard I try, RxJava just baffles me. There must be better ways!
I also have never been a fan of XML and JSON as data transfer mechanisms. In Valhalla, we use protocol buffers, which are much more efficient.
What is your favorite software tool?
Kevin: I’ve been really liking CLion and really all the JetBrains tools lately regarding software development.
David: I’ve been doing Android programming lately and appreciate Android Studio. However, I’m old school though and still mostly use vi for C++ development, with occasional use of Visual C++. Maybe it is time to try CLion.
Why was Valhalla started?
Kevin: Mapping solutions generally need to provide three separate but interconnected high-level bits of functionality. Those are: Search, Display and Routing. Valhalla was meant to solve the latter at an open source mapping API start-up called Mapzen which was run out of the Samsung Accelerator program (a start-up incubator). At the time the open source routing engine scene was still fairly young which allowed us (the team that conceived of Valhalla) the opportunity to build one from scratch by focusing on a few novel primary features not seen in competitors.
David: When Valhalla was started, there were many routing solutions handling driving routes pretty well. However, other modes of transportation were second class citizens. Bicycles, pedestrian, motor scooters, and mulit-modal routing didn’t have the support and quality as automobile routing.
How does Valhalla work?
Kevin: This is quite a difficult question to answer simply because of the scope of the project but I’ll give it a try. Valhalla may likely be best understood by some of its design goals/philosophies coupled with a description of some of its components. Valhalla is a C++ library which provides a number of APIs centered around the key problem of routing, directions and wayfinding. The library is accessible via python bindings, an HTTP api or by calling the C++ library directly. The library is divided into several core bits of functionality:
Data-processing - to turn OSM data into a compacted and normalized graph
Routing - finding a path through the graph at run time
Directions - annotating that path with maneuvers and natural language descriptions of how to follow the path
The data processing is done offline and consists of pulling in OSM-formatted data, elevation, transit, historical traffic patterns or other data sources and building a graph that we can route on. Routing and directions are performed at request time.
Design-wise, Valhalla uses a tiled hierarchical data structure to store the graph. Each tile adheres to a custom binary format that requires (almost) no parsing. This allows Valhalla to memory-map the data and do a little bit of pointer arithmetic to facilitate graph searches. Tiles also lend themselves well to smaller footprint devices like cell phones.
Once a path is found it is annotated with maneuvers and text descriptions and the route itself is serialized to JSON (or protocol buffers) for the client/caller to consume in their application.
There are lots of different APIs apart from the typical A to B “shortest path” algorithm. Additionally, Valhalla supports real-time traffic conditions, adheres to time of day restrictions and allows for a large variety of customization of the “type” of route at request time.
David: I will add to what Kevin states above. While Valhalla does not directly support navigation along a prescribed path (generated from Valhalla’s routing methods), the information from Valhalla readily supports navigation and guidance. Valhalla’s maneuver generation (calling out where turns require guidance to the user) and directions are first class. Also, many commercial mapping data sources focus on driving. OSM (until recently) has had much better support for pedestrian and bicycling than commercial sources, and Valhalla enhances the ability to route and navigate for these travel modes.
How does Valhalla support real-time traffic conditions and adhere to time of day restrictions?
Kevin: The algorithms support tiled real-time data sources that, if present on the machine where the services are running, will be used to influence the computed route. We do this by creating a tar file which has real time tiles in it, initially blank. Then it is the system integrators job to write a process that updates the tar file on the fly. The routing process has this tar memory mapped, and the "sidecar" process also memory maps this same tar for writing updates.
We leave the process of getting those updates from whatever traffic data provider up to the person administrating the service. Since there are infinite ways the data could look or be delivered, it's best not to have too much of an opinionated stance there and let that up to individuals and their specific project needs.
Who, or what, was the biggest inspiration for Valhalla?
Kevin: I had been working at MapQuest with Dave and the rest of the Valhalla team for around 6 years. For the first 2 years I worked on the routing side of the maps API equation, but for the remaining 4 years I had been the lead developer on the display side creating visual map tiles that the end user would see. Unfortunately, MapQuest decided it wanted to relocate its primary development office out of Lancaster, Pennsylvania (where it was founded) and focus more on its office in Denver, Colorado. At that time Mapzen was looking to expand its offerings to include routing so we decided to join and become the team supporting that effort.
Divide and conquer is an old idea. If you can break a problem into many smaller easier to solve problems, and solve them individually, then getting the full solution is only a matter of scale. Not surprisingly, mapping, especially the display part of the problem, exploits this design paradigm. Specifically, we break the visual map into tiles and send those to the client/caller who wants to display them. In this way they can decide on how much of the map they want to see to some level of granularity, they can decide on the level of parallelism they want to use in fetching the tiles, and they can use the tiling (since its a uniform grid) as a cache key to avoid having to always fetch data if its data they had fetched before.
I suggested to Dave that when we join Mapzen we should consider tiling the graph; meaning we would chop the graph into a uniformly gridded (spatially) set of data blobs. He and I then briefly talked about how such a data structure could exist and maintain a proper topology. Mapzen was an open source company so we knew it would be open. Dave’s experience in routing made it clear that there had to be some degree of hierarchy in the graph structure (for performance reasons). This is when Dave said to me “We should call it T.H.O.R.: tiled hierarchical open-source routing”. To which I said, “there’s going to be a lot more components, we should call it Valhalla and each piece can be one of the Norse mythological figures”.
David: THOR was just one of the components of Valhalla - there are other code directories (not really libraries, rather groupings of code under the Valhalla umbrella) that we named with the Norse theme. Valhalla ties it together under a single repository. Kevin answered this quite thoroughly. Kevin’s idea of tiling the routing graph is a crucial part of Valhalla. It is a key differentiator and one that allows Valhalla to be successfully used in mobile environments.
Are there any overarching goals of Valhalla that drive design or implementation? If so, what trade-offs have been made in Valhalla as a consequence of these goals?
Kevin: There are several “requirements” that we adhere to as far as design/implementation goes:
It should run on very modest hardware (Raspberry Pi, old android phones) with very modest resources
The graph should contain general attribution so that at request time we can customize what makes the “shortest path” by weighting the graph attributes differently depending on request parameters
The router should work with an incomplete graph (if you are missing tiles the router will still route)
Data will remain backward and forward compatible within the same major version
The primary trade-offs we’ve hit so far are not being able to change around the graph data structure so that we don’t break data compatibility. We also trade run-time performance for the sake of request-time customizability.
David: The idea of tiling the routing graph has been key to allowing Valhalla’s use in mobile navigation applications. At Hammerhead, we have successfully used Valhalla for bicycle routing and navigation on custom Android hardware with modest processing power, memory, and storage.
What is the most challenging problem that’s been solved in Valhalla, so far?
Kevin: It’s a very imprecise answer, but the final composition of all the parts that make the final user-facing API is the most significant problem that the software solves. There is incredible complexity in tying all the pieces together in a coherent and usable way I’ve already mentioned some, but there are a lot of discrete pieces:
The offline ETLs (there are at least 5 different data sources we combine)
Online ETLs for real-time traffic conditions and incidents
The system for customizing the path finding to match the users request-time preferences
Supporting like 8 modes of travel on a single dataset
The spatial indexing system so we can find candidate edges in the graph given input coordinates
The 8 different graph traversal algorithms that accomplish different tasks on the network
The maneuver generation and system for localization the narrative that go with a given maneuver
Different serializers depending on which of the 8 different APIs you called
The operational design and componentry that ensures request isolation for maximal server stability
David: I’m not sure if it is truly solved, but developing a solution for isochrones was challenging and interesting. Isochrones allow a visual representation of where one can travel within specific time increments.
Are there any projects similar to Valhalla? If so, what were they lacking that made you consider building something new?
David: The closest I can think of are OSRM (Open Source Routing Machine) and GraphHopper.
OSRM is open source and very fast/efficient for solving many routing problems. However, it is not readily usable on low-end systems and mobile devices. Also, it is not very flexible - if you want to adjust costing (which is key to determining the lowest cost path) you have to regenerate the data. So it trades off customization and flexibility for high performance.
I’m not sure how much of GraphHopper is open source. It was somewhat mature when we started Valhalla. It is written in Java and has some customization as well as more performant options similar to OSRM. The main drawback compared to Valhalla is that it isn’t tailored to mobile environments. I think they supported an Android build at one time, but later they dropped support.
What was the most surprising thing you learned while working on Valhalla?
Kevin: Memory-mapping is one of the most useful tools that kernel designers ever thought of and I thank them every day for it. It allows you to do amazing things on very modest hardware. If you’ve not played with it, you should give it a try and spend a day learning about it.
David: I agree with Kevin on this one, though I learned about memory mapping a long time ago. I have successfully used memory mapping across many projects and organizations, starting with memory mapping with Unix workstations in the early 1990s. Being able to efficiently access data from files without copying to local structures or classes is such an advantage over other approaches. In Valhalla, we structure the routing graph in such a way that when computing routes we can use pointers to memory mapped locations and cast them to structures (or classes) that we can immediately access in code. This is quite efficient!
Where is Valhalla currently being used?
Kevin:
Tesla client/server-side navigation
Mapbox (and its automotive customers like BMW)
Mapillary (acquired by Facebook/Meta)
Many many start-ups that want to focus on their core competency rather than build their own router
David: I will add that Valhalla has been used in several bicycle navigation computers (small devices mounted near the handlebars). The company I work for uses Valhalla. I also believe that Wahoo does as well (they did several years ago).
Does Valhalla get support from companies that are using it?
Kevin: Yep, a number of the contributors use Valhalla in their day jobs, which leads to contributions here and there, both large and small.
David: If you count the occasional code contribution back to Valhalla, then I would say yes.
Is Valhalla intended to eventually be monetized?
Kevin: No. Valhalla is technically part of the Linux Foundation. This allows us to seek funding for its development using Linux Foundation procedural guidance but thus far we haven’t needed to take advantage of that. Other private companies do monetize Valhalla as part of their own API offerings or as part of their primary product as a feature to paying customers, but the open source project is maintained by its founders, and we have never had plans to monetize it. I, for one, would oppose such an idea.
David: No.
What are you most proud of?
Kevin: I took great pride in working with the Tesla engineers to integrate Valhalla into their in-car navigation system, as well as with the BMW engineers on their integration as well. The automotive industry is an incredibly interesting and highly competitive space, and I’m proud that Valhalla could serve those use-cases.
David: Automobile navigation is an exciting (though highly competitive) industry, and I take pride seeing its use in this industry. However, as a long time cyclist, I really enjoy seeing my work with Valhalla used in this space.
How do you balance your work on open-source with your day job and other responsibilities?
Kevin: Over time, I’ve evolved primarily into a mentorship role. This means I do code review, design and Q and A on other folks who are cutting their teeth on the code-base. From time to time, I will jump in and implement something if the scope is manageable time-wise. I have a big family (6 kids) and so I’m primarily only able to contribute in the mornings, nights and weekends as most of the rest of my time is dominated by my day job and my family’s needs.
David: I leave most of the Valhalla open source work to Kevin and others, only occasionally responding to questions and issues.
Have you ever experienced burnout? How did you deal with it?
Kevin: Yes. When you work for a company that primarily sells access to APIs and you are successful, you will end up inevitably courting many different companies with different needs all at once. The trick to navigating that is finding ways to kill 2 birds (requested features) with one stone (implementation/developer time) but often we are talking about killing 2 birds, a zebra, maybe an elk and a whale and it's just not possible to find a way to meet all their needs without dedicating separate efforts.
The only way to deal with it is to prioritize the various animals you’re hunting (is the metaphor still working?), assign developer resources starting at the top of the priority list and take some estimates. You’ll then need to negotiate on timelines with each animal individually and see what you need to juggle around. The problem is over constrained so at the end of the day you have to be ok with failing to bag some of your wild game.
David: I can’t think of any times I felt truly burnt out in my career. I moved to part-time employment this year after 41 years of full time work as a software engineer. I guess that is one way to alleviate burnout!
Where do you see the project heading next?
Kevin: Every day, a new person posts an issue asking about: can it do X thing? The answer can sometimes be “no and it likely will never do,” but more often than not the answer is “interesting, we could do it like this, is that what you are thinking, cool to make it happen I would suggest…”
David: I could see Valhalla adding support for navigation and guidance, so it can be more easily used in mobile solutions. For now, navigation support is left to the developers who integrate Valhalla into their project.
Are there any other projects besides Valhalla that you’re working on?
Kevin: There is a library called prime_server which Valhalla uses for its operational concerns. It's the thing that we wrap the library with to handle request-flow through the different pieces of the library in an operationally sound way. The API is very stable, but here and there we find issues, patch them, and upgrade Valhalla to take advantage of them.
David: No.
Where do you see software development heading next?
Kevin: Is this my cue to jump onto the AI bandwagon? Call me a skeptic or maybe a romantic but I truly hope that AI does not become a primary tool engineers make use of in the near future. At least not in the way that the evangelists would like us to believe, i.e. the AI writes your code for you after you rattle off a few natural language commands to it.
Don’t get me wrong, it could be great for a bit of task management or menial work. For example, in Star Trek the captain would say things like: “Computer, how many life forms are on that Borg Cube?” I could see a reasonable integration in an IDE where the AI does analytics on a code-base to help inform the engineer rather than to do the engineer's work for him. The engineer could say something like: “Find me instances of that object which never call their ::Foo method”.
I remember when people thought map-reduce was going to change the world, or when they thought machine learning was going to change the world. And to a degree they did; they became tools we use to solve problems. With AI, it could be another generic tool but the generative bits, I’m skeptical that they could be used for anything other than trivial tasks. The purpose of the AI is to take what it’s seen, identify patterns, and, in some form, regurgitate those that match the user’s intent or combination of intents. While combinations could be somewhat novel the components will not truly be. I don’t really want to think that engineering, which essentially requires a person to invent new things, will be boiled down to whatever things engineers of the past did as understood by an AI that was trained on them. I would prefer engineering to remain a discipline where the potential for truly novel ideas continues to exist.
David: I don’t think about this much. I remember in the 1990s when virtual reality was the next big thing. Then the hype died down and virtual reality found its uses (though not for everything the hype predicted). Same thing seems to happen every few years.
Want to join the conversation about one of the projects featured this week? Drop a comment, or see what others are saying!
Interested in sponsoring the newsletter, or know of any cool projects or interesting developers you want us to interview? Reach out at osh@codesee.io or mention us @ConsoleWeekly!
Vitalis 🇺🇦 The most original and unusual landmark in Odesa, which has become a symbol of the creativity of Odesa residents. Tech Stuff Cursor I really really like Cursor. I had a great time using VS
Daily Coding Problem Good morning! Here's your coding interview problem for today. This problem was asked by Apple. You are going on a road trip, and would like to create a suitable music playlist.
Also: How to Add Emails to Your Tasks To-Do List in Gmail, and More! How-To Geek Logo December 28, 2024 Did You Know In December 2014, two con men from Girona, Spain, agreed to sell a fake Francisco de
In 2023, China led global car production, contributing nearly a third of total output. Which countries followed in this competitive industry? View Online | Subscribe | Download Our App FEATURED STORY
Hey there, There's always something going on over at Real Python as far as Python tutorials go. Here's what you may have missed this past week: Learn From 2024's Most Popular Python
THN Daily Updates Newsletter cover Resilient Cybersecurity ($39.99 Value) FREE for a Limited Time Reconstruct your defense strategy in an evolving cyber world Download Now Sponsored LATEST NEWS Dec 28,
iPhoneLife Logo Sponsored email sent by iPhone Life Hands Down One Of The Best Cards For 2025 Offering 0% interest until 2026 If you have outstanding credit card debt, getting a new 0% intro APR credit
What Rewriting a 40-Year-Old Project Taught Me About Software Development Read on: my website / Read time: 7 minutes The .NET Weekly is brought to you by: As the year wraps up, it's clear API
Email isn't displaying correctly? Read this e-mail on the Web This Week in Rust issue 579 — 25 DEC 2024 Hello and welcome to another issue of This Week in Rust! Rust is a programming language
