Algorithm
来Offer的金牌讲师吕老师最近出了一道关于System Design的原创习题。虽然是道热腾腾的新题目，但题目中的原理却是在工业界被广泛应用的。掌握这道题，无论是在求职应聘还是在职场工作中，都能让你受益。下面，就让我们一起帮助习题中的主人公 —— 赵老师，完成他的Time Machine吧！
Dr.Zhao: “Shhh… Press the diamond on my Tesla to turn on a time machine!”
OK, let's build a time machine for Dr. Zhao.
The time machine has memory, just like our computers. For each memory read or write, the user may use the following methods to operate. The time machine’s memory supports these two basic operations:
(1) byte read (long location) returns the value of a given memory location
(2) write (long location, byte value) updates the value of a given memory location
To act as a time machine, Dr. Zhao wants us to add one more operation:
byte read (long location, long timestamp)
With this added operation, the magic of our time machine starts!
Specifically, it can return the historical values of one given memory location. For example, I may read the value in location L 10 days ago, or even years ago. We do not need to worry about the time machine being restarted. With the magical diamond, Dr. Zhao’s time machine will never fail. Now, how to design such a time machine with your code?
You may start with something like:
interface TimeMachine {
byte read (long location);
write (long location, byte value);
byte read (long location, long timestamp);
}
Dr. Zhao is waiting for your implementations. As a limitation, you CANNOT use any language built-in data structures except arrays. You may want to implement your own data structures like linked lists, binary trees, or hash maps.
A few follow ups:
1. Suppose there are multiple threads operate on the same time machine concurrently, how to handle these operations? What will be the performance impact?
2. If the machine keeps running and we keep writing new values into the time machine, what will happen? How to deal with this? What will be the performance impact?
3. Dr. Zhao now allows us to use language built-in data structures like LinkedList, HashMap, TreeMap, etc. Can you easily replace your own implementations with them?
讨论和解答
其实计算机软件系统中经常会遇到这样的“时间机器"。这种时间机器的语义在工业界项目中是广泛存在的，一般被称为Multi-Versioning。
设计这样的“机器”，主要要解决的问题有两个：
► 1. 系统中可能存在的地址是非常多的。
在这个问题中，我们沿用一般计算机中的⽅方法，用64个二进制位描述一个内存地址。可以想象，如果把这些地址跟我们对应的“时间机器”程序中的地址⼀一对应的话，会是一件⼏乎不能做到的事情。
► 2. 对于每个地址，如果我们真的要能够⽀支持读出历史某个时刻的值的话，那么我们就真的需要把这些内容保存下来。可是系统中，时间是在不停增长的，与此同时，每个地址对应的值也可能在不停地被修改。如何保存这些历史上的值，会是另一个问题。
我们可以先从一个最简单的问题开始考虑：假设我们的时间机器中可以保存历史任意时刻的内存中的内容，而不需要考虑内存的消耗，那么上述的两个问题就被分开了。
STEP 1
我们⾸首先考虑问题1，如何组织系统中大量的内存地址呢？其实计算机科学中一个最常见的解决思路就是Hashing。
就像一般的hash算法一样，我们可以将若干个内存地址按照某种规律映射到⼀个“桶”（bucket）中。这样，⼀个近乎于无穷大的内存地址空间就可以用有限的数据元素来管理了，如下面这个图：
在这里，我们使用了⼀一个叫做history table的数据结构来组织所有的时间机器内部的数据。
STEP 2
能够把所有的内存地址都映射到history table中之后，我们就可以着⼿手解决另⼀一个问题了了，也就是如何组织所有系统中曾经有过的值。
对于这一点，我们可以做一个很简单的扩充：History table中的每一项拥有一个链表。对于任意一个地址，我们可以在History table中按照时间的先后顺序，倒序保存每次写入的值，每次写⼊对应链表中的一个节点，记录每个值的同时记录写入的时间。这样，History table中保存着所有被映射到同⼀个项上的地址的所有历史上的值。
链表的每⼀项会存有如下内容：操作对应的地址（addr），操作发⽣的时间（t），和操作写入的新值（val），如下图：
整个链表的整体组织如下图：
因此，当写入地址L时，我们只需根据地址L找到对应的history table中的一项，然后创建⼀个链表节点，记录当前写对应的地址L，值和时间。此后，将这个节点从头部插入链表即可。随着时间推移，链表⾃自然会形成时间倒序。
当读取地址L时，我们只需在链表中找到对应地址的首个节点即可。当读取特定时刻t的地址L时，我们需要在链表中找到对应地址的、写入时刻⼩于t的首个节点就好了。若我们遍历完整个链表仍然不能找到满足条件的记录，那么说明这个地址从来没有被写过。
接下来很多同学的疑惑都集中在，如果系统⼀直不停地运行下去，那么这个链表会无限地延长呀，这种情况怎么办呢？
而工业界中解决无限增长的历史记录的问题也非常简单：扔掉。
对于很多实际系统，通常可以设定一条记录的最长存在时间（Time to live, TTL）。超出TTL的数据都将被系统自动回收，这样就可以避免历史数据无限堆积的问题了。如果系统被多个线程并发访问时，我们可以设定一个系统整体的时间，然后让并发的操作线程上锁后更新链表并更新系统时间即可。
若允许直接利用Java等语言中的预定义数据结构，我们可以充分借用TreeMap等数据结构加速链表查询的步骤。事实上，很多⼯工业界中按照时间进行记录的部分都利用了TreeMap加速查找。