A long time ago, in a time zone far far away…
Software engineers have been fighting the never ending battle for the one true representation of time that is simple, clearly defined, and unambiguous. Luckily for Zoba, we have already won half the battle by headquartering in the right time zone.
Time is a foundational component of today’s software, especially in distributed services and systems. Despite the fact that computer scientists have been working hard to tame time since the inception of computers, we still have fun challenges like time synchronization, leap seconds, time storage and representation, etc. Whether we will ever be able to conquer time, only time can tell (pun intended).
Although Zoba is a geospatial data science company, we care not only about where an event happens but also when. As a result, handling time series data is central to everything we build.
It is impossible to cover any time-related topic in depth in a single blog post. Each topic is worthy of its own research and already has decades of academic literature on it. In this post I will focus on the niche use cases we have at Zoba and some of the unique challenges we have come across in our work.
Zoba use case
At the heart of Zoba, we process a lot of events from customers and turn them into incredible insights and actions that help customers increase revenue. Our machine learning models continuously extract geospatial and temporal information from time series data.
Since our customers are in time zones that span 19 hours and all output date times that need to be location aware, we have to do a fair amount of time zone conversions.
Zoba offers a suite of intelligence API endpoints and a dashboard for analytics. When querying metrics for a given city, results are computed based on events in the city’s time zone so that they reflect what happened in the city on any given day. This is essential for customers to compare the performance of different cities without having to worry about metrics being cut off at arbitrary day boundaries.
Similarly to analytics, when we schedule tasks that deliver optimization results to customers, the schedule has to be aware of the cities’ time zones. An operations shift that deploys scooters at 5am in Berlin runs at a different time than a shift that goes out at 5am in Austin. A subsequent blog post will elaborate on the unique challenges we faced building such a scheduling system.
Unlike the two use cases above where it is critical to manage time zones correctly but less essential to maximize speed, the third use case requires both. In order to discover patterns in vehicle usage in a city, we group events together by time of week. Time of week is defined as the hours from the beginning of the Monday of that week. There are a total of 168 hours in a week. For example, operators see different fleet usage during the Monday morning rush hour versus on a Sunday morning, but Mondays across multiple consecutive weeks often share similar patterns.
As part of the preprocessing steps to the machine learning models, events that happen at a similar time of week are grouped together. The number of events passing through our data pipelines typically ranges from hundreds of thousands to tens of millions in a single run. The grouping not only has to be aware of the given city’s time zone, but also be efficient.
Most engineers who have worked intimately with date time in software development probably have nightmares of the time zone goblins chasing them in Eternity. The handling of time zones in modern software leaves much to be desired.
We will cover the different technical challenges we faced and share our learnings below.
Storage
The first challenge we had was choosing the proper time storage format. Since we store data from many different time zones, a standard time storage format across all types of data makes development easier and code less error prone.
One choice is to store all date times without time zone information, sometimes referred to as naive date time. Unless the usage is strictly limited and the time zone-less date times are never exposed, this approach is strongly discouraged. More often than not, this approach leads to error prone spaghetti code and errors that are extremely hard to debug.
We decided to separate time zone information from the date times and store the date times as POSIX timestamps (also known as Unix time) that are consistent throughout the code base. One common misconception is that POSIX timestamps (or timestamps for short) have no time zone information. On the contrary, POSIX timestamps are by definition always in UTC. It is defined as the number of seconds elapsed since the Unix epoch, which is 1970–01–01 00:00:00 UTC. All computers understand this concept because it is baked into the operating system’s kernel. If you accidentally use the elapsed seconds since 1970–01–01 00:00:00 of any time zone other than UTC as timestamp, it will lead to confusion and weird bugs in the system stack.
One of the benefits of using timestamps is that you can represent any point in time using a single number (except when you really care about the leap seconds). It is much easier and more efficient to store an integer representation of a timestamp than its string form. We store timestamps as 64-bit signed integers, which is enough for a little over 292 billion years in the future. We will leave the overflow problem for another eon.
The other benefit of storing date times as timestamps, which is probably also the biggest, is that we can delay time zone conversion until the timestamps need to be displayed for human consumption. By doing this, we can have consistent time handling throughout the code base assuming date times are in UTC.
Cities rarely change time zones, so time zone information is stored as an attribute of a city. We use IANA time zone names to avoid ambiguity around daylight saving transitions. For example, instead of using Eastern Daylight Time (EDT) for New York which only applies during the summer months, we use America/New_York or its older form US/Eastern. When accepting time zone input from users, it is best practice to validate that it is in IANA form to avoid unexpected time zone bugs.
There are more exotic time storage formats in various systems, one such format commonly used for globally unique ID generation is the elapsed seconds since the inception of the product which saves some bits. For example, if the reference point is today, using only 32 bits can represent 136 years into the future. That should be plenty to let most engineers sleep tight. If POSIX time is used here, the same 32 bits can only represent 86 years into the future. This technique is common in distributed systems where time is only used for comparisons, not as wall clock time.
Daylight saving time
When we talk about time zones, it is impossible to ignore Daylight Saving Time (DST for short). It is worth noting that DST is not an intrinsic property of the universe. It is merely a human invention to remind ourselves that not all inventions can withstand the test of time.
Twice a year, some parts of the world wake up to find themselves with a day that is one hour longer or shorter than normal. If this is not confusing enough, imagine different parts of the world making this transition on different days, sometimes even different parts of the same state¹ make different transitions. Unfortunately, this is the world we live in. If anything related to time handling will bite you in your professional life, it is almost guaranteed to be DST.
If you only care about local wall clock time, DST probably matters less to your use case. If I wake up at 7am local time everyday, it’s the same wall clock time regardless of whether DST is in effect or not. However, if you ever want to compare two date times or make time zone conversions, making sure DST is taken into account is essential. Depending on whether DST is in effect or not, the difference between two time zones or two date times in the same or different time zones can be different.
Because DST is seasonal and location specific, it does not make sense to ask if DST is in effect without giving the specific date time and location. For this reason, it does not make sense to calculate the difference between date times or time zones without knowing if DST is in effect, either. If you use Python, this usually means that you have to localize a naive date time or normalize a time zone aware date time to get the proper time zone offset with DST taken into account.
One of the pitfalls in DST handling is forgetting to correct the time zone offset after date time arithmetic. The textbook example is adding an hour during the “spring-forward” DST transition. For example, adding an hour to 2020–03–08 01:00:00 New York local time actually results in 2020–03–08 03:00:00. 2am does not exist on 2020–03–08 in New York. How nice! Without normalizing the date time after the addition of an hour, you will end up with a date time with an incorrect time zone offset.
On the other hand, an extra hour materializes out of thin air during the “fall-back” DST transition. 1am appears twice on 2020–11–01 in New York. In other words, every year people in New York will experience a 23 hour day and a 25 hour day in local time. UTC, however, only has 24 hour days. This is yet another reason to use UTC internally.
We have developed a good practice of always writing unit tests to cover DST transition days in multiple time zones for any code that manipulates time. It is highly recommended if you want production stable code.
Fast time bucketing
Python date time libraries like pytz or Pendulum make the above operations relatively easy. However, we have found them to be lacking in performance for our last use case, grouping millions of events by hour of week.
In a simple microbenchmark on a 2019 15-inch MacBook Pro, date time localization takes roughly 3 times longer than normalization, and about 100 times longer than pure integer arithmetic.
Even though the individual operations look very fast, repeating them tens of millions of times can add up to minutes for a single run.
Given that our use case is to find the right time of week buckets for UTC date times in a given city’s local time zone, we built a ring data structure using pure integer arithmetic. This approach yielded a 6x speed up and removed a major bottleneck in one of our data pipelines.
The ring data structure represents time of week as a point along the ring; the ring “wraps around” so that the end of one week is the start of the next. The ring has length 168, with each unit of length covering an hour of the week. It wraps around at the origin into the next or previous week depending on whether the direction of traversal is clockwise or counterclockwise. The 168 ranges can have arbitrary bucket names assigned to them. For example, 7am to 10am on Monday can be named “Monday rush hours”.
For any event that spans a time range, the ring makes it very easy for us to answer questions like “which bucket does the event start and end in?” and “what buckets does the event span?”. The second question would be hard to answer if we only had a lookup table from hour of week to bucket name. The ring comes in really handy in this case.
The ring can be thought of as a lookup table that also preserves ordering and supports infinite iteration in both directions. Given a week’s start time, we can locate a timestamp’s position on the ring in O(logn) time where n is the number of buckets. Traversing the ring from start to end gives us the buckets covered by a time range in chronological order.
At a low level, the ring data structure is implemented as an immutable and compact binary search tree. The advantage of using such a data structure is that it is CPU cache friendly, and so it is faster when performing millions of lookups at once.
The tokens on the ring define the boundaries of different buckets. They are all floating point numbers representing hours of week to support buckets that don’t align on the hour. All ring operations are performed on timestamps to avoid the overhead of Python date time manipulation. When the final results are returned to the caller, they are converted back to time zone aware datetime objects.
Because the ring stores static information unrelated to individual events, it can be constructed beforehand and cached throughout the run. The ring itself is immutable once constructed and all time zone conversions take place at the API layer. The ring can even be shared across multiple runs. The whole data structure is compact and can easily be serialized into several kilobytes for persistence.
As efficient as this approach is, it is not what we started with first. If not for the significant test coverage we had on this use case and all the baselines we had built up over time to verify correctness, we would not have felt confident introducing such a sophisticated time manipulation solution in our core product. Our experience has taught us that when working with time, it is better to stick to the standards, use consistent approaches, and cover the corner cases because they matter.
In this post, I shared some of the technical challenges we have faced working with time series data but this is just one of the many engineering challenges we face at Zoba. No system is a silver bullet. Engineering is all about tradeoffs, even for the best use cases. Understanding the use case at hand will save you trouble when making tradeoffs. If you are interested in solving problems like these and would like to challenge yourself, we are hiring software engineers like you.
[1]: Arizona does not observe DST. However, the part of Navajo Nation inside Arizona does observe DST.
