Archive for 九月, 2012

背景

         MySQL中在对某个字段做包含匹配时可以用like。

先看这个结构和结果

 

CREATE TABLE `tb` ( 

`id` int(11) NOT NULL AUTO_INCREMENT,

`user_id` bigint(20) DEFAULT NULL,

`title` varchar(128) NOT NULL,

`memo` varchar(2000) DEFAULT NULL,

PRIMARY KEY (`id`),

KEY `title` (`title`)

) ENGINE=InnoDB DEFAULT CHARSET=utf8;

 

 

mysql> explain select * from tb where title like ‘%abcd%’;

+—-+————-+——-+——+—————+——+———+——+——+————-+

| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra       |

+—-+————-+——-+——+—————+——+———+——+——+————-+

|  1 | SIMPLE      | tb    | ALL  | NULL          | NULL | NULL    | NULL |    1 | Using where |

+—-+————-+——-+——+—————+——+———+——+——+————-+

1 row in set (1.65 sec)

 

由于like用的是 ‘%xx%’, 不符合前缀匹配的规则,因此用不上索引title,只能作全表扫描。

 

问题

以上为官方回答。但是如果是在 InnoDB这种聚集索引组织的表中,假设这个表单行很大,比如后面还有若干个类似memo的字段。

这样聚集索引会很大,导致全表扫描需要读更多的磁盘。而理想情况应该是这个流程

1)       遍历title索引,从中读取和过滤所有title中匹配like条件的id

2)       用id到聚簇索引中读数据。

在单行很大,而like能够过滤掉比较多语句的情况下,上面的流程肯定比全表扫描更快,也更省资源。

 

FORCE INDEX行不行?

         第一个反应是用force index。

mysql> explain select * from tb force index(title) where title like ‘%abcd%’; 

+—-+————-+——-+——+—————+——+———+——+——+————-+

| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra       |

+—-+————-+——-+——+—————+——+———+——+——+————-+

|  1 | SIMPLE      | tb    | ALL  | NULL          | NULL | NULL    | NULL |    1 | Using where |

+—-+————-+——-+——+—————+——+———+——+——+————-+

1 row in set (0.00 sec)

 

 

显然不行。原因是通常情况下,force index只能从possible_keys中强制选择某一个索引,但是这个查询的possible_keys是NULL, force index 无效。

 

覆盖索引

我们想到覆盖索引,试验这个语句。

mysql> explain select id from tb  where title like ‘%abcd%’; 

+—-+————-+——-+——-+—————+——-+———+——+——+————————–+

| id | select_type | table | type  | possible_keys | key   | key_len | ref  | rows | Extra                    |

+—-+————-+——-+——-+—————+——-+———+——+——+————————–+

|  1 | SIMPLE      | tb    | index | NULL          | title | 386     | NULL |    1 | Using where; Using index |

+—-+————-+——-+——-+—————+——-+———+——+——+————————–+

1 row in set (0.00 sec)

 

我们看到这个语句用上了title索引,而且Using index表明用上了覆盖索引。

 

有同学可能会疑惑,这里possible_keys是NULL, 为什么key用上了title,应了那句“nothing imposible”?

 

实际上在MySQL优化器里面专门加了这一段,在type= JT_ALL时,会特别扫一下所有能够满足的覆盖索引,并找长度最短的那个。

这么做的考虑就是基于选择小的索引,减少读盘。重要的是,这个优化对于现有的引擎是通用的。

 

因此上面说的“通常情况下”的例外就是:force index可以强制使用覆盖索引。比如常见的 select count(*) from tb. 这时候你force index所有已存在的索引都是可以生效的。

 

权宜之计

了解了覆盖索引的效果,我们可以把查询改写为如下,以满足我们最开始希望的执行流程。

mysql> explain Select * from (select id from tb where title like ‘%a’) t1 join tb  using (id); 

+—-+————-+————-+——–+—————+————+———+——-+——+————————–+

| id | select_type | table       | type   | possible_keys | key        | key_len | ref   | rows | Extra                    |

+—-+————-+————-+——–+—————+————+———+——-+——+————————–+

|  1 | PRIMARY     | <derived2>  | system | NULL          | NULL       | NULL    | NULL  |    1 |                          |

|  1 | PRIMARY     | tb | const  | PRIMARY       | PRIMARY    | 4       | const |    1 |                          |

|  2 | DERIVED     | tb | index  | NULL          | idx_userid | 386     | NULL  |    1 | Using where; Using index |

+—-+————-+————-+——–+—————+————+———+——-+——+————————–+

3 rows in set (0.00 sec)

 

 

从explain结果中看执行流程是按照我们之前描述的那样,但是引入了JOIN。

 

 补充说明

JOIN写法还会引入primary key查询的时候是随机查询,因此最终的效率受like的过滤效果影响。

 

这个改写对性能的提升效果取决于要使用的索引与总数据量的大小比较,需要作应用测试。

 

zz from: http://dinglin.iteye.com/blog/1687358

好代码的标准各不相同,根据不同的应用场景也有所区别,但总有一些共性,下文是Robert Martin提出的SOLID类设计原则,推荐一下。

附评几条,我认为最易于实行的,也比较容易出效果的:

l  单一责任原则:只有一个理由去修改一个类。想做到这点,直接的方式是,每个方法只做一件事情(能用一句话描述清楚的事情),一个类中的所有方法只做一种类型的事情(检验修改理由是否只有一种)。

l  不要自我重复:想cp+修改代码前,思考能否将公共部分重构为类或者方法。

l  接口分离原则:一个类对另一个类的依赖应该限制在最小化的接口上。

l  你不需要它:不要添加你“认为以后可能有用”的代码。只在“事到临头”时才添加代码。 我们做架构时经常考虑扩展性,怎样把握扩展和过度设计,这个还真是得在屡败屡战中积累经验了。不过当结合到单一责任原则,使模块、类间耦合较小,我们先写简单的代码,当需要扩展时,也可以保证修改范围可控。

l  简单化,傻瓜化(KISS):让它能工作的最简单的方法是什么?和“你不需要它”其实说的一回事,当只有10w pv时,我们去考虑1亿pv时的问题,就叫自讨苦吃。但是也得平衡的是,怎样做到风险预估,在危险真正来临前解决它。

 

设计是一门艺术,不是简单的背熟设计模式,而是在实践中不停摸索、调整的过程,期待与大家共进步。

 

 

S.O.L.I.D.类设计原则

本文是由敏捷宣言签署人之一、《 Clean Code(代码整洁之道)》一书的作者Robert C. Martin为他的《Applying Principles and Patterns》这本书搜集整理而来。

单一责任原则(SRP)

只有一个理由去修改一个类。例如,如果一个业务规则的改变会导致这个类的修改,那么,数据库、界面、报表格式或系统任何其它的部分的改变都不该迫使这个类做修改。

开发/关闭原则(OCP)

软件构成(类,模块,方法等)向扩展行为开放,向修改行为关闭。

Liskov替换原则(LSP)

子类必须能够用来当作基类使用。如果类A继承类B,任何能使用A的地方,B也同样可以使用。例如,是否还记得,正方形可以看作是矩形!当进行扩展时:前提条件不许绕过,后置条件不能放宽限制,可见常量不能被修改(?)。常量:在扩展之前或之后,用户都需要依靠这个常量来传递信息。正确的使用set形式的继承关系。不遵守set语义是非常危险的。归纳:使用超类的引用的任何上下文中也可以使用其子类的引用替代。这个原则极大的限制了在纯扩展(继承)机制里可以做的事情。不遵守会带来风险。

接口分离原则(ISP)

一个类对另一个类的依赖应该限制在最小化的接口上。

反向依赖原则(DIP)

依赖抽象层(接口),而不是具体类。

其它重要原则

Demeter定律

也被称做封锁信息原则:只跟朋友交流

一个对象O的任何一个方法M只能调用下列类型的对象的方法:

  • 它自己
  • 它的参量
  • 它创建/实例化的对象
  • 它的直接组件对象

参考

好莱坞原则

不要调用我,我会调用你的。

不要自我重复(DRY)

去掉重复代码。

对接口编程,而不是对实现

反向依赖的另外一种说法。

你不需要它(YAGNI)

不要添加你“认为以后可能有用”的代码。只在“事到临头”时才添加代码。

简单化,傻瓜化(KISS)

让它能工作的最简单的方法是什么?

 

zz from: http://www.aqee.net/s-o-l-i-d-class-design-principles/

作者:richard_ma ,发布于2012-7-2

许多人用shell脚本完成一些简单任务,而且变成了他们生命的一部分。不幸的是,shell脚本在运行异常时会受到非常大的影响。在写脚本时将这类问题最小化是十分必要的。本文中我将介绍一些让bash脚本变得健壮的技术。

使用set -u

你因为没有对变量初始化而使脚本崩溃过多少次?对于我来说,很多次。

chroot=$1

rm -rf $chroot/usr/share/doc 如果上面的代码你没有给参数就运行,你不会仅仅删除掉chroot中的文档,而是将系统的所有文档都删除。那你应该做些什么呢?好在bash提供了set -u,当你使用未初始化的变量时,让bash自动退出。你也可以使用可读性更强一点的set -o nounset。

david% bash /tmp/shrink-chroot.sh

$chroot=

david% bash -u /tmp/shrink-chroot.sh

/tmp/shrink-chroot.sh: line 3: $1: unbound variable

david%

使用set -e

你写的每一个脚本的开始都应该包含set -e。这告诉bash一但有任何一个语句返回非真的值,则退出bash。使用-e的好处是避免错误滚雪球般的变成严重错误,能尽早的捕获错误。更加可读的版本:set -o errexit

使用-e把你从检查错误中解放出来。如果你忘记了检查,bash会替你做这件事。不过你也没有办法使用$?来获取命令执行状态了,因为bash无法获得任何非0的返回值。你可以使用另一种结构:

command

if [ “$?”-ne 0]; then echo “command failed”; exit 1; fi

可以替换成:

command || { echo “command failed”; exit 1; }

或者使用:

if ! command; then echo “command failed”; exit 1; fi

如果你必须使用返回非0值的命令,或者你对返回值并不感兴趣呢?你可以使用 command || true ,或者你有一段很长的代码,你可以暂时关闭错误检查功能,不过我建议你谨慎使用。

set +e

command1

command2

set -e

相关文档指出,bash默认返回管道中最后一个命令的值,也许是你不想要的那个。比如执行 false | true 将会被认为命令成功执行。如果你想让这样的命令被认为是执行失败,可以使用 set -o pipefail

程序防御 – 考虑意料之外的事

你的脚本也许会被放到“意外”的账户下运行,像缺少文件或者目录没有被创建等情况。你可以做一些预防这些错误事情。比如,当你创建一个目录后,如果父目录不存在,mkdir 命令会返回一个错误。如果你创建目录时给mkdir命令加上-p选项,它会在创建需要的目录前,把需要的父目录创建出来。另一个例子是 rm 命令。如果你要删除一个不存在的文件,它会“吐槽”并且你的脚本会停止工作。(因为你使用了-e选项,对吧?)你可以使用-f选项来解决这个问题,在文件不存在的时候让脚本继续工作。

准备好处理文件名中的空格

有些人从在文件名或者命令行参数中使用空格,你需要在编写脚本时时刻记得这件事。你需要时刻记得用引号包围变量。

if [ $filename = “foo” ];

当$filename变量包含空格时就会挂掉。可以这样解决:

if [ “$filename” = “foo” ];

使用$@变量时,你也需要使用引号,因为空格隔开的两个参数会被解释成两个独立的部分。

david% foo() { for i in $@; do echo $i; done }; foo bar “baz quux”

bar

baz

quux

david% foo() { for i in “$@”; do echo $i; done }; foo bar “baz quux”

bar

baz quux

我没有想到任何不能使用”$@”的时候,所以当你有疑问的时候,使用引号就没有错误。

如果你同时使用find和xargs,你应该使用 -print0 来让字符分割文件名,而不是换行符分割。

david% touch “foo bar”

david% find | xargs ls

ls: ./foo: No such file or directory

ls: bar: No such file or directory

david% find -print0 | xargs -0 ls

./foo bar

设置的陷阱

当你编写的脚本挂掉后,文件系统处于未知状态。比如锁文件状态、临时文件状态或者更新了一个文件后在更新下一个文件前挂掉。如果你能解决这些问题,无论是删除锁文件,又或者在脚本遇到问题时回滚到已知状态,你都是非常棒的。幸运的是,bash提供了一种方法,当bash接收到一个UNIX信号时,运行一个命令或者一个函数。可以使用trap命令。

trap command signal [signal …]

你可以链接多个信号(列表可以使用kill -l获得),但是为了清理残局,我们只使用其中的三个:INT,TERM和EXIT。你可以使用-as来让traps恢复到初始状态。

信号描述

INT Interrupt – 当有人使用Ctrl-C终止脚本时被触发

TERM Terminate – 当有人使用kill杀死脚本进程时被触发

EXIT Exit – 这是一个伪信号,当脚本正常退出或者set -e后因为出错而退出时被触发

当你使用锁文件时,可以这样写:

if [ ! -e $lockfile ]; then

touch $lockfile

critical-section

rm $lockfile

else

echo “critical-section is already running”

fi

当最重要的部分(critical-section)正在运行时,如果杀死了脚本进程,会发生什么呢?锁文件会被扔在那,而且你的脚本在它被删除以前再也不会运行了。解决方法:

if [ ! -e $lockfile ]; then

trap ” rm -f $lockfile; exit” INT TERM EXIT

touch $lockfile

critical-section

rm $lockfile

trap – INT TERM EXIT

else

echo “critical-section is already running”

fi

现在当你杀死进程时,锁文件一同被删除。注意在trap命令中明确地退出了脚本,否则脚本会继续执行trap后面的命令。

竟态条件 (wikipedia)

在上面锁文件的例子中,有一个竟态条件是不得不指出的,它存在于判断锁文件和创建锁文件之间。一个可行的解决方法是使用IO重定向和bash的noclobber(wikipedia)模式,重定向到不存在的文件。我们可以这么做:

if ( set -o noclobber; echo “$$” > “$lockfile”) 2> /dev/null;

then

trap ‘rm -f “$lockfile”; exit $?’ INT TERM EXIT

critical-section

rm -f “$lockfile”

trap – INT TERM EXIT

else

echo “Failed to acquire lockfile: $lockfile”

echo “held by $(cat $lockfile)”

fi

更复杂一点儿的问题是你要更新一大堆文件,当它们更新过程中出现问题时,你是否能让脚本挂得更加优雅一些。你想确认那些正确更新了,哪些根本没有变化。比如你需要一个添加用户的脚本。

add_to_passwd $user

cp -a /etc/skel /home/$user

chown $user /home/$user -R

当磁盘空间不足或者进程中途被杀死,这个脚本就会出现问题。在这种情况下,你也许希望用户账户不存在,而且他的文件也应该被删除。

rollback() {

del_from_passwd $user

if [ -e /home/$user ]; then

rm -rf /home/$user

fi

exit

}

trap rollback INT TERM EXIT

add_to_passwd $user

cp -a /etc/skel /home/$user

chown $user /home/$user -R

trap – INT TERM EXIT

在脚本最后需要使用trap关闭rollback调用,否则当脚本正常退出的时候rollback将会被调用,那么脚本等于什么都没做。

保持原子化

又是你需要一次更新目录中的一大堆文件,比如你需要将URL重写到另一个网站的域名。你也许会写:

for file in $(find /var/www -type f -name “*.html”); do

perl -pi -e ‘s/www.example.net/www.example.com/’ $file

done

如果修改到一半是脚本出现问题,一部分使用www.example.com,而另一部分使用www.example.net。你可以使用备份和trap解决,但在升级过程中你的网站URL是不一致的。

解决方法是将这个改变做成一个原子操作。先对数据做一个副本,在副本中更新URL,再用副本替换掉现在工作的版本。你需要确认副本和工作版本目录在同一个磁盘分区上,这样你就可以利用Linux系统的优势,它移动目录仅仅是更新目录指向的inode节点。

cp -a /var/www /var/www-tmp

for file in $(find /var/www-tmp -type -f -name “*.html”); do

perl -pi -e ‘s/www.example.net/www.example.com/’ $file

done

mv /var/www /var/www-old

mv /var/www-tmp /var/www

这意味着如果更新过程出问题,线上系统不会受影响。线上系统受影响的时间降低为两次mv操作的时间,这个时间非常短,因为文件系统仅更新inode而不用真正的复制所有的数据。

这种技术的缺点是你需要两倍的磁盘空间,而且那些长时间打开文件的进程需要比较长的时间才能升级到新文件版本,建议更新完成后重新启动这些进程。对于apache服务器来说这不是问题,因为它每次都重新打开文件。你可以使用lsof命令查看当前正打开的文件。优势是你有了一个先前的备份,当你需要还原时,它就派上用场了。

 

zz from:http://www.uml.org.cn/embeded/201207025.asp

zz from: http://www.cnblogs.com/zhengyun_ustc/archive/2012/09/19/getremoteaddr.html

 

外界流传的JAVA/PHP服务器端获取客户端IP都是这么取的:

伪代码:
1)ip = request.getHeader(“X-FORWARDED-FOR“)
    可伪造,参考附录A
2)如果该值为空或数组长度为0或等于”unknown”,那么:
ip = request.getHeader(“Proxy-Client-IP”)
3)如果该值为空或数组长度为0或等于”unknown”,那么:
ip = request.getHeader(“WL-Proxy-Client-IP”)
4)如果该值为空或数组长度为0或等于”unknown”,那么:
ip = request.getHeader(“HTTP_CLIENT_IP”)
    可伪造
5)如果该值为空或数组长度为0或等于”unknown”,那么:
ip = request.getRemoteAddr()
    可对于匿名代理服务器,可隐匿原始ip,参考附录B
之所以搞这么麻烦,是因为存在很多种网络结构,如 Nginx+Resin、Apache+WebLogic、Squid+Nginx。下面挨个儿讲一下。
郑昀 :△
首先,明确一下,Nginx 配置一般如下所示:
              location / {
proxy_pass       http://yourdomain.com;
proxy_set_header   Host             $host;
proxy_set_header   X-Real-IP        $remote_addr;
proxy_set_header   X-Forwarded-For  $proxy_add_x_forwarded_for;
}
注意看红色字体,这些配置与下面的闯关拿IP有关。
———————————————————————————————
——第一关|X-Forwarded-For :背景——
这是一个 Squid 开发的字段,并非 RFC 标准。
简称 XFF 头,只有在通过了 HTTP 代理或者负载均衡服务器时才会添加该项。在 Squid 开发文档中可以找到该项的详细介绍。
XFF 格式如下:
X-Forwarded-For: client1, proxy1, proxy2
可以看出,XFF 头信息可以有多个,中间用逗号分隔,第一项为真实的客户端ip,剩下的就是曾经经过的代理或负载均衡服务器的ip地址。
——第一关|X-Forwarded-For :场景=客户端–CDN–Nginx——
当用户请求经过 CDN 后到达 Nginx 负载均衡服务器时,其 XFF 头信息应该为 “客户端IP,CDN的IP”。
一般情况下CDN服务商出于自身安全考虑会将屏蔽CDN的ip,只保留客户端ip。
那么请求头到达 Nginx 时:
  • 在默认情况下,Nginx 并不会对 XFF 头做任何处理
    • 此时 Nginx 后面的 Resin/Apache/Tomcat 通过 request.getHeader(“X-FORWARDED-FOR”) 获得的ip仍然是原始ip
  • 当 Nginx 设置 X-Forwarded-For 等于 $proxy_add_x_forwarded_for 时:
    • 如果从CDN过来的请求没有设置 XFF 头(通常这种事情不会发生),XFF 头为 CDN 的ip
      • 此时相对于 Nginx 来说,客户端就是 CDN
    • 如果 CDN 设置了 XFF 头,我们这里又设置了一次,且值为$proxy_add_x_forwarded_for 的话:
      • XFF 头为“客户端IP,Nginx负载均衡服务器IP”,这样取第一个值即可
      • 这也就是大家所常见的场景!
http://images.cnblogs.com/cnblogs_com/zhengyun_ustc/255879/o_client-cdn-nginx-resin.png
综上所述,XFF 头在上图的场景,Resin 通过 request.getHeader(“X-FORWARDED-FOR”) 获得的ip字符串,做一个split,第一个元素就是原始ip。
那么,XFF 头可以伪造吗?
——第一关|X-Forwarded-For :伪造——
可以伪造。
XFF 头仅仅是 HTTP Headers 中的一分子,自然是可以随意增删改的。如附录A所示。
很多投票系统都有此漏洞,它们简单地取 XFF 头中定义的ip地址设置为来源地址,因此第三方可以伪造任何ip投票。
———————————————————————————————
——第二和第三关|Proxy-Client-IP/WL-Proxy-Client-IP :背景——
Proxy-Client-IP 字段和 WL-Proxy-Client-IP 字段只在 Apache(Weblogic Plug-In Enable)+WebLogic 搭配下出现,其中“WL” 就是 WebLogic 的缩写。
即访问路径是:
Client -> Apache WebServer + Weblogic http plugin -> Weblogic Instances
所以这两关对于我们来说仅仅是兼容而已,怕你突然把 Nginx+Resin 换成 Apache+WebLogic 。
也可以直接忽略这两个字段。
———————————————————————————————
——第四关|HTTP-Client-IP :背景——
HTTP_CLIENT_IP 是代理服务器发送的HTTP头。
很多时候 Nginx 配置中也并没有下面这项:
proxy_set_header HTTP_CLIENT_IP $remote_addr;
所以本关也可以忽略。
郑昀 :△
———————————————————————————————
——第五关| request.getRemoteAddr() :背景——
从 request.getRemoteAddr() 函数的定义看:
    Returns the Internet Protocol (IP) address of the client or last proxy that sent the request.

实际上,REMOTE_ADDR 是客户端跟服务器“握手”时的IP,但如果使用了“匿名代理”,REMOTE_ADDR 将显示代理服务器的ip,或者最后一个代理服务器的ip。请参考附录B。

综上,
java/php 里拿到的ip地址可能是伪造的或代理服务器的ip。
 
郑昀 :△
+++附录A XFF 与 Nginx 配置的测试用例+++
测试环境: nginx+resin
内网IP:172.16.100.10
客户端IP:123.123.123.123

测试页面: test.jsp
<%
out.println(“x-forwarded-for: ” + request.getHeader(“x-forwarded-for”));
out.println(“remote hosts: ” + request.getRemoteAddr());
%>

nginx 配置一
proxy_set_header X-Real-IP $remote_addr;
proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
wget测试
wget -O aa –header=”X-Forwarded-For:192.168.0.1″ “http://test.com/test.jsp”
页面返回结果:
x-forwarded-for: 192.168.0.1, 123.123.123.123
remote hosts: 172.16.100.10
curl测试
curl -H “X-Forwarded-For:192.168.0.1″ “http://test.com/test.jsp”
x-forwarded-for: 192.168.0.1, 123.123.123.123
remote hosts: 172.16.100.10
nginx 配置二
proxy_set_header X-Real-IP $remote_addr;
proxy_set_header X-Forwarded-For $remote_addr;
proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;

wget测试:
wget -O aa –header=”X-Forwarded-For:192.168.0.1″ “http://test.com/test.jsp”
页面返回结果:
x-forwarded-for: 123.123.123.123
remote hosts: 172.16.100.10

curl测试
curl -H “X-Forwarded-For:192.168.0.1″ “http://test.com/test.jsp”
x-forwarded-for: 123.123.123.123
remote hosts: 172.16.100.10

测试结果:
1、配置

proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
增加了一个真实ip X-Forwarded-For,并且顺序是增加到了“后面”。

2、配置

proxy_set_header X-Forwarded-For $remote_addr;
清空了客户端伪造传入的X-Forwarded-For,
保证了使用 request.getHeader(“x-forwarded-for”) 获取的ip为真实ip,
或者用“,”分隔,截取 X-Forwarded-For 最后的值。
+++附录B 搜狗浏览器高速模式的测试用例+++
访问路径:
搜狗浏览器“高速”模式(即使用代理)–>LVS–>Apache
获得的值为:
x-forwarded-for:180.70.92.43   (即真实ip)
Proxy-Client-IP:null
WL-Proxy-Client-IP:null
getRemoteAddr:123.126.50.185  (即搜狗代理ip)
×××参考资源:×××
1,http://bbs.linuxtone.org/thread-9050-1-1.html
2,http://hi.baidu.com/thinkinginlamp/item/e2cf05263eb4d18e6e2cc3e6
3,http://bbs.chinaunix.net/thread-3659453-1-1.html

关于InnoDB索引长度限制的tips

有同学问到InnoDB的索引长度问题,简单说几个tips。

 

关于3072

大家经常碰到InnoDB单列索引长度不能超过767bytes,实际上联合索引还有一个限制是3072。

 

mysql> CREATE TABLE `tb` (
    ->   `a` varchar(255) DEFAULT NULL,
    ->   `b` varchar(255) DEFAULT NULL,
    ->   `c` varchar(255) DEFAULT NULL,
    ->   `d` varchar(255) DEFAULT NULL,
    ->   `e` varchar(255) DEFAULT NULL,
    ->   KEY `a` (`a`,`b`,`c`,`d`,`e`)
    -> ) ENGINE=InnoDB DEFAULT CHARSET=utf8;
ERROR 1071 (42000): Specified key was too long; max key length is 3072 bytes

可以看到,由于每个字段占用255*3, 因此这个索引的大小是3825>3072,报错。

 

为什么3072

我们知道InnoDB一个page的默认大小是16k。由于是Btree组织,要求叶子节点上一个page至少要包含两条记录(否则就退化链表了)。

所以一个记录最多不能超过8k。
又由于InnoDB的聚簇索引结构,一个二级索引要包含主键索引,因此每个单个索引不能超过4k (极端情况,pk和某个二级索引都达到这个限制)。
由于需要预留和辅助空间,扣掉后不能超过3500,取个“整数”就是(1024*3)。

 

单列索引限制

上面有提到单列索引限制767,起因是256×3-1。这个3是字符最大占用空间(utf8)。但是在5.5以后,开始支持4个字节的uutf8。255×4>767, 于是增加了一个参数叫做 innodb_large_prefix。

这个参数默认值是OFF。当改为ON时,允许列索引最大达到3072。

如下效果(5.5):

 

可以看到默认行为是建表成功,报一个warning,并且将长度阶段为255。

 

注意要生效需要加row_format=compressed或者dynamic  。

无锁队列的实现

by 陈皓

关于无锁队列的实现,网上有很多文章,虽然本文可能和那些文章有所重复,但是我还是想以我自己的方式把这些文章中的重要的知识点串起来和大家讲一讲这个技术。下面开始正文。

关于CAS等原子操作

在开始说无锁队列之前,我们需要知道一个很重要的技术就是CAS操作——Compare & Set,或是 Compare & Swap,现在几乎所有的CPU指令都支持CAS的原子操作,X86下对应的是 CMPXCHG 汇编指令。有了这个原子操作,我们就可以用其来实现各种无锁(lock free)的数据结构。

这个操作用C语言来描述就是下面这个样子:(代码来自Wikipedia的Compare And Swap词条)意思就是说,看一看内存*reg里的值是不是oldval,如果是的话,则对其赋值newval。

int compare_and_swap (int* reg, int oldval, int newval)
{
  int old_reg_val = *reg;
  if (old_reg_val == oldval)
     *reg = newval;
  return old_reg_val;
}

这个操作可以变种为返回bool值的形式(返回 bool值的好处在于,可以调用者知道有没有更新成功):
bool compare_and_swap (int *accum, int *dest, int newval)
{
  if ( *accum == *dest ) {
      *dest = newval;
      return true;
  }
  return false;
}

与CAS相似的还有下面的原子操作:(这些东西大家自己看Wikipedia吧)

注:在实际的C/C++程序中,CAS的各种实现版本如下:

 

1)GCC的CAS

GCC4.1+版本中支持CAS的原子操作(完整的原子操作可参看 GCC Atomic Builtins

bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)
type __sync_val_compare_and_swap (type *ptr, type oldval type newval, ...)

2)Windows的CAS

在Windows下,你可以使用下面的Windows API来完成CAS:(完整的Windows原子操作可参看MSDN的InterLocked Functions

 InterlockedCompareExchange ( __inout LONG volatile *Target,
                                 __in LONG Exchange,
                                 __in LONG Comperand);

3) C++11中的CAS

C++11中的STL中的atomic类的函数可以让你跨平台。(完整的C++11的原子操作可参看 Atomic Operation Library

template< class T >
bool atomic_compare_exchange_weak( std::atomic<T>* obj,
                                   T* expected, T desired );
template< class T >
bool atomic_compare_exchange_weak( volatile std::atomic<T>* obj,
                                   T* expected, T desired );

无锁队列的链表实现

下面的东西主要来自John D. Valois 1994年10月在拉斯维加斯的并行和分布系统系统国际大会上的一篇论文——《Implementing Lock-Free Queues》。

我们先来看一下进队列用CAS实现的方式:

EnQueue(x) //进队列
{
    //准备新加入的结点数据
    q = new record();
    q->value = x;
    q->next = NULL;

    do {
        p = tail; //取链表尾指针的快照
    } while( CAS(p->next, NULL, q) != TRUE); //如果没有把结点链上,再试

    CAS(tail, p, q); //置尾结点
}

我们可以看到,程序中的那个 do- while 的 Re-Try-Loo。就是说,很有可能我在准备在队列尾加入结点时,别的线程已经加成功了,于是tail指针就变了,于是我的CAS返回了false,于是程序再试,直到试成功为止。这个很像我们的抢电话热的不停重播的情况。

你会看到,为什么我们的“置尾结点”的操作不判断是否成功,因为:

  1. 如果有一个线程T1,它的while中的CAS如果成功的话,那么其它所有的 随后线程的CAS都会失败,然后就会再循环,
  2. 此时,如果T1 线程还没有更新tail指针,其它的线程继续失败,因为tail->next不是NULL了。
  3. 直到T1线程更新完tail指针,于是其它的线程中的某个线程就可以得到新的tail指针,继续往下走了。

这里有一个潜在的问题——如果T1线程在用CAS更新tail指针的之前,线程停掉了,那么其它线程就进入死循环了。下面是改良版的EnQueue()

EnQueue(x) //进队列改良版
{
    q = new record();
    q->value = x;
    q->next = NULL;

    p = tail;
    oldp = p
    do {
        while (p->next != NULL)
            p = p->next;
    } while( CAS(p.next, NULL, q) != TRUE); //如果没有把结点链上,再试

    CAS(tail, oldp, q); //置尾结点
}

我们让每个线程,自己fetch 指针 p 到链表尾。但是这样的fetch会很影响性能。而通实际情况看下来,99.9%的情况不会有线程停转的情况,所以,更好的做法是,你可以接合上述的这两个版本,如果retry的次数超了一个值的话(比如说3次),那么,就自己fetch指针。

好了,我们解决了EnQueue,我们再来看看DeQueue的代码:(很简单,我就不解释了)

DeQueue() //出队列
{
    do{
        p = head;
        if (p->next == NULL){
            return ERR_EMPTY_QUEUE;
        }
    while( CAS(head, p, p->next) != TRUE );
    return p->next->value;
}

我们可以看到,DeQueue的代码操作的是 head->next,而不是head本身。这样考虑是因为一个边界条件,我们需要一个dummy的头指针来解决链表中如果只有一个元素,head和tail都指向同一个结点的问题,这样EnQueue和DeQueue要互相排斥了

注:上图的tail正处于更新之前的装态。

CAS的ABA问题

所谓ABA(见维基百科的ABA词条),问题基本是这个样子:

  1. 进程P1在共享变量中读到值为A
  2. P1被抢占了,进程P2执行
  3. P2把共享变量里的值从A改成了B,再改回到A,此时被P1抢占。
  4. P1回来看到共享变量里的值没有被改变,于是继续执行。

虽然P1以为变量值没有改变,继续执行了,但是这个会引发一些潜在的问题。ABA问题最容易发生在lock free 的算法中的,CAS首当其冲,因为CAS判断的是指针的地址。如果这个地址被重用了呢,问题就很大了。

比如上述的DeQueue()函数,因为我们要让head和tail分开,所以我们引入了一个dummy指针给head,当我们做CAS的之前,如果head的那块内存被回收并被重用了,而重用的内存又被EnQueue()进来了,这会有很大的问题。(内存管理中重用内存基本上是一种很常见的行为

这个例子你可能没有看懂,维基百科上给了一个活生生的例子——

你拿着一个装满钱的手提箱在飞机场,此时过来了一个火辣性感的美女,然后她很暖昧地挑逗着你,并趁你不注意的时候,把用一个一模一样的手提箱和你那装满钱的箱子调了个包,然后就离开了,你看到你的手提箱还在那,于是就提着手提箱去赶飞机去了。

这就是ABA的问题。

解决ABA的问题

维基百科上给了一个解——使用double-CAS(双保险的CAS),例如,在32位系统上,我们要检查64位的内容

1)一次用CAS检查双倍长度的值,前半部是指针,后半部分是一个计数器。

2)只有这两个都一样,才算通过检查,要吧赋新的值。并把计数器累加1。

这样一来,ABA发生时,虽然值一样,但是计数器就不一样(但是在32位的系统上,这个计数器会溢出回来又从1开始的,这还是会有ABA的问题)

当然,我们这个队列的问题就是不想让那个内存重用,这样明确的业务问题比较好解决,论文《Implementing Lock-Free Queues》给出一这么一个方法——使用结点内存引用计数refcnt

SafeRead(q)
{
    loop:
        p = q->next;
        if (p == NULL){
            return p;
        }

        Fetch&Add(p->refcnt, 1);

        if (p == q->next){
            return p;
        }else{
            Release(p);
        }
    goto loop;
}

其中的 Fetch&Add和Release分是是加引用计数和减引用计数,都是原子操作,这样就可以阻止内存被回收了。

用数组实现无锁队列

本实现来自论文《Implementing Lock-Free Queues

使用数组来实现队列是很常见的方法,因为没有内存的分部和释放,一切都会变得简单,实现的思路如下:

1)数组队列应该是一个ring buffer形式的数组(环形数组)

2)数组的元素应该有三个可能的值:HEAD,TAIL,EMPTY(当然,还有实际的数据)

3)数组一开始全部初始化成EMPTY,有两个相邻的元素要初始化成HEAD和TAIL,这代表空队列。

4)EnQueue操作。假设数据x要入队列,定位TAIL的位置,使用double-CAS方法把(TAIL, EMPTY) 更新成 (x, TAIL)。需要注意,如果找不到(TAIL, EMPTY),则说明队列满了。

5)DeQueue操作。定位HEAD的位置,把(HEAD, x)更新成(EMPTY, HEAD),并把x返回。同样需要注意,如果x是TAIL,则说明队列为空。

算法的一个关键是——如何定位HEAD或TAIL?

1)我们可以声明两个计数器,一个用来计数EnQueue的次数,一个用来计数DeQueue的次数。

2)这两个计算器使用使用Fetch&ADD来进行原子累加,在EnQueue或DeQueue完成的时候累加就好了。

3)累加后求个模什么的就可以知道TAIL和HEAD的位置了。

如下图所示:

 小结

以上基本上就是所有的无锁队列的技术细节,这些技术都可以用在其它的无锁数据结构上。

1)无锁队列主要是通过CAS、FAA这些原子操作,和Retry-Loop实现。

2)对于Retry-Loop,我个人感觉其实和锁什么什么两样。只是这种“锁”的粒度变小了,主要是“锁”HEAD和TAIL这两个关键资源。而不是整个数据结构。

还有一些和Lock Free的文章你可以去看看:

注:我配了一张look-free的自行车,寓意为——如果不用专门的车锁,那么自行得自己锁自己!

淘宝开放平台架构组件体系初探

作者 岑文初 发布于 2009年9月29日

zz from: http://www.infoq.com/cn/news/2009/09/top-arch-components

淘宝开放平台(TaoBao Open Platform,简称TOP)的整个架构体系是组件化体系架构,可以是很少的几个基础组件构成的Skeleton,也可以是融入了商业想象的Amazing Architecture。这里就通过对于这些组件的罗列,描述出在TOP这个大体系中,各个组件所处的地位及作用。TOP的“兵器谱”是在现阶段商业需求及平台非业务性需求指导下形成的,未来TOP将继续发展,“兵器谱”也会不断演进。

下图是整个TOP当前的一个组件结构图:

图中,红色虚线就是TOP的Skeleton。TOP当前从业务模块功能角度来划分,可以分成三个层次:基础平台组件层,基础业务组件层,普通业务组件层。基础平台组件层,倾向于平台级别功能满足及对平台稳定性,可用性的支持。基础业务组件层,是介于平台服务于普通业务服务之间的组件,部分利用了平台基础组件层的组件,来抽象出一层公用业务服务组件,为业务组件提供通用的基础支持。

安全组件

安全组件主要从四个角色去考虑整体的安全策略及具体的实施方案,这四个角色是:用户,应用,平台,服务。

平台本身的安全主要是基于在大并发和大流量的情况下,保证平台自身稳定性和可用性,同时也要兼顾在平台开放的服务不相互干扰和影响。因此采取服务分流隔离机制,通过虚拟配置及软负载方式将服务请求动态分流和隔离,保证了服务之间相互的独立性,同时也充分利用TOP的能力。频率控制及流量控制除了保护TOP自身不受到攻击,也为后端服务提供者作了天然的一个保护屏障,保证服务请求压力可以在TOP上可控,防止流量直接压倒服务提供者。用户隐私安全在淘宝尤为重要,用户信息的安全性也在淘宝开放的过程中被放到了首位。在开放平台设计中,除了采用普通开放平台的认证模式以外(OAuth类似流程),还在服务调用过程中通过区分应用角色来限制对于用户信息的获取和使用。同时针对不同的应用类型(插件,Web应用,客户端应用,手机应用)都有各自不同的用户授权方式,保证用户的知情权。App的安全其实也是为了保证对服务的请求及对用户信息的获取不被不法的应用信息盗取者所利用,根据应用角色及自己对于安全的需求,采取多种方式或者组合的方式来实现App信息的保密性,保护App自身安全,也保证了平台服务的数据安全。服务安全指的是对于服务来说分成了几个层级,不同层级的服务对于安全级别的要求不同(不需要交验应用身份,需要交验应用身份,需要用户授权,用户可选择授权等),在应用访问服务的时候,就会需要根据服务级别的不同采用不同的访问控制流程。根据上述的四个角色对于安全的考虑,通过应用角色的定义,服务虚拟组的编排,黑名单(频率控制及流量控制),多模式用户令牌等手段,形成了多种模式的安全控制流程。

服务路由组件

服务路由是开放平台最基本的功能,如果排除商业因素,那么对于TOP最基本上来看可以看作一个服务路由器,服务路由主要的功能如下图展示:

服务路由组件需要支持多服务类型的服务接入,不同服务类型主要表现在两个维度:1.服务对外的展现方式(REST OR RPC),这两种形态的服务没有任何好坏之分,只是根据各自的系统形态来选择采用哪一种模式来对外暴露,RPC比较符合过去应用开放的风格,REST比较适合面向资源的架构。同时对于同步,异步,通知,大数据量的服务,都会有不同的接入方式和调用方式支持,满足各种业务场景的需求。多通信协议支持,表示服务请求到了TOP以后,TOP负责将请求继续发送给服务提供者,不论服务提供者采用什么方式和TOP交互,最终将得到的结果返回给客户,服务调用者将会对后端的服务请求过程透明,同时可以使TOP很容易接入一些传统遗留系统的服务,或者是对通信有特殊需求的服务。特性支持主要是会有对内容的一些特殊处理,例如压缩,在CS或者手机应用交互过程中,就会需要对数据量有所压缩,满足业务需求。

监控告警组件

下图是监控告警组件的基本功能图

监控和告警模块在TOP中起到越来越重要的作用,访问量逐日膨胀,运行期TOP是一个黑盒,无法知晓当前系统实际的健康状况,当出现问题以后比较难以定位。服务监控主要是服务质量(响应时间),短时间段内的服务请求峰值,和阶段性的趋势。系统和平台主要是对底层基础组件的监控,同时及时地通知TOP负责人处理线上即将要发生的事情。对于应用的监控通常就是从客户端和服务端两面对于应用当前的情况作汇总分析。当监控发现异常以后,就交由告警部分按照一定的发送策略给相关的负责人,在第一时间将问题解决。

日志组件

日志组件和其他系统的日志组件基本没有太大的区别,只是在对于海量数据写出和获取的方法做了优化(例如异步分页批量输出等)。日志组件主要负责,打点,收集,分析,数据库记录,归档。

协议转换组件

这里谈到的协议转换指的是对于请求和返回的协议,TOP可以做适配,来满足服务调用者和服务发布者之间在服务协议失配的情况下还是能够正常通信。当前支持JSON,XML,Atom,二进制协议之间的转换,当然转换描述文档将会配置在TOP。同时返回的数据内容,也可以通过协议转换,返回给客户端常规的xml或者json类型的数据。

服务流程化组件

服务流程化指的是将离散的服务通过流程描述文档能够虚拟的串联成为一个新的服务,这样更加适合调用者使用,同时将服务的一些内部逻辑隐藏起来。这很类似于SOA中的服务编排,同时也可以参看Yahoo的Pipe,那就是一种典型的服务串联,同时还提供了方便的界面直接交由用户通过手动拖拉的方式来使用服务串联。

服务流程化最大的特点就是将不同类型的服务能够根据业务场景的需求组合成简单的流程性服务,极大降低了服务开发者由于对服务流程不熟悉而犯错的几率,同时也为服务开发者提高了开发效率。

计费组件

当前计费模型主要是按流量收费和插件分成两种模式,因此计费组件还比较简单,当前就是基于日志做分析,未来会考虑在流量上的各种特殊模式(打包,优惠等等)。

容器组件(TBML)

产生原因:

  • 数据隐私性
  • 开发便利性
  • 业务升级透明化
  • 监控全局化
  • 开发标准化

作用:

  • 数据操作可控,保护终端用户隐私(结合cookie和标签,控制ISV业务数据操作尺度,提高数据安全性)
  • 提供标准业务流程标签,简化开发者对于业务流程理解过程。
  • 标签化接口方式,完成数据获取和页面渲染,后台业务升级对ISV透明化。
  • 标签获取客户端信息,将监控扩展到整个业务请求过程。制定行业化标签库,形成统一开发标准。

TBML首先需要根据业务需求及场景定义出对应的标签库,也就是制定Taobao的标签标准,最简单的获取用户信息标签,到最复杂的业务操作流程标签都会成为标签库中的一部分。同时在服务端需要有解释引擎来翻译标签,解释引擎一方面需要去了解标签内容和含义,同时需要请求后台多个API,串联成为流程化的服务,从应用的输入,得到最后的输出,当然期间也需要处理异常的情况。最后还需要关注的就是安全控制,在交验标签传递来的数据时,需要对数据作完整性及合法性的交验,防止通过标签数据的特殊性攻击后台服务接口。

TBQL组件

TBQL其实是一种服务调用的方式,也是通过一种程序员和开发者习惯的方式,将对资源的REST请求转换成一种类似QL的请求,对于面向资源性的架构体系来说是十分有利的。同时对于API来说,使用者会更加自然的去采用连接和过滤得方式得到需要的数据。

QL解释引擎负责对于TBQL的翻译工作,数据存储的MetaData保存在数据库中,可以指导QL解释引擎翻译。需要支持不同数据来源的连接和过滤,在获得结果以后需要做格式转换返回给服务调用者(通常就是xml)。与容器一样,需要着重考虑安全性问题,对于传统的SQL注入就是典型攻击QL系统的案例,需要谨慎处理解析中对于字符的翻译工作。在流程中出现异常,需要制定策略来判断是否直接返回错误还是支持部分容错。

TOPID组件

TOPID组件有点类似于Facebook的Connect,需要在淘宝和淘宝的合作开发者之间建立起双向的用户互通的标准和流程,同时也为服务互通打好基础,毕竟业务的互动需要基于可以互通的用户体系。

总结

以上仅仅只是简单的罗列了一下TOP技术体系架构中的一些组件化的内容,同时在这些组件的背后有着更多的基础性项目的支持,例如统一配置中心对于系统动态扩容的支持,分布式缓存对于监控告警的支持,分布式文件系统对于海量小文件保存和获取的支持等等。同时以上每一个模块都有各自特殊的定制和优化,例如路由模块就需要有Lazy的服务参数解析模式来提高处理性能,安全体系中需要有动态密钥机制来保证高安全性等等。

TOP从萌芽走向成熟,不论从技术架构还是商业规划都处于不断摸索和改进的过程,当前的技术体系仅仅是现阶段的一个需求缩影,未来在市场不断成熟,开发者不断介入和反馈的情况下,TOP会走得更快更远,TOP的“兵器谱”会更加丰富,更加出彩。

========================

http://www.csdn.net/article/2012-07-26/2807765

SDCC讲师专访:淘宝岑文初谈开放平台架构

CSDN:请您对自己做个简单介绍,尤其是在开放平台方面的技术经验和积累。您目前最关注哪些技术领域?

岑文初:从2007年底开始构建阿里系最早的开放平台,2009年正式加入淘宝开始负责淘宝开放平台基础架构建设,2012年负责整个淘宝的开放平台技术和产品团队。

开放平台发展的过程中技术也不断的在发展,从最早的网站服务化(SCA,OSGI),平台授权(OAuth),服务流控与服务隔离(Web容器异步化服务处理),服务生命周期管理(服务接入与文档,SDK自动化等),到后来的平台透明化(海量流式数据即时分析),多样化服务(ATS异步大任务处理服务,Streaming API流式数据推送服务,支持并行和串行化的QL服务),无线客户端的安全及服务易用(IOS、Android),JS组件(支持网站接入)。

CSDN:作为电商开放平台的代表,您觉得淘宝开放平台在架构方面有哪些特点?尤其在系统稳定和数据安全性方面,淘宝用到了哪些技术、经历了哪些磨历?

岑文初:淘宝开放平台架构关键词:透明,核心模块小,按需简化设计,多层次设计配合(js,client,server),服务模式创新。

系统稳定:1.Web容器异步化支持服务流控和隔离。同步的http服务处理模式在初期后端服务不多,服务质量差异不大的情况下能够满足需求,但是当后端服务越来越多(最初30个公开服务到今天300多个公开服务),服务质量和响应参差不齐的情况下,开放平台自身的稳定性直接受制于后端某一个服务,因此当后端某一个服务出现不稳定,就会直接使得淘宝开放平台服务全线无法服务,因此将同步的http服务中转改造为异步中转并设置了权重线程池来差异化对待不同重要度的服务,最后实现服务之间质量影响隔离,服务与平台稳定性隔离。

2.基于流式数据分析可以每一分钟产出业务和系统的统计数据。对比一些基线和告警阀值,最快速度的定位问题,并且采取运行期控制的方式来避免问题的扩大。

数据安全:

1.淘宝开放平台是所有开放平台中对于数据安全要求最高最细的开放平台,当前除了使用业界标准的OAuth2,同时还将安全控制从服务纬度细化到了服务字段级别,同时对于数据安全性分成了四个级别,结合应用形态和应用安全指标差异化控制。

2.通过JS组件化集成实现对用户发起服务和isv应用服务端发起服务的差别验证,对于电子商务买家类服务开放提高了安全性。3.提供无线端SDK静态类库方式,平衡无线用户的安全性和用户体验。

CSDN:在淘宝11.11活动中,面对这种突发的海量访问请求,淘宝开放平台采取了哪些应对措施?

岑文初:淘宝的11.11访问量其实一直在预期以内,因为平台自身对于数据流解析,异步化都保证了高效的系统处理能力,同时可以卸载的一些服务控制保证了服务控制流程如果出现问题可以随时降级处理,保证业务正常支持。另一方面,对于海量订单的对外输出,提供了Streaming api,降低轮询服务带来的压力,同时能够给开发者和商家最快速的消息投递。

CSDN:定义设计API接口有哪些学问和经验可以分享的?

岑文初:对于数据获取类服务非常重要的一点就是保留fields字段,也就是可以支持有选择的数据返回,这样对于服务升级(字段增加或者减少)都会非常主动,同时也非常适合做QL映射。

另一方面,对外提供服务必须要先定义服务处理所对应的资源定义,这样可以避免服务过程化设计开放(服务要设计为面向资源开放),保证业务内部逻辑变更对外透明。对于操作型服务(更新,删除,新增),需要防范重放攻击,业务需要支持一些主键字段或者随机一次性会话字段。

前面分别学习了sina微博计数器mysql、cache与硬件加速方案,以及redis、sina自研发的counter方案   ,有一些相关名词和资料再赘述一下。

旁路式缓存与穿透式缓存

http://stblog.baidu-tech.com/?p=1643

http://www.hudong.com/wiki/CACHE%E5%AD%98%E5%82%A8%E5%99%A8

 

幂等性

http://coolshell.cn/articles/4787.html

HTTP方法的幂等性是指一次和多次请求某一个资源应该具有同样的副作用

 

base64

http://zh.wikipedia.org/wiki/Base64

Base64是一种基于64个可打印字符来表示二进制数据的表示方法

 

Leveldb

http://blog.nosqlfan.com/html/3570.html

http://rdc.taobao.com/blog/cs/?p=1378

LevelDB是Google开发的一个key-value存储,其已经作为存储引擎被Riak和Kyoto Tycoon所支持(这里和这里),在国内淘宝的Tair开源key-value存储也已经将LevelDB作为其持久化存储引擎,并部署在线上使用。
Redis当前的持久化机制是vm机制:使用虚拟内存,即将冷数据放磁盘热并保存一份映射

Redis作者期望更改其持久化机制:

http://blog.nosqlfan.com/html/1047.html

1.使用虚拟内存,即将冷数据放磁盘热并保存一份映射。(目前Redis使用的方式)
2.将数据以内存映射的方式存磁盘,操作数据时直接操作磁盘,然后使用操作系统的Cache作为操作缓冲层。(作者称其为MongoDB的方式)
3.将数据按自定义的格式存磁盘,但操作数据时并不直接操作磁盘,而是操作内存并在某种条件下将内存数据写到磁盘上。(作者打算使用的新方式)

虚拟内存和文件内存映射

http://www.linuxeden.com/html/develop/20100328/94323.html

LZF压缩

http://blog.sina.com.cn/s/blog_538dd0670100bb2k.html

上文分析了《sina微博计数器的设计》一文提到的Mysql/cache实现方式,这里继续其他方案的学习,包括redis和微博自己开发的couter计数器。

Redis实现计数器

对于Redis,我也只是耳闻未曾亲用,但NoSQL的原理大致相似吧。它作为一种NoSQL数据库,一般认为其读写速度都优于传统关系型数据库。按照原文分析,存储64位key+32位value,还需要其他辅助存储空间,故每个key-value对需要76字节的空间(该估算,需要了解Redis数据结构)。如果是百万级别的数据,需要百M级别的存储空间;千万级别,是G级别的存储空间,都还可以接受。但是对于微博这种千亿级别的数据,7600G的存储空间就难以接受了。更何况还要考虑主从备份的问题呢?

即使按照原文下面的分析,0评论0转发的微博占多数,故不存储这些0数据了呢?也只是存储空间降低到3040G。分析该方法,读写性能和复杂度应该都是可以接受的,但问题出在内存消耗过多。这里有一个疑问,之前用tokyo cabinet的hash类型数据库时,是可以指定需要缓存多少数据在内存中,而整体数据持久化在文件里。这样的话,内存其实不会真的消耗到那么多。Redis应该也支持吧?如果不支持,换其他NoSQL呢?其实原文下面的counter计数器也是基于这种思路,并简化了存储struct。

(这里也激发一个兴趣:PHP存储一个int、字符、数组、对象都需要多少空间呢?我虽然会去了解其源码,但是没有这么细致的分析过。)

开发Counter实现计数器

先列举其优化方法如下:

  1. 应对稀疏数据
  2. 合并转发、评论数目为一个结构体,定长
  3. 初始化时开辟大内存空间,采用二次hash的方式解决碰撞
  4. 转发、评论数 32位 -> 16位
  5. 改变数据结构,压缩value,定长->变长
  6. 优化key
  7. 批量查询
  8. 内存+磁盘,冷热数据分别处理
  9. 定期备份内存数据,配合append log,应对故障
  10. 分布式

1. 应对稀疏数据:

不存储转发、评论数为0的微博,该思路虽然简单,但是很重要!我们之前做推荐算法时,也是使用类似的思路过滤了不活跃用户,从而将数据量降低了一个数量级。(再罗嗦一下,为什么cache+存储时,cache里就必须存储0呢?是因为如果不存储,会导致cache不命中,进而继续访问DB。)

2. 合并转发、评论数目为一个结构体,定长:

这个是结合业务需求的直观想法,既然转发、评论数经常一起获取,那就存储在一起。写操作也是原子的,转发数+1应该是:偏移至weibo_id对应的item->ptr.repost_num++。

3. 初始化时开辟大内存空间,采用二次hash的方式解决碰撞

数组偏移是最快的操作。一次读取请求,处理流程可能是:计算其整数类型的hash key,偏移数组下标,读取,比较key是否一致,若一致则返回,否则处理碰撞。写操作类似。

hash碰撞有两种解决思路:不断探测;hash链表。原文采用的是“不断探测”的方法。到这里,存储40G条有效微博数据,其内存使用空间是640GB=16B×40G。

4. 转发、评论数 32位 -> 16位

这个思路很直接,内存还是大,就再想办法,这里是结合业务需求,搞了value,将32位正整数变成16位short。对于超出16位存储的数据,另外开辟内存存储。虽然略微增加了复杂度,但是内存变成了480G=12B×40G。(所以,优化一方面是技术,另一方面也是对业务需求的深入了解和思考)

5. 改变数据结构,压缩value,定长->变长

这一条还是在减少内存,采取的是压缩数据的思路。我对压缩算法和压缩比不了解,只能推测(学无止境啊!)。其原先的思路是针对每个item做变长压缩:

struct直接压缩

在这种思路下,为了保证可直接偏移数组下标,就要求每个item定长,所以如其所述,节省出来的空闲空间也没什么用。而将一维变成二维甚至更多维,并针对value做压缩后,效果就不一样了:

变长压缩value

我的理解是,针对“item”分片,比如1024个item作为一个mini block。将item里的key和value分别存储,repost_num和comment_num可以拆开也可以不拆开。这时,key仍然是连续hash存储的,当定位到key之后,需要获取到其对应的value block指针。一个key block中,该指针值是相同的,所以可以共享。那么怎样获取到这个共享数据的位置呢?我能想到的方案是,将指针存储在每个key block的顶部,故该位置=当前key指针-(当前key指针-初始位置)%(1024+1)。不知道有没有更好的方案?

这种方式,假设value的压缩比是50%,则所需内存为:(8B+2B)*40G=400G是存储key数组和value数组的空间。还需要header的存储空间,假设repost_num和comment_num一起存储,每个分片是1k个item,则=8B*(40G/1k)=320M。如果多拆分列,则会增加header的存储空间,但相对而言,还是很小的。

6. 优化key

以上都是针对value的压缩,其实key也是可以优化的。以上本来key也是被分片了,如果我们能使每个block中,key的高位或者低位有重合,那么这个重合部分,就可以存储到block的header里!更进一步,如果先对weibo_id分区,再hash,一来分区之后便于后面做分布式;二来对hash函数没什么特殊要求;三来,每个分区内数据量减少,也可以降低碰撞的几率。这时,只需要将每个分区内的weibo_id的高位存储在table header里,就可以将weibo_id从64位降低到32位,在不压缩value时内存空间=(4+2+2)*40G=320G;若同时做value压缩,并假设压缩比为0.5,则其内存空间=(4+2)*40G=240G。其数据结构为:

 

7.批量查询:根据原文给出的数据推测,counter会把一次批量查询的10条weibo_id拆分为20次key请求(为什么是20次??即使将repost和comment拆开,也不会影响到key的查询吧?),如果这些key对应value在相同的block里,则解压的操作是可以省略的。

8. 内存+磁盘,冷热数据分别处理

原文在分析热点数据时,提到了LRU导致必须cache 0数据,为什么呢?因为使用LRU意味着,当我们访问cache不命中时,有可能是数据从来没被写入cache,或者超时被expire了,或者由于cache不足根据LRU策略被踢出了。所以,不命中cache,还得再访问持久化存储获取数据。

为了避免存储0值,原文采用的是根据weibo_id区分,半年内的weibo_id肯定在cache中,如果没有则代表其值=0;半年前的weibo_id肯定在持久化存储里,不访问cache,直接去读持久化存储。

一次涉及到持久化存储的写过程是:根据weibo_id判断是否在硬盘,若是,读取内存里的硬盘block索引获取硬盘文件位置,读硬盘取整个block,存储在内存的cold block里,返回数据。

那么写过程呢?由于写之前,肯定得先读(微博页面得先显示,然后才能操作),所以写时数据应该在cold block里(cold block的溢出机制不知道什么样?如果打开页面很久之后再操作呢?)那么根据原文推测,这时仅写cold block。而之后cold block与硬盘文件的merge应该是由其他进程延时/触发独立完成的。

在这种优化思路下,可以设置最大内存,若超过,则flush数据到硬盘,并修改作为标识的weibo_id即可。

9. 定期备份内存数据,配合append log,应对故障:

这里应该是有一个后台进程or线程,定期地把内存里的数据保存到硬盘文件,结合其所说的append log,猜测这个进程可能是根据log来持久化数据,而不一定直接从内存读取吧?因为如果读取内存的话,是否就需要加全局锁呢?即使是分table持久化,也需要对table加锁。

还提到了二级索引。这里可能是对内存分table、分block做二级索引,也有可能是针对硬盘文件的。不过考虑到硬盘文件读取较少,可能不会费这个功夫吧?

(针对分散的旧数据做攻击,会不会造成计数器性能问题?有什么防护措施呢?)

10. 分布式:

跟分table的思路一样,只是粒度会更大,每台服务器负责多个table。既然是master-slave架构,那么主从间如何同步,append log是一种思路。

 

 

 

这两天,有一篇很技术的博客《微博计数器的设计12》,逐步介绍了大并发、大数据量时,sina微博计数器的实现原理,详情请 移步原文欣赏。

作为一个架构初学者,看到很多似曾相识的名词和未透彻的技术,这里对名词进行解释,对每一种设计方式尝试剖析。

使用MySql数据库实现计数器

这种是最简单的方法,可能的表设计是:

create table weibo_ext(

weibo_id bigint not null,

repost_num integer default 0,

comment_num integer default 0,

UNIQUE KEY `weibo_id_idx` (weibo_id)

) ENGINE=innodb;

当数据量在百万甚至千万时,单表都还可能支撑。(to myself:这里,如果能给出预估的并发量就更好了)但是,由于微博的转发、评论数变化较快,即读写频率都很高,所以可能会出现读写锁竞争,导致访问变慢。

当数据量到达500w时,就得为分表做准备了,如原文所述:

  1. 按id取模,把数据拆分到N个表当中去
  2. 按id的时间来分段拆表,满了就建新表

第一种方法,比如我们建了8张weibo_ext_N表,结构都与weibo_ext一致。在代码端,weibo_id%8依次分散到各个表进行读写。这样当读写一条微博时,表较小会较快。批量查询的话,则可能要做1-8次表查询。更严重的情况是,当所有表都膨胀到千万数据量时,再添加新表会很痛苦,几乎所有数据都需要重新散列到各表中。

有没有更好的散列方法了呢?分布式应用中,有一种叫一致性hash算法。上面取模仅仅散列了key,而一致性hash还会额外散列服务器,两种散列方式需要保证数据空间一致,从而使散列后每个服务器节点负责一片散列空间里的数据。当新增服务器时,只会影响到原先一台服务器的一部分数据。针对一致性hash,还有一种升级方案,即将每个真实的服务器实为多个虚拟服务器,并均匀散列到数据空间里。采用这种方式,对mysql按id随机的分表,会有一定帮助。

第二种方法,是按id区间分表,很简单,不重复。

这两种方法,千亿条微博需要生成上千张表,为了稳定性和效率还需要做一主多从的数据库,成本较高。

使用Mysql+memcached实现计数器

假设采取了mysql实现计数器的方案,并姑且不考虑存储成本,但是当访问量提升之后,Mysql还是会成为性能瓶颈,尤其是写操作也很频繁时,数据库缓存可能频繁失效,也有可能发生读写锁竞争使访问堆积,再引起mysql connection不足的问题,进而导致web server响应缓慢、可用进程数不足,使前端用户感觉到页面刷新慢甚至无法打开。

那么惯性思维,我们会想到添加memcached之类的缓存,来减轻mysql的负担。由于需要保证计数的原子性,即转发、评论数的增加需要在缓存内部完成,而非先get再set,可能会将转发和评论数分表存储,即weibo_id=>repost_num和weibo_id=>comment_num两条。如原文所述,有两个弊端:空数据也得Cache浪费内存, Cache频繁失效。针对cache频繁失效,还需要考虑,是超时失效,还是每次写操作都强制delete使失效呢?前者会造成数据不一致,后者会增加写操作的复杂度。

这种方式,不但要接受mysql的存储成本,还增加了memcached的成本。

结合牛B硬件实现计数器

我对硬件没什么了解,只能google到一些资料。猜测其实现方式是:

  1. mysql作为持久化存储,但是不使用传统的sql访问方式,而是handlesocket,免去了sql优化解析等步骤,直接操作数据,提高速度
  2. 固态硬盘,提高硬盘读写效率
  3. cache缓存访问量高的数据

我一向小成本开发,不太了解这种方案会消耗多少money、提速到何种程度?

学习《sina微博计数器的设计》二