缘起

sqlite写入500条不大的记录居然要花费20多秒的时间，太慢了！！！

分析

sqlite是一个非常优秀的嵌入式数据库，读取性能非常好，写入性能就比较差一些，为什么写入性能差呢？下面做了一个测试。

下面是对500+条记录些操作的系统调用的观察，发现时间基本花费在了fdatasync系统调用上，调用2064次；write系统调用虽然8049次，但是write并不保证逻辑，所以速度很快。

$ strace -c php test.php 
27.688107013702 （耗时27.6s）
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 88.73    0.073919          36      2064           fdatasync
  3.88    0.003231           0      8049           write
  3.77    0.003144           6       516           unlink
  1.12    0.000929           0      6730           fcntl64
  0.90    0.000751           0      9118         3 _llseek
  0.86    0.000720           1      1218        82 open
  0.24    0.000198           0      1143           close
  0.20    0.000167           0      1182           read
  0.16    0.000131           0       520       518 access
  0.05    0.000039           1        42         1 lstat64
  0.04    0.000033           0       194           mmap2
  0.03    0.000027           0        92           munmap
  0.03    0.000021           0        58        49 stat64
  0.00    0.000000           0         1           execve
  0.00    0.000000           0        20           time
  0.00    0.000000           0        21           brk
  0.00    0.000000           0         3         2 ioctl
  0.00    0.000000           0         3           gettimeofday
  0.00    0.000000           0         1           readlink
  0.00    0.000000           0         2           uname
  0.00    0.000000           0        28           mprotect
  0.00    0.000000           0         4           poll
  0.00    0.000000           0         5           rt_sigaction
  0.00    0.000000           0         2           rt_sigprocmask
  0.00    0.000000           0         2           getcwd
  0.00    0.000000           0         1           getrlimit
  0.00    0.000000           0       648           fstat64
  0.00    0.000000           0         4           futex
  0.00    0.000000           0         1           sched_setaffinity
  0.00    0.000000           0         2           sched_getaffinity
  0.00    0.000000           0         1           set_thread_area
  0.00    0.000000           0         1           set_tid_address
  0.00    0.000000           0         1           set_robust_list
  0.00    0.000000           0         4           socket
  0.00    0.000000           0         4         2 connect
  0.00    0.000000           0         1           send
  0.00    0.000000           0         1           recvfrom
  0.00    0.000000           0         1           shutdown
  0.00    0.000000           0         5           setsockopt
------ ----------- ----------- --------- --------- ----------------
100.00    0.083310                 31693       657 total

$ strace -c php test.php

27.688107013702 （耗时27.6s）

% time seconds usecs/call calls errors syscall

------ ----------- ----------- --------- --------- ----------------

88.73 0.073919 36 2064 fdatasync

3.88 0.003231 0 8049 write

3.77 0.003144 6 516 unlink

1.12 0.000929 0 6730 fcntl64

0.90 0.000751 0 9118 3 _llseek

0.86 0.000720 1 1218 82 open

0.24 0.000198 0 1143 close

0.20 0.000167 0 1182 read

0.16 0.000131 0 520 518 access

0.05 0.000039 1 42 1 lstat64

0.04 0.000033 0 194 mmap2

0.03 0.000027 0 92 munmap

0.03 0.000021 0 58 49 stat64

0.00 0.000000 0 1 execve

0.00 0.000000 0 20 time

0.00 0.000000 0 21 brk

0.00 0.000000 0 3 2 ioctl

0.00 0.000000 0 3 gettimeofday

0.00 0.000000 0 1 readlink

0.00 0.000000 0 2 uname

0.00 0.000000 0 28 mprotect

0.00 0.000000 0 4 poll

0.00 0.000000 0 5 rt_sigaction

0.00 0.000000 0 2 rt_sigprocmask

0.00 0.000000 0 2 getcwd

0.00 0.000000 0 1 getrlimit

0.00 0.000000 0 648 fstat64

0.00 0.000000 0 4 futex

0.00 0.000000 0 1 sched_setaffinity

0.00 0.000000 0 2 sched_getaffinity

0.00 0.000000 0 1 set_thread_area

0.00 0.000000 0 1 set_tid_address

0.00 0.000000 0 1 set_robust_list

0.00 0.000000 0 4 socket

0.00 0.000000 0 4 2 connect

0.00 0.000000 0 1 send

0.00 0.000000 0 1 recvfrom

0.00 0.000000 0 1 shutdown

0.00 0.000000 0 5 setsockopt

------ ----------- ----------- --------- --------- ----------------

100.00 0.083310 31693 657 total

查资料

http://www.cnblogs.com/KimSky/archive/2011/05/31/2064028.html

发现：如果使用事务的方式批量插入数据，效果会有明显改善，因为默认情况下每次写入操作都会落地才返回的（更加安全靠谱），如果使用事务，则批量数据一次性落地。

修改代码，分析系统调用如下：（发现fdatasync调用12次）

$ strace -c php test.php 
0.20949816703796 （耗时 209ms）
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 71.64    0.000998          83        12           fdatasync
  7.61    0.000106           1       155           read
  5.24    0.000073           0       194           mmap2
  4.16    0.000058           0       195           write
  2.58    0.000036           0       135           fstat64
  1.65    0.000023           0        92           munmap
  1.58    0.000022           1        28           mprotect
  1.51    0.000021           1        42         1 lstat64
  1.44    0.000020          20         1           readlink
  1.29    0.000018           0       238         3 _llseek
  1.29    0.000018           0        58        49 stat64
  0.00    0.000000           0       192        82 open
  0.00    0.000000           0       117           close
  0.00    0.000000           0         3           unlink
  0.00    0.000000           0         1           execve
  0.00    0.000000           0        20           time
  0.00    0.000000           0         7         5 access
  0.00    0.000000           0        21           brk
  0.00    0.000000           0         3         2 ioctl
  0.00    0.000000           0         3           gettimeofday
  0.00    0.000000           0         2           uname
  0.00    0.000000           0         4           poll
  0.00    0.000000           0         5           rt_sigaction
  0.00    0.000000           0         2           rt_sigprocmask
  0.00    0.000000           0         2           getcwd
  0.00    0.000000           0         1           getrlimit
  0.00    0.000000           0        61           fcntl64
  0.00    0.000000           0         4           futex
  0.00    0.000000           0         1           sched_setaffinity
  0.00    0.000000           0         2           sched_getaffinity
  0.00    0.000000           0         1           set_thread_area
  0.00    0.000000           0         1           set_tid_address
  0.00    0.000000           0         1           set_robust_list
  0.00    0.000000           0         4           socket
  0.00    0.000000           0         4         2 connect
  0.00    0.000000           0         1           send
  0.00    0.000000           0         1           recvfrom
  0.00    0.000000           0         1           shutdown
  0.00    0.000000           0         5           setsockopt
------ ----------- ----------- --------- --------- ----------------
100.00    0.001393                  1620       144 total

$ strace -c php test.php

0.20949816703796 （耗时 209ms）

% time seconds usecs/call calls errors syscall

------ ----------- ----------- --------- --------- ----------------

71.64 0.000998 83 12 fdatasync

7.61 0.000106 1 155 read

5.24 0.000073 0 194 mmap2

4.16 0.000058 0 195 write

2.58 0.000036 0 135 fstat64

1.65 0.000023 0 92 munmap

1.58 0.000022 1 28 mprotect

1.51 0.000021 1 42 1 lstat64

1.44 0.000020 20 1 readlink

1.29 0.000018 0 238 3 _llseek

1.29 0.000018 0 58 49 stat64

0.00 0.000000 0 192 82 open

0.00 0.000000 0 117 close

0.00 0.000000 0 3 unlink

0.00 0.000000 0 1 execve

0.00 0.000000 0 20 time

0.00 0.000000 0 7 5 access

0.00 0.000000 0 21 brk

0.00 0.000000 0 3 2 ioctl

0.00 0.000000 0 3 gettimeofday

0.00 0.000000 0 2 uname

0.00 0.000000 0 4 poll

0.00 0.000000 0 5 rt_sigaction

0.00 0.000000 0 2 rt_sigprocmask

0.00 0.000000 0 2 getcwd

0.00 0.000000 0 1 getrlimit

0.00 0.000000 0 61 fcntl64

0.00 0.000000 0 4 futex

0.00 0.000000 0 1 sched_setaffinity

0.00 0.000000 0 2 sched_getaffinity

0.00 0.000000 0 1 set_thread_area

0.00 0.000000 0 1 set_tid_address

0.00 0.000000 0 1 set_robust_list

0.00 0.000000 0 4 socket

0.00 0.000000 0 4 2 connect

0.00 0.000000 0 1 send

0.00 0.000000 0 1 recvfrom

0.00 0.000000 0 1 shutdown

0.00 0.000000 0 5 setsockopt

------ ----------- ----------- --------- --------- ----------------

100.00 0.001393 1620 144 total

结论：

1. 借用事务采用批量写入的方式来加速写操作

2. 如果业务上不能批量操作呢？似乎有一个nosync的sqlite版本（不知道为什么不是一个配置选项）

参考资料： http://www.sqlite.org/speed.html

3. 如果数据量太大，可以分多批提交事务，因为事务是需要内存的。（不过，sqlite一般不会存放N个G的数据的，几百MB已经算是比较大的了，这样的数据量内存还是吃的消的）

参考资料：

http://www.phpchina.com/archives/view-33876-1.html

关于sqlite的系列分析文章（可以看看）

http://www.cnblogs.com/hustcat/archive/2009/02/12/1389448.html

SQLite的原子提交原理

http://www.cnblogs.com/vagerent/archive/2008/11/05/1327247.html

关于mysql的几个小知识

1. 在insert语句不设置超时时间的情况下，如果server端磁盘满了，则client端可能会被无限期阻塞

2. InnoDB的show table status中显示的rows是一个约数，上下差别还比较大，确数需要用select count(*)来计算；

PHP实现的一维关联数组序列化

下面是一个典型的k-v存储格式的PHP实现：

class db {
        public function test() {
         //.....
        }
	private function pack($arr) {
		$str = '';
		foreach($arr as $key=>$val) {
			$str .= pack("n", strlen($key)).pack("n", strlen($val)).$key.$val;
		}
		return $str;
	}
	private function unpackUserInfo($str) {
		$arrResult = array();
		$len = strlen($str);
		if ($len < 5) return $arrResult;
		$pos = 0;
		while($len - $pos >= 5) {
			$arr1 = unpack("n", substr($str, $pos, 2));
			$arr2 = unpack("n", substr($str, $pos+2, 2));

			$len_key = $arr1[1];
			$len_val = $arr2[1];
			$key = substr($str, $pos + 4, $len_key);
			$val = substr($str, $pos + 4 + $len_key, $len_val);
			$pos += 4 + $len_key + $len_val;
			$arrResult[$key] = $val;
		}
		return $arrResult;
	}

}

class db {

public function test() {

//.....

}

private function pack($arr) {

$str = '';

foreach($arr as $key=>$val) {

$str .= pack("n", strlen($key)).pack("n", strlen($val)).$key.$val;

}

return $str;

}

private function unpackUserInfo($str) {

$arrResult = array();

$len = strlen($str);

if ($len < 5) return $arrResult;

$pos = 0;

while($len - $pos >= 5) {

$arr1 = unpack("n", substr($str, $pos, 2));

$arr2 = unpack("n", substr($str, $pos+2, 2));

$len_key = $arr1[1];

$len_val = $arr2[1];

$key = substr($str, $pos + 4, $len_key);

$val = substr($str, $pos + 4 + $len_key, $len_val);

$pos += 4 + $len_key + $len_val;

$arrResult[$key] = $val;

}

return $arrResult;

}

注意：

1. pack(“n”,…) 使得key、value长度都限制在65535以内

IE6下经典的请求abort问题

摘自：http://www.cnblogs.com/shihao/archive/2012/06/22/2559042.html

IE6 a标签的请求被abort的原因

最近项目中掉进IE6 a标签abort两次坑，第一次是a标签绑定一个事件，href='javascript:;'这样a标签触发了事件，切换验证码图片，结果验证码图片总是显示不出来，通过抓包显示状态为abort。其实这个的原因可以从IE6中a标签执行顺序说起，IE6中a标签执行onclick在执行默认事件（即href跳转）之前，当触发了绑定的事件之后，那么处理完事件之后，如果不return false或者阻止默认事件，则会继续执行href跳转，IE6会认为页面跳转到其他页面或者页面重新刷新，则abort之前onclick事件中的请求。

所以当onclick时，做出的获取最新验证码图片的请求，会因为下一步href的触发而abort。同时，如果你在a绑定的事件中做ajax请求，那么也会被无情的abort。

IE6 a标签的请求被abort的解决方案

解决的方法就是在onclick或者绑定事件中return false来阻止a标签跳转的默认事件。
例如下面的代码：

&lt;a href="javascript:void(0)" onclick="fn();return false;"&gt;Test&lt;/a&gt;

1	<a href="javascript:void(0)" onclick="fn();return false;">Test</a>

或者你也可以给a标签的href写成“#”，即当前页面的锚点，这样页面就不会跳转，自然不会abort请求。

最好的方式还是两种都用，保险！

其他参考资料：

http://www.web92.net/758.html

http://www.cnblogs.com/Ren_Lei/archive/2010/09/26/1836130.html

面试题

编写算法，从10亿个浮点数当中，选出其中最大的10000个。

1、读入的头10000个数，直接创建二叉排序树。O(1)
2、对以后每个读入的数，比较是否比前10000个数中最小的大。(N次比较)如果小的话接着读下面的数。O(N)
3、如果大，查找二叉排序树，找到应当插入的位置。
4、删除当前最小的结点。
5、重复步骤2，直到10亿个数全都读完。
6、按照中序遍历输出当前二叉排序树中的所有10000个数字。
基本上算法的时间复杂度是O(N)次比较
算法的空间复杂度是10000(常数)

Bloom Filter算法及应用

1. 引言
问题：有1000瓶药，但是其中有一瓶是有毒的，小白鼠吃了24小时后就会死掉，请问，在24小时找出有毒的药物，最少需要多少只小白鼠？
答案是：10只，一只小白鼠可以表示2种状态，2^10可以表示1024种状态
分析可参考：http://lzj0470.iteye.com/blog/657579
通过二进制向量组来扩展描述的状态，Bloom Filter(BF)算法也是利用这个思想，其本质是上是一个很长的二进制向量和一系列随机映射函数

2. 概述
问题：快速判断一个元素是否在一个集合中
解决方法：一般来说，我们会用HASH表来存储集合中的数据，好处是快速准确，缺点是存储效率低，在海量数据时一般服务器无法存储。
BF是针对哈希表存储效率低的问题，而衍生出来的一种算法。
其通过利用二进制数组来描述一个集合，来判断一个元素是否属于这个集合
优点是：快速查找，并具有非常高的存储效率
缺点是：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合

3. 算法描述
BF包含：
1)一个m位的二进位数组，每一位初始化时置为0
2)k个相互独立的hash函数
算法：
针对一个n个元素的集合，通过k个hash函数，将集合中的每个元素都映射到二进位数组中，映射到的位置置为1
例如：对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1
在判断某个元素P是否在这个集合时，通过对P应用k次hash函数，判断其对应所有的位置都是1，如果是则认为P是集合中的元素，否则不是。

4. 最优位数组m大小及hash函数个数
在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合。因此，如何根据输入元素个数n，确定位数组m的大小及hash函数个数是一个非常重要的问题。
经过一些复杂的证明（可参考相关文档），可以得到：
1）当hash函数个数k=(ln2)*(m/n)时错误率最小
2）在错误率不大于E的情况下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合，但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)的1.44倍

5. 应用
有10亿个url，如何判断一个新的url是否在这个url的集合中？
一个url平均长度为52，如果用Hash表解决的话，由于Hash表的存储效率一般只有50%，因此10个url大概需要100G内存，一般服务器无法存储。
使用BF，要求错误率小于万分之一。
此时，输入元素n=10亿，最大错误率E=0.0001
可计算出：m=nlg(1/E)*1.44=57.6亿，大概需要7.2亿（57.6亿/8）个字节，即720M内存。
Hash函数个数：k=(ln2)*(m/n) 大概4个Hash函数

6.总结
BF通过牺牲一定的错误率来保证时间和空间（鱼与熊掌，不可兼得），目前被广泛应用于海量数据处理及数据库系统中。
例如，在Big table和Cassandra中，都使用BF作为索引结构。
P.S 针对BF的错误识别问题，可以通过建立白名单的方式解决。

参考文献：
paper：Network Applications of Bloom Filters: A Survey
http://blog.csdn.net/jiaomeng/article/details/1495500

迅雷面试题

1.给你10台机器，每个机器2个cpu，2g内存，现在已知在10亿条记录的数据库里执行一次查询需要5秒，问用什么方法能让90%的查询能在100毫秒以内返回结果。
2.一个长度为10000的字符串，写一个算法，找出最长的重复子串，如abczzacbca,结果是bc。最后就做出这一道题目，时间复杂度为O(n!), 空间复杂度为O(n)。

算法题：
1.连接两个单向链表，返回排序后的结果。
2.一个保存有10000个URL的文本文件，删除其中相同的URL。
3.将9个石子放在9×9的方格中，要求同行、同列、45度上无两个石子。

智力题：
1.一笔画四条直线穿过3×3的9个点。
2.国王给三个囚犯每人戴了一顶帽子，帽子不是黑色就是白色，并且告诉囚犯们谁看到其它两个人都是白帽子或者知道自己戴的是黑帽子，谁就能被释放。囚犯们能看到其它的人帽子颜色，但是看不到自己的帽子颜色。过了一段时间，三个囚犯都没有说话，其中一个聪明的囚犯立刻肯定自己戴的是黑帽子，你知道为什么吗？
3.有16个硬币，A和B轮流拿，每次拿的个数只能是1，2，4之一，谁最后拿谁就输。问可以保证赢吗？?

文件的打开方式

用法：

1. 不存在则创建之，存在则直接用之

因为w/w+ 会清空文件，故不用

2. 打开文件后可以随意改写和读取文件的任何部分

因为 a/a+ 不能随意seek到文件的任意位置，故不用

**fopen()** 中 *`mode`* 的可能值列表
`mode`	说明
‘r’	只读方式打开，将文件指针指向文件头。
‘r+’	读写方式打开，将文件指针指向文件头。
‘w’	写入方式打开，将文件指针指向文件头并将文件大小截为零。如果文件不存在则尝试创建之。
‘w+’	读写方式打开，将文件指针指向文件头并将文件大小截为零。如果文件不存在则尝试创建之。
‘a’	写入方式打开，将文件指针指向文件末尾。如果文件不存在则尝试创建之。
‘a+’	读写方式打开，将文件指针指向文件末尾。如果文件不存在则尝试创建之。
‘x’	创建并以写入方式打开，将文件指针指向文件头。如果文件已存在，则 fopen() 调用失败并返回 `FALSE`，并生成一条 `E_WARNING`级别的错误信息。如果文件不存在则尝试创建之。这和给底层的 open(2) 系统调用指定 O_EXCL\|O_CREAT 标记是等价的。
‘x+’	创建并以读写方式打开，其他的行为和 ‘x’ 一样。

注意：

1. w+ 方式总是会把原文件清空的

2. a+ 方式是不能来回fseek的

所以，或许你需要的是 r+ 方式，自己先判断一下文件是否存在，不存在则创建之即可

关于文件的最后修改时间

有这么一个现象，明明看着日志文件的最后修改时间不断地变化，但是日志内容却没有增长，看了一下是磁盘空间满了；

这里说明一个逻辑，对于已存在的文件，即使磁盘空间满了，更新文件的时候虽更新失败，依然会导致文件的最后修改时间发生变化；推测：更新文件内容时，应该是先更新文件的最后修改时间，然后再更新内容的；如果更新最后修改时间在后，似乎程序员不会让更新内容失败的情况下依然去更新最后修改时间的

fgets的第二个参数

缘起

string fgets ( resource $handle [, int $length ] );

第二个参数指定可以读取的最大长度，但是比较有意思的是，如果最终没有读取到换行，则返回的不是$length个字节，而是 $length -1 个字节，文档是这么写的，事实也是这样子的，那么为什么制造这么一个小插曲呢？说多少就是多少不是很好嘛，为什么还要少一个字节呢？

分析

因为PHP是用c写的，这可能也不是PHP故意如此的，或许C就是这样的，于是：

man fgets

…

fgets() reads in at most one less than size characters from stream and stores them into the buffer pointed to by
s. Reading stops after an EOF or a newline. If a newline is read, it is stored into the buffer. A ‘\0’ is
stored after the last character in the buffer.

…

看来这和字符串buffer的长度是有关系的，字符串总是要以”\0″（是零不是欧）结尾的，所以真正得到的长度比指定的长度是小1的。

如果一行是3个字符（带上换行），这时候，指定fgets的最大长度为3，则读不出来换行，只能读到2个字符，写一次才能读到换行

PHP版的tail -f

缘起

每天生成一个文件，用一个程序实时读文件，类似tail -f ，但是程序需要能自动切换文件

问题

脚本

<?php
$fp = fopen("a.txt", "r");
while(1) {
    $ret = fgets($fp);
    if ($ret === false){ 
        sleep(1); 
        fseek($fp, 0, SEEK_CUR);  // 如果没有fseek，则新的内容将无法读出来
    }
    echo $ret;
}

<?php

$fp = fopen("a.txt", "r");

while(1) {

$ret = fgets($fp);

if ($ret === false){

sleep(1);

fseek($fp, 0, SEEK_CUR); // 如果没有fseek，则新的内容将无法读出来

}

echo $ret;

}

具体可参考fseek的实现：main/streams/streams.c

strace: ptrace(PTRACE_CONT,1,133): Input/output error

这是strace的一个bug，已经修复：

https://bugzilla.redhat.com/show_bug.cgi?id=590172

https://bugzilla.redhat.com/show_bug.cgi?id=594616

PHPor 的Blog

关于sqlite的事务的使用

缘起

分析

查资料

结论：

关于mysql的几个小知识

PHP实现的一维关联数组序列化

IE6下经典的请求abort问题

IE6 a标签的请求被abort的原因

IE6 a标签的请求被abort的解决方案

面试题

文件的打开方式

关于文件的最后修改时间

fgets的第二个参数

缘起

分析

PHP版的tail -f

缘起

问题

脚本

strace: ptrace(PTRACE_CONT,1,133): Input/output error