>非结构化的大数据存取

>前两天和朋友聊到一个有意思的话题，那就是非结构化的大数据如何去存储。内容大概是这样：

一个数据库系统可以实现非结构化的存储，其方法是采用xml来定义数据，并将数据作为一个大数据字段。那么问题来了，当这个字段特别大的时候，比如1G，不能简单的载入到内存中，那么我们应该怎么做？

感觉这个挺有意思，就分析一下。

对于这个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>

那么 select from tab where fname = ‘Samuel’ 返回一个对象person（或文档对象），具有这么些个属性。（这种类型的数据库查询不一定适合用传统的关系型数据库的SQL，很有可能是xPath、query与SQL的结合，这里仅用来作为示意。）

问题来了，如果这个文档对象非常之大，达到了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

同样的，删除也可以通过标记段已删除来实现，下次再变大的时候，可以继续使用，或者用新的段来代替。多次删除之后，可能会有大量的删除段存在，这就需要重整，亦或使用其他方法来防止大量删除段的出现。这些细节以及实现在这里暂不细说了。

这样，我们就解决了第一个问题，如何去存储这种非结构化大数据。当然，各个数据库都有自己的实现，性能优劣各不相同，也可参考。

## 访问

数据库访问一般来说都是由各数据库厂商提供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），这是非常影响效率的。

因此，我们可以计算该修改的位置，看它是处于哪一个数据块，而仅仅修改一个数据段，从而大幅提高效率。同时，如果修改的范围过大，可以考虑整个更新。这些都需要记录修改的信息来实现。

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也需要长时间的优化。