1. 23 Nov 2014

    生成Java JDBC访问代码,从SQL文件

    JDBC访问数据库

    通过JDBC访问数据库,相信不少人都用过。比较辛苦,有很多的boilerplate。很多聪明的程序员也发现了这个问题,通过各种方式来解决这个问题(当然,他们也为了解决另外的问题, boilerplate是其中之一),比如Hibernate,iBATIS,JdbcTemplate(Spring),等等。这几种,各有各的优势,也有很多用户。

    最近在项目中,受Thrift,以及其它一些项目启发,试着写了一个程序,来自动生成JDBC的访问代码。

    SQL,简洁,表达力强

    SQL,表达能力强,没有多少boilerplate:

    SELECT isbn, title, price, price * 0.06 AS sales_tax
    FROM  Book WHERE price > 100.00 ORDER BY title limit 10;

    程序:函数,参数,返回值

    我们在写程序时,可能价格是个参数,还需要支持分页(limit, offset),返回的是List, 于是就是:

    func list<Book> getBooksByPrice(float price, i32 limit, i32 offset) {
      SELECT isbn, title, price, price * 0.06 AS sales_tax
      FROM  Book WHERE price > :price ORDER BY title limit :limit, :offset;
    }

    这段话,表达是清楚的,并且没有额外的“客套话”。 如果有一个程序,输入是上面的code,生成的code是可以直接被调用的函数,将是理想情况。

    java-jdbc

    这里有个问题,Book 未定义。当然,我们可以解析SQL语句,找到它来自 Book 表,继而contact数据库,找到Book表的metadata,能找到各个字段的数据类型, 就能定义Book了。如果这里面有Join的情况,会多联系几张表。 这样引入了联系数据库的依赖,增加依赖一般是需要再三考虑的。另外,解析SQL,找出字段的来源去脉,推断类型,不是一件简单的工作。

    但有个折中的办法,引入一些冗余(为什么是冗余呢?因为这个Book定义的信息是可以推导出来的)

    struct Book {
        string isbn
        string title
        float price
        float salesTax
    }

    虽加入了一些冗余,貌似还可以接受。

    我试着用Python写了这个程序 java-jdbc,输入是上面的代码,输出是Java代码(函数)。

    示例

    运行命令

    python java_jdbc.py --input example.sf --out gen-java

    就会在 gen-java目录生成访问数据库的代码。其中输入文件(example.sf):

    namespace java me.shenfeng
    
    struct Item {
        i32 id
        string name
    }
    
    // select
    func Item getItemById(i32 id) {
        select * form item where id = :id
    }
    func list<Item> getItems(int limit, int offset) {
        select * from item limit :limit, :offset
    }
    func list<Item> getItems(list<i32> ids) {
        select * from item where id in (:ids) order by FIELD(id, :ids)
    }
    
    // insert, return generated primary key
    func i32 saveItem(string name) {
        insert into item (name) value (:name)
    }
    
    // update
    func void updateItem(i32 id, string newName) {
        update item set name = :newName where id = :id
    }
    
    // delete
    func void deleteItemById(i32 id) {
        delete from item where id = :id
    }

    生成的API:

    2

    相比其它方案的优势,缺点,以及以后的方向

    相比Hibernate,iBATIS,JdbcTemplate(Spring),java-jdbc优点:

    1. 理解成本低,几乎是self-explained。
    2. runtime零依赖,生成的code不依赖任何第三方库
    3. 对join等支持良好,对各个数据库的“特殊” 特性,“原生”支持。
    4. 维护方便。维护SQL,几乎是最简单的,SQL的文档也很多。
    5. 实现简单 (300多行Python code)

    缺点:

    1. 有的同学不是很喜欢SQL
    2. 功能单一,有些挺实用的功能,比如cache机制,读写分离机制,并没有支持

    后面的方向嘛,由于这相当于定义了新的语言,可以通过扩展语言的方式,来扩展功能,比如

    // 最多cache 10000,通过lru策略淘汰,每个cache时间,最多3600s。 TODO
    @lru(size=10000, expire=3600s)
    func list<Book> getBooksByPrice(float price, i32 limit, i32 offset) {
      SELECT isbn, title, price, price * 0.06 AS sales_tax
      FROM  Book WHERE price > :price ORDER BY title limit :limit, :offset;
    }
  2. 02 Feb 2014

    诈金花各类别牌的概率分布:统计的方法

    过年,诈金花游戏

    大年初三,走亲访戚。弟弟女朋友到家串门,4人一起玩诈金花游戏打发时间。一连玩了好几把,没有赢过一次,全当陪练了:连对子都没来过。我好奇了,

    1. 抓到各类牌的概率是多少?
    2. 怎么样最大化赢的概率:在已知自己的牌,以及对方的出价的前提下,是应该跟/弃/加价?

    第一个问题是第二个的基础。每次选择都是一种冒险(除非手握3张A,这时需要的是诱导),但需要努力做到是caculated risk。

    相信是可以通过数学计算得出各类牌的概率。但对于我这样一个可以通过程序来奴役机器的程序员来说,另外一个自然的想法:让机器随机发牌,通过统计,来估算各类牌出现的概率,当样本空间足够大,统计结果会逼近理论值。

    结论

    每次发4个人的牌,随机发10万次,统计40万副牌中,各类的概率分布: one

    一个意外的有趣发现,牌面上,同花色顺子大,但出现概率上,顺子更小。同样的还有同花顺3同牌

    计算了德州扑克的概率分布:它的9种类别的牌的概率,严格按照递增顺序。似乎设计诈金花的人,概率差一点。德州扑克也更好玩:未来的不确定性,以及博弈。

    在n人的游戏中,发n副牌,最大的一副牌的类别的概率分布:

    2

    3

    4

    5

    6

    code

    发牌:一副牌,先洗牌,再从中抽出numhands份,各n张牌

    def deal(numhands, n=5, deck=[i + s for i in '23456789TJQKA' for s in "SHDC"]):
        "Shuffle the deck and deal out numhands n-card hands"
        random.shuffle(deck)
        return [deck[n * i:n * (i + 1)] for i in range(numhands)]

    计算牌面类别

    def jinhua_rank(hand):
        groups = group(["--23456789TJQKA".index(r) for r, s in hand])
        counts, ranks = unzip(groups)
        ranks = sorted(ranks, reverse=True)
    
        straight = len(set(ranks)) == 3 and (max(ranks) - min(ranks) == 2) # 顺子
        flush = len(set([s for r, s in hand])) == 1 # 同花
    
        if counts == (3, ):  # 3各牌,一样
            return 8, max(ranks)
        elif straight and flush: # 同花顺
            return 7, max(ranks)
        elif flush:  # 同花
            return 6, ranks
        elif straight:  # 顺子
            return 5, max(ranks)
        elif counts == (2, 1):  # 一对
            return 4, kind(2, ranks), ranks
        else: # 3单
            return 3, ranks

    辅助函数

    def group(items):
        groups = [(items.count(x), x) for x in set(items)]
        groups.sort(reverse=True)
        return groups
    
    def unzip(pairs): return zip(*pairs)
  3. 11 Jan 2014

    代理的代理:上网,抓取利器

    介绍

    做为一个网名,每天花不少时间浏览网页,由于某些原因,某些网站,在某个国家访问起来有困难。让人沮丧。采用过的方法,有如下几种:

    1. 使用代理(以及某些工具配合某些浏览器插件,如proxy switchy),缺点是,不是特别稳定。
    2. 使用VPN,速度慢,特别时访问国内的网站
    3. 有些公司,会在路由器或者网关上,做手脚。干净的解决这个问题

    另外最近打算加入一家创业公司,需要全网抓数据,并分析。数据也是对方的宝贵资源,不会轻易让你抓的,会通过各种方式封杀:比如ip rate limiting和user rate limiting等。要和对方斗志斗勇。

    今天周末,早上起床后,想着:我应该要解决这两个问题,要干净利落,透明。

    方案

    代理的代理,对代理进行负载均衡

    可以写一个程序,它自己是一个HTTP代理服务器,但相对于一般的代理服务器,它有几个特点:

    1. 程序部署在本地(或者内网,供家人或者团队使用)
    2. 对于国内的访问(比如baidu,youku,weibo等),它简单的代理请求,overhead小
    3. 对于国外的访问(比如某几个社交网站),它把收到的请求,转发给另外的代理服务器
    4. 维护一组代理服务器(数千个),对他们进行分组,进行负载均衡,代理切换等,减轻被IP rate limiting的机会,也加快速度
    5. 按照HTTP协议,cache一些资源(上网加速)
    6. 实现HTTP connect,用于支持HTTPS。由于内网使用,可以不做安全限制(比如仅允许433端口)

    这样,它既是一个上网加速器,还能助我透明畅游海外,并且减轻 crawler维护多代理,进行代理切换的工作。

    小文件整体cache到redis,大文件metadata存redis,文件存硬盘。哈哈,这样可以从硬盘上收割无数图片和视频,算是额外收获了。

    有点意思。

    可行性调研

    上午开始编码,通过实际写code,来验证可行性。HTTP 代理服务器比较简单,HTTP,SOCKS代理协议也比较容易实现。搞了几个小时,程序基本work,可以做到浏览twiter,并且上youku也很快。

    接下来工作

    完善code,让程序更强壮。还有cache到硬盘的图片,好好规划一下,方便收割。

  4. 04 Jan 2014

    小探Python内存使用overhead

    内存使用10倍以上,出乎预料

    周五在公司时,继续处理推荐相关的code,做物品之间的相似度矩阵计算:通过<用户,物品>矩阵,可以计算出物品(item)两两之间的相似度,生成相似度矩阵,它是协同过滤的基础数据。对每个物品,仅保留与它最相近的120个物品,以及相似度。程序用C++写的,加上用手工优化的hashmap,多核心同时计算,跑满8个CPU,2分钟左右可以算完600万左右的item的相似度计算。

    算完后,相似度关系存为binary的文件(为了快速load)。binary仅对机器友好,对人不友好。得想办法让人可以方便得查看。打算用tornado做一个web界面,可以随便点击查看,这样也给展示更详细得信息提供了可能性:物品以ID表示,如团购项目ID。web工具,可以通过查询数据库,显示团购项目的详细信息,如标题,价格,品类,销量,商家,地址等。这工具能方便我了解数据,培养sense,以及算法排查,领导查看也方便(相比于给领导一个binary文件,似乎给一个可以点击的URL靠谱一些)。

    由于相似度文件1G多一点(binary),C++ load到内存后,RAM在1.5G内。知道python耗内存,但开发机有16G内存,按照Python比C++多耗10倍计算,程序也能跑下来。基于这个考虑,迅速coding。C++load时,耗时在2s内,python慢悠悠的,30s还没有见停。浏览了会儿Hacker News。感觉机器卡:机器在辛苦的swap,Python进程已耗掉了12G+内存。果断kill -9

    Python耗内存,早有心理准备,但一个数量级的内存跑程序还困难,还是出乎了意料。

    C++处理

    相似度在文件和内存都是map的形式:

    # item_id 以及和它相似的 items,以及相似度score
    item_id => (item_id, score)+

    (item_id, score)在C++里面是一个struct:

    struct IdScore {
        int id;
        float score;
    };
    # 在内存中,耗掉8bytes
    sizeof(IdScore) => 8

    C++通过mmap文件,通过强制类型转化,把文件中bytes转成了IdScore array。简单迅速。

    通过sys.getsizeof查看对象大小

    Python没有那么方便,需要通过struct.unpack 成tuple。

    相对与C和C++里面的sizeof, Python里可以则是sys.getsizeof

    import sys
    sys.getsizeof((1, 1.0))  # 72

    有些出乎意料,tuple算是很节约的了,也需要72 字节,是C++的9倍。

    print sys.getsizeof([1, 1.0]) # 88 list。 list比tuple "贵" 一些
    print sys.getsizeof(1) # 24 int。int不便宜。
    print sys.getsizeof("") # 37 empty string。空字符串也要37 bytes,不便宜。
    print sys.getsizeof("abc") # 40 string with 3 chars
    
    class IdScore(object):
        def __init__(self, id, score):
            self.id = id
            self.score = score
    
    # 64。貌似比tuple少一点。那是假象,每个IdScore对象还包含一个__dict__
    # getsizeof 算 __dict__8个字节(一指针),但__dict__是独享,需要加进去
    # 可以通过__slots__ 节约 __dict__开销
    print sys.getsizeof(IdScore(1, 1.0))

    数字1耗掉了24字节,空字符串耗掉37字节。

    翻阅cpython源码

    Python 的 int 实际上是一个 struct PyIntObjectintobject.h#L23

    typedef struct {
        PyObject_HEAD
        long ob_ival;
    } PyIntObject;
    
    /* PyObject_HEAD 的定义,在 https://github.com/python/cpython/blob/2.7/Include/object.h#L65  */
    
    /* Define pointers to support a doubly-linked list of all live heap objects. */
    #define _PyObject_HEAD_EXTRA            \
        struct _object *_ob_next;           \
        struct _object *_ob_prev;

    两个指针,一个long,难怪有24bytes。

    Python的其它对象也有类似的struct结构(至少有PyObject_HEAD),不便宜。

    后记

    虽然Python多用了很多珍贵的内存,但开发迅速,能节约很多宝贵的时间(用少量的money换时间,早实践了。2年前为自己配的台式机,果断上i7 2600,16G。今年初入的Macbook Pro retina也是16G的配置,貌似是非定制化的顶配)

    能快速prototype,验证想法是非常重要的。

    一般情况下,程序的优化是可以通过重新设计数据结构达到的。这也不例外。想到了一个很简单的优化,让python也能用不到2G内存,处理这堆数据了:

    1. mmap 数据文件到内存为array
    2. 建立Index:map,存储 item_it => array的下标(和老版本不同,老版本是把数据 unpack 到内存了。
    3. 查询时,通过map查到下标,再通过struct.unpack 得到和它相似的其它 items,以及score
  5. 22 Dec 2013

    gperftools-httpd分析server性能杂记

    前记

    Redis 相信很多人很熟悉了:广泛使用key-value store,提供方便的访问Hash,List,Set等接口。Redis的通讯协议简洁,高效,并且客户端成熟。

    最近在写一个程序shenfeng/pedis,C++实现的一个Redis协议的server,封装facebook 的rocksdb,提供基于磁盘的List,Hash API(比如RPUSH,LRANGE,HSET,HGET,参见Redis的文档)。

    rocksdb继承于Gogole 的leveldb,是一个磁盘key-value lib,并提供了Merge-Operator 的支持,为实现高效率的基于磁盘List, Hash API创造了条件。

    pedis将是推荐系统的基础服务,提供以下功能:

    1. 存储每个user的历史行为:user和item的关系
    2. 快速提取user的行为:用户的历史决定了这个用户,是个性化算法的基础
    3. 定期dump <用户,行为>矩阵,用于离线模型训练

    曾用redis来存储用户的历史行为,无奈存储了10亿左右<用户,行为>对后,内存消耗大(20G),向公司要机器困难(相比于写code),嗨,公司对个性化推荐这块不舍得资源投入。无奈之余,花周末时间,写个pedis从根上解决内存资源少的问题。

    由于Redis的协议比较简单,今天周末,在家用C++实现了协议的Decode和Encode(有限状态机的方式,redis_proto.hpp),网络库采用的Redis的ae.c,server已经能跑起来了。用reids提供的redis-benchmark工具测试了一下性能,和redis-server相差不大,在i7-2600上,每秒能搞定200k次get,set请求。

    一时兴起,按照前一篇bloggperftools 初探 - gperftools-httpd介绍的方法,用gperftools跑了一下我的code和redis code:

    profile脚本

    # 启动redis-server,会启动一个http server,监听在9999端口,使得可以用pprof分析性能
    export LD_PRELOAD=/home/feng/workspace/gperftools-httpd-read-only/libghttpd-preload.so
    ./src/redis-server
    
    # 发出1千万get请求,50个长连接
    ./src/redis-benchmark -p 7389 -t get -n 10000000
    
    # 分析性能,生成svg调用关系和cost图
    google-pprof ./src/redis-server 'http://localhost:9999/pprof/profile'

    profile 结果

    1. 点击查看redis-server的profile结果
    2. 点击查看pedis-server的profile结果

    几个比较有意思的观察:

    1. redis-server, pedis-server每秒都可以处理200k次请求
    2. redis-server的结果中,epoll_ctlepoll_wait耗时都比较多,各7%-8%。但这是在每秒用户程序收发20万次请求的情况下。但正常的程序,很少有每秒这么大量的首发,所以epoll很难成为系统的瓶颈。
    3. 仔细观察pedis-server的结果,仅epoll_ctl耗时较多,epoll_ctl难觅踪影。原因是我做了一个特别的优化,在绝大部分情况下,可以省掉epoll_ctl的调用,并且可以降低latency(稍后会整理一个Pull Request,提给Redis)
    4. 没有竞争的锁,开销小。 pedis-server图中,有__pthread_之类条目,因为pedis-server将会是多线程的,每个写会加锁,但这个测试,server是单线程的,所以锁没有竞争。
    5. 两个程序中耗时最多的都是 __write_nocancel,50%左右,它是write(2),把数据包copy到TCP buffer里
    6. __read_nocancel也很耗时,占10%左右。它是read(2),从TCP buffer拷贝数据到用户程序的buffer

    redis-server中epoll_ctl耗时

    epoll_ctl

    pedis-server中epoll_ctl难觅踪影,epoll_wait耗时

    epoll_ctl