我希望

我希望我能做个明白人——知道我从哪来、站在哪里、要到哪去。能懂什么能让自己快乐而什么不能,看得清什么是幸福的根本,什么是多余的奖励。最重要的是,不要被任何外力所挟持而朝着我不要的终点狂奔。一定要一直明白呀,少年。

数据采集的优化之旅

最近在做一个数据同步的小工具,具体场景就是将某个数据库中的几张表,同步到另一个数据库中。

没有采取抓binlog的方式去做,一是解析binlog不是一个很简单的工作。二是对延迟的要求不是很高,2min是可接受范围。所以采取扫全表,全量同步的方式去做。

简单的业务代码写完,发现同步一张9w条数据的表,竟然TMD要近10分钟。立马检查代码的问题。首先要确认主要耗时的是SQL执行、还是在序列化阶段的耗时,通过Guava库中的stopwatch,很好的分析了各个阶段的耗时。惊奇的发现一个简单的SELECT查询,竟然扫了全表。立马检查表结果,发现select查询中的column并没有建立索引。这是踩的第一个坑。

解决了索引问题之后,测试之后,扫一张9w条数据的表耗时接近2min,然而我们线上环境,一张表的数据接近90w条,那么单线程扫一遍,耗时也将接近20min,同样是一个不可接受的时间。

自然而然地想到采用了多线程的方式去完成同步任务。首先,将数据分片,select min(id), max(id) from table;查询到主键最大、最小ID之后,将ID range到不同的线程去执行业务逻辑。

测试之后,发现有的线程耗时很低,有的线程耗时远远超过其他线程几个数量级的耗时。这时,多线程的耗时,取决于最长耗时。立马想到,主键id分布不是均匀的。

为了保证绝对的平均任务数,首先select count(*) from table;得到表中数据的数量之后,num = count / threadNums;相当于每个线程执行的row行数是相同的。select max(id) from (select id from table where id >= min order by id limit num) as t;这条SQL就拿到了每个线程的最大ID值。select * from table where id >= min and id < max;这样就得到了每个线程的数据。

测试之后,任务耗时接近9s,属于可接受范围。

做的一个小工具,也是学到了不少知识。还有很多值得优化的地方。

sql parser By ANTLR

Antlr

识别出所有有效的句子、词组、字词组等,识别语言的程序叫做解析器(Parser)或者语法分析器(syntax analyzer)。

  • recognize all the valid sentences and subphrase
  • parser of syntax analyzers: recognize languages
  • ANTLR meta-language
  • sentence as a input stream, look up words in dictionary

phrase 1:

  • lexical analysis: group characters into words or symbols(tokens)
  • lexer: group the related tokens into token classes or token types

phrase 2:

  • feed off these tokens to recognize the sentence structure
  • parse tree or syntax tree: ANTLR generated parsers build a data structure

basic data flow of a language recognizer

Implementing Parsers

  • recursive-descent parser -> kind of top-down parser implementation

  • graph traced out by invoking methods stat(), assign(), and expr() mirrors the interior parse tree nodes.

charStream -> tokenStream -> parse tree

parse-tree Listeners

ANTLR会为Token生成子类--parseTreeListener,并且实现了每个规则的进入和退出的方法。
ANTLR为每个Rule都会生成一个Context对象,它会记录识别时的所有信息。ANTLR提供了Listener和Visitor两种遍历机制。Listener是全自动化的,ANTLR会主导深度优先遍历过程,我们只需处理各种事件就可以了。而Visitor则提供了可控的遍历方式,我们可以自行决定是否显示地调用子结点的visit方法。

presto中ANTLR的应用

what is Presto?

Presto is an open source distributed SQL query engine for running interactive analytic queries against data sources of all sizes ranging from gigabytes to petabytes.

Presto was designed and written from the ground up for interactive analytics and approaches the speed of commercial data warehouses while scaling to the size of organizations like Facebook.

presto-parser

首先来看一下SqlBase.g4的内容,其中定义了SQL Base的TOKEN。

截取一部分

grammar SqlBase;  
tokens {  
    DELIMITER
}
singleStatement  
    : statement EOF
    ;
singleExpression  
    : expression EOF
    ;
statement  
    : query                                                            #statementDefault
    | USE schema=identifier                                            #use
    | USE catalog=identifier '.' schema=identifier                     #use
    | CREATE TABLE (IF NOT EXISTS)? qualifiedName
        (WITH tableProperties)? AS query
        (WITH (NO)? DATA)?                                             #createTableAsSelect
    | CREATE TABLE (IF NOT EXISTS)? qualifiedName
        '(' tableElement (',' tableElement)* ')'
        (WITH tableProperties)?                                        #createTable
    | DROP TABLE (IF EXISTS)? qualifiedName                            #dropTable
    | INSERT INTO qualifiedName columnAliases? query                   #insertInto
    | DELETE FROM qualifiedName (WHERE booleanExpression)?             #delete
    | ALTER TABLE from=qualifiedName RENAME TO to=qualifiedName        #renameTable
    | ALTER TABLE tableName=qualifiedName
        RENAME COLUMN from=identifier TO to=identifier                 #renameColumn
    | ALTER TABLE tableName=qualifiedName
        ADD COLUMN column=tableElement                                 #addColumn
    | CREATE (OR REPLACE)? VIEW qualifiedName AS query                 #createView
    | DROP VIEW (IF EXISTS)? qualifiedName                             #dropView
    | CALL qualifiedName '(' (callArgument (',' callArgument)*)? ')'   #call
    | GRANT
        (privilege (',' privilege)* | ALL PRIVILEGES)
        ON TABLE? qualifiedName TO grantee=identifier
        (WITH GRANT OPTION)?                                           #grant
    | REVOKE
        (GRANT OPTION FOR)?
        (privilege (',' privilege)* | ALL PRIVILEGES)
        ON TABLE? qualifiedName FROM grantee=identifier                #revoke
    | EXPLAIN ANALYZE?
        ('(' explainOption (',' explainOption)* ')')? statement        #explain

定义好g4之后,antlr会根据定义的Token生成对应的Parser。 包com.facebook.presto.parser.SqlParser中InvokeParser的实现:

private Node invokeParser(String name, String sql, Function<SqlBaseParser, ParserRuleContext> parseFunction)  
    {
        try {
            SqlBaseLexer lexer = new SqlBaseLexer(new CaseInsensitiveStream(new ANTLRInputStream(sql)));
            CommonTokenStream tokenStream = new CommonTokenStream(lexer);
            SqlBaseParser parser = new SqlBaseParser(tokenStream);
            parser.addParseListener(new PostProcessor());
            lexer.removeErrorListeners();
            lexer.addErrorListener(ERROR_LISTENER);
            parser.removeErrorListeners();
            parser.addErrorListener(ERROR_LISTENER);
            ParserRuleContext tree;
            try {          parser.getInterpreter().setPredictionMode(PredictionMode.SLL);
                tree = parseFunction.apply(parser);
            }
            catch (ParseCancellationException ex) {
                tokenStream.reset(); // rewind input stream
                parser.reset();
                parser.getInterpreter().setPredictionMode(PredictionMode.LL);
                tree = parseFunction.apply(parser);
            }
            return new AstBuilder().visit(tree);
        }
        catch (StackOverflowError e) {
            throw new ParsingException(name + " is too large (stack overflow while parsing)");
        }
    }

InvokeParser() 返回的是一个AST语法树。
ASTBuilder 类中定义了各个Node节点的访问方法。

罗茜计划

副标题是: 遇见一个合适的人有多难。

故事大致就是:

澳大利亚的大学遗传学副教授,智商无上限、情商无下限的39岁大龄单身男青年唐,为了解决找对象难题,决定启动寻妻计划。他誓要把找对象这件事当作一个科研项目来抓,认为只要设定足够合理的条件,收集足够丰富的样本,真爱就能跟基因研究一样结果妥妥地出现。青年唐开始了他笑点不断、感动不断的寻妻大作战!

从一开始,教授就定制了一个调查问卷。题目诸如:

  • 素食主义者 or 肉食主义者
  • 抽烟、喝酒、纹身(莫名想到我抽烟、我喝酒但我仍是个好女孩-。-)
  • 爱吃什么口味的冰淇淋
  • 等等等等

看到这里,我内心还是有那么一丝不解的。因为我好像从来就没有这些条条框框的东西。一路走来,我好像是一位一直去适应别人的人,不会有太多自己的立场。

直到唐遇到了罗茜,一个活生生把唐按时按点的生活敲地粉碎的人的出现,打乱了唐所有的计划。作为一个老教授,我相信唐还是会被罗茜吸引的。虽然,她只是个服务生,没有唐希望的高智商,甚至简单的数学计算都很困难。几年前,我还是一个希望能找个同是计算机专业的女朋友的。因为遇到太多太多的女同学们,问我,你们学计算机的、搞软件的是不是就是修电脑的。还有那种,听说你在A厂工作,你们买东西有没有内部折扣。。。每每遇到这样的"朋友",其实我很想一耳瓜子扇过去的。后来呢,我交了一个同样是做技术的女朋友。可是,做技术的都比较犟,谁都不服谁,为了一个问题会争吵不休。。。到了我现在这个年纪,我觉得我铺在工作上的心思已经太多了,不想要到家之后,仍然跟女朋友讨论“什么是面向对象编程”这种话题。

说到底,遇到一个合适的人,确实很难。最可怕的是,你根本不知道什么样的人才真的合适你。每个人都有自己的Rosie Project,个中滋味还是要自己体会的好。或许,这个Project,我会在最优化的过程中,越走越远呢。^_^

记阿里人工智能研讨会

题外话

之前没有了解过知识图谱,同样也是第一次参加研讨会。 总体而言,研讨会能够快速,高效地了解到学术界目前的研究方向。

Background

知识图谱,简而言之,就是以三元组代表(HeadEntity, Relationship, TailEntity)头实体,尾实体以及它们之间的关系。

知识图谱(Mapping Knowledge Domain)也被称为科学知识图谱,在图书情报界称为知识域可视化或知识领域映射地图,是显示知识发展进程与结构关系的一系列各种不同的图形,用可视化技术描述知识资源及其载体,挖掘、分析、构建、绘制和显示知识及它们之间的相互联系。

具体来说,知识图谱是通过将应用数学、图形学、信息可视化技术、信息科学等学科的理论与方法与计量学引文分析、共现分析等方法结合,并利用可视化的图谱形象地展示学科的核心结构、发展历史、前沿领域以及整体知识架构达到多学科融合目的的现代理论。它把复杂的知识领域通过数据挖掘、信息处理、知识计量和图形绘制而显示出来,揭示知识领域的动态发展规律,为学科研究提供切实的、有价值的参考。

Google知识图谱Wiki

其他代表知识库:

  1. WordNet
  2. Freebase

目前研究方向

分布式表示学习(distributed representation, embeddings)

主要研究思路: 将知识图谱嵌入到低维向量空间
  • 实体和关系都表示为低维向量
  • 有效表示和度量实体、关系间的语义关联

知识表示代表模型:

对每个事实(head, relation, tail),将relation看做从head到tail的翻译操作。

训练的优化目标为: h + r = t

此外还有Neural Tensor Network(NTN)以及Energy Model。 NTN Energy Model

表示学习在处理一对多、多对一、多对多的关系时,不能较好的处理。当出现多个结果时,每个结果的权重相当。

在TransE的基础上考虑关系对实体的影响

有以下两个典型的算法:

  • TransH
  • TransR

TransH TransR

Path Ranking

关系路径的表示学习: Recursive Neural Network(RNN)

考虑了关系路径的TransE算法为PTransE:

relation之间的组合语义,通常包括 ADD, MULTIPLY, RNN

通常关系之间的每个组合,需要单独训练一个目标函数。 在大规模复杂的知识图谱中,目标函数也会呈现指数级增长。

Probabilistic Graphical Models

这个算法,由于落地难的问题,大家都没有讲=.=

王志春-讲解了规则学习的几个方法:

  • 归纳逻辑程序设计 ILP
  • 类似数据挖掘中的关联规则
  • 关系路径
  • 分布式表示

韩先培-介绍了相关无监督语义关系抽取:

  • bootstrapping
  • distant supervision
  • Open IE(Stanford OpenIE)

写在最后

刘知远讲解的TransE非常的Solid,而且开源了算法实现https://github.com/thunlp/KG2E

王泉研究员,我只能献上我的膝盖了,语速很快,思路无敌清晰。简简单单的一个slide就能把当前知识图谱的研究方向洋洋洒洒的讲出来。

最后附上 刘知远的 ppt 大规模知识图谱的表示学习