Month: 四月 2018

Python time 模块

时间戳,struct_time 可以被认为是一个表示时间的整数序列,一共9项对应于 C 中对应的数据结构,注意其中不包含时区信息

函数 | 说明
—-|—-
time.time | 获取当前时间戳,即 GMT 的 epoch 秒数
time.clock()|获取进程时间,即从进程开始执行的时间
time.sleep() |停止当前线程若干秒
time.strftime|产生可读时间字符串
time.strptime |parse time
time.strftime()/time.mktime()/time.asctime() | 均接受 struct_time 作为参数
time.gmtime()/time.localtime()/time.strptime() | 返回的是对应时间的struct_time

# time.time vs time.clock

time.clock measures the cpu time spent, if you code does heavy IO or GPU computing, the result is WRONG, time.time is not precise but works all the time~

微信开发笔记

可以使用微信的测试号学习如何开发
http://mp.weixin.qq.com/debug/cgi-bin/sandbox?t=sandbox/login

公众号对于消息的处理相当于使用了微信的服务器做转发代理, 发送到公众号的后端服务器, 而一旦进入网页就相当于直接同服务器通信了. 微信会使用 POST 发送消息到服务器

对于消息的处理有一个签名的过程, 这样后端服务器可以判断消息是否来自微信, 从而防止 API 被恶意滥用盗用.

所以这些繁杂的事情不如交个框架去处理

APPID/APPSECRET 相当于公众号的账号和密码, 通过这两个组合获取一个 access_token 用于平时访问, access_token 是有有效期的, 即使明文传送被泄露了也问题不大

问题是, 服务器需要记得去刷新这个 token, 所以这些东西应该交给框架最好了

微信开放了 JS SDK 可以使用图片语音地图等一系列的应用, 不错

常用的一些 meta 标签

1.  
2.  
3.  
4.  

iOS中浏览器直接访问站点时,navigator.standalone为false,从 主屏启动webapp 时,navigator.standalone为true
移动版本webkit 为 input元素提供了autocapitalize属性,通过指定autocapitalize=”off”来关闭键盘默认首字母大写
开发者指定 的 target属性就失效了,但是可以通过指定当前元素的-webkit-touch-callout样式属性为none来禁止iOS弹出这些按钮

同样为一个img标签指定-webkit-touch-callout为none也会禁止设备弹出列表按钮,这样用户就无法保存\复制你的图片了
指定文字标签的-webkit-user-select属性为none便可以禁止iOS用户选中文字

django dump to csv

“`
import csv
from django.db.models.loading import get_model

def dump(qs, outfile_path):
“””
Takes in a Django queryset and spits out a CSV file.

Usage::

>> from utils import dump2csv
>> from dummy_app.models import *
>> qs = DummyModel.objects.all()
>> dump2csv.dump(qs, ‘./data/dump.csv’)

Based on a snippet by zbyte64::

http://www.djangosnippets.org/snippets/790/
“””
model = qs.model
writer = csv.writer(open(outfile_path, ‘w’))

headers = []
for field in model._meta.fields:
headers.append(field.name)
writer.writerow(headers)

for obj in qs:
row = []
for field in headers:
val = getattr(obj, field)
if callable(val):
val = val()
if type(val) == unicode:
val = val.encode(“utf-8”)
row.append(val)
writer.writerow(row)
“`

CSS 布局基础知识

# 布局

网页的布局是面向文档流的,也就是每个元素默认都是从左到右,从上到下依次排列的。当然就像文章一样,有些元素比如标题默认就会另起一行,并且单独占据这一行。

所有的元素都分为三类:inline、inline-block、和 block。

其中 block 元素占据了一行的位置,即使他们的宽度不够一行,并且他们有自己的宽度和高度,比如 h1 元素。

inline-block 结合了 inline 和 block 元素的特性,首先他布局是 inline 的,也就是不会另起一行,但是又可以设定单独的高度和宽度。

`display: none` 将会完全不渲染该元素, `visibility: hidden` 会渲染这个元素,只是在该显式的地方留下空白

## 使用 inline-box 的布局

![](https://ws1.sinaimg.cn/large/006tKfTcly1fquqqp791hj30kr0i1gpe.jpg)

# 定位

CSS 中元素的定位有如下几种,可以使用 position 指定

方法 | 说明
—-|—-
static|默认的定位方法,指的是在文档中的位置是静态的
relative|relative to its static positions, if set(top, left, bottom, right)
fixed|fixed to the viewport, if set(top, left, bottom, right)
absolute|behaves like fixed, but relative to nearest non-static ancestor
float|floated element will become a block element, but it will not occupy one row

使用 float 的布局

![](https://ws3.sinaimg.cn/large/006tKfTcly1fsktnrsi5dj30kc0hp781.jpg)

### 后续元素没有占据指定空间

元素浮动之后,它后面的元素就会去占据它的位置,然而我们往往并不想影响到后面的元素,所以应该指定它后面的元素清除浮动。

not stretching parent element
floating elements will also not stretching the element containing it, to fix that, add overflow: auto to the parent element

# 盒模型

## 讨厌的 content-box 模型

width set width of the content, and

* padding will push out the border…
* background-color only set for content area
* entire width is for border

![](https://ws3.sinaimg.cn/large/006tKfTcly1fqurrspk7ej30ah09gq39.jpg)

## 符合直觉的 border-box 模型

as shown by the picture, border-box width sets the entire width, contains border + padding + content

如下图所示,border-box 模型设定的快读包含了 **border + padding + content**

![](https://ws4.sinaimg.cn/large/006tKfTcly1fqurs7z1chj30ge094wgg.jpg)

# responsive design

query device width

“`
@media screen and (mid/max-width: xxxpx)
“`

set viewport

“`

“`

# 记录 CSS 的一个坑

## 在 td 元素上无法使用 width

可以通过指定: table-layout: fixed 解决

## centering

“`
margin: 0 auto;
“`

## css columns

“`
column-count: x;
column-gap: xpx;
“`

## 通过 js 获得最终 CSS 属性

https://developer.mozilla.org/zh-CN/docs/Web/API/Window/getComputedStyle

# reference

[1] http://learnlayout.com

Python coroutine 以及和 Goroutine 的对比

# Python 中的 coroutine

Python 3.5 中终于引入了 `async` 和 `await` 关键字,算是在语言层次上支持了 coroutine。

## coroutine 基础

coroutine 又被称为用户级线程,也就是可以在一个系统线程中模拟多个线程构成的并发操作,对于有 GIL 的 Python 来说,反正线程也是费了,不失为多了一种选择,使用 asyncio 来爬取网页可以这样写:

首先,`pip install pulsar lxml`。pulsar 是一个异步版的 http 库。

“`
import asyncio
from pulsar.apps import http

client = http.HttpClient()

async def fetch(url):
r = await client.get(url)
return r.content.decode(‘utf-8’)

async def main():
page = await fetch(“http://toutiao.com”)
print(page)

if __name__ == “__main__”:
loop = asyncio.get_event_loop()
loop.run_until_complete(main())
“`

注意其中我们使用 `async def` 定义了一个 `coroutine function`,并且在其中调用(await)了另一个 coroutine function。在 Python 中只有在使用 async def 定义的函数上下文中才能使用 await。

如果我们需要下载多个网址呢?

## coroutine 并发

“`
import asyncio
import lxml.html
from pulsar.apps import http

client = http.HttpClient()

async def fetch(url):
r = await client.get(url)
return r.content.decode(‘utf-8’)

def get_title(page):
doc = lxml.html.fromstring(page)
return doc.xpath(“//title/text()”)[0]

async def main():
urls = [‘https://www.toutiao.com’, ‘https://www.douban.com’, ‘https://www.sina.com.cn’]
futures = []
for url in urls:
future = asyncio.ensure_future(fetch(url))
futures.append(future)
pages = await asyncio.gather(*futures)
for url, page in zip(urls, pages):
print(url, get_title(page))

if __name__ == “__main__”:
loop = asyncio.get_event_loop()
loop.run_until_complete(main())
“`

在上面的例子中,我们在 for 循环使用 `asyncio.ensure_future` 创建了三个 Future 对象。Future 对象指的是可以在未来(future)的某个时间获得结果的一个对象。然后我们使用 `asyncio.gather` 来同时 `await` 了这三个 Future。在我们 await 的时候,可以认为这三个 future 是”并发”执行的。如果你了解 JavaScript 的话,可以看出来 Future 就相当于 JS 中的 Promise 对象。注意这里的并发指的是 IO 上可以并发加速,如果从 CPU 上考虑的话,因为都是在一个线程中,也就没有性能提升的,所以说协程特别适合于 IO 密集的应用。

不过,对于初学者来说,经常会直接 await 每一个协程,导致实际上没有任何并发。比如下面的代码就是错误的:

“`
async def main():
urls = [‘https://www.toutiao.com’, ‘https://www.douban.com’, ‘https://www.sina.com.cn’]
for url in urls:
page = await fetch(url)
print(page)
“`

上面这种错误有人称作 async/await hell,可以参考这篇文章:[如何避免async/await地狱](https://www.zcfy.cc/article/how-to-escape-async-await-hell)

## 协程的调度

我们知道线程是内核进行抢占式的调度的,这样就确保了每个线程都有执行的机会。而 coroutine 运行在同一个线程中,由语言的运行时中的 EventLoop(事件循环)来进行调度。和大多数语言一样,在 Python 中,协程的调度是非抢占式的,也就是说一个协程必须主动让出执行机会,其他协程才有机会运行。让出执行的关键字就是 `await`。也就是说一个协程如果阻塞了,持续不让出 CPU,那么整个线程就卡住了,没有任何并发。比如下面的例子:

“`
% cat time_sleep.py

import asyncio
import time

async def do_work():
time.sleep(1)

async def main():
for _ in range(3)s:
future = asyncio.ensure_future(do_work())
futures.append(future)
await asyncio.gather(*futures)

if __name__ == “__main__”:
loop = asyncio.get_event_loop()
loop.run_until_complete(main())

% time python time_sleep.py
python no_concurrent.py 0.13s user 0.03s system 5% cpu 3.173 total
“`

虽然我们使用了 asyncio.gather 来并发执行,但是依然可以看到执行时间是 3.173s。因为 time.sleep 是一个阻塞性的操作,只能顺序执行,所以整个运行时间就是 3s。如果要修复这个程序可以改成这样:

“`
% cat aio_sleep.py


async def do_work():
await asyncio.sleep(1)

% time python aio_sleep.py
python aio_sleep.py 0.13s user 0.03s system 13% cpu 1.166 total
“`

使用 asyncio.sleep 替换了阻塞的 time.sleep,执行时间是 1.166s。这样暴露两个问题:

1. Python 整个异步编程生态的问题,之前标准库和各种第三方库的阻塞性函数都不能用了,requests 不能用了,redis.py 不能用了,甚至 open 函数都不能用了。所以 Python 的最大问题不是不好用,而是生态环境不好。
2. 一旦开始采用 async 函数,那么你整个程序都必须是 async 的,不然总会有阻塞的地方,也就是说 async 具有传染性。

这两点结合在一起导致想要写一个完全异步的 Python 程序还是有一定挑战的。

# Goroutine

最近闲暇时间看了看 Go 语言相关的东西。发现 Go 原生的并发模型非常好用。Go 中的 goroutine 类似于其他语言中的 corouine,最重要的是 goroutine 是 go 与生俱来的特性,所以几乎所有库都是可以直接用的,避免了 Python 中需要把所有库重写一遍的问题。

用 Go 来重写一下并发下载:

“`
package main

import (
“fmt”
“io/ioutil”
“log”
“net/http”
)

func fetch(url string, bodies chan []byte) {
resp, err := http.Get(url)
if err != nil {
log.Fatalf(“error %s”, err)
}
defer resp.Body.Close()
body, _ := ioutil.ReadAll(resp.Body)
bodies <- body } func main() { urls := []string{ "https://www.toutiao.com", "https://www.douban.com", "https://www.sina.com.cn", } bodies := make(chan []byte) for _, url := range urls { go fetch(url, bodies) } for i := 0; i < len(urls); i++ { fmt.Println(string(<-bodies)[:100]) fmt.Println("--------------------") } close(bodies) } ``` ## Goroutine 的调度 Goroutine 中不需要显式使用 await 交出控制权,但是 Go 也不会严格按照时间片去调度 goroutine,而是会在可能阻塞的地方插入调度。Goroutine 的调度可以看做是半抢占式的。 ## 和系统线程之间的映射关系 Python 中的协程是严格的 1:N 关系,也就是一个线程对应了多个协程。而 Go 中是 M:N 的关系,也就是 N 个协程会映射分配到 M 个线程上,这样带来了两点好处: 1. CPU 密集的应用使用 goroutine 也会获得加速; 2. 即使有少量阻塞的操作,也只会阻塞某个 worker 线程,而不会把整个程序阻塞。 总之,在高并发方面,Go 语言的确有不少优势。

函数式编程中的 Pattern Matching (模式匹配)

以 haskell 为例,简单来说,pattern 就像是数学中的分段函数。通过使用 pattern matching,就可以对不同的参数定义不同的函数体。当调用函数的时候,可以通过对比实参和形参的模式就可以选择正确的函数体。

比较一下

和对应的 haskell 代码:

“`
fib 0 = 1
fib 1 = 1
fib n | n >= 2
= fib (n-1) + fib (n-2)
“`

注意在分段函数中 “n ≥ 2” 这个条件在 haskell 中变成了一个 guard。但是另外两个条件就是简单的 pattern。Pattern 就是可以测试值和结构的条件,比如 `x:xs`, `(x, y, z)`, 或者 `x`。在一个分段函数定义中,基于 `=` 或者 `∈` 的条件会变成简单的 pattern,而其他的更广义的条件会变成 guard。如果用 guard 来重写一下上面的函数:

“`
fib n | n == 0 = 1
| n == 1 = 1
| n >= 2 = fib (n-1) + fib (n-2)
“`

# 和 switch/ifelse 语句的区别

1. 编译器可以替你检查你是否覆盖了所有情形
2. 可以直接把 pattern match 作为一个赋值语句
3. 如果你有一个不同类型复合的变量,每一个匹配结果都会有不同的类型
4. 使用 pattern matching 在某些情况下要简洁得多[4]

# REF

1. https://stackoverflow.com/questions/2225774/haskell-pattern-matching-what-is-it
2. https://www.zhihu.com/question/22344888
3. https://stackoverflow.com/questions/199918/explaining-pattern-matching-vs-switch
4. https://hongjiang.info/scala-pattern-matching-1/

[译] 用 Python 编写一个模板引擎

一直对模板引擎的实现很好奇,正好看到了这篇文章,翻译一下,供大家学习、参考。

我们编写一个最简单的模板引擎,并且探索一下它的底层实现。如果你想直接看代码的话,GitHub 是你的好朋友

语言设计

这里设计的模板语言非常基础。使用两种标签,变量和块。

<!-- 变量使用 `{{` 和 `}}` 作为标识-->
<div>{{my_var}}</div>

<!-- 块使用 `{%` 和 `%}` 作为标识-->
{% each items %}
    <div>{{it}}</div>
{% end %}

大多数的块需要使用关闭标签,关闭标签使用{% end %}表示。

这个模板引擎能够处理基本的循环和条件语句,而且也支持在块中使用 callable。在我看来,能够在模板中调用任意的 Python 函数非常方便。

循环

使用循环可以遍历集合或者 iterable。

{% each people %}
    <div>{{it.name}}</div>
{% end %}

{% each [1, 2, 3] %}
    <div>{{it}}</div>
{% end %}

{% each records %}
    <div>{{..name}}</div>
{% end %}

在上面的例子里面,people 是一个集合,it 指向了当前迭代的元素。使用点分隔的路径会被解析成字典属性。使用 .. 可以访问外部上下文中的对象。

条件语句

条件语句不需要多解释。这个语言支持 if 和 else 结构,而且支持 ==, <=, >=, !=, is, <, > 这几个操作符。

{% if num > 5 %}
    <div>more than 5</div>
{% else %}
    <div>less than or equal to 5</div>
{% end %}

调用块

Callable 可以通过模板上下文传递,并且使用普通位置参数或者具名参数调用。调用块不需要使用 end 关闭。

<!-- 使用普通参数... -->
<div class='date'>{% call prettify date_created %}</div>
<!-- ...使用具名参数 -->
<div>{% call log 'here' verbosity='debug' %}</div>

原理

在探索引擎是如何编译和渲染模板之前,我们需要了解下在内存中如何表示一个编译好的模板。

编译器使用抽象语法树(Abstract Syntax Tree, AST)来表示计算机程序。AST 是对源代码进行词法分析(lexical analysis)的结果。AST 相对源代码来说有很多好处,比如说它不包含任何无关紧要的文本元素,比如说分隔符这种。而且,树中的节点可以使用属性来添加更多的功能,而不需要改动代码。

我们会解析并分析模板来构造这样一棵树,并用它来表示编译后的模板。渲染的时候,遍历这棵树,传给它对应的上下文,然后输出 HTML。

模板切词(tokenize)

解析的第一步是把内容分隔成不同的片段。每个片段可以是任意的 HTML 或者是一个标签。这里使用正则表达式和 split() 函数分隔文本。

VAR_TOKEN_START = '{{'
VAR_TOKEN_END = '}}'
BLOCK_TOKEN_START = '{%'
BLOCK_TOKEN_END = '%}'
TOK_REGEX = re.compile(r"(%s.*?%s|%s.*?%s)" % (
    VAR_TOKEN_START,
    VAR_TOKEN_END,
    BLOCK_TOKEN_START,
    BLOCK_TOKEN_END
))

让我们来看一下 TOK_REGEX。可以看到这个正则的意思是 TOK_REGEX 要么是一个变量标签,要么是一个块标签,这是为了让变量标签和块标签都能够分隔文本。表达式的最外层是一个括号,用来捕获匹配到的文本。其中的 ? 表示非贪婪的匹配。我们想让我们的正则表达式是惰性的,并且在第一次匹配到的时候停下来。

下面这个例子实际展示了一下上面的正则:

>>> TOK_REGEX.split('{% each vars %}<i>{{it}}</i>{% endeach %}')
['{% each vars %}', '<i>', '{{it}}', '</i>', '{% endeach %}']

把每个片段封装成 Fragment 对象。这个对象包含了片段的类型,并且可以作为编译函数的参数。片段有以下四种类型:

VAR_FRAGMENT = 0
OPEN_BLOCK_FRAGMENT = 1
CLOSE_BLOCK_FRAGMENT = 2
TEXT_FRAGMENT = 3

构建 AST

一旦我们做好了分词,下一步就可以遍历每个片段并构建语法树了。我们使用 Node 类来作为树的节点的基类,然后创建对每一种节点类型创建子类。每个子类都必须提供 process_fragmentrender 方法。process_fragment 用来进一步解析片段的内容并且把需要的属性存到 Node 对象上。render 方法负责使用提供的上下文转换对应的节点内容到 HTML。

子类也可以实现 enter_scopeexit_scope 钩子方法,这两个方法不是必须的。在编译器编译期间,会调用这两个钩子函数,他们应该负责进一步的初始化和清理工作。当一个 Node 创建了一个新的作用域(scope)的时候,会调用 enter_scope,当退出作用域时,会调用 exit_scope。关于作用域,下面会讲到。

Node 基类如下:

class _Node(object):
    def __init__(self, fragment=None):
        self.children = []
        self.creates_scope = False
        self.process_fragment(fragment)

    def process_fragment(self, fragment):
        pass

    def enter_scope(self):
        pass

    def render(self, context):
        pass

    def exit_scope(self):
        pass

    def render_children(self, context, children=None):
        if children is None:
            children = self.children
        def render_child(child):
            child_html = child.render(context)
            return '' if not child_html else str(child_html)
        return ''.join(map(render_child, children))

下面是变量节点的定义:

class _Variable(_Node):
    def process_fragment(self, fragment):
        self.name = fragment

    def render(self, context):
        return resolve_in_context(self.name, context)

为了确定 Node 的类型(并且进一步初始化正确的类),需要查看片段的类型和文本。文本和变量片段直接翻译成文本节点和变量节点。块片段需要一些额外的处理 —— 他们的类型是使用块命令来确定的。比如说:

{% each items %}

是一个 each 类型的块节点,因为块命令是 each。

一个节点也可以创建作用域。在编译时,我们记录当前的作用域,并且把新的节点作为作为当前作用域的子节点。一旦遇到一个正确的关闭标签,关闭当前作用域,并且从作用域栈中把当前作用域 pop 出来,使用栈顶作为新的作用域。

def compile(self):
    root = _Root()
    scope_stack = [root]
    for fragment in self.each_fragment():
        if not scope_stack:
            raise TemplateError('nesting issues')
        parent_scope = scope_stack[-1]
        if fragment.type == CLOSE_BLOCK_FRAGMENT:
            parent_scope.exit_scope()
            scope_stack.pop()
            continue
        new_node = self.create_node(fragment)
        if new_node:
            parent_scope.children.append(new_node)
            if new_node.creates_scope:
                scope_stack.append(new_node)
                new_node.enter_scope()
    return root

渲染

管线的最后一步就是把 AST 渲染成 HTML 了。这一步访问 AST 中的所有节点并且使用传递给模板的 context 参数调用 render 方法。在渲染过程中,render 不断地解析上下文变量的值。可以使用使用 ast.literal_eval 函数,它可以安全的执行包含了 Python 代码的字符串。

def eval_expression(expr):
    try:
        return 'literal', ast.literal_eval(expr)
    except ValueError, SyntaxError:
        return 'name', expr

如果我们使用上下文变量,而不是字面量的话,需要在上下文中搜索来找到它的值。在这里需要处理包含点的变量名以及使用两个点访问外部上下文的变量。下面是 resolve 函数,也是整个难题的最后一部分了~

def resolve(name, context):
    if name.startswith('..'):
        context = context.get('..', {})
        name = name[2:]
    try:
        for tok in name.split('.'):
            context = context[tok]
        return context
    except KeyError:
        raise TemplateContextError(name)

结论

我希望这个小小的学术联系能够让你对模板引擎是怎样工作的有一点初步的感觉。这个生产级别的代码还差得很远,但是也可以作为你开发更好的工具的基础。

你可以在 GitHub 上找到完整的代码,你也可以进一步在 Hacker News 上讨论。

感谢 Nassos Hadjipapas, Alex Loizou, Panagiotis Papageorgiou and Gearoid O’Rourke 审阅本文。

Linux 上的 DNS 缓存

Linux 内核中没有 DNS 缓存

Firefox 内置了 DNS 缓存

`nscd` 可以提供本地的 DNS 缓存,好多机器开了,但是据说这个服务有很多问题。

Python 使用了 `getaddrinfo` 函数,会使用系统的 DNS 缓存

像 `nslookup` 和是dig这样的工具会 bypass 掉 DNS 缓存。

另外 Go 语言好像也不会使用本机的 DNS 缓存,即使开了

https://wiki.archlinux.org/index.php/dnsmasq 可以用来做本地缓存

还可以使用systemd提供的resolved

1 https://stackoverflow.com/questions/11020027/dns-caching-in-linux

读《The Anatomy of a large-scale hypertextual Web search engine》

Google 在1997年的论文[1], 到现在(2017)的话, 已经有二十年的历史了, 然而对于编写一个小的搜索引擎, 依然有好多具有指导意义的地方.

The Anatomy of a large-scale hypertextual Web search engine 这篇论文应该是一片总结性质的论文, 而且论文并没有多少的关于数据结构等的实现细节. 只是大体描绘了一下架构.

# Google的算法

首先, Google大量使用了在超文本也就是网页中存在的结构, 也就是锚文本和链接. 还有就是如何有效的处理在网页上, 所有人都可以任意发布任何文字的问题, Google在这片文章里给的解决方案是PageRank.

在20年前, 主要问题是, 网页已经开始快速增长, 然而当时的所有搜索引擎给出的结果只是搜索结果的数量也增长了, 却没能把最相关的结果放在首页. 因为人们并不会因为给出结果多而去多看几页, 所以这样的结果是不可取的. 在设计Google的过程中, Google还考虑了随着web规模的增长, 会对现有的体系造成的影响以及如何应对.

Google 还表达了对当时的搜索引擎都是商业化的, 因而一些诸如用户查询之类的结果无法共学术应用的情况表达了不满. (呵呵, Google这不是打自己的脸么)

对于 PageRank 算法, 提到了简单的公式:

![](https://ws1.sinaimg.cn/large/006tKfTcly1fqazehy4zdj30im02mmxd.jpg)

其中Tx表示的是指向A页面的所有页面, C表示的是一个页面上所有的外链. 对于这个公式的解释是这样的. 假设有一个随机的浏览者, 他不断的点击网页中的链接, 从不点后退, 直到他感到烦了, 然后在随机的拿一个网页开始点击. 其中d就表示了这个人会感到烦了的概率. 这样造成的结果就是如果一个网页有很多的的外链指向他的话, 他就有很大的机会获得比较高的PR, 或者如果一个很权威的站点指向的他的话, 也有很大机会获得比较高的PR.

对于锚文本, 大多数网站都是把他和所在的页联系起来, Google还把锚文本以及PR值和它指向的页面联系起来.

# Google的架构

其实这部分才是我最感兴趣的地方. 之所以今天会抽出时间来阅读这篇论文, 主要就是想写个小爬虫, 然后发现写来写去, 太不优雅了, 才想起翻出Google的论文读一读.

## Google整体架构

![](https://ws2.sinaimg.cn/large/006tKfTcly1fqazes7038j30gn0iitbl.jpg)

Google的架构非常的模块化, 基本上可以看到整个图, 就知道每个模块是负责做什么的. 大概分成了几个部分: 爬虫(下载器), indexer, barrel, sorter, 和(searcher)前端服务.

其中

1. 爬虫负责下载网页, 其中每一个url都会有一个唯一的docID.
2. indexer负责解析网页中的单词, 生成hit记录, 并产生前向索引. 然后抽出所有的链接.
3. URLResolver会把indexer生成的锚文本读取并放到锚文本和链接放到索引中, 然后生成一个docID -> docID 的映射数据库. 这个数据库用来计算PageRank.
4. sorter根据indexer生成的正向索引, 根据wordID建立反向索引. 为了节省内存, 这块是inplace做的. 并且产生了wordID的列表和偏移
5. searcher负责接收用户的请求, 然后使用DumpLexicon产生的lexicon和倒排和PageRank一起做出响应.

## 用到的数据结构

由于一个磁盘寻道就会花费 10ms 的时间(1997), 所以Google几乎所有的数据结构都是存在大文件中的. 他们实现了基于固定宽度ISAM, 按照docID排序的document索引, 索引中包含了当前文件状态, 指向repository的指针, 文件的校验和, 不同的统计信息等. 变长信息, 比如标题和url存在另一个文件中. (YN: SSD对这个问题有什么影响呢)

hitlist指的是某个单词在谋篇文档中出现的位置, 字体, 大小写等信息. Google手写了一个htilist的编码模式, 对于每个hit花费2byte

barrel中存放按照docID排序存放document

## 模块

### 爬虫

爬虫又分为了两个部分, URLServer 负责分发URL给Crawler. Crawler 是分布式的, 有多个实例, 负责下载网页. 每获得一个URL的时候, 都会生成一个docID. Google使用了一个URLServer 和 3个Crawler. 每一个Crawler大概会维持300个连接, 可以达到每秒钟爬取100个网页. 并且使用了异步IO来管理事件.

#### DNS

Google指出爬虫的一个瓶颈在于每个请求都需要去请求DNS. 所以他们在每一个Crawler上都设置了DNS 缓存.

YN: 对于HTTP 1.1来说, 默认连接都是keep-alive的, 对于URLServer分发连接应该应该同一个域名尽量分发到同一个crawler上, 这样可以尽量避免建立连接的开销.

indexer会把下载到的网页分解成hit记录,每一个hit记录了单词, 在文档中的位置, 和大概的字体大小和是否是大写等因素. indexer还会把所有的链接都抽取出来, 并存到一个anchor文件中. 这个文件保存了链接的指向和锚文本等元素.

## rank

Google并没有手工为每一个因素指定多少权重, 而是设计了一套反馈系统来帮助我们调节参数.

# 结果评估

Google认为他们的搜索能够产生最好的结果的原因是因为使用了PageRank. Google在9天内下载了2600万的网页, indexer的处理能力在 54qps, 其中

# 拓展

query cacheing, smart disk allocation, subindices

链接合适应该重新抓取, 何时应该抓取新连接

使用了NFS, 性能有问题

## YN:

如何判定为一个hub也 -> 识别列表
hub页的链接产出率 -> 根据一个列表页是否产生新连接来动态的调整hub页的抓取频率

[1] http://infolab.stanford.edu/~backrub/google.html

爬虫 IP 封禁与反封禁

反爬虫的核心在于区分开正常用户访问和恶意爬虫用户。来源 IP 是访问很重要的一个特征,我们可以从来源 IP 的角度来做出不少反爬虫策略。

* 是否是代理IP
* 是否是民用IP
* IP 地理信息

一般来说,大规模的爬虫我们都会放到服务器上去跑,搭建代理集群也会在服务器上,而正常用户的IP地址则来自家用IP范围内。这就给反爬虫的一方提供了便利,对于来自数据中心的请求可以直接限制访问甚至直接屏蔽掉,而对于家用的IP地址则宽容一些。

下面我们来看几个实例

# 直接爬取网站

一般正常用户的页面访问量很小,如果发现某个 IP 的访问量特别大,那么肯定是爬虫,直接封禁即可,或者每次都需要输入验证码访问。

IP 被封禁后一般不会被解封,或者需要很长时间,这时候只有两种思路,要么降低频率,更改自己的行为特征,避免被封,要么更换 IP。一般来说,不管怎样更改自己的行为,访问量还是很难降下来的,这时候只能换一个 IP 继续爬。

# 使用代理网站提供的代理IP

一些黑客会使用端口扫描器扫描互联网上的开放代理,然后免费或者付费提供给其他用户使用,比如下面这些网站:

![免费代理](https://ws2.sinaimg.cn/large/006tNbRwly1fu6vtfrvgvj30zy0pgn3y.jpg)

但是这些网站的代理中能直接使用的可能不到10%,而且失效时间很短。所以要使用这些代理 IP,需要首先爬取这些网站,然后随取随用。

# 利用 ADSL 服务器更换 IP

网上有一些小的厂商代理了各地运营商的服务,搭建了一些小的服务器,一般内存只有 512M,而硬盘只有 8G,但是好处是通过 ADSL 上网,因此可以随时更换 IP。比如笔者搭建的这个动态代理:

![ADSL](https://ws4.sinaimg.cn/large/006tNbRwly1fu6vpix9s0j30wq0aa77o.jpg)

每三十分钟更换一次 IP,而这些服务器也很便宜,在 100-200 每月,所以大可以搭建一个集群,这样基本上一个 IP 被封之前也基本被换掉了。

要封禁这种用户也很简单,可以看出虽然 IP 在更换,但是基本上还是在一个 B 段之内,一个 B 段也就6w个用户,直接封了就行了

# 利用数据中心提供的更换 IP 接口来

有些爬虫会利用阿里云或者AWS的弹性 IP 来爬数据,反爬虫的第一步可以把阿里云的 IP 都屏蔽掉,正常用户一般是不会用这些 IP 来访问的。

# 附录

阿里云的出口 IP 列表:

“`
deny 42.96.128.0/17;
deny 42.120.0.0/16;
deny 42.121.0.0/16;
deny 42.156.128.0/17;
deny 110.75.0.0/16;
deny 110.76.0.0/19;
deny 110.76.32.0/20;
deny 110.76.48.0/20;
deny 110.173.192.0/20;
deny 110.173.208.0/20;
deny 112.74.0.0/16;
deny 112.124.0.0/16;
deny 112.127.0.0/16;
deny 114.215.0.0/16;
deny 115.28.0.0/16;
deny 115.29.0.0/16;
deny 115.124.16.0/22;
deny 115.124.20.0/22;
deny 115.124.24.0/21;
deny 119.38.208.0/21;
deny 119.38.216.0/21;
deny 119.42.224.0/20;
deny 119.42.242.0/23;
deny 119.42.244.0/22;
deny 120.24.0.0/14;
deny 120.24.0.0/16;
deny 120.25.0.0/18;
deny 120.25.64.0/19;
deny 120.25.96.0/21;
deny 120.25.108.0/24;
deny 120.25.110.0/24;
deny 120.25.111.0/24;
deny 121.0.16.0/21;
deny 121.0.24.0/22;
deny 121.0.28.0/22;
deny 121.40.0.0/14;
deny 121.42.0.0/18;
deny 121.42.0.0/24;
deny 121.42.64.0/18;
deny 121.42.128.0/18;
deny 121.42.192.0/19;
deny 121.42.224.0/19;
deny 121.196.0.0/16;
deny 121.197.0.0/16;
deny 121.198.0.0/16;
deny 121.199.0.0/16;
deny 140.205.0.0/16;
deny 203.209.250.0/23;
deny 218.244.128.0/19;
deny 223.4.0.0/16;
deny 223.5.0.0/16;
deny 223.5.5.0/24;
deny 223.6.0.0/16;
deny 223.6.6.0/24;
deny 223.7.0.0/16;
101.200.0.0/15 
101.37.0.0/16 
101.37.0.0/17 
101.37.0.0/24 
101.37.128.0/17 
103.52.196.0/22 
103.52.196.0/23 
103.52.196.0/24 
103.52.198.0/23 
106.11.0.0/16 
106.11.0.0/17 
106.11.0.0/18 
106.11.1.0/24 
106.11.128.0/17 
106.11.32.0/22 
106.11.36.0/22 
106.11.48.0/21 
106.11.56.0/21 
106.11.64.0/19 
110.173.192.0/20 
110.173.196.0/24 
110.173.208.0/20 
110.75.0.0/16 
110.75.236.0/22 
110.75.239.0/24 
110.75.240.0/20 
110.75.242.0/24 
110.75.243.0/24 
110.75.244.0/22 
110.76.0.0/19 
110.76.21.0/24 
110.76.32.0/20 
110.76.48.0/20 
112.124.0.0/16 
112.125.0.0/16 
112.126.0.0/16 
112.127.0.0/16 
112.74.0.0/16 
112.74.0.0/17 
112.74.116.0/22 
112.74.120.0/22 
112.74.128.0/17 
112.74.32.0/19 
112.74.64.0/22 
112.74.68.0/22 
114.215.0.0/16 
114.55.0.0/16 
114.55.0.0/17 
114.55.128.0/17 
115.124.16.0/22 
115.124.20.0/22 
115.124.24.0/21 
115.28.0.0/16 
115.29.0.0/16 
118.190.0.0/16 
118.190.0.0/17 
118.190.0.0/24 
118.190.128.0/17 
118.31.0.0/16 
118.31.0.0/17 
118.31.0.0/24 
118.31.128.0/17 
119.38.208.0/21 
119.38.216.0/21 
119.38.219.0/24 
119.42.224.0/20 
119.42.242.0/23 
119.42.244.0/22 
119.42.248.0/21 
120.24.0.0/14 
120.24.0.0/15 
120.25.0.0/18 
120.25.104.0/22 
120.25.108.0/24 
120.25.110.0/24 
120.25.111.0/24 
120.25.112.0/23 
120.25.115.0/24 
120.25.136.0/22 
120.25.64.0/19 
120.25.96.0/21 
120.27.0.0/17 
120.27.128.0/17 
120.27.128.0/18 
120.27.192.0/18 
120.55.0.0/16 
120.76.0.0/15 
120.76.0.0/16 
120.77.0.0/16 
120.78.0.0/15 
121.0.16.0/21 
121.0.24.0/22 
121.0.28.0/22 
121.196.0.0/16 
121.197.0.0/16 
121.198.0.0/16 
121.199.0.0/16 
121.40.0.0/14 
121.42.0.0/18 
121.42.0.0/24 
121.42.128.0/18 
121.42.17.0/24 
121.42.192.0/19 
121.42.224.0/19 
121.42.64.0/18 
123.56.0.0/15 
123.56.0.0/16 
123.57.0.0/16 
139.129.0.0/16 
139.129.0.0/17 
139.129.128.0/17 
139.196.0.0/16 
139.196.0.0/17 
139.196.128.0/17 
139.224.0.0/16 
139.224.0.0/17 
139.224.128.0/17 
140.205.0.0/16 
140.205.128.0/18 
140.205.192.0/18 
140.205.32.0/19 
140.205.76.0/24 
182.92.0.0/16 
203.107.0.0/24 
203.107.1.0/24 
203.209.224.0/19 
218.244.128.0/19 
223.4.0.0/16 
223.5.0.0/16 
223.5.5.0/24 
223.6.0.0/16 
223.6.6.0/24 
223.7.0.0/16 
39.100.0.0/14 
39.104.0.0/14 
39.104.0.0/15 
39.104.0.0/24 
39.106.0.0/15 
39.108.0.0/16 
39.108.0.0/17 
39.108.0.0/24 
39.108.128.0/17 
39.96.0.0/13 
39.96.0.0/14 
39.96.0.0/24 
42.120.0.0/16 
42.121.0.0/16 
42.156.128.0/17 
42.96.128.0/17 
45.113.40.0/22 
45.113.40.0/23 
45.113.40.0/24 
45.113.42.0/23 
47.92.0.0/14 
47.92.0.0/15 
47.92.0.0/24 
47.94.0.0/15
“`