October 2011 Archives

关系代数中的除

| No Comments | No TrackBacks

简单记一笔,感谢 Stanford 的 数据库入门 课程课后作业 (有人在 StackOverflow提问)。复习一下。

应用场景:找出一家能制作全部30岁以上人士需要的Pizza种类的Pizza店。

在示范数据库中给出的四个关系:

Person(name, age, gender)       // name is a key
Frequents(name, pizzeria)       // [name,pizzeria] is a key
Eats(name, pizza)               // [name,pizza] is a key
Serves(pizzeria, pizza, price)  // [pizzeria,pizza] is a key

通过一些计算,我们可以得到两个投影:

投影 A:

Chicago Pizza | cheese  | cheese
Chicago Pizza | cheese  | supreme
Chicago Pizza | supreme | cheese
Chicago Pizza | supreme | supreme
Dominos       | cheese  | cheese
Dominos       | cheese  | supreme

投影 B:

cheese  | cheese
cheese  | supreme
supreme | cheese
supreme | supreme

需要的结果是 A/B:

Chicago Pizza

有时,数据库系统并不直接提供关系除操作。这时可以用下面的方法替代:

首先,生成所有 Pizza 店,以及所有 Pizza 类型的笛卡尔积,记为T:

然后,计算该笛卡尔积和 Serves 上的投影R: π{pizzeria,pizza}(Serves) 之差:T-R。

这样,T-R得到的结果便是不存在的 pizzeria,pizza 组合。从其中取 π{pizzeria},然后从全部 pizzeria 中扣掉,即可得到希望的结果了。

#lspe之Disks

| No Comments | No TrackBacks

今天去 Y! 参加了 #lspe 的一个交流会。

比较感兴趣的项目是之前了解过但仔细看过的 FlashCache,这是 Facebook 搞的一个 SSD 加速模块,原理不复杂,是在文件系统下面做上一层集关联(set-associative)高速缓存,提供了LRU和FIFO两种淘汰方法。这次 Mohan Srinivasan 讲解的时候提到了以前公开发表的讲稿上没有的一个内容----按线程id/线程组id去做的黑白名单,并对MySQL进行了修改,令其在扫描表时不做cache。从使用的角度,这个不失为一个不错的折衷方法。

第二个创意不错,使用压缩和 dedup 的方法在 1ms 延迟内做到 1:5 到 1:10 的数据缩减,从而实现低成本的 SSD 阵列。这个概念卖给愿意做虚拟化的企业是很好的,但是对其他应用可能就差点意思了,特别是数据安全唯一的保障是及时做远程复制,这个不太理想。不过,在存到 SSD 上之前先做排重或压缩来减少 I/O 数据量,假如能做到很好的压缩比,并控制 write clustering 令其尽量凑整而避免过量的擦写的话,确实能够极大地改善 SSD 的寿命。不过这个presentation主要是介绍产品,具体的技术介绍的不多。

另一个比较感兴趣的是 Cirrascale 的一个刀片设计,这个设计中在(竖直放置)1U厚度的刀片上放了12块硬盘(如果有导轨,可以热插拔!),并通过 SAS 交换机来连接,电源外置。刀片单元上下各一组工业风扇来散热。机箱设计的相当不错,充分考虑了散热问题。由于 SAS 可以做 multi-path,这个设计的可靠性应该是很好的。同时也极大地节省了空间,和 Dell 同类的刀片相比需要的空间是 7:27。

Dennis Ritchie病逝

| No Comments | No TrackBacks

C语言和 UNIX 之父、K&R 的"R",Dennis Ritchie,于2011年10月12日在家中病逝。

Dennis Ritchie 在 Bell 实验室对 Ken Thompson 设计的 B 语言进行了扩展,并以此为基础设计了 C 语言。 C 语言与当时设计操作系统常用的汇编语言相比,提供了更好的可移植性,并成为了 UNIX 系统高可移植性的基础。Dennis Ritchie 做的这些工作是开创性的。这些工作使得我们能够使用包括数据结构、函数等高级语言特性的语言书写程序,并可以很容易地移植到不同类型的硬件上,同时又保持与为不同的硬件手工书写的汇编代码接近的性能。C++ 之父 Bjarne Stroustrup 对于 Ritchie 的工作如此评价:"They said it couldn't be done, and he did it."。即使在 40 多年后的今天, C 仍然在从嵌入式设备到超级计算机在内的各种计算环境中广泛使用。

"UNIX is very simple, it just needs a genius to understand its simplicity."

Google Authenticator 是一个 TOTP(基于时间的一次性口令)实现,它采用了 RFC 4226 算法。

Google Authenticator 与 RSA SecurID 非常类似。具体来说,它使用一个随机串和以整数表达的时间作为输入去计算 HOTP(算法是 HMAC-SHA-1),然后取输出的最后几位作为一次性口令。

虽然目前已经发现了一些 SHA-1 的弱点,但目前为止还没有公开的已知算法可以从 hash 值直接高效地反推出明文信息。另一方面, HOTP 只截取 hash 的最后几位,因此,攻击者在知道可能的明文信息之后,还必须获得足够多的 TOTP 时间和 hash 值才能够进行离线验证。

在现代 Unix 系统上,通常使用 PAM 来完成系统的验证工作。在 FreeBSD 上,可以通过 security/pam_google_authenticator 来安装 Google Authenticator 的 PAM 模块。这样就可以配置 sudo 来使用它做验证了。

在 /usr/local/etc/pam.d/sudo 中,auth部分预设是这样的:

auth		include		system

这表示采用系统内建的 'system' 规则配置。我们在这后面加入强制使用 Google Authenticator 的配置:

auth		required	/usr/local/lib/pam_google_authenticator.so noskewadj

这里的 required 表示如果验证失败则认为整个验证链失败。

如果不需要用户重新输入口令,则可以用上面这行换掉include那行。

在 sudoers 中还需要配置使用口令。如果是 NOPASSWD,则系统会绕过 auth 这一部分。

需要注意的是,由于 sudo 是一个特权提升点,因此假如用可以被用户自行改动的文件作为访问控制机制,便会构成一个显然的安全漏洞。因此,对应的 Google Authenticator 配置应以 sudo 的目标用户的身份进行(此外还应在sudoers中配置 Defaults rootpw):

sudo google-authenticator

也许应该抽时间改进一下,例如把 authenticator 的修改做成 setuid 的,并实现先验证之后再改?

Steven Paul "Steve" Jobs (1955 - 2011) passed away peacefully today. There aren't enough words to express all he contributed to this world.

Today, a shocking news have shaken the industry. Steve Jobs, a pioneer of our industry, after several years of struggling with cancer, passed away at 56. This marks a loss not only to Apple computer, but the whole industry, even Apple's business rivals.

I want to quote his 2005 Commencement at Stanford:

When I was 17, I read a quote that went something like: "If you live each day as if it was your last, someday you'll most certainly be right." It made an impression on me, and since then, for the past 33 years, I have looked in the mirror every morning and asked myself: "If today were the last day of my life, would I want to do what I am about to do today?" And whenever the answer has been "No" for too many days in a row, I know I need to change something.

Remembering that I'll be dead soon is the most important tool I've ever encountered to help me make the big choices in life. Because almost everything -- all external expectations, all pride, all fear of embarrassment or failure - these things just fall away in the face of death, leaving only what is truly important. Remembering that you are going to die is the best way I know to avoid the trap of thinking you have something to lose. You are already naked. There is no reason not to follow your heart.

Your time is limited, so don't waste it living someone else's life. Don't be trapped by dogma -- which is living with the results of other people's thinking. Don't let the noise of others' opinions drown out your own inner voice. And most important, have the courage to follow your heart and intuition. They somehow already know what you truly want to become. Everything else is secondary.

When I was young, there was an amazing publication called The Whole Earth Catalog, which was one of the bibles of my generation. It was created by a fellow named Stewart Brand not far from here in Menlo Park, and he brought it to life with his poetic touch. This was in the late 1960's, before personal computers and desktop publishing, so it was all made with typewriters, scissors, and polaroid cameras. It was sort of like Google in paperback form, 35 years before Google came along: it was idealistic, and overflowing with neat tools and great notions.

Stewart and his team put out several issues of The Whole Earth Catalog, and then when it had run its course, they put out a final issue. It was the mid-1970s, and I was your age. On the back cover of their final issue was a photograph of an early morning country road, the kind you might find yourself hitchhiking on if you were so adventurous. Beneath it were the words: "Stay Hungry. Stay Foolish." It was their farewell message as they signed off. Stay Hungry. Stay Foolish. And I have always wished that for myself. And now, as you graduate to begin anew, I wish that for you.

Stay Hungry. Stay Foolish.

We remember him for his inspiration to the world, his creativity and leadership, and his determination facing death. May he rest in peace.

Monthly Archives

Pages

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