判断某个area是否被已有area cover的算法以及其在实践中的应用
大部分的coding工作可能更像是glue。设计好合适的data abstraction以及interface，按照合适的语言部署到合适的platform上。很多时候关键的问题都被解决好了，剩下的似乎就是把不同小部分的模块组成在一起的操作了。
最近终于有了一个把实际的algorithm使用到一个framework中的体会。具体问题背景是这样的: 对于一个in-memory的data management system, 不同partition的data是分布式地存储在不同的node上，不仅仅raw data 是分布式地存储，这些raw data 的metadat 也是分布式地进行存储。那在query的时候怎么能知道这些data是不是都avaliable了？比如一个data被分成了10个partition,可能传输的时候只有5个到了data management service里，这个时候一个query过来，如何知道这个数据还没传输完整？
之前的一种方式是在client端使用lock，比如在准备传data的时候加一个lock，然后在data传送完成之后再加一个lock。在query的过程中，如果发现指定的数据已被lock，就返回正在处理的状态。这个方法虽然可行，但总是引入了额外复杂的机制，比如client在传数据之前还要设置lock，增加了额外的复杂操作，这就让人很不爽。
作为一个负责任的distributed data management server，最起码应该知道过来的数据是不是完整的啊，这个怎么能让client通过distributed lock的方式去控制呢，感觉像是甩锅的操作。况且之前的code中的lock机制也实现的不怎么好，总是莫名其妙的卡在一个地方，让人感到很郁闷，无从下手。
于是在新的server中打算提供一个算法，就是检测某个指定的partition是否已经被cover。这个说起来好像挺容易，具体还是参考了stack over flow 上的答案。开始的时候还以为要用segment tree 什么的判断是否cover，但是这里的方法很简洁，并且支持不同维度的data，不论data dim 是 1 2 3 或者是更高的维度，都能支持。
首先每个 server 都知道自己所负责的domain的范围是什么（这个由DHT决定），当前的server中存储了一些数据的metadata，然后一个query过来，要看这个query是否被这些已经存在的 metadata 完全覆盖。比如一个server 负责的是 [1,20]，然后有一些数据比[1,5],[6,8],[10,15] 存储在这个server中，如果query是[1,8]则返回true，因为[1,8]中的元素都已经存在于server中，如果是[1,10]则返回false，因为9号元素不在这个server中。 这里用到的思路大致如下。首先建立一个query set, 这个set在开始的时候只有一个元素，就是query的范围。然后是遍历metadata中已经有的元素，对于每个被遍历到的元素，在遍历query set中的元素，如果没有重叠，则继续，如果query set中的元素被覆盖，则对应元素从query set 中pop出来，如果有重叠的部分，则重叠的部分消去，原本的query set中的元素被分解成为两个元素，重新加入到query set中。最后查看query set中是否还有元素。如果为空则被cover，否则就没有被cover。
这个算法的好处是适用于不同维度的数据，复杂的地方就是2维或者3维的时候，将原来的元素分解可能会比较麻烦。
当然这里是原本的元素是比较规则的rectangle，就是与xyz轴平行。如果更复杂的图形可能就涉及到了计算几何中的一些方法，需要用到segment tree之类的方法扫过整个空间那样操作，这个暂时就不具体深究了。
