Redesign a Slow Holiday Lookup for Low Latency
Programs look up public holidays through a client library that makes a slow network call for every lookup. Redesign it so lookups answer in about a millisecond while holiday changes still reach every program in time.
Problem statement
For this exercise, assume a company runs an internal holiday lookup that many of its programs use, for example to skip non-working days when they schedule payments or count business days. A program calls `getHolidays(countryCode, year)` through a C++ client library that is linked into the program.
The call returns every public holiday of that country in that year, each with its name and full date, such as 2027/07/14 Bastille Day for country code FR and year 2027.
Today the library sends every call over the network to a holiday service that your team owns. That service stores no holiday data. For each call it asks an upstream holiday source run by a different team, which answers with the month and day only, and the service adds the requested year to each date before it replies.
A call takes about 150 milliseconds as seen by the program, and some programs make many calls, so their owners say it is far too slow. Redesign the system so that programs get their answers much faster, while holiday changes still reach them.
Also assume: - Your team owns the holiday service and the client library. The upstream source cannot be changed: it answers one country and year per call, it allows your service at most 20 calls a second, and it never tells callers that its data changed. - Holiday data changes rarely.
The lists for a new year appear once a year, and a correction or an extra one-off holiday arrives a few times a month, sometimes only days before the date. - Client teams take weeks to rebuild their programs with a new library version, so the signature of `getHolidays` must stay the same.
You may add new functions to the library. - A program must never get a partial list, or a list that mixes old and new data, for one country and year. An unknown country or year must be told apart from a year that has no holidays, and both must be told apart from data that could not be loaded.
- Changing the upstream source, regional calendars inside a country, half days and time zones are out of scope.
What to build
- A program calls getHolidays with a country code and a year and gets every holiday of that country and year with its name and full date, or a clear answer that the country or year is unknown, which is different from a year with no holidays.
- When the upstream source adds, corrects or removes a holiday, every running program returns the new list within 15 minutes, without any client team rebuilding or restarting its program.
- A program can ask which version of the holiday data it is using and how old that data is, and the holiday team can see which running processes are behind.
At scale
- For this exercise, assume about 200 country codes, years from 1990 to two years after the current year, and about 12 holidays per country and year, so all the holiday data together is a few megabytes.
- For this exercise, assume about 10,000 program processes on about 2,000 machines make up to 100,000 lookups a second together at peak, and that 95 percent of lookups must return within 1 millisecond as seen by the calling program.
- For this exercise, assume one upstream call takes about 120 milliseconds, and that an added, corrected or removed holiday must reach every running program within 15 minutes.
- For this exercise, assume that programs keep answering from the last complete data they had while the holiday service or the upstream source is down, that a process which starts while the holiday service is down must still answer, and that all 10,000 processes may restart within the same 5 minutes, for example after a weekly deployment.