??xml version="1.0" encoding="utf-8" standalone="yes"?> U别Q?中 ??/a> (shenyyi@cn.ibm.com), 软g工程? IBM 中国软g开发中?br />
2008 q?5 ?29 ?/p>
我们l常?x)碰到这L(fng)问题Q用 telnet/ssh d?jin)远E的 Linux 服务器,q行?jin)一些耗时较长的Q务, l果却由于网l的不稳定导致Q务中途失败。如何让命o(h)提交后不受本地关闭终端窗?|络断开q接的干扰呢Q下面D?jin)一些例子, (zhn)可以针对不同的场景选择不同的方式来处理q个问题?/p>
如果只是临时有一个命令需要长旉q行Q什么方法能最便的保证它在后台E_q行呢? 我们知道Q当用户注销QlogoutQ或者网l断开Ӟl端?x)收?HUPQhangupQ信号从而关闭其所有子q程。因此,我们的解军_法就有两U途径Q要么让q程忽略 HUP 信号Q要么让q程q行在新的会(x)话里从而成Z属于此终端的子进E? nohup 无疑是我们首先想到的办法。顾名思义Qnohup 的用途就是让提交的命令忽?hangup 信号。让我们先来看一?nohup 的帮助信息:(x) 可见Qnohup 的用是十分方便的,只需在要处理的命令前加上 nohup 卛_Q标准输出和标准错误~省?x)被重定向?nohup.out 文g中。一般我们可在结֊?strong>"&"来将命o(h)同时攑օ后台q行Q也可用 nohup 无疑能通过忽略 HUP 信号来我们的进E避免中途被中断Q但如果我们换个角度思考,如果我们的进E不属于接受 HUP 信号的终端的子进E,那么自然也就不会(x)受到 HUP 信号的媄(jing)响了(jin)。setsid p帮助我们做到q一炏V让我们先来看一?setsid 的帮助信息:(x) 可见 setsid 的用也是非常方便的Q也只需在要处理的命令前加上 setsid 卛_?/p>
值得注意的是Q上例中我们的进E?ID(PID)?1094Q而它的父 IDQPPIDQؓ(f)1Q即?init q程 IDQ,q不是当前终端的q程 ID。请此例与nohup ?/a>中的?ID 做比较?/p>
3?amp;
q里q有一个关?subshell 的小技巧。我们知道,一个或多个命名包含?#8220;()”中就能让q些命o(h)在子 shell 中运行中Q从而扩展出很多有趣的功能,我们现在要讨论的是其中之一?/p>
当我们将"&"也放?#8220;()”内之后,我们׃(x)发现所提交的作业ƈ不在作业列表中,也就是说Q是无法通过 从上例中可以看出Q新提交的进E的?IDQPPIDQؓ(f)1Qinit q程?PIDQ,q不是当前终端的q程 ID。因此ƈ不属于当前终端的子进E,从而也׃?x)受到当前终端?HUP 信号的媄(jing)响了(jin)?/p>
我们已经知道Q如果事先在命o(h)前加?nohup 或?setsid 可以避?HUP 信号的媄(jing)响。但是如果我们未加Q何处理就已经提交?jin)命令,该如何补救才能让它避?HUP 信号的媄(jing)响呢Q? q时惛_ nohup 或?setsid 已经为时已晚Q只能通过作业调度?disown 来解册个问题(sh)(jin)。让我们来看一?disown 的帮助信息:(x) 可以看出Q我们可以用如下方式来达成我们的目的?/p>
需要注意的是,当用过 disown 之后Q会(x)把目标作业从作业列表中U除Q我们将不能再?code>jobs来查看它Q但是依然能够用 但是q有一个问题,q种Ҏ(gu)的操作对象是作业Q如果我们在q行命o(h)时在l尾加了(jin)"&"来它成Z个作业ƈ在后台运行,那么׃事大吉了(jin)Q我们可以通过 CTRL-z 的用途就是将当前q程挂vQSuspendQ,然后我们可以用 我们已经知道?jin)如何让q程免受 HUP 信号的媄(jing)响,但是如果有大量这U命令需要在E_的后台里q行Q如何避免对每条命o(h)都做q样的操作呢Q? 此时最方便的方法就?screen ?jin)。简单的_(d)screen 提供?ANSI/VT100 的终端模拟器Q它能够在一个真实终端下q行多个全屏的伪l端。screen 的参数很多,h很强大的功能Q我们在此仅介绍其常用功能以?qing)简要分析一下ؓ(f)什么?screen 能够避免 HUP 信号的媄(jing)响。我们先看一?screen 的帮助信息:(x) 使用 screen 很方便,有以下几个常用选项Q?/p>
当我们用“-r”q接?screen ?x)话后,我们可以在q个伪终端里面ؓ(f)所Ʋؓ(f)Q再也不用担?HUP 信号?x)对我们的进E造成影响Q也不用l每个命令前都加?#8220;nohup”或?#8220;setsid”?jin)。这是ؓ(f)什么呢Q让我来看一下下面两个例子吧?/p>
我们可以看出Q未使用 screen 时我们所处的 bash ?sshd 的子q程Q当 ssh 断开q接ӞHUP 信号自然?x)?jing)响到它下面的所有子q程Q包括我们新建立?ping q程Q?/p>
而用了(jin) screen 后就不同?jin),此?bash ?screen 的子q程Q?screen ?initQPID?Q的子进E。那么当 ssh 断开q接ӞHUP 信号自然不会(x)影响?screen 下面的子q程?jin)?/p>
现在几种Ҏ(gu)已经介绍完毕Q我们可以根据不同的场景来选择不同的方案。nohup/setsid 无疑是(f)旉要时最方便的方法,disown 能帮助我们来事后补救当前已经在运行了(jin)的作业,?screen 则是在大扚w操作时不二的选择?jin)?/p>
x(chng)QIBM 中国软g开发中?WebSphere Portal 部门软g工程师?/p>
]]>
IBM 公司保留?developerWorks |站上发表的内容的著作权。未lIBM公司或原始作者的书面明确许可Q请勿{载。如果?zhn)希望转蝲Q请通过 提交转蝲h表单 联系我们的编辑团队?/span>
文档选项
惌q程在断开q接后依然保持运行?如果该进E已l开始运行了(jin)该如何补救? 如果有大量这c需求如何简化操作?
hangup 名称的来?/strong>
?Unix 的早期版本中Q每个终端都?x)通过 modem 和系l通讯。当用户 logout Ӟmodem ׃(x)挂断Qhang upQ电(sh)话?同理Q当 modem 断开q接Ӟ׃(x)l终端发?hangup 信号来通知其关闭所有子q程?
NOHUP(1) User Commands NOHUP(1)
NAME
nohup - run a command immune to hangups, with output to a non-tty
SYNOPSIS
nohup COMMAND [ARG]...
nohup OPTION
DESCRIPTION
Run COMMAND, ignoring hangup signals.
--help display this help and exit
--version
output version information and exit
">filename 2>&1"
来更改缺省的重定向文件名?/p>
nohup CZ
[root@pvcent107 ~]# nohup ping www.ibm.com &
[1] 3059
nohup: appending output to `nohup.out'
[root@pvcent107 ~]# ps -ef |grep 3059
root 3059 984 0 21:06 pts/3 00:00:00 ping www.ibm.com
root 3067 984 0 21:06 pts/3 00:00:00 grep 3059
[root@pvcent107 ~]#
2。setsid
SETSID(8) Linux Programmer’s Manual SETSID(8)
NAME
setsid - run a program in a new session
SYNOPSIS
setsid program [ arg ... ]
DESCRIPTION
setsid runs a program in a new session.
setsid CZ
[root@pvcent107 ~]# setsid ping www.ibm.com
[root@pvcent107 ~]# ps -ef |grep www.ibm.com
root 31094 1 0 07:28 ? 00:00:00 ping www.ibm.com
root 31102 29217 0 07:29 pts/4 00:00:00 grep www.ibm.com
[root@pvcent107 ~]#
jobs
来查看的。让我们来看看ؓ(f)什么这样就能躲q?HUP 信号的媄(jing)响吧?/p>
subshell CZ
[root@pvcent107 ~]# (ping www.ibm.com &)
[root@pvcent107 ~]# ps -ef |grep www.ibm.com
root 16270 1 0 14:13 pts/4 00:00:00 ping www.ibm.com
root 16278 15362 0 14:13 pts/4 00:00:00 grep www.ibm.com
[root@pvcent107 ~]#
回页?/strong>
disown [-ar] [-h] [jobspec ...]
Without options, each jobspec is removed from the table of
active jobs. If the -h option is given, each jobspec is not
removed from the table, but is marked so that SIGHUP is not
sent to the job if the shell receives a SIGHUP. If no jobspec
is present, and neither the -a nor the -r option is supplied,
the current job is used. If no jobspec is supplied, the -a
option means to remove or mark all jobs; the -r option without
a jobspec argument restricts operation to running jobs. The
return value is 0 unless a jobspec does not specify a valid
job.
灉|q用 CTRL-z
在我们的日常工作中,我们可以?CTRL-z 来将当前q程挂v到后台暂停运行,执行一些别的操作,然后再用 fg 来将挂v的进E重新放回前収ͼ也可?bg 来将挂v的进E放在后収ͼ(j)l箋(hu)q行。这h们就可以在一个终端内灉|切换q行多个dQ这一点在调试代码时尤为有用。因为将代码~辑器挂起到后台再重新放回时Q光标定位仍然停留在上次挂v时的位置Q避免了(jin)重新定位的麻?ch)?
ps -ef
查找到它?/p>
jobs
命o(h)来得到所有作业的列表。但是如果ƈ没有把当前命令作Z业来q行Q如何才能得到它的作业号呢?{案是?CTRL-zQ按住Ctrl键的同时按住z键)(j)?jin)?/p>
jobs
命o(h)来查询它的作业号Q再?code>bg jobspec 来将它放入后台ƈl箋(hu)q行。需要注意的是,如果挂v?x)?jing)响当前进E的q行l果Q请慎用此方法?/p>
disown CZ1Q如果提交命令时已经?#8220;&”命令放入后台运行,则可以直接?#8220;disown”Q?/strong>
[root@pvcent107 build]# cp -r testLargeFile largeFile &
[1] 4825
[root@pvcent107 build]# jobs
[1]+ Running cp -i -r testLargeFile largeFile &
[root@pvcent107 build]# disown -h %1
[root@pvcent107 build]# ps -ef |grep largeFile
root 4825 968 1 09:46 pts/4 00:00:00 cp -i -r testLargeFile largeFile
root 4853 968 0 09:46 pts/4 00:00:00 grep largeFile
[root@pvcent107 build]# logout
disown CZ2Q如果提交命令时未?#8220;&”命令放入后台运行,可?CTRL-z ?#8220;bg”其攑օ后台Q再使用“disown”Q?/strong>
[root@pvcent107 build]# cp -r testLargeFile largeFile2
[1]+ Stopped cp -i -r testLargeFile largeFile2
[root@pvcent107 build]# bg %1
[1]+ cp -i -r testLargeFile largeFile2 &
[root@pvcent107 build]# jobs
[1]+ Running cp -i -r testLargeFile largeFile2 &
[root@pvcent107 build]# disown -h %1
[root@pvcent107 build]# ps -ef |grep largeFile2
root 5790 5577 1 10:04 pts/3 00:00:00 cp -i -r testLargeFile largeFile2
root 5824 5577 0 10:05 pts/3 00:00:00 grep largeFile2
[root@pvcent107 build]#
回页?/strong>
SCREEN(1) SCREEN(1)
NAME
screen - screen manager with VT100/ANSI terminal emulation
SYNOPSIS
screen [ -options ] [ cmd [ args ] ]
screen -r [[pid.]tty[.host]]
screen -r sessionowner/[[pid.]tty[.host]]
DESCRIPTION
Screen is a full-screen window manager that multiplexes a physical
terminal between several processes (typically interactive shells).
Each virtual terminal provides the functions of a DEC VT100 terminal
and, in addition, several control functions from the ISO 6429 (ECMA
48, ANSI X3.64) and ISO 2022 standards (e.g. insert/delete line and
support for multiple character sets). There is a scrollback history
buffer for each virtual terminal and a copy-and-paste mechanism that
allows moving text regions between windows.
CTRL-a d
来暂时断开当前?x)话?
screen CZ
[root@pvcent107 ~]# screen -dmS Urumchi
[root@pvcent107 ~]# screen -list
There is a screen on:
12842.Urumchi (Detached)
1 Socket in /tmp/screens/S-root.
[root@pvcent107 ~]# screen -r Urumchi
1. 未?screen 时新q程的进E树(wi)
[root@pvcent107 ~]# ping www.google.com &
[1] 9499
[root@pvcent107 ~]# pstree -H 9499
init─┬─Xvnc
├─acpid
├─atd
├─2*[sendmail]
├─sshd─?/span>─sshd───bash───pstree
? └─sshd───bash───ping
2. 使用?screen 后新q程的进E树(wi)
[root@pvcent107 ~]# screen -r Urumchi
[root@pvcent107 ~]# ping www.ibm.com &
[1] 9488
[root@pvcent107 ~]# pstree -H 9488
init─┬─Xvnc
├─acpid
├─atd
├─screen───bash───ping
├─2*[sendmail]
回页?/strong>
回页?/strong>
]]>
通过使用 trQ?zhn)可以非常?gu)地实?sed 的许多最基本功能。?zhn)可以?tr 看作?sed 的(极其Q简化的变(sh)Q它可以用一个字W来替换另一个字W,或者可以完全除M些字W。?zhn)也可以用它来除去重复字符。这是所?tr 所能够做的?br />
tr用来从标准输入中通过替换或删除操作进行字W{换。tr主要用于删除文g中控制字W或q行字符转换。用tr时要转换两个字符Ԍ(x)字符?用于查询Q?字符?用于处理各种转换。tr刚执行时Q字W串1中的字符被映到字符?中的字符Q然后{换操作开始?br />
带有最常用选项的tr命o(h)格式为:(x)
tr -c -d -s ["string1_to_translate_from"] ["string2_to_translate_to"] < input-file
q里Q?br />
-c 用字W串1中字W集的补集替换此字符集,要求字符集ؓ(f)ASCII?br />
-d 删除字符?中所有输入字W?br />
-s 删除所有重复出现字W序列,只保留第一个;卛_重复出现字符串压~ؓ(f)一个字W串?br />
input-file是{换文件名。虽然可以用其他格式输入,但这U格式最常用?br />
2、字W范?br />
指定字符?或字W串2的内Ҏ(gu)Q只能用单字符或字W串范围或列表?br />
[a-z] a-z内的字符l成的字W串?br />
[A-Z] A-Z内的字符l成的字W串?br />
[0-9] 数字丌Ӏ?br />
\octal 一个三位的八进制数Q对应有效的ASCII字符?br />
[O*n] 表示字符O重复出现指定ơ数n。因此[O*2]匚wOO的字W串?br />
tr中特定控制字W的不同表达方式
速记W含义八q制方式
\a Ctrl-G 铃声\007
\b Ctrl-H 退格符\010
\f Ctrl-L 走行换页\014
\n Ctrl-J 新行\012
\r Ctrl-M 回R\015
\t Ctrl-I tab键\011
\v Ctrl-X \030
3、应用例?br />
Q?Q去除oops.txt里面的重复的写字符
tr -s "[a-z]"<oops.txt >result.txt
Q?Q删除空?br />
tr -s "[\012]" < plan.txt ?tr -s ["\n"] < plan.txt
Q?Q有旉要删除文件中的^MQƈ代之以换?br />
tr -s "[\015]" "[\n]" < file ?tr -s "[\r]" "[\n]" < file
Q?Q大写到写
cat a.txt |tr "[a-z]" "[A-Z]" >b.txt
Q?Q删除指定字W?br />
一个星期的日程表。Q务是从其中删除所有数字,只保留日期。日期有大写Q也有小写格式。因此需指定两个字符范围[a-z]和[A-Z]Q命令tr -cs "[a-z][A-Z]" "[\012*]" 文件每行所有不包含在[a-z]或[A-Z]Q所有希腊字母)(j)的字W串攑֜字符?中ƈ转换Z新行?s选项表明压羃所有新行, -c表明保留所有字母不动。原文g如下Q后跟tr命o(h)Q?br />
tr -cs "[a-z][A-Z]" "[\012*]" <diary.txt
Q?Q{换控制字W?br />
tr的第一个功能就是{换控制字W,特别是从dos向UNIX下蝲文gӞ忘记讄ftp关于回R换行转换的选项时更是如此。cat -v filename 昄控制字符?br />
cat -v stat.txt
box aa^^^^^12^M
apple bbas^^^^23^M
^Z
猜想‘^ ^ ^ ^ ^ ^’是tab键。每一行以Ctrl-Ml尾Q文件结Ctrl-ZQ以下是改动Ҏ(gu)?br />
使用-s选项Q查看ASCII表。^的八q制代码?36Q^M?15Qtab键是011Q^Z?32 ,下面按步骤完成最l功能?br />
用tab键替换^ ^ ^ ^ ^ ^Q命令ؓ(f)"\136" "[\011*]"。将l果重定向到临时工作文gstat.tmp
tr -s "[\136]" "[\011*]" <stat.txt >stat.tmp
用新行替换每行末^MQƈ用\n去除^ZQ输入要来自于(f)时工作文件stat.tmp?br />
tr -s "[\015][\032]" "\n" <stat.tmp
要删除所有的tab键,代之以空|使用命o(h)
tr -s "[\011]" "[\040*]" <input.file
Q?Q替换passwd文g中所有冒P代之以tab键,可以增加可读?br />
tr -s "[:]" "[\011]" < /etc/passwd ?tr -s "[:]" "[\t]" < /etc/passwd
Q?Q路径h可读?br />
如果?echo $PATH 或?echo $LD_LIBRARY_PATH {类似的命o(h)来显C\径信息的话,我们看到的将?x)是一大堆用冒可接在一L(fng)路径Q?tr命o(h)可以把这些冒可{换ؓ(f)回RQ这Pq些路径具有很好的可读性了(jin)
echo $PATH | tr ":" "\n"
Q?Q可以在vi内用所有这些命令!只要CQ在tr命o(h)前要加上(zhn)希望处理的行范围和感叹?Q!Q,?1,$!tr -d '\t'Q美元符可C最后一行)(j)?br />
Q?0Q另外,当有人给(zhn)发送了(jin)一个在 Mac OS ?DOS/Windows 机器上创建的文本文gӞ(zhn)会(x)发现tr非常有用?br />
如果没有文件保存(sh)ؓ(f)使用 UNIX 换行W来表示行结束这U格式,则需要将q样的文件{换成本机 UNIX 格式Q否则一些命令实用程序不?x)正地处理q些文g。Mac OS 的行以回R字符(\r)l束Q许多文本处理工具将q样的文件作Z行来处理。ؓ(f)?jin)纠正这个问题,可以用下列技巧:(x)
Mac -> UNIXQtr "\r" "\n"<macfile > unixfile
UNIX -> MacQtr "\n" "\r"<unixfile > macfile
Microsoft DOS/Windows U定Q文本的每行以回车字W?\r)q后跟换行符(\n)l束。ؓ(f)?jin)纠正这个问题,可以使用下列命o(h)Q?br />
DOS -> UNIXQtr -d "\r"<dosfile > unixfile
UNIX -> DOSQ在q种情况下,需要用awkQ因为tr不能插入两个字符来替换一个字W。要使用?awk 命o(h)?awk '{ print $0"\r" }'<unixfile > dosfile
]]>
1、找到相应的软g包,比如soft.version.rpmQ下载到本机某个目录Q?
2、打开一个终端,su -成root用户Q?
3、cd soft.version.rpm所在的目录Q?
4、输入rpm -ivh soft.version.rpm
二、deb包安装方式步骤:(x)
1、找到相应的软g包,比如soft.version.debQ下载到本机某个目录Q?
2、打开一个终端,su -成root用户Q?
3、cd soft.version.deb所在的目录Q?
4、输入dpkg -i soft.version.deb
三、tar.gz源代码包安装方式Q?
1、找到相应的软g包,比如soft.tar.gzQ下载到本机某个目录Q?
2、打开一个终端,su -成root用户Q?
3、cd soft.tar.gz所在的目录Q?
4、tar -xzvf soft.tar.gz //一般会(x)生成一个soft目录
5、cd soft
6?/configure
7、make
8、make install
四、tar.bz2源代码包安装方式Q?
1、找到相应的软g包,比如soft.tar.bz2Q下载到本机某个目录Q?
2、打开一个终端,su -成root用户Q?
3、cd soft.tar.bz2所在的目录Q?
4、tar -xjvf soft.tar.bz2 //一般会(x)生成一个soft目录
5、cd soft
6?/configure
7、make
8、make install
五、apt方式安装Q?
1、打开一个终端,su -成root用户Q?
2、apt-cache search soft 注:(x)soft是你要找的Y件的名称或相关信?
3、如?中找C(jin)软gsoft.versionQ则用apt-get install soft.version命o(h)?
装Y?注:(x)只要你可以上|,只需要用apt-cache search查找软gQ用apt-get
install软g
六、bin文g安装Q?
如果你下载到的Y件名是soft.binQ一般情况下是个可执行文Ӟ安装Ҏ(gu)如下Q?
1、打开一个终端,su -成root用户Q?
2、chmod +x soft.bin
3?/soft.bin //q行q个命o(h)可以安装Y件了(jin)
七、不需要安装的软gQ?
有了(jin)些YӞ比如lumaqqQ是不需要安装的Q自带jre解压~后可直接运行。假?
下蝲的是lumaqq.tar.gzQ用方法如下:(x)
1、打开一个终端,su -成root用户Q?
2、tar -xzvf lumaqq.tar.gz //q一步会(x)生成一个叫LumaQQ的目?
3、cd LumaQQ
4、chmod +x lumaqq //讄lumaqqq个E序文g为可q行
5、此时就可以q行lumaqq?jin),用命?/lumaqq卛_Q但每次q行要输入全路径?
切换到刚才生成的LumaQQ目录?
6、ؓ(f)?jin)保证不讄路径可以用Q你可以?bin目录下徏立一个lumaqq的链接,
用命令ln -s lumaqq /bin/ 卛_Q以后Q何时候打开一个终端输入lumaqq可?
启动QQ聊天软g?
7?如果你要想lumaqq有个菜单,使用菜单~辑工具Q比如Alacarte Menu
EditorQ找C面生成的LumaQQ目录里的lumaqq讄一个菜单项可以了(jin)Q当然你
也可以直接到 /usr/share/applications目录Q按照里面其?.desktop文g的格
式生成一个自qdesktop文g卛_?/p>
Google原理QZTQ?/p>
q篇文章中,我们介绍?jin)googleQ它是一个大型的搜烦(ch)引擎Qof a large-scale search engineQ的原型Q搜索引擎在文本中应用q泛。Google的设计能够高效地抓网ƈ建立索引Q它的查询结果比其它现有pȝ都高明。这个原型的全文和超q接的数据库臛_包含24‘000‘000个网c(din)我们可以从http://google.stanford.edu/ 下蝲?/p>
设计搜烦(ch)引擎是一富有挑(xi)战性的工作。搜索引擎ؓ(f)上亿个网徏立烦(ch)引,其中包含大量q然不同的词汇。而且每天要回{成千上万个查询。在|络中,管大型搜烦(ch)引擎非常重要Q但是学术界却很研I它。此外由于技术的快速发展和|页的大量增加,现在建立一个搜索引擎和三年前完全不同?/p>
本文详细介绍?jin)我们的大型搜?ch)引擎Q据我们所知,在公开发表的论文中Q这是第一描q地如此详细。除?jin)把传统数据搜?ch)技术应用到如此大量U网中所遇到的问题,q有许多新的技术挑(xi)战,包括应用文本中的附加信息改q搜索结果?/p>
本文解册个问题,描述如何q用文本中的附加信息,建立一个大型实用系l。Q何h都可以在|上随意发布信息Q如何有效地处理q些无组l的文本集合,也是本文要关注的问题?/p>
关键?nbsp;World Wide WebQ搜索引擎,信息(g)索,PageRank, Google 1 l论 Web l信息检索带来了(jin)新的?xi)战。Web上的信息量快速增长,同时不断有毫无经验的新用h体验W(xu)ebq门艺术。h们喜Ƣ用链接来网上冲,通常都以?nbsp;Yahooq样重要的网|搜烦(ch)引擎开始。大家认为List(目录)有效地包含了(jin)大家感兴的主题Q但是它h主观性,建立和维护的代h(hun)高,升慢,不能包括所有深奥的主题。基于关键词的自动搜索引擎通常q回太多的低质量的匹配。问题更遭的是Q一些广告ؓ(f)?jin)赢得h们的x(chng)x(chng)设法误导自动搜烦(ch)引擎?/p>
我们建立?jin)一个大型搜索引擎解决了(jin)现有pȝ中的很多问题。应用超文本l构Q大大提高(sh)(jin)查询质量。我们的pȝ命名为googleQ取名自googol的通俗拼法Q即10?00ơ方Q这和我们的目标建立一个大型搜索引擎不谋而合?/p>
1.1 |络搜烦(ch)引擎—升U换代(scaling upQ:(x)1994-2000 搜烦(ch)引擎技术不得不快速升U(scale dramaticallyQ跟上成倍增长的web数量?994q_(d)W一个Web搜烦(ch)引擎QW(xu)orld Wide Web Worm(WWWW)可以(g)索到110Q?00个网和W(xu)eb的文件。到1994q?1月,的搜索引擎声U可以检索到2‘000'000 QWebCrawlerQ至100‘000'000个网l文Ӟ来自 Search Engine WatchQ。可以预见到2000q_(d)可检索到的网将过1‘000'000‘000。同Ӟ搜烦(ch)引擎的访问量也会(x)以惊人的速度增长。在1997q的三四月䆾QW(xu)orld Wide Web Worm q_每天收到1500个查询?/p>
?997q?1月,Altavista 声称它每天要处理大约20'000'000个查询。随着|络用户的增长,?000q_(d)自动搜烦(ch)引擎每天处理上亿个查询。我们系l的设计目标要解册多问题,包括质量和可升性,引入升搜烦(ch)引擎技术(scaling search engine technologyQ,把它升到如此大量的数据上?/p>
1.2 GoogleQ跟上Web的步伐(Scaling with the WebQ徏立一个能够和当今web规模盔R应的搜索引擎会(x)面(f)许多?xi)战。抓|页技术必够快Q才能跟上网变化的速度Qkeep them up to dateQ。存储烦(ch)引和文档的空间必够大。烦(ch)引系l必能够有效地处理上千亿的数据。处理查询必dQ达到每U能处理成百上千个查询(hundreds to thousands per second.Q。随着Web的不断增长,q些d变得来艰巨。然而硬件的执行效率和成本也在快速增长,可以部分抉|q些困难?/p>
q有几个值得注意的因素,如磁盘的寻道旉Qdisk seek timeQ,操作pȝ的效率(operating system robustnessQ。在设计Google的过E中Q我们既考虑?jin)Web的增镉K度Q又考虑?jin)技术的更新。Google的设计能够很好的升处理量数据集。它能够有效地利用存储空间来存储索引。优化的数据l构能够快速有效地存取Q参?.2节)(j)。进一步,我们希望Q相对于所抓取的文本文件和HTML|页的数量而言Q存储和建立索引的代价尽可能的小Q参考附录BQ。对于象Googleq样的集中式pȝQ采取这些措施得C(jin)令h满意的系l可升性(scaling propertiesQ?/p>
1. 3设计目标
1.3.1提高搜烦(ch)质量我们的主要目标是提高Web搜烦(ch)引擎的质量?nbsp;1994q_(d)有h认ؓ(f)建立全搜索烦(ch)引(a complete search indexQ可以查找M数据都变得容易。根据Best of the Web 1994 -- Navigators Q?#8220;最好的D服务可以使在Web上搜索Q何信息都很容易(当时所有的数据都可以被dQ?#8221;。然?997q的WebpE然不同。近来搜索引擎的用户已经证实索引的完整性不是评h索质量的唯一标准。用h兴趣的搜索结果往(xin)往(xin)湮没?#8220;垃圾l果Junk result”中。实际上Q到1997q?1月ؓ(f)止,四大商业搜烦(ch)引擎中只有一个能够找到它自己Q搜索自己名字时q回的前十个l果中有它自己)(j)。导致这一问题的主要原因是文档的烦(ch)引数目增加了(jin)好几个数量Q但是用戯够看的文档数却没有增加。用户仍然只希望看前面几十个搜烦(ch)l果。因此,当集合增大时Q我们就需要工具ɾl果_Q在q回的前几十个结果中Q有x(chng)档的数量Q。由于是从成千上万个有点相关的文档中选出几十个,实际上,相关的概念就是指最好的文档。高_非常重要Q甚至以响应Q系l能够返回的有关文档的LQؓ(f)代h(hun)。o(h)人高兴的是利用超文本链接提供的信息有助于改进搜烦(ch)和其它应用。尤其是链接l构和链接文本,为相x(chng)的判断和高质量的过滤提供了(jin)大量的信息。Google既利用了(jin)链接l构又用C(jin)anchor文本Q见2.1?.2 节)(j)?/p>
1.3.2搜烦(ch)引擎的学术研I着旉的流逝,除了(jin)发展q速,W(xu)eb来商业化?993q_(d)只有1.5%的Web服务是来? com域名。到1997q_(d)过?0%。同Ӟ搜烦(ch)引擎从学术领域走q商业。到现在大多数搜索引擎被公司所有,很少技公开术细节。这导致搜索引擎技术很大程度上仍然是暗操作,q們做广告(见附录AQ。Google的主要目标是推动学术领域在此斚w的发展,和对它的?jin)解。另一个设计目标是l大家一个实用的pȝ。应用对我们来说非常重要Q因为现代网l系l中存在大量的有用数据(us because we think some of the most interesting research will involve leveraging the vast amount of usage data that is available from modern web systemsQ。例如,每天有几千万个研I。然而,得到q些数据却非常困难,主要因ؓ(f)它们没有商业价倹{我们最后的设计目标是徏立一个体pȝ构能够支持新的关于v量Web数据的研I。ؓ(f)?jin)支持新研究QGoogle以压~的形式保存?sh)(jin)实际所抓到的文档。设计google的目标之一是要徏立一个环境其他研究者能够很快进入这个领域,处理量Web数据Q得到满意的l果Q而通过其它Ҏ(gu)却很隑־到结果。系l在短时间内被徏立v来,已经有几论文用C(jin) Google建的数据库,更多的在h中。我们的另一个目标是建立一个宇宙空间实验室似的环境Q在q里研究者甚臛_生都可以Ҏ(gu)们的量Web数据设计或做一些实验?/p>
2. pȝ特点 Google搜烦(ch)引擎有两个重要特点,有助于得到高_ֺ的搜索结果?/p>
W一点,应用Web的链接结构计每个网늚Rank|UCؓ(f)PageRankQ将?8详l描q它?/p>
W二点,Google利用链接改q搜索结果?/p>
2.1 PageRank:l网|?nbsp;Web的引用(链接Q图是重要的资源Q却被当今的搜烦(ch)引擎很大E度上忽视了(jin)。我们徏立了(jin)一个包?18‘000'000个超链接的图Q它是一个具有重要意义的h。这些图能够快速地计算|页的PageRank|它是一个客观的标准Q较好的W合Z?j)目中对一个网重要程度的评h(hun)Q徏立的基础是通过引用判断重要性。因此在web中,PageRank能够优化关键词查询的l果。对于大多数的主题,在网|题查询中用PageRank优化单文本匹配,我们得到?jin)o(h)人惊叹的l果Q从google.stanford.edu可以得到演示Q。对于Googleȝl中的全文搜索,PageRank也帮?jin)不忙?/p>
2.1.1计算PageRank 文献?hu)(g)索中的引用理论用到Web中,引用|页的链接数Q一定程度上反映?jin)该|页的重要性和质量。PageRank发展?jin)这U思想Q网间的链接是不^{的?/p>
PageRank 定义如下: 我们假设T1…Tn指向|页A(ch)Q例如,被引用)(j)。参数d是制动因子,使结果在0Q?之间。通常d{于0.85。在下一节将详细介绍d。CQAQ定义ؓ(f)|页 A指向其它|页的链接数Q网A(ch)的PageRank值由下式l出Q?nbsp;PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) 注意PageRank的Ş式,分布到各个网中Q因此所有网늚PageRank和是1?nbsp;PageRank或PRQAQ可以用单的q代法计算Q相应规格化Web链接矩阵的主特征向量。中{规模的|站计算26‘000'000|页?nbsp;PageRankDp几小时。还有一些技术细节超Z(jin)本文的范围?/p>
2.1.2直觉判断 PageRank被看作用戯为的模型。我们假讄上冲是随机的,不断点击链接Q从不返回,最l烦(ch)?jin),另外随机选一个网重新开始冲。随问一个网늚可能性就是它的PageRank倹{制动因子d是随问一个网늃(ch)?jin)的可能性,随机另选一个网c(din)对单个|页或一l网,一个重要的变量加入到制动因子d中。这允许个h可以故意地误导系l,以得到较高的PageRank倹{我们还有其它的PageRank法Q见98c(din)?/p>
另外的直觉判断是一个网|很多|页指向它,或者一些PageRank值高的网|向它Q则q个|页很重要。直觉地Q在Web中,一个网被很多|页引用Q那么这个网值得一看。一个网被象Yahooq样重要的主引用即使一ơ,也值得一看。如果一个网늚质量不高Q或者是死链接,象Yahooq样的主不?x)链向它?nbsp;PageRank处理?jin)这两方面因素,q过|络链接递归C递?/p>
2.2链接描述文字QAnchor TextQ我们的搜烦(ch)引擎寚w接文本进行了(jin)Ҏ(gu)的处理。大多数搜烦(ch)引擎把链接文字和它所铑的网(the page that the link is onQ联pv来。另外,把它和链接所指向的网联pv来。这有几点好处?/p>
W一Q通常链接描述文字比网|w更_地描q该|页?/p>
W二Q链接描q文字可能链向的文档不能被文本搜索引擎检索到Q例如图像,E序和数据库。有可能使返回的|页不能被抓到。注意哪些抓不到的网将?x)带来一些问题。在q回l用户前(g)不?jin)它们的有效性。这U情冉|索引擎可能返回一个根本不存在的网,但是有超U链接指向它。然而这U结果可以被?xi)出来的Q所以此cȝ问题很少发生。链接描q文字是对被铑|页的宣传,q个思想被用在World Wide Web Worm 中,主要因ؓ(f)它有助于搜烦(ch)非文本信息,能够用少量的已下载文档扩大搜索范围。我们大量应用链接描q文字,因ؓ(f)它有助于提高搜烦(ch)l果的质量。有效地利用链接描述文字技术上存在一些困难,因ؓ(f)必须处理大量的数据。现在我们能抓到24‘000'000个网,已经(g)索到259‘000'000多个链接描述文字?/p>
2.3其它特点除了(jin)PageRank和应用链接描q文字外QGoogleq有一些其它特炏V?/p>
W一,所有hit都有位置信息Q所以它可以在搜索中q泛应用邻近性(proximityQ?/p>
W二QGoogle跟踪一些可视化外表l节Q例如字受黑体大号字比其它文字更重要?/p>
W三Q知识库存储?jin)原始的全文html|页?/p>
3 有关工作 Web(g)索研I的历史短。World Wide Web WormQ)(j)是最早的搜烦(ch)引擎之一。后来出C(jin)一些用于学术研I的搜烦(ch)引擎Q现在它们中的大多数被上?jng)公司拥有。与Web的增长和搜烦(ch)引擎的重要性相比,有关当今搜烦(ch)引擎技术的优秀论文相当。根据Michael MauldinQLycos Inc的首席科学家Q? Q?#8220;各种各样的服务(包括LycosQ非常关注这些数据库的细节?#8221;虽然在搜索引擎的某些特点上做?jin)大量工作。具有代表性的工作有,对现有商业搜索引擎的l果q行传递,或徏立小型的个性化的搜索引擎。最后有关信息检索系l的研究很多Q尤其在有组l机构集合(well controlled collectionsQ方面。在下面两节Q我们将讨论在信息检索系l中的哪些领域需要改q以便更好的工作在Web上?/p>
3.1信息(g)索信息检索系l诞生在几年前,q发展迅速。然而大多数信息(g)索系l研I的对象是小规模的单一的有l织l构的集合,例如U学论文集,或相关主题的新闻故事。实际上Q信息检索的主要基准Qthe Text Retrieval ConferenceQ)(j)Q用规模的、有l织l构的集合作为它们的基准?/p>
大型文集基准只有20GBQ相比之下,我们抓到?4000000个网占147GB。在TREC上工作良好的pȝQ在Web上却不一定生好的结果。例如,标准向量I间模型企图q回和查询请求最相近的文档,把查询请求和文档都看作由出现在它们中的词汇组成的向量。在Web环境下,q种{略常常q回非常短的文档Q这些文档往(xin)往(xin)是查询词再加几个字。例如,查询“Bill Clinton”Q返回的|页只包?#8220;Bill Clinton Sucks”Q这是我们从一个主要搜索引擎中看到的。网l上有些争议Q用户应该更准确地表达他们想查询什么,在他们的查询h中用更多的词。我们强烈反对这U观炏V如果用h?gu)?#8220;Bill Clinton”q样的查询请求,应该得到理想的查询结果,因ؓ(f)q个主题有许多高质量的信息。象所l的例子Q我们认Z息检索标准需要发展,以便有效地处理Web数据?/p>
3.2有组l结构的集合QWell Controlled CollectionsQ与Web的不同点 Web是完全无l织的异构的大量文档的集合。Web中的文档无论内在信息q是隐含信息都存在大量的异构性。例如,文档内部q?jin)不同的语言Q既有hc语a又有E序Q,词汇Qemail地址Q链接,邮政~码Q电(sh)话号码,产品P(j)Q类型(文本QHTMLQPDFQ图像,声音Q,有些甚至是机器创建的文gQlog文gQ或数据库的输出Q。可以从文档中推断出来,但ƈ不包含在文档中的信息UCؓ(f)隐含信息。隐含信息包括来源的信誉Q更新频率,质量Q访问量和引用。不但隐含信息的可能来源各种各样Q而且被检的信息也大不相同,相差可达好几个数量。例如,一个重要主늚使用量,象Yahoo 每天览数达C百万ơ,于此相比无名的历史文章可能十q才被访问一ơ。很明显Q搜索引擎对q两cM息的处理是不同的?nbsp;Web与有l织l构集合之间的另外一个明昑别是Q事实上Q向Web上传信息没有M限制。灵zd用这点可以发布Q何对搜烦(ch)引擎影响重大的信息,使\由阻塞,加上为牟利故意操U|索引擎,q些已经成ؓ(f)一个严重的问题。这些问题还没有被传l的闭的信息检索系l所提出来。它兛_(j)的是元数据的努力Q这在Web 搜烦(ch)引擎中却不适用Q因为网中的Q何文本都不会(x)向用户声UC图操U|索引擎。甚x(chng)些公ؓ(f)牟利专门操纵搜烦(ch)引擎?/p>
4 pȝ分析QSystem AnatomyQ首先,我们提供高水q的有关体系l构的讨论。然后,详细描述重要的数据结构。最后,主要应用Q抓|页Q烦(ch)引,搜烦(ch)被严格地检查?nbsp;Figure 1. High Level Google Architecture 4.1Google体系l构概述q一节,我们看看整个系l是如何工作的(give a high levelQ,见图1。本节不讨论应用和数据结构,在后几节中讨论。ؓ(f)?jin)效率大部分Google是用c或c++实现的,既可以在Solaris也可以在 Linux上运行?/p>
Googlepȝ中,抓网(下蝲|页Q是由几个分布式crawlers完成的。一个URL服务器负责向crawlers 提供URL列表。抓来的|页交给存储服务器storeserver。然后,由存储服务器压羃|页q把它们存到知识库repository中。每个网都有一个IDQ称作docIDQ当新URL从网中分析出时Q就被分配一个docID。由索引器和排序器负责徏立烦(ch)引index function。烦(ch)引器从知识库中读取文档,对其解压~和分析。每个文档被转换成一l词的出现情况,UC命中h(hun)its。HitsU录?jin)词Q词在文档中的位|,最接近的字P大小写。烦(ch)引器把这些hits分配Cl桶barrel中,产生l过部分排序后的索引。烦(ch)引器的另一个重要功能是分析|页中所有的链接Q将有关的重要信息存在链接描qanchors文g中。该文g包含?jin)够的信息Q可以用来判断每个链接链出链入节点的信息Q和链接文本?nbsp;URL分解器resolver阅读链接描述anchors文gQƈ把相对URL转换成绝对URLQ再转换成docID。ؓ(f)链接描述文本~制索引Qƈ与它所指向的docID兌h。同时徏立由docID对组成的链接数据库。用于计所有文档的PageRank倹{用docID分类后的barrelsQ送给排序器sorterQ再Ҏ(gu)wordIDq行分类Q徏立反向烦(ch)引inverted index。这个操作要恰到好处Q以便几乎不需要暂存空间。排序器q给出docID和偏U量列表Q徏立反向烦(ch)引。一个叫DumpLexicon的程序把q个列表和由索引器生的字典l合在一P建立一个新的字典,供搜索器使用。这个搜索器是利用一个Web服务器,使用由DumpLexicon所生成的字典,利用上述反向索引以及(qing)面{PageRank来回{用L(fng)提问?nbsp;4.2主要数据l构l过优化的Google数据l构Q能够用较小的代h取大量文档,建立索引和查询。虽然近几年CPU和输入输出速率q速提高。磁盘寻道仍焉?0ms。Q何时候Googlepȝ的设计都可能地避免盘寻道。这Ҏ(gu)据结构的设计影响很大?/p>
4.2.1大文件大文g BigFiles是指虚拟文g生成的多文gpȝQ用长度?4位的整型数据d。多文gpȝ之间的空间分配是自动完成的。BigFiles包也处理已分配和未分配文件描q符。由于操U늳l不能满x(chng)们的需要,BigFiles也支持基本的压羃选项?/p>
4.2.2知识?nbsp;Figure 2. Repository Data Structure 知识库包含每个网늚全部HTML。每个网는zlibQ见RFC1950Q压~。压~技术的选择既要考虑速度又要考虑压羃率。我们选择zlib的速度而不是压~率很高的bzip。知识库用bzip的压~率接近4Q?。而用zlib的压~率?Q?。文档一个挨着一个的存储在知识库中,前缀是docIDQ长度,URLQ见?。访问知识库不需要其它的数据l构。这有助于数据一致性和升。用其它数据l构重构pȝQ我们只需要修改知识库和crawler错误列表文g?/p>
4.2.3文g索引文g索引保存?sh)(jin)有x(chng)档的一些信息。烦(ch)引以docID的顺序排列,定宽ISAMQIndex sequential access modeQ。每条记录包括当前文件状态,一个指向知识库的指针,文g校验和,各种l计表。如果一个文档已l被抓到Q指针指向docinfo文gQ该文g的宽度可变,包含?jin)URL和标题。否则指针指向包含这个URL的URL列表。这U设计考虑到简z的数据l构Q以?qing)在查询中只需要一个磁盘寻道时间就能够讉K一条记录。还有一个文件用于把URL转换成docID。它是URL校验和与相应docID的列表,按校验和排序。要想知道某个URL的docIDQ需要计URL的校验和Q然后在校验和文件中执行二进制查找,扑ֈ它的docID。通过对这个文件进行合qӞ可以把一批URL转换成对应的docID。URL分析器用q项技术把URL转换成docID。这U成Ҏ(gu)新的模式是至关重要的Q否则每个链接都需要一ơ查询,假如用一块磁盘,322‘000'000个链接的数据集合花费一个多月的旉?/p>
4.2.4词典词典有几U不同的形式。和以前pȝ的重要不同是Q词典对内存的要求可以在合理的h(hun)格内。现在实现的pȝQ一?56M内存的机器就可以把词典装入到内存?sh)。现在的词典包含14000000词汇Q虽然一些很用的词汇没有加入到词典中)(j)。它执行分两部分—词汇表Q用null分隔的连l串Q和指针的哈希表。不同的函数Q词汇表有一些辅助信息,q超Z(jin)本文的范围?/p>
4.2.5 hit list hit list是一文档中所出现的词的列表,包括位置Q字P大小写。Hit list占很大空_(d)用在正向和反向烦(ch)引中。因此,它的表示形式有效越好。我们考虑?jin)几U方案来~码位置Q字P大小写—简单编码(3个整型数Q,紧凑~码Q支持优化分配比特位Q,哈夫曼编码。Hit的详l信息见?。我们的紧凑~码每个hit?字节。有两种cdhitQ特Dhit和普通hit。特D?nbsp;hit包含URLQ标题,链接描述文字Qmeta tag。普通hit包含其它每g事。它包括大小写特征位Q字P12比特用于描述词在文档中的位置Q所有超q?095的位|标Cؓ(f)4096Q。字号采用相对于文档的其它部分的相对大小表示Q占3比特(实际只用7个|因ؓ(f)111标志是特Dhit)。特Dhit由大写特征位,字号位ؓ(f)7表示它是Ҏ(gu) hitQ用4比特表示Ҏ(gu)hit的类型,8比特表示位置。对于anchor hit八比特位|位分出4比特用来表示在anchor中的位置Q?比特用于表明anchor出现的哈希表hash of the docID。短语查询是有限的,Ҏ(gu)些词没有_多的anchor。我们希望更新anchor hit的存储方式,以便解决地址位和docIDhash域位C的问题?/p>
因ؓ(f)搜烦(ch)Ӟ你不?x)因为文档的字号比别的文档大而特D对待它Q所以采用相对字受?nbsp;hit表的长度存储在hit前。ؓ(f)节省I间hit表长度,在正向烦(ch)引中和wordIDl合在一P在反向烦(ch)引中和docIDl合存储。这限制它相应地只??比特Q用些技巧,可以从wordID中?bitQ如果大于这些比Ҏ(gu)能表C的长度Q用溢出码填充,其后两字节是真正的长度?nbsp;Figure 3. Forward and Reverse Indexes and the Lexicon
4.2.6正向索引实际上,正向索引已经部分排序。它被存在一定数量的barrel中(我们?4个barrelsQ。每个barrel装着一定范围的wordID。如果一文档中的词落到某个 barrelQ它的docID被记录到这个barrel中,紧跟着那些词(文档中所有的词汇Q还是落入该barrel中的词汇Q对应的hitlist。这U模式需要稍多些的存储空_(d)因ؓ(f)一个docID被用多次Q但是它节省?jin)桶数和旉Q最后排序器q行索引旉低编码的复杂度。更q一步的措施是,我们不是存储docID本nQ而是存储相对于该桶最的docID的差。用q种Ҏ(gu)Q未排序的barrel的docID只需24位,省下8位记录hitlist ѝ?/p>
4.2.7反向索引除了(jin)反向索引由sorter加工处理之外Q它和正向烦(ch)引包含相同的桶。对每个有效的docIDQ字典包含一个指向该词所在桶的指针。它指向由docID和它的相应hitlistl成的doclishQ这个doclist代表?jin)所有包含该词的文档?nbsp;doclist中docID的顺序是一个重要的问题。最单的解决办法是用doclish排序。这U方法合q多个词时很快。另一个可选方案是用文档中该词出现的次数排序。这U方法回{单词查询,所用时间微不道。当多词查询时几乎是从头开始。ƈ且当用其它Rank法改进索引Ӟ非常困难。我们综合了(jin)q两U方法,建立两组反向索引barrelQ一lbarrels的hitlist只包含标题和anchor hitQ另一lbarrel包含全部的hitlist。我们首先查W一l烦(ch)引桶Q看有没有匹配的,然后查较大的那组桶?/p>
4.3抓网运行网l爬行机器h是一具有挑(xi)战性的d。执行的性能和可靠性甚x(chng)重要Q还有一些社?x)焦炏V网l爬行是一w常薄q应用Q它需要成百上千的web服务器和各种域名服务器的参与Q这些服务器不是我们pȝ所能控制的。ؓ(f)?jin)覆盖几十亿的网,Google拥有快速的分布式网l爬行系l。一个URL服务器给若干个网l爬行机器hQ我们采?个)(j)提供URL列表。URL服务器和|络爬行机器人都是用Python实现的。每个网l爬行机器h可以同时打开300个链接。抓取网必够快。最快时Q用4个网l爬行机器h每秒可以爬行100个网c(din)速率达每U?00K。执行的重点是找DNS。每个网l爬行机器h有它自己?nbsp;DNS cacheQ所以它不必每个|页都查DNS。每一百个q接都有几种不同的状态:(x)查DNSQ连接主机,发送请求,接收回答。这些因素ɾ|络爬行机器人成为系l比较复杂的部分。它用异步IO处理事gQ若q请求队列从一个网站到另一个网站不停的抓取|页。运行一个链接到500多万台服务器的网늈行机器hQ?nbsp;1千多万登陆口Q导致了(jin)大量的Email和电(sh)话。因为网民众多,L些h不知道网l爬行机器h是何物,q是他们看到的第一个网l爬行机器h。几乎每天我们都?x)收到这L(fng)Email“哦,你从我们的网站看?jin)太多的|页Q你惛_什么?”q有一些h不知道网l搜索机器h避免协议Qthe robots exclusion protocolQ,以ؓ(f)他们的网上写着“版权所有,勿被索引”的字样就?x)被保护不被索引Q不必说Q这L(fng)话很难被web crawler理解。因为数据量如此之大Q还?sh)(x)遇C些意想不到的事情。例如,我们的系l曾l企图抓一个在U游戏,l果抓到?jin)游戏中的大量垃圾信息。解册个问题很单。但是我们下载了(jin)几千万网后才发C(jin)q个问题。因为网和服务器的U类J多Q实际上不在大部分Internet上运行它?yu)测试一个网늈行机器h是不可能。L有几百个隐含的问题发生在整个web的一个网上Q导致网l爬行机器h崩溃Q或者更p,D不可预测的不正确的行为。能够访问大部分Internet的系l必ȝ力充沛ƈ_ֿ(j)试q。由于象crawlerq样大型复杂的系lL产生q样那样的问题,因此p一些资源读q些 EmailQ当问题发生时解军_Q是有必要的?/p>
4.4Web索引分析—Q何运行在整个Web上的分析器必能够处理可能包含错误的大型集合。范围从HTML标记到标C间几K字节?Q非ASCII字符Q几癑ֱHTML标记的嵌套,各种各样令h难以惌的错误。ؓ(f)?jin)获得最大的速度Q我们没有采用YACC产生上下文无x(chng)法CFG分析器,而是采用灉|的方式生词汇分析器Q它自己配有堆栈。分析器的改q大大提高(sh)(jin)q行速度Q它的精力如此充沛完成了(jin)大量工作。把文档装入barrel建立索引—分析完一文档,之后把该文档装入barrel中,用内存(sh)的hash表—字典,每个词汇被{换成一?nbsp;wordID。当hash表字怸加入新的Ҏ(gu)Q笨拙地存入文g。一旦词汇被转换成wordIDQ它们在当前文档的出现就转换成hitlistQ被写进正向barrel。烦(ch)引阶Dƈ行的主要困难是字兔R要共享?/p>
我们采用的方法是Q基本字怸?40万个固定词汇Q不在基本字怸的词汇写入日志,而不是共享字典。这U方法多个烦(ch)引器可以q行工作Q最后一个烦(ch)引器只需处理一个较?yu)的额外词汇日志。排序—ؓ(f)?jin)徏立反向?ch)引,排序器读取每个正?nbsp;barrelQ以wordID排序Q徏立只有标题anchor hi t的反向烦(ch)引barrel和全文反向烦(ch)引barrel。这个过E一ơ只处理一个barrelQ所以只需要少量暂存空间。排序阶D也是ƈ行的Q我们简单地同时q行可能多的排序器Q不同的排序器处理不同的桶。由于barrel不适合装入dQ排序器q一步依据wordID和docID把它分成若干子Q以侉K合装入d。然后排序器把每个篮子装入主存进行排序,q把它的内容写回到短反向barrel和全文反向barrel?/p>
4.5搜烦(ch)搜烦(ch)的目标是提供有效的高质量的搜索结果。多数大型商业搜索引擎好像在效率斚wp?jin)很大力气。因此我们的研究以搜索质量ؓ(f)重点Q相信我们的解决Ҏ(gu)也可以用到那些商业系l中?/p>
Google查询评h(hun)q程见图4?/p>
1. 分析查询?/p>
2. 把词汇{换成wordID?/p>
3. 在短barrel中查找每个词汇doclist的开头?/p>
4. 扫描doclist直到扑ֈ一匹配所有关键词的文?/p>
5. 计算该文档的rank
6. 如果我们在短barrelQƈ且在所有doclist的末,开始从全文barrel的doclist的开头查找每个词Qgoto W四?/p>
7. 如果不在Mdoclist的结,q回W四步?/p>
8. Ҏ(gu)rank排序匚w文档Q返回前k个。图4 Google查询评h(hun)在有限的响应旉内,一旦找C定数量的匚w文档Q搜索引擎自动执行步?。这意味着Q返回的l果是子优化的。我们现在研I其它方法来解决q个问题。过L据PageRank排序hitQ看来能够改q这U状c(din)?/p>
4.5.1 Rankingpȝ Google比典型搜索引擎保存(sh)(jin)更多的web信息。每个hitlish包括位置Q字P大小写。另外,我们q考虑?jin)链接描q文字。Rankl合所有这些信息是困难的。ranking函数设计依据是没有某个因素对rank影响重大。首先,考虑最单的情况—单个词查询。ؓ(f)?jin)单个词查询中一个文档的 rankQGoole在文档的hitlist中查找该词。Google认ؓ(f)每个hit是几U不同类型(标题Q链接描q文字anchorQURLQ普通大字号文本Q普通小字号文本Q?#8230;…Q之一Q每U有它自qcd权重。类型权重徏立了(jin)一个类型烦(ch)引向量。Google计算hitlist中每Uhit的数量。然后每个hit数{换成count-weight。Count-weight开始随hit数线性增加,很快逐渐停止Q以至于hitC此不相关。我们计?nbsp;count-weight向量和type-weight向量的标量积作ؓ(f)文档的IR倹{最后IR值结合PageRank作ؓ(f)文档的最后rank 对于多词查询Q更复杂些。现在,多词hitlist必须同时扫描Q以便关键词出现在同一文档中的权重比分别出现时高。相邻词的hit一起匹配。对每个匚w hit 的集合计相d。相dZhit在文档中的距,分成10个不同的bin|范围从短语匹配到Ҏ(gu)不相兟뀂不仅计每chit敎ͼ而且要计每U类型的盔R度,每个cd怼度对Q有一个类型相d权type-prox-weight。Count转换成count-weightQ计count- weight type-proc-weight的标量积作ؓ(f)IR倹{应用某Udebug mode所有这些数和矩阵与查询l果一hC出来。这些显C有助于改进rankpȝ?/p>
4.5.2反馈 rank函数有很多参数象type-weight和type-prox-weight。指明这些参数的正确值有炚w色艺术black art。ؓ(f)此,我们的搜索引擎有一个用户反馈机制。值得信Q的用户可以随意地评h(hun)q回的结果。保存反馈。然后,当修改rank函数ӞҎ(gu)以前搜烦(ch)?nbsp;rankQ我们可以看C改带来的的媄(jing)响。虽然不是十全十,但是它给Z(jin)一些思\Q当rank函数改变时对搜烦(ch)l果的媄(jing)响?/p>
5执行和结果搜索结果的质量是搜索引擎最重要的度量标准。完全用戯价体p超Z(jin)本文的论q范_(d)对于大多数搜索,我们的经验说明Google的搜索结果比那些主要的商业搜索引擎好。作Z个应用PageRankQ链接描q文字,盔R度的例子Q图4l出?jin)Google搜烦(ch)bill Clinton的结果。它说明?jin)Google的一些特炏V服务器对结果进行聚cR这对过滤结果集合相当有帮助。这个查询,相当一部分l果来自 whitehouse.gov域,q正是我们所需要的。现在大多数商业搜烦(ch)引擎不会(x)q回M来自whitehouse.gov的结果,q是相当不对的。注意第一个搜索结果没有标题。因为它不是被抓到的。Google是根据链接描q文字决定它是一个好的查询结果。同样地Q第五个l果是一个Email地址Q当然是不可能抓到的。也是链接描q文字的l果。所有这些结果质量都很高Q最后检查没有死链接。因为它们中的大部分PageRankD高。PageRank 癑ֈ比用U色U条表示。没有结果只含Bill没有Clinton或只含Clinton没有Bill。因出现的相q性非帔R要。当然搜索引擎质量的真实试包含q泛的用户学?fn)或l果分析Q此处篇q有限,误者自己去体验GoogleQ?a >http://google.stanford.edu/?nbsp;5.1存储需求除?jin)搜索质量,Google的设计可以随着Web规模的增大而有效地增大成本。一斚w有效地利用存储空间。表1列出?jin)一些统计数字的明细表和Google存储的需求。由于压~技术的应用知识库只需53GB的存储空间。是所有要存储数据的三分之一。按当今盘?sh)hQ知识库相对于有用的数据来说比较便宜。搜索引擎需要的所有数据的存储I间大约55GB。大多数查询h只需要短反向索引。文件烦(ch)引应用先q的~码和压~技术,一个高质量的搜索引擎可以运行在7GB的新PC?/p>
5.2pȝ执行搜烦(ch)引擎抓网和建立索引的效率非帔R要。Google的主要操作是抓网,索引Q排序。很难测试抓全部|页需要多时_(d)因ؓ(f)盘满了(jin)Q域名服务器崩溃Q或者其它问题导致系l停止。ȝ来说Q大U需?天时间下?6000000|页Q包括错误)(j)。然而,一旦系l运行顺利,速度非常快,下蝲最?1000000|页只需?3时Q^均每?000000|页Q每U?8.5个网c(din)烦(ch)引器和网l爬行机器h同步q行。烦(ch)引器比网l爬行机器h快。因为我们花费了(jin)大量旉优化索引器,使它不是瓉。这些优化包括批量更新文档烦(ch)引,本地盘数据l构的安排。烦(ch)引器每秒处理54个网c(din)排序器完全q行Q用4台机器,排序的整个过E大概需?4时?/p>
5.3搜烦(ch)执行改进搜烦(ch)执行不是我们研究的重炏V当前版本的Google可以??0U间回答查询h。时间大部分p在NFS盘I(y)O上(׃盘普遍比机器慢Q。进一步说QGoogle没有做Q何优化,例如查询~冲区,常用词汇子烦(ch)引,和其它常用的优化技术。我们們于通过分布式,gQYӞ和算法的改进来提高Google的速度。我们的目标是每U能处理几百个请求。表2有几个现在版本Google响应查询旉的例子。它们说明IO~冲区对再次搜烦(ch)速度的媄(jing)响?nbsp;6l论 Google设计成可伸羃的搜索引擎。主要目标是在快速发展的World Wide Web上提供高质量的搜索结果。Google应用?jin)一些技术改q搜索质量包括PageRankQ链接描q文字,盔R信息。进一步说QGoogle是一个收集网,建立索引Q执行搜索请求的完整的体pȝ构?/p>
6.1未来的工作大型Web搜烦(ch)引擎是个复杂的系l,q有很多事情要做。我们直接的目标是提高搜索效率,覆盖大约100000000个网c(din)一些简单的改进提高?sh)(jin)效率包括请求缓冲区Qy妙地分配盘I间Q子索引。另一个需要研I的领域是更新。我们必L一个y妙的法来决定哪些旧|页需要重新抓取,哪些新网需要被抓取。这个目标已l由实现?jin)。受需求驱动,用代理cache创徏搜烦(ch)数据库是一个有前途的研究领域。我们计划加一些简单的已经被商业搜索引擎支持的特征Q例如布?yu)(dng)算术符P否定Q填充。然而另外一些应用刚刚开始探索,例如相关反馈Q聚c(Google现在支持单的ZL名的聚类Q。我们还计划支持用户上下文(象用户地址Q,l果摘要。我们正在扩大链接结构和链接文本的应用。简单的实验证明Q通过增加用户主页的权重或书签QPageRank可以个性化。对于链接文本,我们正在试验用链接周围的文本加入到链接文本。Web搜烦(ch)引擎提供?jin)丰富的研究N。如此之多以至于我们不能在此一一列DQ因此在不久的将来,我们希望所做的工作不止本节提到的?/p>
6.2高质量搜索当?nbsp;Web搜烦(ch)引擎用户所面(f)的最大问题是搜烦(ch)l果的质量。结果常常是好笑的,q且出用户的眼界,他们常常灰心(j)丧气费?jin)宝늚旉。例如,一个最行的商业搜索引擎搜?#8220;Bill Clillton”的结果是the Bill Clinton Joke of the Day: April 14, 1997。Google的设计目标是随着Web的快速发展提供高质量的搜索结果,Ҏ(gu)扑ֈ信息。ؓ(f)此,Google大量应用文本信息包括链接结构和链接文本。Googleq用C(jin)盔R性和字号信息。评h索引擎是困难的,我们主观地发现Google的搜索质量比当今商业搜烦(ch)引擎高。通过PageRank分析链接l构?nbsp;Google能够评h(hun)|页的质量。用链接文本描述链接所指向的网|助于搜烦(ch)引擎q回相关的结果(某种E度上提高(sh)(jin)质量Q。最后,利用盔R性信息大大提高(sh)(jin)很多搜烦(ch)的相x(chng)?/p>
6.3可升U的体系l构除了(jin)搜烦(ch)质量QGoogle设计成可升的。空间和旉必须高效Q处理整个Web时固定的几个因素非常重要。实现GooglepȝQCPU、访存、内存容量、磁盘寻道时间、磁盘吞吐量、磁盘容量、网lIO都是瓉。在一些操作中Q已l改q的 Google克服?jin)一些瓶颈。Google的主要数据结构能够有效利用存储空间。进一步,|页爬行Q烦(ch)引,排序已经_建立大部分web索引Q共 24000000个网,用时不到一星期。我们希望能在一个月内徏?00000000|页的烦(ch)引?/p>
6.4研究工具 Google不仅是高质量的搜索引擎,它还是研I工兗Google搜集的数据已l用在许多其它论文中Q提交给学术?x)议和许多其它方式。最q的研究Q例如,提出?jin)Web查询的局限性,不需要网l就可以回答。这说明Google不仅是重要的研究工具Q而且必不可少Q应用广泛。我们希望Google是全世界研究者的资源Q带动搜索引擎技术的更新换代?nbsp;7致谢 Scott Hassan and Alan Steremberg评h(hun)?jin)Google的改q。他们的才智无可替代Q作者由衷地感谢他们。感谢Hector Garcia-Molina, Rajeev Motwani, Jeff Ullman, and Terry Winograd和全部WebBase开发组的支持和富有深刻见解的讨论。最后感谢IBMQIntelQSun和投资者的h支持Qؓ(f)我们提供讑֤。这里所描述的研I是Stanfordl合数字图书馆计划的一部分Q由国家U学自然基金支持Q合作协议号IRI-9411306。DARPA QNASAQInterva研究QStanford数字图书馆计划的工业合作伙伴也ؓ(f)q项合作协议提供?jin)资金。参考文?nbsp;?
Google的设计目标是可升U到10亿网c(din)我们的盘和机器大概能处理q么多网c(din)系l各个部分耗费的L间是q行的和U性的。包括网늈行机器hQ烦(ch)引器和排序器。扩展后我们认ؓ(f)大多数数据结构运行良好。然?0亿网|q所有常用操作系l的极限Q我们目前运行在Solaris和Linux上)(j)。包括主存地址Q开放文件描q符的数量,|络socket和带宽,以及(qing)其它因素。我们认为当|页数量大大过10亿网|Q会(x)大大增加pȝ复杂性?nbsp;9.2集中式烦(ch)引体pȝ可升U性随着计算机性能的提高,量文本索引的成本比较公q뀂当然带宽需求高的其它应用如视频Q越来越普遍。但是,与多媒体例如视频相比Q文本品的成本低,因此文本仍然普遍?
? Googlepȝ的工作流E图
(注:(x)原图来自Sergey Brin and Lawrence Page, The Anatomy of a Large-Scale Hypertextual. Web Search Engine, 1998.http://www-db.stanford.edu/%7Ebackrub/Google.html)
①Google使用高速的分布式爬行器(Crawler)pȝ中的漫游遍历?Googlebot)定时地遍历网,遍历到的网送到存储服务?Store Server)中?/p>
?nbsp;存储服务器用zlib格式压羃软g这些网进行无损压~处理后存入数据库Repository中。Repository获得?jin)每个网늚完全Html 代码后,对其压羃后的|页?qing)URLq行分析Q记录下|页长度、URL、URL长度和网内容,q赋予每个网一个文档号(docID)Q以便当pȝ出现故障的时候,可以?qing)时完整地进行网늚数据恢复?/p>
③烦(ch)引器(Indexer)从Repository中读取数据,以后做以下四步工作:(x)
?a) 读取的数据解压~后q行分析Q它?yu)网中每个有意义的词进行统计后Q{化ؓ(f)关键?wordID)的若q烦(ch)引项(Hits)Q生成烦(ch)引项列表Q该列表包括关键词、关键词的位|、关键词的大和大小写状态等。烦(ch)引项列表被存入到数据?Barrels)中,q生成以文档?docID)部分排序的顺排档索引?/p>
索引Ҏ(gu)据其重要E度分ؓ(f)两种Q当索引中的关键词出现在URL、标题、锚文本(Anchor Text)和标{中Ӟ表示该烦(ch)引项比较重要Q称为特D烦(ch)引项(Fancy Hits)Q其余情况则UCؓ(f)普通烦(ch)引项(Plain Hits)。在pȝ中每个Hit用两个字?byte)存储l构表示Q特D烦(ch)引项??bit)表示大小写,用二q制代码111(??表示是特D烦(ch)引项Q其?2位有4位表C特D烦(ch)引项的类?即hit是出现在URL、标题、链接结点还是标{中)Q剩?位表Chit在网中的具体位|;普通烦(ch)引项是用1位表C大写Q?位表C字体大,其余12位表C在|页中的具体位置?/p>
排档烦(ch)引和Hit的存储结构如?所C?/p>
? 排档烦(ch)引和Hit的存储结?/p>
值得注意的是Q当Ҏ(gu)索引Ҏ(gu)自Anchor TextӞҎ(gu)索引用来表CZ|的信息Q?位)(j)分Z部分Q?位表CAnchor Text出现的具体位|,?位则用来与表CAnchor Text所链接|页的docID相连接,q个docID是由URL Resolverl过转化存入排档烦(ch)引的?/p>
(b)索引器除?jin)对|页中有意义的词q行分析外,q分析网늚所有超文本链接Q将其Anchor Text、URL指向{关键信息存入到Anchor文档库中?/p>
(c)索引器生成一个烦(ch)引词?Lexicon)Q它包括两个部分Q关键词的列表和指针列表Q用于倒排档文档相q接(如图3所C??/p>
(d) 索引器还分析过的网늼排成一个与Repository相连接的文档索引(Document Index)Qƈ记录下网늚URL和标题,以便可以准确查找出在Repository中存储的原网内宏V而且把没有分析的|页传给URL ServerQ以便在下一ơ工作流E中q行索引分析?/p>
⑤URL分析器(URL ResolverQ读取Anchor文档中的信息Q然后做⑥中的工作?/p>
?a) 其锚文?Anchor Text)所指向的URL转换成网늚docIDQ?b)该docID与原|页的docID形成“链接?#8221;Q存入Link数据库中Q?c)?nbsp;Anchor Text指向的网늚docID与顺排档Ҏ(gu)索引Anchor Hits相连接?/p>
⑦数据库Link记录?jin)网늚链接关系Q用来计网늚PageRank倹{?/p>
⑧文档烦(ch)?Document Index)把没有进行烦(ch)引分析的|页传递给URL ServerQURL Server则向Crawler提供待遍历的URLQ这Pq些未被索引的网在下一ơ工作流E中被索引分析?/p>
⑨排序器QSorterQ对数据?Barrels)的顺排档索引重新q行排序Q生成以关键?wordID)为烦(ch)引的倒排档烦(ch)引。倒排档烦(ch)引结构如?所C:(x)
? 倒排档烦(ch)引结?/p>
?nbsp;生成的倒排档烦(ch)引与先前q(ch)引器产生的烦(ch)引词?Lexicon)相连接生一个新的烦(ch)引词表供搜烦(ch)?Searcher)使用。搜索器的功能是q|务器实现的,Ҏ(gu)C生的索引词表l合上述的文档烦(ch)?Document Index)和Link数据库计的|页PageRank值来匚w(g)索?/p>
在执行检索时QGoogle通常遵@以下步骤Q以下所指的是单个检索词的情况)(j)Q?/p>
(1)检索词转化成相应的wordIDQ?/p>
(2)利用LexiconQ检索出包含该wordID的网늚docIDQ?/p>
(3)Ҏ(gu)与Lexicon相连的倒排档烦(ch)引,分析各网中的相关烦(ch)引项的情况,计算各网和(g)索词的匹配程度,必要时调用顺排档索引Q?/p>
(4)Ҏ(gu)各网늚匚wE度Q结合根据Link产生的相应网늚PageRank情况Q对(g)索结果进行排序;
(5)调用Document Index中的docID?qing)其相应的URLQ将排序l果生成(g)索结果的最l列表,提供l检索用戗?/p>
用户(g)索包含多个检索词的情况与以上单个(g)索词的情늱|(x)先做单个(g)索词的检索,然后Ҏ(gu)?hu)(g)索式中检索符L(fng)要求q行必要的布?yu)(dng)操作或其他操作?/p>
who am i ?/span>whoami有何区别Q?/span>
首先要说?/span>uid?/span>euidQ?/span>effective user idQ的区别?/span>uid是?/span>login的时候用的idQ?/span>euid则是你当前的有效id。因为登录后我们可以使用su切换用户w䆾Q所?/span>uid?/span>euid可能是不同的Q程序在q行的时候一般看的都?/span>euidQ当然也有特出的Q?/span>who am i是一个?/span>
举个例子Q用L(fng)ABC登陆Q?/span>su变成rootQ用who am i看到的是ABCQ?/span>whoami命o(h)看到的是root?/span>
login: u1
Password:
$ su
Password:
# /usr/ucb/whoami
root
# who am i
u