存储引擎设计

存储引擎会设计成k-v，也就是键值对，按时间序列和图像帧以及雷达帧进行存取。核心数据结构采用跳表-哈希表-双向链表，具体分为时间序列-帧序列跳表，通道号（根据通道号可分辨雷达数据or图片数据）哈希表，数据存储链表。时间序列-帧序列跳表的key会分为2个级别，第一个级别的key存储的是时间序列，由于同一时间序存在多个帧序列，而帧序列可以看成时间序列的子序列，因此按第一级跳表可以找到某一时刻，从第二级跳表可以找到这个时刻的具体帧序列，帧序列的value会存储一个哈希表的原始指针或者迭代器。这个哈希表的key为通道号，因此可以通过跳表加哈希表得到某时刻某序列某通道，哈希表的value存储的是指向真实存储数据的链表的原始指针或者迭代器。最底层的双向链表用来存储数据。由于时间序列是线性增加的，因此大大降低哈希碰撞的概率，当内存够大时可以将哈希设计成很大的桶内存，以便存入很多的Key值，出现哈希碰撞直接用链表就可以，因为时间序列是很紧凑的（理论上每一秒应该都有数据传入），几乎在key这层内存不会存在碎片，如果采用再哈希等方法则key会打到很远的内存，这样哈希会失去意义，找这个Key的时间从常数时间变成遍历整层表。底层的双向链表设计成一段连续的内存接一段连续的内存，某个时刻某个图像或雷达帧的某个通道的数据会存在一个连续的内存中，它的下一个指针指向下一段某个时刻某个帧的某个通道的数据。

存储引擎在架构上设计分为两个级别，由于图像和雷达数据的特征以及数据的来源需要考虑传感器从socket读入，所以设计上需要考虑网络io，内核中断，磁盘io与qps。因此将存储引擎设计成两个级别，第一个级别为数据不是很多的时候，会在内存分配一块内存池，在存入内存池之前会设计一个buffer缓冲区，用来应对网络数据骤增而磁盘io跟不上的情况，因为磁盘io速度远远小于内存读写并且cpu计算的速度，寄存器，L1缓存等读写的速度远远高于磁盘io，buffer直接设计成环形缓冲区即可，新来的数据插在队尾，队列头数据写入内存池。当数据量骤增时，存储引擎不会因为qps增大而跑满io，当数据量很小时，也不会产生进程饥饿，甚至进程产生阻塞，以防止busyloop。当数据量达到内存池水位时，当前内存池的权限会设成只读，同时会开启写入磁盘的线程，此时当前内存池数据只能向磁盘写，而不能从socket写入，因此会开启第二块内存池也就是第二个级别，从socket写入内存池和第一块内存池写入磁盘是两个线程，因此可以实现后端异步的写数据。同时第一块内存池在写入磁盘的同时，会维持一个LRUCache，也就是最近最少使用缓存，该缓存用来维持被频繁查询或存储的key值。LRUCache的底层设计同样和上面提到的数据结构是一样的设计，只不过它的底层需要设计成双端队列，当某个数据被查询时会将数据移到底层的队列尾，当队列满的时候，将队列头数据清除掉，由于LRUCache维护的是最近最少使用的数据，因此队列头的数据就是当前时刻驻留内存最久的未使用过的数据，直接从队列清除即可。维护LRUCache的原因是如果每次查询数据都从磁盘读，则速度会远远小于内存读，因此在数据从内存写入磁盘的时候可以同时维护一部分活跃数据驻留在内存，该数据量不能过大否则会吃很多内存。

因此，存入数据，按照跳表-哈希表-双向链表的逆向顺序，自底向上存储，数据流向会从socket到内存到Buffer缓冲区到内存池，这时候如果内存池未满，无需写入磁盘，当内存池达到水位时，开启另一块内存池，将之前内存池的数据异步写入磁盘，同时维持一个LRUCache,将这块内存池权限改为只读。读取数据，首先当内存池没有写满的时候，直接去内存池读，当内存池写满的时候，先去LRUCache读，如果数据没有保存在LRUCache，则去磁盘读，数据查找按照跳表-哈希表-双向链表的正向顺序，自顶向下查找。

说明：

不采用树形结构的原因：1)查找，也就是取数据：树形索引都是以平衡二叉树为原型的基础上的变种，比如红黑树，b+树，字典树，这些树的查找时间复杂度大概维持在O(lgn)--不考虑n叉树它们的时间复杂度在一个量级，而基于跳表和哈希表的数据结构则是维持在常数时间，因此查找效率会优于树形结构。哈希的弊端在于由于一般场景的key是分散的，所以会产生大量的内存碎片，而我们的场景下则不存在这个问题，由于时间是连续的，因此哈希不会出现大量内存碎片。2)

存入数据：树形结构为了维持它的平衡特点（左叶子节点小于根节点小于右叶子节点），以防止退化成链表，需要不断的做平衡调整也就是左旋和右旋，由于我们的key值是时间序列，是一个线性递增序列，如果用树去存，每插入一个数据都在左旋，而如果不做平衡调整退化成一个线性结构的话，存入数据的时间复杂度是不变的，但是查找的时间复杂度会达到遍历整个数据结构的时间，远远高于哈希的常数时间。

线程设计：

由于存储引擎以网络io, 磁盘io为主，因此线程设计都是以io bound型线程为主，引擎的瓶颈几乎大概率出现在io，因此每个进程无需设计多线程去并行计算，只需要采用一个进程只有一个线程的模型，同时多个事件拥有多个进程。整体线程设计为，网络io一个线程，该线程负责读多个通道数据，socket读到的数据写入Buffer缓冲区并且写入内存池需要设计一个线程，此时有两种情形，异步写入磁盘需要一个线程，直接在内存池将部分数据保存成LRUCache需要一个线程，查找数据需要一个线程。

难点：

我认为的难点主要在于数据的同步设计，也就是原子操作的设计，比如读写的优先级设计，临界区的设计以及锁的设计，比如无锁实现可重入，锁的粒度，线程安全。