December 2009 Archives

文件系统与大扇区

| 1 Comment | No TrackBacks

大扇区(超过旧式标准的512字节扇区)是改善硬件工艺或访问方式以后的一种直接提高存储密度的方法。对于磁介质来说,其盘片被分成若干的磁道(通常是同心圆)、每个磁道分成若干的扇区或称扇段,扇区是磁盘读写时的最小操作单元。对于基于闪存的存储设备而言,扇区则是一种模拟传统磁盘的概念。

对于磁盘来说,由于它是一种机械和电子一体化设备,由于各种原因的限制,其寻址和持续读写的可靠性方面都有一定的限制,例如,马达维持同样的转速,且磁头能够稳定在同一个位置,并将数据可靠地连续读写,可能只能持续8KiB或16KiB,为了提高可靠性,我们往往会需要在这之后重新校准设备。另一方面,对于随机写入的情形,较小的数据块有时会更为有利,同时,避免对磁介质的不必要的反复覆写,也有助于提高其使用寿命。因此,在磁道的基础上又引入了扇区的概念。

现代磁盘的设计中,扇区除了用户可见的部分之外,其前后还有一定的空隙用于定位和校验。这些空隙和其附近的介质一样可以用来保存数据,只是制造商和操作系统的撰写者通常不推荐使用这些空间。软盘上的这些空隙在DOS时代可以通过对控制器直接编程并改变扇区尺寸的方式强制覆写,并用类似的方法读出,从而起到一定的保密效果。

随着制造工艺的改善,现今的硬盘在十年前就早已不必受限于512字节的限制。由于在每个扇区前后都需要添加一些信息会浪费一部分空间并增加潜在的定位开销,因此硬盘制造商开始推出4KiB扇区的磁盘。这种磁盘在系统检测时会仍然汇报扇区尺寸是512字节,但物理扇区则是4KiB,并保持现有的512字节编址方式不便,从而与现有的BIOS保持兼容。

另一种已经存在一段时间的大扇区是Flash设备。这类设备采用的方法类似,不过其大扇区更多地是出于制造和避免不必要的擦写而不是提高存储密度考虑。

最后一种大扇区是RAID。许多RAID级别是一次性操作一整个stripe的,此时这种stripe也可以视为一种大扇区。

对于大扇区的支持主要是操作系统,特别是文件系统的责任,而应用程序只需确保自己操作的记录尽量是对齐的整块(例如,16K的记录,在文件中的偏移量都是从16K的整数倍开始)。文件系统需要保证应用程序对于磁盘的这种预期是能够满足的,换言之,文件系统的数据结构不应在磁盘上导致新的不对齐问题,这类不对齐可能是由于分区格式引起,也可能是文件系统本身的设计问题,如果存在这样的问题,操作系统中都需要予以纠正:例如,传统上从第63个512字节逻辑扇区开始的分区,可以牺牲掉一个512字节单元来换取对齐4KiB物理扇区的目的,由于对齐写入和读出操作需要的实际物理操作要少一半左右,因此这样做能够显著地改善性能并提高设备的使用寿命。

FreeBSD 9-CURRENT中目前已经支持通过GEOM子系统的stripe信息来描述磁盘或RAID的物理扇区尺寸以及GEOM相对于物理扇区的偏移量。新的ahci(4)驱动目前已经能够提供相关的GEOM信息给更上层的驱动程序了。

网址缩短服务

| 1 Comment | No TrackBacks

前一段时间帮一个朋友做了一个非常简单的网址缩短服务,已经上线运行了一段时间,这里把当时设计的一些想法分享出来,等有时间我会把代码也发布出来,程序很简单,用 web.py 做的。

网址缩短服务需要考虑两个问题,第一个问题是如何有效地查询,即,作为约束条件,在访问"短网址"的时候,它必须能够迅速的将结果返回;第二个问题是如何有效地将写操作复制出去。还有一点就是,缩短形成的短网址要真的越短越好。

接口

整个服务包括两个主要接口:一个是请求短网址,输入为网址(作为HTTP回应),输出为短网址;另一个是请求重定向,输入为短网址,输出为到短网址对应的真实网址的HTTP 302重定向回应。

设计

请求短网址的流程大致如下:

首先,检测输入的网址是否有效。

然后,计算输入的网址的 SHA256 散列值(计算时增加一个系统全局的salt值)的 URL-safe base64,并查找此散列串是否已经存在;如果已经存在,但对应的网址不同,目前版本将返回一异常(由于SHA256设计中的雪崩效应,这种情况基本可以忽略)。

如果不存在,则从前3位开始逐字向后取散列串,在查找表中查找到找到相同URL,或找不到结果为止;如果找不到结果,则将目前散列串的子串以及网址插入。

请求重定向的流程大致如下:

首先检测输入是否有效(不超长或超短)。

然后,直接从Berkeley DB中查找字符串对应的URL(实际实现中,将db文件以散列串首个字符命名,以利于未来将负载分散到不同的服务器)。

返回302回应。

未来的改进

目前的设计假定存在 2^0或2^1或2^2 .. 2^6 个节点能够提直接提供转向服务。转向回应信息可以在前端代理上永久缓存,因此可以通过增加前端代理服务器,而不是后端转向服务节点的方式来进行扩展。目前设计中故障转移等机制比较简单(根据SHA256计算出来的优先权值轮转),未来版本需要解决集群的原子提交问题。

目前的设计没有考虑自定义短网址,比如 foo.com/survey 这样的情况。这个问题可通过在长域名表(完整SHA256 base64与URL映射关系)基础上再增加一个查找表的方法来解决。

目前设计没有考虑删除以及禁止访问某些短网址的情况。

什么乱七八糟的东西都往数据库里面硬塞,该做的索引不做,不该做的索引一大堆,这再不慢等什么呢,天理难容嘛......

buffer和cache是两个经常被混为一谈的概念。从直观上说,两者都具备改善系统 I/O 吞吐量的能力,但是这两个概念是有区别的,其提高系统I/O吞吐量的原因也不尽相同。

cache改善系统性能的主要原因是数据访问的 局部性,即,通常应用程序在一段时间内操作的数据集的某个有限的部分,通常是很小的一部分。硬件实现的cache通常会只使用一小块(与主存相比)访问速度很快,但相对比较昂贵的存储部件,并放置于距离CPU较近的位置。

buffer改善系统性能的主要原因是减少不必要的状态切换和设备I/O。由于制造工艺等个方面的原因,系统中不同部件的速度往往是不一样的,一次进行批量的操作(例如,预先读取,或者将写数据凑成一个整数之后再写),往往要比到需要时等待这些操作完成要节省时间,并且有效地降低状态切换导致的开销。

还有一个比较显著的区别是,cache通常是硬件或OS提供,用户程序不需要(多数情况下也没有办法)为其分配存储的机制,通常它在使用者,如用户程序看来是透明的,它属于提供cache的一方而不是其使用者;而buffer往往是由用户程序知道并且与OS共享(换言之,用户程序需要分配一块内存,并告诉OS这块内存将要用于某种操作),或由OS分配,并在主机和外设之间共享(例如网卡的DMA buffer),在使用者看来它通常不是透明的,这些内存往往属于控制内存的程序,如用户程序,或OS,而不是向其传递数据的OS,或硬件。

不过,这个区别主要是传统意义上的cache。最近几年引入的一些新概念,特别是Internet cache并不能用这种方法来区分。我认为最关键的区别其实在于,buffer主要作用是在于减少实际的I/O操作次数,即,将多次操作尽量合并成一次的成批操作,通常其中的数据在操作完成之后,buffer不会被继续使用;而cache的主要作用在于更好地利用局部性原理,减少不必要的I/O,避免代价昂贵(例如,速度很慢)的I/O操作。

SU+J

| No Comments | No TrackBacks

Jeff Roberson 下周左右将会正式发表对于 UFS 的一项改进,为 Soft Updates 加入 Journal-ling,从而简化其恢复逻辑,并消除对 fsck 的依赖。

目前常见的保持元数据一致性的方法有四种:最原始的、将元数据以同步方式写盘的方法,性能非常差;常见的文件系统中使用的元数据回写日志(如ext3),缺点是无法检验日志本身的正确性,而且元数据需要写入两次因此对性能有潜在影响;Soft Updates,缺点是需要运行fsck来释放资源泄漏,而这个操作很耗时,且实现本身比较复杂;Copy-on-Write,在WAFL和ZFS中采用的技术,随着硬盘的淘汰随机存取时间不再是性能瓶颈,应该是未来的发展趋势,目前的缺点是会导致产生较多碎片。SU+J结合了Soft Updates和Journalling的优点,即,使用Soft Updates来确保写到磁盘上的数据的一致性,而使用Journalling来确保资源泄漏能够迅速回收,从而消除了fsck的必要性。

非常期待看到明年BSDCan的presentation。虽然目前我拿到的代码还有少量毛边,但是总体来说这次改进:

  • 不需要修改磁盘上的文件系统数据结构,因此能够用于现有系统;
  • 减少了 Soft Updates 本身的复杂性,每个事务所需的描述数据只需32个字节,扫完32K次操作(1MB日志数据)需要的时间只需2秒不到;
  • 极大地减少了由于 fsck 需要吃很多内存、很多 I/O 导致的恢复速度慢的问题,这个实现基本上可以不再使用fsck了

服务器挂了

| No Comments | No TrackBacks
如题。其实已经算是超期服役了,这次是硬件故障,相当严重的硬件故障,不过还是希望能多用一段时间。

Monthly Archives

Pages

OpenID accepted here Learn more about OpenID
Powered by Movable Type 5.2.11