Tech Ideas

C++,Linux,Algorithm,Crypto,Lisp,etc

Python 自动翻译成 C++ ,彻底保证离线在线特征一致


一,问题背景

随着深度学习的广泛应用,在搜索引擎/推荐系统/机器视觉等业务系统中,越来越多的深度学习模型部署到线上服务。

机器学习模型在离线训练时,一般要将输入的数据做特征工程预处理,再输入模型在 TensorFlow PyTorch 等框架上做训练。

1.常见的特征工程逻辑

常见的特征工程逻辑有:

  1. 分箱/分桶 离散化
  2. log/exp 对数/幂等 math numpy 常见数学运算
  3. 特征缩放/归一化/截断
  4. 交叉特征生成
  5. 分词匹配程度计算
  6. 字符串分隔匹配判断tong
  7. 缺省值填充等
  8. 数据平滑
  9. onehot 编码,hash 编码等

这些特征工程代码,当然一般使用深度学习最主要的语言 python 实现。

二,业务痛点

离线训练完成,模型上线部署后,同样要用 C++ 重新实现 这些 python 的特征工程逻辑代码。

我们发现,“用 C++ 重新实现” 这个步骤,给实际业务带来了大量的问题:

  1. 繁琐,费时费力,极容易出现 python 和 C++ 代码不一致
  2. 不一致会直接影响模型在线上的效果,导致大盘业务指标不如预期,产生各种 bad case
  3. 不一致难以发现,无法测试,无法监控,经常要靠用户投诉反馈,甚至大盘数据异常才能发现

用 DAT 重实现 CppJieba 中文分词算法,降低 99% 内存消耗


一,问题背景

中文分词应用比较广泛的开源算法,是 jieba 结巴分词,结巴分词较高性能的实现是 C++ 版本的 CppJieba : https://github.com/yanyiwu/cppjieba

在实际使用 CppJieba 的过程中,我们发现 CppJieba 的内存占用比较高。

比如对一个 76W 词 大小 11MB 的词典 ,加载 2份 (比如为了支持平滑改动用户词典)就需要耗费 505MB内存。

这对一些多进程的后台服务,浪费大量内存,难以接受,因此这里希望削减内存耗费。

经过初步调查,确定改进方法,然后动手改造,最终把 505MB 缩减到了 4.7MB ,实现了 99% 内存降低

此处也有 issue 讨论 https://github.com/yanyiwu/cppjieba/issues/3

代码稍后可能会开源出来。

GB 规模语料上的高性能新词发现算法


分词是中文搜索的重要环节,目前分词算法已经比较成熟,分词错误的主要是由于未登录词。

因此发现业务领域语料库中的新词,减少未登录词,对改善搜索引擎的用户体验有重要意义。

新词发现的一种常用算法,是 matrix67 大神 2012 年提出的 《互联网时代的社会语言学:基于SNS的文本数据挖掘》 https://www.matrix67.com/blog/archives/5044

其主要思路,是统计语料中出现的所有 ngram 子字符串的凝固度,自由度,信息熵。

算法中需要统计所有 ngram 子字符串的 左熵右熵,实现该算法时,一般以子字符串为 key,用哈希表来存。

但随着语料库变大时,内存消耗变大,

比如之前的 python 版本实现,对 200MB 的语料,就需要约 30G 内存来存哈希表,

导致单机内存不足无法运行,而且对这样规模的语料库,算法需要跑一两天才能出结果。

这里我应用一些工程实现方面的技巧, 把用哈希表统计左熵右熵的计算,拆分成多个子哈希表,分批计算,并利用多核并行,大幅度优化了算法的性能。

最终实现了 GB 大小语料上的新词发现,并把运行时间缩减到了 30 分钟左右 。

https://github.com/hankcs/HanLP/wiki/%E6%96%B0%E8%AF%8D%E8%AF%86%E5%88%AB

TLS协议分析 与 现代加密通信协议设计

最近发现密码学很有意思,刚好还和工作有点关系,就研究了一下,本文是其中一部分笔记和一些思考。

密码学理论艰深,概念繁多,本人知识水平有限,错误难免,如果您发现错误,请务必指出,非常感谢!

本文禁止转载

本文目标:

  1. 学习鉴赏TLS协议的设计,透彻理解原理和重点细节
  2. 跟进一下密码学应用领域的历史和进展
  3. 整理现代加密通信协议设计的一般思路

本文有门槛,读者需要对现代密码学有清晰而系统的理解,建议花精力补足背景知识再读。本文最后的参考文献里有一些很不错的学习资料。

现代密码学实践指南[2015年]


本文介绍目前现代密码学的最先进技术, 前半部分主要翻译自 《Cryptographic Right Answers》,附上收集的资料,和byron个人的理解。

密码学理论艰深,概念繁多,本人知识水平有限,错误难免,如果您发现错误,请务必指出,非常感谢!


下文分类介绍在各种适用场景下,你应该使用的现代密码学算法

1. 加密数据 :

按照优先级,应该选择:

(1) 首选 NaCl库,或者libsodium库,使用里面的crypto_secretbox()/crypto_secretbox_open() 函数 (2) Chacha20-Poly1305 算法 (3) AES-GCM 算法

适用场景:当你需要避免把明文数据在网络上传输的时候。

以上3种算法,都是AEAD类的算法,AEAD是2015年最好的选择。 其中的(2)和(3)在结构上类似:一个流加密模式的算法,配合一个多项式结构的MAC。 (2)是一个流加密算法,配合一个为通用cpu优化的MAC算法, 对密码学库的实现者来说,Poly1305也比GCM更容易安全地实现。 AES-GCM是工业标准(TLS目前主要用的就是AES-GCM),现代CPU通常都有专门为AES-GCM设计的硬件指令,但是在没有硬件指令支持的CPU上(比如32位的arm),(3)性能低于(2)。

Nginx下配置高性能,高安全性的https TLS服务

下文以nginx为例,介绍如何部署一个高性能,高安全性的https服务器。

并附送一个优化出来的openssl编译脚本,可以编译出一个高性能,高安全性的openssl库,您可以直接复制粘贴使用。

此处直接给出实践指导,后续再写文章解释tls协议的这些原理细节。

nginx下https配置的优化点,主要有:

  1. session ticket
  2. session id cache
  3. ocsp stapling
  4. http KeepAlive
  5. ECDHE等ciphersuite优化
  6. openssl 编译优化

一, nginx https的配置

先贴一下nginx配置,如下。

是根据mozilla的权威文档 ,和生成工具(选择 nginx,intermediate ) 生成的配置为基础,加入session ticket等配置的结果

【翻译】密码学一小时必知

本文翻译了Colin Percival 于2010年在bsdcan的演讲ppt

原文标题:Everything you need to know about cryptography in 1 hour

演讲时间:May 13, 2010

原文在 https://www.bsdcan.org/2010/schedule/attachments/135_crypto1hr.pdf

演讲视频在 https://www.youtube.com/watch?v=jzY3m5Kv7Y8 ( 请自行翻墙 )

Colin Percival 是密码学方面的专家,FreeBSD项目的安全长官,Tarsnap在线备份服务的创始人,scrypt密钥衍生算法的作者,致力于改进软件中密码学的应用,向程序员传播密码学的正确使用。

【翻译/介绍】jump Consistent hash:零内存消耗,均匀,快速,简洁,来自Google的一致性哈希算法

简介

jump consistent hash是一种一致性哈希算法, 此算法零内存消耗均匀分配快速,并且只有5行代码

此算法适合使用在分shard的分布式存储系统中 。

此算法的作者是 Google 的 John Lamping 和 Eric Veach,论文原文在 http://arxiv.org/ftp/arxiv/papers/1406/1406.2294.pdf

完整代码:

JumpConsistentHash
1
2
3
4
5
6
7
8
9
int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        key = key * 2862933555777941757ULL + 1;
        j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
    }
    return b;
}

输入是一个64位的key,和桶的数量(一般对应服务器的数量),输出是一个桶的编号。

SSL/TLS CipherSuite 介绍

本文是关于SSL/TLS的 CipherSuite 的信息摘录,翻译。如有疑问,欢迎指出。

一,CipherSuite的概念

CipherSuite 这个名词目前没看到有好的中文翻译,个人觉得翻译成“加密算法套件”比较合适。Cipher泛指是密码学的加密算法,例如 aes, rsa, ecdh 等。 tls是由各类基础算法,作为原语组合而成。 一个CipherSuite是4个算法的组合:

  1. 1个authentication (认证)算法
  2. 1个encryption(加密)算法
  3. 1个message authentication code (消息认证码 简称MAC)算法
  4. 1 个key exchange(密钥交换)算法

Mock C++ Function for Unit Test

在单元测试中,我们需要提供业务逻辑的mock版本, 当业务逻辑实现为C++的virtual function时,这是很容易的,我们只需要写一个子类, 实现virtual function就行了,Google 的 gmock就针对这种情况设计。

可是,如果遗留代码中有一般C函数,非virtual的类成员函数,模板函数,inline函数,如何提供mock版本呢?

下面的代码用一点trick实现了上述函数的运行时mock。