非结构化的大数据存取

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

一个数据库系统可以实现非结构化的存储，其方法是采用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也需要长时间的优化。

.Net Frameowrk 4.0 Compatibility

关于pb如何支持 deploy 到.NET 4.0的一个research

HTML 5 Inside – Multi Media 多媒体

 

本文基于 HTM5 标准草案 2009年8月25日版
转载请保留出处：http://SamuelChen.net

在以前的猫（modem）年代，人们挣扎在以几或者几十 bit 与 byte 来计量的传输速率上。在那个时候，几乎所有的内容都是基于文字的，电子邮件、新闻组、BBS甚至网页。不像现在，我们可以在网页中放入众多的图片、视频甚至游戏，那时候人们常常使用字符阵来组成图像，表达略微丰富一点的内容（在BBS最常见）。即使是这样，都让人欣喜不已。

随着带宽的不断提高，那么何时我们可以在页面中加入图片了呢？我找到了这篇文章 - “Why do we have an IMG element?”。这篇文章记述了 img 标签的来由， img 元素是在1993年的时候才被提议加入HTML的。

今天，在HTML5中，加入了两个新的元素 video 和 audio ，用于视频和音频的呈现，更加的丰富了媒体内容的表达。

那么我也问一下，为什么我们要有 video 和 audio 元素？

首先，带宽的提高，使得视频、音频的在线观看已经很方便。

其次，目前web页面中用以播放视频和音频的主要手段是嵌入第三方插件，坏处显而易见，无论是安全性或者是性能，都不如浏览器原生支持的好。

因此，我们需要在HTML5中引入新的元素来原生支持更多的媒体内容。

video 元素

video 元素是用来在页面中呈现一段视频或者电影的元素。如果浏览器不支持该元素，那么就不应将该元素呈现给用户。

video 元素在内容模型中，同时属于Flow content, Phrase content 和 Embeded content。很好理解，因为它引入其他的资源，所以是Embeded；而Embeded 包含于Phrase，Phrase又包含于Flow。或者这么理解，由于它参与布局（有至少一个text或者embeded子节点），所以是Flow content；它有内容（有至少一个text或者embeded子节点），所以是Phrase content。

如果video包含了control属性，那么它是一个Interactive content。同样很好理解，因为有了控制面板，所以可以交互。

下面以一个例子来说明.

Avatar - Film Clip

代码如下：

  1: <video id="avatar" width =320 height=240
  2:   src="http://www.youtube.com/get_video?video_id=CXF-VZVdR2Y&t=vjVQa1PpcFOgfEMPW684qS5mePzQgVa3Oo4l0YQnvSc%3D&fmt=18"  
  3:   controls  autobuffer autoplay loop
  4:   poster="http://farm3.static.flickr.com/2779/4202108032_3a261b7370.jpg"
  5: />
  6: 

与大多数元素一样，video 也可以使用id来定义唯一标识，width和height来定义宽高，以及其他的全局属性（Global attributes），就不再赘述。

代码中第2、3行的几个属性是媒体元素（media element）的通用属性，也就是说，audio也有这几个属性。

与img元素一样，video也是用src 属性来用以标识媒体源，其值是一个URL字符串。指定该属性后，浏览器在渲染时就会用原生播放器载入该视频。要注意的是，img不属于媒体内容，因此它的src与这个src本质上是有区别的。

另外的四个标签都是布尔型，分别用来获取或设置播放器的行为，其作用如下：

• controls 设置是否显示播放界面，使得用户可以进行播放、暂停、随机浏览或者全屏等操作。标准中提到的这些功能用的是“应该（should）”，那么这些功能就不是必须的，具体的功能和外观依赖于浏览器的实现。



• autoplay 设置是否自动播放。当含有此属性时，播放器会在载入呈现之后立即尝试播放指定的媒体资源。



• autobuffer 设置是否自动缓存。当含有此属性时，意味着页面制作者提示浏览器（或客户程序）该媒体内容极有可能被用户播放，播放器需要在载入呈现之后开始下载媒体资源并缓存，但并不立即播放。如果video元素同时含有该属性与autoplay属性，该属性必须被忽略，但这不认为是一个错误。



• loop 设置是否循环播放。如果该属性被指定，则意味着提示播放器需要在该媒体播放至结尾后重新从头开始播放。

第4行的 poster 属性是video的特有属性，用来标识该媒体资源的海报（静态画面，一般来说是显示视频中第一个非空白帧）。如果指定了该属性，那么当媒体内容无效时，会显示指定的图片。该属性值是一个指向图片的URL。经过测试，在没有被缓存或者播放的情况下（内容没有载入时），都会显示该图片。

另外，video 元素还有两个特有的属性 videowidth 和 videoheight 。这两个属性是只读的，分别用来获取视频固有解析度的宽和高，如果未知则返回0。

audio 元素

audio 元素用来在页面中呈现一段音频或音乐。由于同样属于媒体元素，audio具有和video类似的内容模型和属性。与 video 不同的是，audio 是没有 width, height, poster 以及 videowidth 和 videoheight 的。很容易理解，audio 是没有视觉内容的，所以这些和显示有关的属性都没有。

看一个例子：

富士山下 - 陈奕迅

  1: <audio id="mp3" 
  2:   src="http://event1.wanmei.com/cb/response/upload/audio/witouch/1190691011788.mp3"  
  3:   controls  autobuffer loop autoplay
  4: />
  5: 

source 元素

source 元素是个比较特殊的元素，它是用来指定媒体元素的源信息的，换句话来说就是用以替代 audio 或者 video （或者如果有其他 media element ）中的 src 属性的，它比 src 属性提供了更为丰富的源信息。

source 元素可以为媒体元素指定多个资源，但它本身并不会有任何表现形式。该元素一般作为一个媒体元素的子元素，但也可以独立存在，在标准中并没有提到这一点。当它独立存在时，可以利用DOM和脚本来使用它。

source 元素不属于任何内容模型，它具有 src, type 和 media 这些特有属性。

• src 属性和 video, audio 的一样，是资源的有效URL，要注意的是，在 source 元素中，src是必须要有的。



• type 属性是用来指定资源类型的，其值应为有效的MIME类型字符串，例如 ”video/mp4” 等，从而帮助播放器判断要播放的媒体内容的类型。该属性有一个参数 codecs ，用来指定特定媒体编码解码器，例如 “mp4.v.20.8, mp4a.20.2” 。



• media 属性不是 source 元素特有的属性，也可以用于 link 等元素，它被用来指定一条 MQ （media query）。MQ是用来限定媒体使用的设备以及显示相关等范围的表达式，具体内容请参看 Mozilla Dev Center 。

参考示例（该示例来源于Mozilla 网站）

  1: <video controls>  
  2:   <source src="foo.ogg" type="video/ogg"> <!-- Picked by Firefox -->  
  3:   <source src="foo.mov" type="video/quicktime"> <!-- Picked by Safari -->  
  4:   I'm sorry; your browser doesn't support HTML 5 video.  
  5: </video>  

 

Media 元素（DOM）

Media Elements 实际上是 DOM 中这些媒体元素的基类型，audio 和 video 都可以看做是其子类型（但具体的情况要看浏览器的实现）。 src, autobuffer, autoplay, loop 以及 controls 这些个属性都是其共有的。

Media Elements 定义了一个接口，包括各种状态、常量、属性和方法，同时还定义了各种类型的事件，使得大家可以在脚本中很容易的操作。标准定义很长，请参看 W3C HTML5 - Media Element ，如果以后有相关的深入研究再写，现在用一个视频播放器的小例子来介绍其主要用法。

HTML5 Media Elements sample - Simple Video Player

 

安全和隐私

由于 video 和 audio 的资源可以来自其他网站，因此主要的安全与隐私上的考虑和影响是跨站攻击。这是浏览器实现要考虑的问题，就不再赘述。

HTML 5 Inside – Overview 总览

本文基于 HTM5 标准草案 2009年8月25日版
转载请保留出处：http://SamuelChen.net

HTML5并不是一个全新的语言，它只是在HTML4的基础上进行进化，去掉了一些内容修饰的tag，增加了许多新的特性。我们可以简单的认为 HTML5  = HTML4 - legacy features + colletion of new features
HTML5 有一个很重要的改变，那就是强化了语义。更多的标签引入带来了更加丰富的语义，使得爬虫、解析程序对页面的理解可以更加贴近人的理解。
下面从各个方面来说说。

兼容性

我们常说某某浏览器支持或者不支持HTML5，其实这个并不是一个严谨的说法。事实上，HTML只是一种标记性语言，它是被浏览器解析并渲染显示的，所以并不存在HTML5支持不支持，而应该是HTML5中某一元素是否能被浏览器支持。

由于HTML5是由HTML4发展而来，很多旧有的元素本身就能支持，因此，HTML5是兼容HTML4的，我们更多的是说某浏览器引擎是否支持HTML5中的某一特性。

 各浏览器引擎对元素的支持，来自 Comparison of layout engines (HTML5) - Wikipedia

那么自然而然就有一个问题，如何去判断一个浏览器是否支持某一个特性？我们可以通过创建一个元素是否成功来判断，比如创建函数supports_canvas() 用来判断是否支持canvas :

1:   function supports_canvas() {
2:     return !!document.createElement('canvas').getContext;
3:   }

然后调用这个函数来判断是否支持canvas :

1: if (supports_canvas()) {
2:   document.write("Your browser supports canvas.");
3: } else {
4:   document.write("Your browser does not support canvas.");
5: }

结果如图所示, Chrome4 支持 IE6 不支持:



有人将所有类似的函数封装成了一个库 Modernizr ，你可以直接使用 Modernizr.canvastext, Modernizr.video, modernizr.video.h264 等方式来判断是否支持指定的特性。

内容模型（Content Models）

HTML5采用了一种新的内容模型用以替代HTML4中block和inline的概念。

HTML5 中，所有的元素（Elements）都属于（拥有）某一个定义好的内容模型，这个内容模型描述了这个元素中可以包含哪些节点。

任何一个元素都归于0或多个内容分类，以便将具有相似特性的元素归组。HTML5标准中的内容分类有如下几种（某些元素也会归于其他分类）：

• Metadata content
• Flow content
• Sectioning content
• Heading content
• Phrasing content
• Embedded content
• Interactive content

这些分类之间的关系如图所示。

Metadata content 表示该内容用于设定内容的呈现、行为、文档（document）之间的关系或者传递外界信息（converys “out-of-band” information），基本上可以理解为元素的元数据。

base, command, link, meta, noscript, script, style, title 这些元素、属性或者标签都属于Metadata Content.

非HTML命名空间下的元素，如果它的语义主要是元数据相关的（metadata-related），那么它也是属于metadata content。比如引入第三方的namespace来支持RDF，那么此时就认为这个是属于 metadata content。如代码中所示:

1: <html xmlns="http://www.w3.org/1999/xhtml"
2:       xmlns:r="http://www.w3.org/1999/02/22-rdf-syntax-ns#">
3:  <head>
4:   <title>Hedral's Home Page</title>
5:   <r:RDF>
6:    <Person xmlns="http://www.w3.org/2000/10/swap/pim/contact#"
7:            r:about="http://hedral.example.com/#">
8:     <fullName>Cat Hedral</fullName>
9:     <mailbox r:resource="mailto:hedral@damowmow.com"/>
10:     <personalTitle>Sir</personalTitle>
11:    </Person>
12:   </r:RDF>
13:  </head>
14:  <body>
15:   <h1>My home page</h1>
16:   <p>This is my home page.</p>
17:  </body>
18: </html>

其他几个Content就不一一解释了，看着图加上顾名思义，都比较容易理解。请参考文档 Content Model on Spec 。

文档结构

HTML5 引入了多个新的元素用来更加细致的描述页面、文档结构，这些元素包括 header, nav, section, article, aside, footer ，用以替代目前的使用 div 或者 table 的方式。使用这些元素，作者可以让文档页面更加具有语义，更加易读，也可以让搜索引擎更好的理解页面的内容和各个部分之间的关系，应用API也能更容易、更准确细微的访问文档对象。

如下图（来自于smashing magzine）所示，非常清晰的表述了各个元素对应的文档内容关系。注意，这些元素并不包含布局信息。



其他变化

HTML5基本上是基于DOM的使用来定义该语言的，而HTML4和之前的版本是基于显示与布局的，所以我们在使用时要注意，出发点的不同会造成开发模式侧重点的不同。

沙箱，iframe的不同。HTML5中的iframe除了保留原有的嵌入网页的功能外，还增加了一个沙箱（sandbox）的新功能。这个沙箱功能使得在iframe中载入的网页能受到一系列限制，从而可以增加安全性和稳定性。使用这个功能，需要在iframe元素中使用”sandbox” 属性（attribut）。

可访问性的增强。增加了一些内建提高访问性（accessibility）的属性（比如hidden）、元素（比如progress）。

交互性增强。增加了命令（command）、菜单（menu）、拖拽（Drag & Drop）、撤销管理（Undo Manager）以及复制粘贴（Copy &  Paiste）等元素、属性或特性。

其他的一些变化，请参考spec，如果有时间会在后面的章节中介绍。

HTML5 标准中增强了对于作者（author）和用户代理（user agent）的描述，我将根据不同的上下文，将 author 称为作者、开发人员或者其他，将 user agent 称为客户程序、浏览器、搜索引擎、播放器（浏览器中）或者其他。

HTML 5 Inside - 深入HTML 5

 

本文基于 HTM5 标准草案 2009年8月25日版 以及 HTML5与HTML4的不同 2009年8月25日版 。
转载请保留出处：http://SamuelChen.net

HTML 5 的概念始于2003年，在2004年初期行成其第一个只包括form相关的一些内容的草案，并于同年被提请加入到W3C以探讨互联网应用的未来。显然，这么初步的提案是要被拒的，不过这也引起了很多公司的关注。不久之后，Apple、Mozilla 以及 Opera 都声明愿意继续在这个提案的基础之上进行进一步的研究工作，并将该提案转移到了WHATWG，同时建立了一个正式的公共邮件列表用以讨论。 直到2006年，W3C 才表示了对该提案的兴趣，并于2007年建立专项工作组和WHATWG共同工作。至此，所有的工作组才共同合作发展HTML5。

有人说，HTML5是改变Web开发的新起点，它增加了如此多的让人期待的特性，使得富浏览器端应用不再让人头疼；而也有人说，HTML 5 是W3C 平衡商业利益向WHATWG低头的产物，只是对HTML4进行了些许改进，没有好的设计与规划，只是一个劲的往里塞特性，实质上是一种倒退。

商业巨头们的战争，咱们小家寡民也甭咸吃罗卜淡操心，无论如何，HTML5是一个有着很大变化的新标准，其特性从实用层面上来看，也是非常不错的。

HTML 5 草案形成有一段时间了，同时也有很多的浏览器支持了，很多特性基本上已经定型，更多的只是在细节上变化。因此，在这儿更加详细和深入的研究它，并计划写一个系列记录及分享心得。

名字就叫 html 5 inside 了，至于能不能真正做到 inside 咱慢慢来吧，学而时习之，边学边写。

先来道开胃菜，大家看看这些应用和例子，相信能坚定大家看好HTML5的决心：

• 基于 webkit 的 video player （其实webkit的内容和播放视频无关）
• HTML5 canvas examples 这个里面有很多例子，还有很炫的游戏！
• 厉害的来了！ HTML+JS+SVG 的 Flash runtime !

索引 （可能会修改）

1. HTML 5 Inside – Overview 总览
2. HTML 5 Inside – Interative 交互
3. HTML 5 Inside – Canvas 画布
4. HTML 5 Inside – Multi Media 多媒体
5. HTML 5 Inside – Map 地图
6. HTML 5 Inside – Local Storage/Offline Cache 本地存储/离线缓存
7. HTML 5 Inside – Web Socket 页面上的套接字
8. HTML 5 Inside – Work Thread 工作线程
9. HTML 5 Inside – Messaging 消息
10. HTML 5 Inside – Drag & Drop 拖拽
11. HTML 5 Inside – Copy & Paste 复制粘贴
12. HTML 5 Inside – Dialog, Progress UI增强
13. HTML 5 Inside – DOM 文档对象结构
14. HTML 5 Inside – DataGrid 数据表格

 

Resources:

• Drive Into HTML 5 – Mark Filgrim
• Lachlan Hunt – W3C member
• More on developing naming conventions, Microformats and HTML5
• A Preview of HTML 5 – Lachlan Hunt
• Semantics in HTML 5 – John Allsopp
• Preparing for HTML5 with Semantic Class Names
• HTML 5 Tag Reference – W3C Shool
• HTML 5 Validator – W3C
• HTML5 and the future of the Web