非结构化的大数据存取
前两天和朋友聊到一个有意思的话题，那就是非结构化的大数据如何去存储。内容大概是这样：
感觉这个挺有意思，就分析一下。
对于这个Feature，我们可以假定一些前提，
1、这是一个基于文件存储的数据库，并且该文件系统可以支持无限大的文件。
2、这个数据库系统是个key/value的，key是用于访问，value是用于存储真正的数据。key, value的访问api是基于行和位移的，其他的辅助信息不额外考虑。
3、数据是xml格式的，直接存储在value中。例如有个职员信息 info 是
<fname>Samuel</fname>
<lname>Chen</lname>
<address>
<city>Beijing</city>
<country>China</country>
</address>
<photo>
<![CDATA[
binary data of photo
]]>
</photo>
这样，在访问到的时候，将数据从磁盘读到内存，并更新内存buffer为：
当然，这个内存结构和存储的信息可以根据实际情况来定义。
无可否认的是，这个方法是有效率问题的，时间换空间。可以根据实际情况考虑采用预读，比如当用户使用单向遍历（如ado.net的IDataReader）时，可以在内存允许的范围内预读接下来的N条。
因此，我们可以计算该修改的位置，看它是处于哪一个数据块，而仅仅修改一个数据段，从而大幅提高效率。同时，如果修改的范围过大，可以考虑整个更新。这些都需要记录修改的信息来实现。
当然，这只是个原型，还有数据库的transaction，log等等许多问题需要考虑，同时perfomance也需要长时间的优化。
一个数据库系统可以实现非结构化的存储，其方法是采用xml来定义数据，并将数据作为一个大数据字段。那么问题来了，当这个字段特别大的时候，比如1G，不能简单的载入到内存中，那么我们应该怎么做？
感觉这个挺有意思，就分析一下。
对于这个Feature，我们可以假定一些前提，
1、这是一个基于文件存储的数据库，并且该文件系统可以支持无限大的文件。
2、这个数据库系统是个key/value的，key是用于访问，value是用于存储真正的数据。key, value的访问api是基于行和位移的，其他的辅助信息不额外考虑。
3、数据是xml格式的，直接存储在value中。例如有个职员信息 info 是
<lname>Chen</lname>
<address>
<city>Beijing</city>
<country>China</country>
</address>
<photo>
<![CDATA[
binary data of photo
]]>
</photo>
那么 select * from tab where fname = 'Samuel' 返回一个对象person（或文档对象），具有这么些个属性。（这种类型的数据库查询不一定适合用传统的关系型数据库的SQL，很有可能是xPath、query与SQL的结合，这里仅用来作为示意。）
问题来了，如果这个文档对象非常之大，达到了1G，那么当用户修改了一个字段，比如city变成了Shanghai，这样的一个功能，我们该如何实现？
分析一下，需要解决的问题有下面这么几个：
1、首先是大数据，再者是非结构化，也就是基于行列的存储是不合适的，那么该怎么存储才能使得空间足够也不浪费？
2、这么大的数据内容，直接载入到内存，显然是不太合适的，需要直接在文件中更新。
3、传统的关系型数据库操作只有CRUD，也就是增、删、查、改，其基本结构是字段，如果整个来更新是否合适？如果不整个更新，只更新修改的部分，怎么去实现。
按照这个思路，一个个来解决。
要解决空间浪费或不足的问题，那么存储段就需要具有scalability，可以根据数据大小伸缩，因此可以将其设计成分段的，当需要的时候增加，不需要的时候就释放，如下
如表格所示，key 是固定长度字段，我们在这里并不关心，所需的只是其长度，假定其总长度为 key_len.
Sequence 是每一个record的首地址，可以记录，也可以不记录，列在这里是因为我们需要这个值来做为基本偏移量。
Structure 是每个value所需要的信息，包括是否第一个数据段（head），value 总长是多少（length），下一个段偏移量（next），是否已经删除（deleted），以及本段真实长度（actual length）。通过这些，我们就可以通过计算来访问一块完整数据。
Value 是存储的真实数据，当然也可以有一些其他信息，比如encoding之类。
那么有了这么一个系统，我们就可以存储任意大小的数据（最大长度由length或者系统定义决定，本例中是16777216TB，实际上目前没这么大的）.
例如我们有一块140KB的数据，那么存储的时候会分成如表格所示3段存储，前两段是满存储，最后一段存了12KB，有一定浪费，因此分段大小也是需要考虑的，过大过小都不好（4~8K比较合适），也可以通过让用户配置来决定。当然，如果用一个单独的文件来存储，甚至可以不必分段，只需维护一个偏移+长度表即可，这里就不讨论这种方法了。
当需要修改时，如果数据长度增加了，变成了200KB，我们就可以通过修改偏移量、长度，并增加新段来解决，如表
问题来了，如果这个文档对象非常之大，达到了1G，那么当用户修改了一个字段，比如city变成了Shanghai，这样的一个功能，我们该如何实现？
分析一下，需要解决的问题有下面这么几个：
1、首先是大数据，再者是非结构化，也就是基于行列的存储是不合适的，那么该怎么存储才能使得空间足够也不浪费？
2、这么大的数据内容，直接载入到内存，显然是不太合适的，需要直接在文件中更新。
3、传统的关系型数据库操作只有CRUD，也就是增、删、查、改，其基本结构是字段，如果整个来更新是否合适？如果不整个更新，只更新修改的部分，怎么去实现。
按照这个思路，一个个来解决。
存取
一般来说，对于xml数据存储，是使用字符型blob（binary亦可）字段，可以防止空间浪费或不足。在用的时候读出，存的时候写入。那么当该xml文档非常大的时候，直接读取到内存中就不太现实，此时就需要直接在文件中访问。所以问题就成了这个key/value的系统怎么去设计才能完成这个任务。要解决空间浪费或不足的问题，那么存储段就需要具有scalability，可以根据数据大小伸缩，因此可以将其设计成分段的，当需要的时候增加，不需要的时候就释放，如下
| sequence | key | structure | value | ||||
| offset | we don't care | head | length | next | deleted | actual length | data |
| 4B | 2B + 4KB | 1B (1b) | 16B(16777216TB) | 4B | 1B (1b) | 2B(max=64KB) | 64KB |
| 0x00000001 | 1 | 143360(140K) | 0x00000002 | 0 | 65536(64KB) | xxx | |
| 0x00000002 | 0 | 143360 | 0x00000003 | 0 | 65536 | xxx | |
| 0x00000003 | 0 | 143360 | 0 | 0 | 12288(12KB) | xx |
如表格所示，key 是固定长度字段，我们在这里并不关心，所需的只是其长度，假定其总长度为 key_len.
Sequence 是每一个record的首地址，可以记录，也可以不记录，列在这里是因为我们需要这个值来做为基本偏移量。
Structure 是每个value所需要的信息，包括是否第一个数据段（head），value 总长是多少（length），下一个段偏移量（next），是否已经删除（deleted），以及本段真实长度（actual length）。通过这些，我们就可以通过计算来访问一块完整数据。
Value 是存储的真实数据，当然也可以有一些其他信息，比如encoding之类。
那么有了这么一个系统，我们就可以存储任意大小的数据（最大长度由length或者系统定义决定，本例中是16777216TB，实际上目前没这么大的）.
例如我们有一块140KB的数据，那么存储的时候会分成如表格所示3段存储，前两段是满存储，最后一段存了12KB，有一定浪费，因此分段大小也是需要考虑的，过大过小都不好（4~8K比较合适），也可以通过让用户配置来决定。当然，如果用一个单独的文件来存储，甚至可以不必分段，只需维护一个偏移+长度表即可，这里就不讨论这种方法了。
当需要修改时，如果数据长度增加了，变成了200KB，我们就可以通过修改偏移量、长度，并增加新段来解决，如表
| 0x00000001 | 1 | 204800(200K) | 0x00000002 | 0 | 65536(64KB) | xxx | |
| 0x00000002 | 0 | 204800 | 0x00000003 | 0 | 65536 | xxx | |
| 0x00000003 | 0 | 204800 | 0x00000005 | 0 | 65536 | xxx | |
| 0x00000004 | 1 | 10240 | 0 | 0 | 10240 | yyy | |
| 0x00000005 | 0 | 204800 | 0 | 0 | 8192 | xx |
同样的，删除也可以通过标记段已删除来实现，下次再变大的时候，可以继续使用，或者用新的段来代替。多次删除之后，可能会有大量的删除段存在，这就需要重整，亦或使用其他方法来防止大量删除段的出现。这些细节以及实现在这里暂不细说了。
这样，我们就解决了第一个问题，如何去存储这种非结构化大数据。当然，各个数据库都有自己的实现，性能优劣各不相同，也可参考。
此时的各个字段如 id, emp_id, dept 都是存在于内存的buffer之中，当你使用api访问行、列或者名字的时候（比如ado的recordset），api会计算并返回相应的值。
当碰到非常大的数据时，怎么办？比如info里面有个人信息，还包括照片等等，达到了几十、百兆甚至上G，那么一个查询取出几百条数据，总共的数据超过了内存限制，该怎么办？
这个问题涉及到了两个层面，一个是多行数据过大，一个是单个数据过大。对于第一个问题，多行数据过大，一般来说API都有考虑，会再访问的时候再去取，或者预读等等，暂且不提，这里咱们讨论第二个问题。
其实单个数据的访问也是可以在访问的时候去取的，也就是所谓的access on demand。我们可以在buffer该数据内容中存储访问信息而不是真实数据，在真正用户用到的时候再去数据库取，如表
这样，我们就解决了第一个问题，如何去存储这种非结构化大数据。当然，各个数据库都有自己的实现，性能优劣各不相同，也可参考。
访问
数据库访问一般来说都是由各数据库厂商提供api，比如oracle的OCI/Pro* C。 也有一些通用的包装，如ODBC，JDBC等。无论是哪种方式，当你在程序中使用的时候，访问的都是内存中的buffer，例如| id | emp_id | dept | info |
| 9527 | samc | PB | <fname>Samuel</fname> <lname>Chen</lname> <address> <city>Beijing</city> <country>China</country> </address> <photo> <![CDATA[ binary data of photo ]]> </photo> |
此时的各个字段如 id, emp_id, dept 都是存在于内存的buffer之中，当你使用api访问行、列或者名字的时候（比如ado的recordset），api会计算并返回相应的值。
当碰到非常大的数据时，怎么办？比如info里面有个人信息，还包括照片等等，达到了几十、百兆甚至上G，那么一个查询取出几百条数据，总共的数据超过了内存限制，该怎么办？
这个问题涉及到了两个层面，一个是多行数据过大，一个是单个数据过大。对于第一个问题，多行数据过大，一般来说API都有考虑，会再访问的时候再去取，或者预读等等，暂且不提，这里咱们讨论第二个问题。
其实单个数据的访问也是可以在访问的时候去取的，也就是所谓的access on demand。我们可以在buffer该数据内容中存储访问信息而不是真实数据，在真正用户用到的时候再去数据库取，如表
| id | emp_id | dept | info | info_data |
| 9527 | samc | PB |
key | offset | len | ...
| null |
这样，在访问到的时候，将数据从磁盘读到内存，并更新内存buffer为：
| id | emp_id | dept | info | info_data |
| 9527 | samc | PB |
loaded...
| 0x03677d2d -> |
当然，这个内存结构和存储的信息可以根据实际情况来定义。
无可否认的是，这个方法是有效率问题的，时间换空间。可以根据实际情况考虑采用预读，比如当用户使用单向遍历（如ado.net的IDataReader）时，可以在内存允许的范围内预读接下来的N条。
修改
还是这个例子，如果我们修改了个人信息，把city改为Shanghai，按照传统做法，是要update info，把整个info字段更新一下。
<fname>Samuel</fname>
<lname>Chen</lname>
<address>
<city>Shanghai</city>
<country>China</country>
</address>
<photo>
<![CDATA[
binary data of photo
]]>
</photo>
那么在该数据系统中，仅仅因为更新了整块数据中非常小的一部分（几个字节），我们就需要修改整块大数据（1G），这是非常影响效率的。<lname>Chen</lname>
<address>
<city>Shanghai</city>
<country>China</country>
</address>
<photo>
<![CDATA[
binary data of photo
]]>
</photo>
因此，我们可以计算该修改的位置，看它是处于哪一个数据块，而仅仅修改一个数据段，从而大幅提高效率。同时，如果修改的范围过大，可以考虑整个更新。这些都需要记录修改的信息来实现。
| 0x00000001 | 1 | 204800(200K) | 0x00000002 | 0 | 65536(64KB) | xxx （仅修改该段） | |
| 0x00000002 | 0 | 204800 | 0x00000003 | 0 | 65536 | xxx | |
| 0x00000003 | 0 | 204800 | 0x00000005 | 0 | 65536 | xxx | |
| 0x00000004 | 1 | 10240 | 0 | 0 | 10240 | yyy | |
| 0x00000005 | 0 | 204800 | 0 | 0 | 8192 | xx |
以上的方法可以适用于binary或者字符blob，但是，由于在这个case中，我们考虑的是xml数据，所以需要有一些更进一步的细节考虑。比如根据xml parser实现的不同，数据不一定是按节点顺序存放的，而且节点也不一定是有序的。因此，需要在每个节点的meta中存储段信息（或者其他的方法，根据xml parser/dom的不同具体考虑）
总结
这样，我们就能够很好的处理非结构化大数据的存储和访问了。当然，这只是个原型，还有数据库的transaction，log等等许多问题需要考虑，同时perfomance也需要长时间的优化。
标签： Architect, Articles, Database, Programming, Technology
(墙外)
