破解geetest验证码

本文所述内容仅用于实验学习之用,任何因非法商业用途造成的法律纠纷作者概不负责


破解geetest验证码

写过爬虫的基本都碰到过验证码问题,滑动验证码是其中一类略微高级的验证码类型。国内的滑动验证码基本由geetest提供,本文主要叙述如何绕过(破解)geetest滑动验证码

1. 依赖

  • python 3.6
  • selenium,模拟浏览器请求/渲染
  • lxml,html页面处理
  • pillow,python图像库
  • numpy+peakutils,数学运算

2. 过程

以国内某著名二次元网站为例(不是我说的啊!),登陆界面如图所示,点击验证码的滑块就会弹出验证码,你需要将滑块滑到对应的空缺位置上即可验证成功

login

2.1 dom解析

主要dom如图所示

dom

你所看到的图不是原图,原图经过切片乱序之后由css拼成的,如图所示

disordered_image

2.2 还原原图

观察可得,乱序图有(parts_per_line=26)*2=52块切片,每块切片的宽度part_width和高度可以自行计算得part_height,查阅css手册得background-position的坐标系第一象限在右下角。

对第idx个切片来说,它在乱序图中的位置为background-position取负

它在原图中的位置dest_x=(idx % parts_per_line) * part_widthdest_y=(idx // parts_per_line) * part_height

有了计算公式,可以用pillow的方法切割和拼接图片

# 切割
image.crop((x, y, x+w, y+h))
# 拼接
image.paste(target_image, (dest_x, dest_y))

2.3 获取待验证图片

鼠标悬停在滑块上并不会显示待验证位置在哪,需要点击之后才会显示,需要让selenium执行鼠标点击并且不放这个动作

# 获得滑块对象
drag = driver.find_element_by_css_selector('.gt_slider_knob.gt_show')
# 执行点击并且不放的动作
action = ActionChains(driver)
action.click_and_hold(drag).perform()

这个时候浏览器中应该是这个样子

click_hold

之后截取待验证的图片

# selenium截图
image_to_verify = Image.open(io.BytesIO(driver.get_screenshot_as_png()))
# 调用浏览器,执行js后返回框内图片相对于窗口的坐标
x = driver.execute_script('return $("div.gt_cut_fullbg")[0].getBoundingClientRect().left')
y = driver.execute_script('return $("div.gt_cut_fullbg")[0].getBoundingClientRect().top')
# 切割(同上)
image.crop(...)

2.4 获取拼图块大小

拼图块的dom

<div class="gt_slice gt_show" style="left: 0px; background-image: url(&quot;https://static.geetest.com/pictures/gt/375495539/slice/1d4a39f5d.png&quot;); width: 53px; height: 52px; top: 47px;"></div>

大小都写在style上了,slice_width=53, slice_height=52

2.5 图像处理

这块是破解的核心逻辑,主要思路就是尽可能过滤掉图像中相同的像素,留下的就是不同的,我们主要是去找由两块拼图块垂直方向上的边缘。

我的做法是用自带滤波函数找到图像中的边缘,然后转灰度图,设置恰当阈值,做二值化

image.filter(ImageFilter.FIND_EDGES).convert('L').point(lambda x: 0 if x < 120 else 255)

这里二值化的分界阈值是120,你可以试试别的,看看最终效果。

从右往左,扫描垂直方向上,两幅图里的像素差异,并记录差异像素个数

x_diff = [0] * origin_image.width
    for i in range(origin_image.width - 1, -1, -1):
        diff_count = 0
        for j in range(origin_image.height - 1, -1, -1):
            if origin_image_grey.getpixel((i, j)) != image_to_verify_grey.getpixel((i, j)):
                diff_count += 1
        x_diff[i] = diff_count

将这个x_diff用excel绘制成折线图后,能很明显发现四个波峰

waves

接下去要做的是从这个一维数组中提取四个波峰,这里用到了peakutils

import numpy as np
from peakutils.peak import indexes
waves = indexes(np.array(x_diff), thres=7.0/max(x_diff), min_dist=20)
  • thres,振幅阈值,振幅超过这个值才会被认为是波峰(不是很理解这个参数,求大佬解答)
  • min_dist,波峰之间的最小间隔,理论上要接近拼图块宽度才比较合适,但是我试了效果并不好,不知道为什么

2.6 移动滑块

计算要移动的距离offset=waves[2] - waves[0],并移动滑块

action = ActionChains(driver)
action.drag_and_drop_by_offset(drag, offset, 0).perform()

2.7 完成

效果如图

show

源码:https://github.com/hbprotoss/geetest-crack

上传python包到pypi

注册账号

创建.pypirc文件

[distutils]
index-servers =
  pypi
  pypitest

[pypi]
repository=https://upload.pypi.org/legacy/
username=your_username
password=your_password

[pypitest]
repository=https://test.pypi.org/legacy/
username=your_username
password=your_password

保存到~/.pypirc

chmod 600 ~/.pypirc

准备工作

工作目录结构

root-dir/   # arbitrary working directory name
  setup.py
  setup.cfg
  LICENSE.txt
  README.md
  protoss-pypi/
    __init__.py
    foo.py
    bar.py
    baz.py

setup.py

from distutils.core import setup
setup(
    name='protoss-pypi',
    packages=['protoss-pypi'],
    version='0.1.1',
    description='A random test lib',
    author='hbprotoss',
    author_email='gamespy1991@gmail.com',
    url='https://github.com/hbprotoss/pypitest',
    download_url='https://github.com/hbprotoss/pypitest/archive/master.zip',
    keywords=['testing', 'logging', 'example'],  # arbitrary keywords
    classifiers=[],
)

name和packages保持一致,url写git仓库地址,download_url写源码包地址

setup.cfg

markdown写的readme文件需要显示指定

[metadata]
description-file = README.md

打包上传

正式

python setup.py sdist upload -r pypi

测试

python setup.py sdist upload -r pypitest

参考资料:

http://peterdowns.com/posts/first-time-with-pypi.html

classpath* vs classpath in spring

记录一下spring里读取资源时的classpath*和classpath表达式的区别。不想看细节的可以直接跳到最后直接看结论。

读取资源的主要逻辑在PathMatchingResourcePatternResolver.getResources

public Resource[] getResources(String locationPattern) throws IOException {
    Assert.notNull(locationPattern, "Location pattern must not be null");
    if (locationPattern.startsWith(CLASSPATH_ALL_URL_PREFIX)) {
        // a class path resource (multiple resources for same name possible)
        if (getPathMatcher().isPattern(locationPattern.substring(CLASSPATH_ALL_URL_PREFIX.length()))) {
            // a class path resource pattern
            return findPathMatchingResources(locationPattern);
        }
        else {
            // all class path resources with the given name
            return findAllClassPathResources(locationPattern.substring(CLASSPATH_ALL_URL_PREFIX.length()));
        }
    }
    else {
        // Only look for a pattern after a prefix here
        // (to not get fooled by a pattern symbol in a strange prefix).
        int prefixEnd = locationPattern.indexOf(":") + 1;
        if (getPathMatcher().isPattern(locationPattern.substring(prefixEnd))) {
            // a file pattern
            return findPathMatchingResources(locationPattern);
        }
        else {
            // a single resource with the given name
            return new Resource[] {getResourceLoader().getResource(locationPattern)};
        }
    }
}
  • classpath*:resource

    代码中的if逻辑,通过findAllClassPathResources,遍历整个classpath,搜索所有名字匹配的文件返回

  • classpath:resource

    代码中的else逻辑,getResourceLoader().getResource(locationPattern)最终调用tomcat提供的WebappClassLoader,从classpath中遍历每个目录(包括jar),寻找指定的resource直到找到指定的第一个匹配文件返回

读取完resource列表之后,AbstractBeanDefinitionReader.loadBeanDefinitions会载入得到resource列表

Resource[] resources = ((ResourcePatternResolver) resourceLoader).getResources(location);
int loadCount = loadBeanDefinitions(resources);

结论

classpath*:resource中读取资源,就相当于把整个classpath下能找到的同名resource按照classpath中的次序拼接成一个大文件后载入,位于classpath后部的resource定义会覆盖前面的。由于tomcat会保证WEB-INF/class下的class会放在classpath中的第一位,所以导致jar中的同名resource定义覆盖app中的定义。

classpath:resource仅载入classpath路径中碰到的第一个resource。

Cookie坑一记

关于Cookie的domain属性,RFC6265上是这么说的:

  1. 如果domain属性缺失,那么该cookie只能对当前host可见。比如,xx.com下有个cookie,Set-Cookie头没有带domain属性,那么这个cookie只对xx.com下的页面可见,a.xx.com等子域名不可见
  2. .xx.com这种domain其实是不合法的,只不过浏览器在见到这种域名的时候,需要自动把最前面的.忽略掉,把xx.com作为cookie的domain,即xx.com及其子域名都可见

thymeleaf的坑一记

记录下thymeleaf 3.0新增的th:fieldth:each中生成的变量结合使用时的坑。

代码就是官方例子https://github.com/thymeleaf/thymeleafexamples-stsm.git,在webapp/WEB-INF/seedstartermng.html中118-131行

<tr th:each="row,rowStat : *{rows}">
  <td th:text="${rowStat.count}">1</td>
  <td>
    <select th:field="*{rows[__${rowStat.index}__].variety}">
      <option th:each="var : ${allVarieties}" th:value="${var.id}" th:text="${var.name}">Thymus Thymi</option>
    </select>
  </td>
  <td>
    <input type="text" th:field="*{rows[__${rowStat.index}__].seedsPerCell}" th:errorclass="fieldError" />
  </td>
  <td>
    <button type="submit" name="removeRow" th:value="${rowStat.index}" th:text="#{seedstarter.row.remove}">Remove row</button>
  </td>
</tr>

其中第二个td取出rows中的每一行的variety,做成一个select下拉菜单,当我尝试用${row.variety}替换原文的*{rows[__${rowStat.index}__].variety}时,页面渲染抛出异常Neither BindingResult nor plain target object for bean name 'row' available as request attribute。多方探索之后得出结论:这是我们使用的问题,设计时特意在遇到这种情况时为了避免服务端无法处理提交后的表单,就抛出异常。

用例子中的代码渲染完生成后的页面为:

<tr>
  <td>1</td>
  <td>
    <select id="rows0.variety" name="rows[0].variety">
      <option value="1">Thymus vulgaris</option>
      <option value="2">Thymus x citriodorus</option>
      <option value="3">Thymus herba-barona</option>
      <option value="4">Thymus pseudolaginosus</option>
      <option value="5">Thymus serpyllum</option>
    </select>
  </td>
  <td>
    <input type="text" id="rows0.seedsPerCell" name="rows[0].seedsPerCell" value="">
  </td>
  <td>
    <button type="submit" name="removeRow" value="0">Remove row</button>
  </td>
</tr>

其中,th:field在渲染时会给目标元素加上id和name属性,name属性取*{...}中表达式的值。由于__${rowStat.index}__是个预处理语句,在渲染之前会直接文本替换,所以最终的表达式为rows[0].variety

但是如果是${row.variety},则最终name会被替换为row.variety,由于浏览器作为客户端无法知道服务端的逻辑,这样之后的每个tr中的元素都是这个表达式,表单提交的时候无法被spring解析成一个list对象,就会出现错误。

官方站在实现角度的解释可以看这个issue

XPath备忘

最近写了几个scrapy的爬虫程序,里面用到了xpath,写个日志记录一下用法。

XPath是什么

XPath是一种用于xml、html等结构化文档中寻址定位特定元素等描述性语言

XPath主要功能

下面以如下测试文档为例进行说明:

<html>
    <body>
        <contents id="content">
        <para><a href="one.html" class="normal-link">One</a></para>
        <para><a href="two.html" class="normal-link">Two</a></para>
        <para><a href="three.html" class="ex-link">Three</a></para>
        </contents>
    </body>
</html>

精确路径寻址

指通过精确制定的路径取得元素。例如

和unix文件系统概念一致,有如下几种定位方式:

  • 绝对路径,/html/body/contents/para能查找出文档中的三个para元素
  • 相对路径,在/html/body路径下,/contents/para同样也能查找出这三个para元素
  • 父级路径,.表示当前路径,..表示当前路径的父级路径

模糊路径寻址

不需要指定绝对路径或根据当前路径确定的相对路径,只需要指定某个子结构,就能查找出所有符合这个子结构的元素。如

  • //contents/para在任何路径下,都能查找到整个文档下的这三个para元素
  • .//contents/para能在当前路径下,查找到子节点中任何符合contents/para结构的元素

节点属性匹配

格式:元素[@属性="xxx"]

  • a[@class="normal-link"]能查找出两个有带normal-link class的a链
  • para[a/@class="ex-link"]能查找出一级子元素中有带ex-link class的a链的para元素,这里就是<para><a href="three.html" class="ex-link">Three</a></para>

属性选择

查找某个元素中的特定属性值,如:a[@class="ex-link"]/@href能读取第三个a链的href值

内置函数

  • node(),返回任意种类的节点。比如和内置关键字child组合成/html/body/contents/child::node(),可以选择所有的para节点
  • text(),返回节点中包含的文本。/html/body/contents/para/a[@class="ex-link"]/text()返回Three。特别的,和模糊路径寻址配合,如/html/body/contents//text(),能返回contents下的One Two Three字符串

搭建智能翻墙路由器

本文着重介绍如何搭建智能翻墙路由器,实现避免DNS污染,并且自动根据是否是国内IP来决定是否翻墙,从而使任何连接路由器的设备无障碍穿墙出去。

思路是,用shadowsocks建立起翻墙代理服务,用shadowsocks的udp relay模式转发DNS请求,解决DNS污染,再配置iptables根据IP决定是否走shadowsocks来翻墙。

准备材料

  • 能刷OpenWrt的智能路由器。我用的是小米路由器MINI,16MB ROM,128MB DDR2内存,MT7620A处理器,运行毫无压力(真的不是广告。。。)
  • OpenWrt。这里选的是PandoraBox
  • shadowsocks client,PandoraBox自带
  • ChinaDNS,PandoraBox自带
  • VPS一台
  • shadowsocks server,选用C实现:shadowsocks-libev,go和Python版没有UDP relay功能,不能实现DNS请求转发

步骤

shadowsocks server

shadowsocks-libev的安装参考http://shadowsocks.org/en/download/servers.html中的“C with libev”一节

安装完成之后将如下配置写入config.json

{
    "server":"0.0.0.0",
    "server_port":8025,
    "password":"123456",
    "timeout":300,
    "method":"aes-256-cfb"
}

分别指定了服务器的binding address,端口,密码,超时时间和加密方式。按需更改

在远程VPS上启动shadowsocks server: ss-server -c config.json -u

注意得加上-u选项,enable udprelay mode。用作DNS请求转发,避免DNS污染。

shadowsocks client

在本地路由器上起shadowsocks client

ss-redir

ss-redir用于将客户端的原始数据封装成shadowsocks协议内容,转发给server,实现透明转发。

在本地路由器启动ss-redir: ss-redir -s "your_server_ip" -p "your_server_port" -l "local_service_port" -m "encryption_method" -k "server_password" -f "pid_file_path" 注意这里不需要-u选项,转发的是TCP包,ss-redir也不支持这个选项。

ss-tunnel

ss-tunnel用于实现本地port forward,和ssh的port forward一样,只是加密方式用了shadowsocks协议,用于在本地起服务,转发DNS请求

在本地路由器启动ss-tunnel: ss-tunnel -s "your_server_ip" -p "your_server_port" -l "local_service_port" -m "encryption_method" -k "server_password" -L "server_ip:server_port" -f "pid_file_path" -u

这个-L选项理论上可以填国外DNS的IP/PORT,比如8.8.8.8:53,我在我的VPS起了一个DNS转发服务,填了自己的IP/PORT,效果应该一样。-u是开启udp relay,DNS是UDP包嘛

ChinaDNS

如果所有DNS请求都走国外DNS server,国内有些网站(如微博)在海外有服务器,就会比较慢。ChinaDNS保证的就是国内域名能解析成国内IP,国外域名解析成国外IP。

在本地路由器启动ChinaDNS: chinadns -l /etc/chinadns_iplist.txt -c /etc/chinadns_chnroute.txt -d -p "local_dns_port" -s 114.114.114.114,127.0.0.1:8026

-s选项后加以逗号分隔的DNS服务器列表,最好国内、国外各有一个。由于前面通过ss-tunnel在本地起了一个端口转发到我的DNS服务,所以填的是127.0.0.1:8026

ChinaDNS原理是,向所有列表中的DNS server发DNS请求,判断结果可信任条件是:国内DNS解析出的是国内IP,国外DNS解析出的是国外IP,/etc/chinadns_chnroute.txt里包含了国内IP网段,/etc/chinadns_iplist.txt里包含的是常见的被污染后的DNS解析结果IP。这样只要通过dnsmasq之类的把本地DNS请求转发到ChinaDNS的端口上,就能解决DNS污染的问题。

iptables

前面的准备工作完成之后,只要配置一下iptables,将国内TCP流量直接放行,国外TCP流量转发到ss-redir起的端口就行,判断依据是IP。

在nat表中新建一个SHADOWSOCKS链

iptables -t nat -N SHADOWSOCKS

远程VPS流量直接放行

iptables -t nat -A SHADOWSOCKS -d xxx.xxx.xx.xxx -j RETURN

内网流量直接放行

iptables -t nat -A SHADOWSOCKS -d 0.0.0.0/8 -j RETURN
iptables -t nat -A SHADOWSOCKS -d 10.0.0.0/8 -j RETURN
iptables -t nat -A SHADOWSOCKS -d 127.0.0.0/8 -j RETURN
iptables -t nat -A SHADOWSOCKS -d 169.254.0.0/16 -j RETURN
iptables -t nat -A SHADOWSOCKS -d 172.16.0.0/12 -j RETURN
iptables -t nat -A SHADOWSOCKS -d 192.168.0.0/16 -j RETURN
iptables -t nat -A SHADOWSOCKS -d 224.0.0.0/4 -j RETURN
iptables -t nat -A SHADOWSOCKS -d 240.0.0.0/4 -j RETURN

国内IP流量直接放行(列表较长,这里不列举了,网上随便搜搜就有)

剩下的TCP流量转发到ss-redir端口

iptables -t nat -A SHADOWSOCKS -p tcp -j REDIRECT --to-ports xxx

完工

搞定之后,任何连接这个路由器的设备都能实现透明翻墙了。

以上

关于Python异常处理流程

def f():
    try:
        print 'try'
        raise NameError
    except Exception, e:
        print 'except'
        raise KeyError
    else:
        print 'else'
        raise IOError
    finally:
        print 'finally'
        raise ValueError

在以上代码中,无论try里有没有异常,走得是except还是else,最终抛出的都是finally中的ValueError。为此小记一下Python里的异常处理流程。

Python当前状态的异常信息存储在线程状态PyThreadState中,包括type, value, traceback。无论是主动raise还是bug触发,异常信息最终都会通过PyErr_Restore(Python/errors.c)被修改。

异常处理的主要流程在PyEval_EvalFrameEx(Python/ceval.c)里,也是Python虚拟机的核心处理流程。

先说明几个概念以便理解:

  1. Python虚拟机里PyEval_EvalFrameEx干的活就是物理机里CPU干的活,根据指令作出相应动作
  2. frame:一个函数的执行环境,可以理解为物理机上EBP, ESP等寄存器确定的函数调用栈,外加一点别的状态信息
  3. blockstack:也是一个栈,隶属于一个frame。每当遇到循环或者try异常处理块都会压入一个block对象,块流程完了弹出
  4. traceback:一个链表,记录发生异常时候的调用栈信息
PyObject *
PyEval_EvalFrameEx(PyFrameObject *f, int throwflag)
{

     register enum why_code why; // 每一条指令处理完之后的状态,用来标记是否有异常

     switch(opcode){} // 一个处理字节码指令的巨大switch
     ...

     // 记录traceback,用来在异常最终没有处理时打印调用栈信息
     // 这个why ==WHY_EXCEPTION条件很重要,如果在finally中发生异常,则why的值是WHY_RERAISE,因此不会进入这个条件记录新的traceback,而是直接覆盖当前的traceback,所以在最终的调用栈里,finally异常之前try/except/else中的异常信息也就被覆盖了
       if (why == WHY_EXCEPTION) {
            PyTraceBack_Here(f);

            if (tstate->c_tracefunc != NULL)
                call_exc_trace(tstate->c_tracefunc,
                               tstate->c_traceobj, f);
        }

     // 这种是finally中有异常的状态,reraise
       if (why == WHY_RERAISE)
            why = WHY_EXCEPTION;

     // 栈帧展开,主要为了在当前frame,沿着block栈向上寻找有没有try/except来接住异常

fast_block_end:
        while (why != WHY_NOT && f->f_iblock > 0) {
            /* Peek at the current block. */
            PyTryBlock *b = &f->f_blockstack[f->f_iblock - 1];

           ......

            /* Now we have to pop the block. */
            f->f_iblock--;

           ......

          // 在finally块中
            if (b->b_type == SETUP_FINALLY ||
                ......
                ) {

               // 有异常(raise xxxError或bug触发的情况)
                if (why == WHY_EXCEPTION) {
                    PyObject *exc, *val, *tb;

                    // 取出异常信息,压入执行栈
                    PyErr_Fetch(&exc, &val, &tb);
                    if (tb == NULL) {
                        Py_INCREF(Py_None);
                        PUSH(Py_None);
                    } else
                        PUSH(tb);
                    PUSH(val);
                    PUSH(exc);
                }
                else {
                    // return或者continue语句
                    if (why & (WHY_RETURN | WHY_CONTINUE))
                        PUSH(retval);
                    v = PyInt_FromLong((long)why);
                    PUSH(v);
                }
               // 跳转到END_FINALLY指令进行扫尾工作
                why = WHY_NOT;
                JUMPTO(b->b_handler);
                break;
            }
        } /* unwind stack */

     // 函数返回值为null说明函数中发生异常未处理

    if (why != WHY_RETURN)
        retval = NULL;

     // 栈帧回退,取回上一层函数执行信息

    tstate->frame = f->f_back;

    return retval;
}

补充一点:

dis模块可以“反汇编”Python字节码变成“Python汇编语言”,下面就是示例代码的反汇编结果:

  6           0 SETUP_FINALLY           63 (to 66)
              3 SETUP_EXCEPT            15 (to 21)

  7           6 LOAD_CONST               1 ('try')
              9 PRINT_ITEM
             10 PRINT_NEWLINE

  8          11 LOAD_GLOBAL              0 (NameError)
             14 RAISE_VARARGS            1
             17 POP_BLOCK
             18 JUMP_FORWARD            30 (to 51)

  9     >>   21 DUP_TOP
             22 LOAD_GLOBAL              1 (Exception)
             25 COMPARE_OP              10 (exception match)
             28 POP_JUMP_IF_FALSE       50
             31 POP_TOP
             32 STORE_FAST               0 (e)
             35 POP_TOP

 10          36 LOAD_CONST               2 ('except')
             39 PRINT_ITEM
             40 PRINT_NEWLINE

 11          41 LOAD_GLOBAL              2 (KeyError)
             44 RAISE_VARARGS            1
             47 JUMP_FORWARD            12 (to 62)
        >>   50 END_FINALLY

 13     >>   51 LOAD_CONST               3 ('else')
             54 PRINT_ITEM
             55 PRINT_NEWLINE

 14          56 LOAD_GLOBAL              3 (IOError)
             59 RAISE_VARARGS            1
        >>   62 POP_BLOCK
             63 LOAD_CONST               0 (None)

 16     >>   66 LOAD_CONST               4 ('finally')
             69 PRINT_ITEM
             70 PRINT_NEWLINE

 17          71 LOAD_GLOBAL              4 (ValueError)
             74 RAISE_VARARGS            1
             77 END_FINALLY
             78 LOAD_CONST               0 (None)
             81 RETURN_VALUE

InnoDB引擎索引学习笔记

最近在研究学习MySQL,本文记录下索引相关(主要B-Tree索引)的特性。


索引是什么

数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据。

按所用的数据结构分,有B-Tree索引(B+ Tree)、哈希索引、R-Tree索引等。按数据块的顺序和索引节点的逻辑顺序是否一致可以分为聚集索引和非聚集索引。聚集索引由于物理块连续,在范围扫描的时候可以减少磁头寻道时间,因而比非聚集索引高效。

InnoDB索引结构

InnoDB引擎的索引主体结构是B+Tree(这种数据结构的描述可以参考CSDN博主v_JULY_v的从B树、B+树、B*树谈到R 树)。

其中,主键索引(Primary Index)是聚集索引,中间节点是用于查询的边界值,叶子节点就是数据节点,叶子节点之间通过指针形成双向链表。如图:

primary_index.jpg

辅助索引(Secondary Index)同样为B-Tree索引,只是叶子节点不是数据节点,而是对主键的引用。

secondary_index.jpg

由于此特性,InnoDB引擎要求数据表必须有一个主键,如果没有主键,在数据表创建的时候会自动生成一个唯一非空索引替代。这个特性也决定了InnoDB表的主键最好是一个自增的ID序列,这样在后续插入的过程中不会造成数据块的唯一,提升性能。

当所建立的索引为多列索引的时候,例如KEY(a,b,c),中间节点依旧以最左边的一列a进行索引,只是在叶子节点上保存的不仅仅是a,而是(a,b,c)多字段排序后的序列。

性能实测

下面结合实际例子阐述现象和内部结构的关系

首先建立一个测试表:

CREATE TABLE test (
     id INT NOT NULL AUTO_INCREMENT,
     a INT NOT NULL,
     b INT NOT NULL,
     c INT NOT NULL,
     PRIMARY KEY (id),
     KEY(a,b,c)
)ENGINE=InnoDB;

数据项为(a,b,c)在0~200之间的所有组合项,共计8000000行记录。为了消除几次实验中以query cache为代表的各种server cache对实验数据的影响,每次实验后均重启mysql服务。

索引对查询效率的影响

首先是建立KEY(a,b,c)索引前后的性能对比,能很明显地看到索引大幅提升查询速度。没有索引的时候需要做全表扫描,建立索引之后通过B-Tree搜索。

没有索引(除主键,下同)
[SQL]select * from test where a = 0 and b = 1;
Affected rows: 0
Time: 0.324s

建立KEY(a,b,c)
[SQL]select * from test where a = 0 and b = 1;
Affected rows: 0
Time: 0.004s

由于MySQL优化器的优化,where条件中的各个子条件顺序对索引的使用没有影响。

[SQL]select * from test where b = 1 and a = 0;
Affected rows: 0
Time: 0.002s

当使用的列非严格的索引最左前缀时,可以想象,只有a加速了索引搜索,找到所有符合a条件的记录的之后只能顺序扫描检查c是否符合条件。所以相比没有索引时要快,但是慢于使用严格索引最左前缀时的速度。

[SQL]select * from test where a = 0 and c = 1;
Affected rows: 0
Time: 0.043s

当没有使用到a列作为条件时完全没法使用索引,甚至比没有索引时还要慢。因为建表的时候a在前,b、c在后,并且数据节点有序。在没有索引的测试中,InnoDB引擎到a不为0时自动停止搜索。而在这个例子中需要扫描全表找出满足符合条件的b、c,达到完全没法忍受的16秒。

[SQL]select * from test where b = 0 and c = 1;
Affected rows: 0
Time: 16.023s

索引对排序效率的影响

只要能用到索引,并且ORDER BY后面的列在索引中,则顺序还是倒序排序对性能无影响。因为叶子节点是个双向链表,倒序可以从后向前遍历,与顺序的代价相同。

[SQL]select * from test where a = 0 ORDER BY b;
Affected rows: 0
Time: 0.085s

[SQL]select * from test where a = 0 ORDER BY b DESC;
Affected rows: 0
Time: 0.089s

但是,当有两个字段排序的顺序不同时,叶子节点的有序性就无法用在排序中,必须读出所有叶子节点之后再按指定的字段进行一趟排序,所以速度就慢了下来。

[SQL]select * from test where a = 0 ORDER BY b DESC, c DESC;
Affected rows: 0
Time: 0.089s

[SQL]select * from test where a = 0 ORDER BY b ASC, c DESC;
Affected rows: 0
Time: 0.184s

同样,下面的例子中对索引左边的字段a进行范围选择的时候也没法运用索引,因为多个取值的a无法保证b和c字段有序,必须重新排序

[SQL]select * from test where a <= 0 ORDER BY b;
Affected rows: 0
Time: 0.103s

所以,尽可能做到覆盖索引(即where,order by中用到的字段被索引覆盖),能利用索引加速搜索和排序。


参考资料:

《高性能MySQL》,电子工业出版社,2010年1月

Python垃圾回收机制

题记:我是来填坑的。。。

本文主要结合CPython源码分析一下Python的GC机制(面试的时候被问到这个问题,之前理解不深,答得不好,一波大坑啊。。。)


Python GC主要使用引用计数(reference counting)来跟踪和回收垃圾。在引用计数的基础上,通过“标记-清除”(mark and sweep)解决容器对象可能产生的循环引用问题,通过“分代回收”(generation collection)以空间换时间的方法提高垃圾回收效率。

引用计数

引用计数法在对象内部维护了一个被其他对象引用数的引用计数值,当这个引用计数值为0时,说明这个对象不再被其他对象引用,就可以被回收了。

结合源码来看,所有Python对象的头部包含了这样一个结构PyObject(相当于继承自PyObject):

// object.h
struct _object {
    Py_ssize_t ob_refcnt;
    struct PyTypeObject *ob_type;
} PyObject;

ob_refcnt就是引用计数值。

例如,下面是int型对象的定义:

// intobject.h
typedef struct {
        PyObject_HEAD
        long ob_ival;
} PyIntObject;

引用计数法有很明显的优点:

  1. 高效
  2. 运行期没有停顿
  3. 对象有确定的生命周期
  4. 易于实现

原始的引用计数法也有明显的缺点:

  1. 维护引用计数的次数和引用赋值成正比,而不像mark and sweep等基本与回收的内存数量有关。
  2. 无法解决循环引用的问题。A和B相互引用而再没有外部引用A与B中的任何一个,它们的引用计数都为1,但显然应该被回收。

为了解决这两个致命弱点,Python又引入了以下两种GC机制。

标记-清除

“标记-清除”法是为了解决循环引用问题。可以包含其他对象引用的容器对象(如list, dict, set,甚至class)都可能产生循环引用,为此,在申请内存时,所有容器对象的头部又加上了PyGC_Head来实现“标记-清除”机制。

// objimpl.h
typedef union _gc_head {
    struct {
        union _gc_head *gc_next;
        union _gc_head *gc_prev;
        Py_ssize_t gc_refs;
    } gc;
    long double dummy;  /* force worst-case alignment */
} PyGC_Head;

在为对象申请内存的时候,可以明显看到,实际申请的内存数量已经加上了PyGC_Head的大小

// gcmodule.c
PyObject *
_PyObject_GC_Malloc(size_t basicsize)
{
    PyObject *op;
    PyGC_Head *g = (PyGC_Head *)PyObject_MALLOC(
                sizeof(PyGC_Head) + basicsize);
    if (g == NULL)
        return PyErr_NoMemory();

    ......

    op = FROM_GC(g);
    return op;
}

举例来说,从list对象的创建中,有如下主要逻辑:

// listobject.c
PyObject *
PyList_New(Py_ssize_t size)
{
    PyListObject *op;
    ......
    op = PyObject_GC_New(PyListObject, &PyList_Type);
    ......
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

_PyObject_GC_TRACK就将对象链接到了第0代对象集合中(后文详述分代回收)。

垃圾标记时,先将集合中对象的引用计数复制一份副本(以免在操作过程中破坏真实的引用计数值):

// gcmodule.c
static void
update_refs(PyGC_Head *containers)
{
    PyGC_Head *gc = containers->gc.gc_next;
    for (; gc != containers; gc = gc->gc.gc_next) {
        assert(gc->gc.gc_refs == GC_REACHABLE);
        gc->gc.gc_refs = FROM_GC(gc)->ob_refcnt;
        assert(gc->gc.gc_refs != 0);
    }
}

然后操作这个副本,遍历对象集合,将被引用对象的引用计数副本值减1:

// gcmodule.c
static void
subtract_refs(PyGC_Head *containers)
{
    traverseproc traverse;
    PyGC_Head *gc = containers->gc.gc_next;
    for (; gc != containers; gc=gc->gc.gc_next) {
        traverse = FROM_GC(gc)->ob_type->tp_traverse;
        (void) traverse(FROM_GC(gc),
                   (visitproc)visit_decref,
                   NULL);
    }
}

这个traverse是对象类型定义的函数,用来遍历对象,通过传入的回调函数visit_decref来操作引用计数副本。

例如dict就要在key和value上都用visit_decref操作一遍:

// dictobject.c
static int
dict_traverse(PyObject *op, visitproc visit, void *arg)
{
    Py_ssize_t i = 0;
    PyObject *pk;
    PyObject *pv;

    while (PyDict_Next(op, &i, &pk, &pv)) {
        visit(pk);
        visit(pv);
    }
    return 0;
}

然后根据引用计数副本值是否为0将集合内的对象分成两类,reachable和unreachable,其中unreachable是可以被回收的对象:

// gcmodule.c
static void
move_unreachable(PyGC_Head *young, PyGC_Head *unreachable)
{
    PyGC_Head *gc = young->gc.gc_next;
    while (gc != young) {
        PyGC_Head *next;
        if (gc->gc.gc_refs) {
            PyObject *op = FROM_GC(gc);
            traverseproc traverse = op->ob_type->tp_traverse;
            assert(gc->gc.gc_refs > 0);
            gc->gc.gc_refs = GC_REACHABLE;
            (void) traverse(op,
                            (visitproc)visit_reachable,
                            (void *)young);
            next = gc->gc.gc_next;
        }
        else {
            next = gc->gc.gc_next;
            gc_list_move(gc, unreachable);
            gc->gc.gc_refs = GC_TENTATIVELY_UNREACHABLE;
        }
        gc = next;
    }
}

在处理了weak reference和finalizer等琐碎细节后(本文不展开讲述,有兴趣的童鞋请参考python源码),就可以回收unreachable中的对象了。

分代回收

分代回收的整体思想是:将系统中的所有内存块根据其存活时间划分为不同的集合,每个集合就成为一个“代”,垃圾收集频率随着“代”的存活时间的增大而减小,存活时间通常利用经过几次垃圾回收来度量。

用来表示“代”的结构体是gc_generation, 包括了当前代链表表头、对象数量上限、当前对象数量:

// gcmodule.c
struct gc_generation {
    PyGC_Head head;
    int threshold; /* collection threshold */
    int count; /* count of allocations or collections of younger
              generations */
};

Python默认定义了三代对象集合,索引数越大,对象存活时间越长。

#define NUM_GENERATIONS 3
#define GEN_HEAD(n) (&generations[n].head)

/* linked lists of container objects */
static struct gc_generation generations[NUM_GENERATIONS] = {
    /* PyGC_Head,               threshold,  count */
    {{{GEN_HEAD(0), GEN_HEAD(0), 0}},   700,        0},
    {{{GEN_HEAD(1), GEN_HEAD(1), 0}},   10,     0},
    {{{GEN_HEAD(2), GEN_HEAD(2), 0}},   10,     0},
};

新生成的对象会被加入第0代,前面_PyObject_GC_Malloc中省略的部分就是Python GC触发的时机。每新生成一个对象都会检查第0代有没有满,如果满了就开始着手进行垃圾回收:

 g->gc.gc_refs = GC_UNTRACKED;
 generations[0].count++; /* number of allocated GC objects */
 if (generations[0].count > generations[0].threshold &&
     enabled &&
     generations[0].threshold &&
     !collecting &&
     !PyErr_Occurred()) {
          collecting = 1;
          collect_generations();
          collecting = 0;
 }

参考资料:

  1. 《Python源码剖析》,陈儒著,2008
  2. Wikipedia - Reference counting: http://en.wikipedia.org/wiki/Reference_counting
  3. Wikipedia - Garbage collection: http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)