Author Topic: 【算法江湖】哈希之战  (Read 4227 times)

0 Members and 1 Guest are viewing this topic.

Offline Yao

  • Hero Member
  • *****
  • Posts: 534
    • View Profile
  • BitShares: yao
  • GitHub: imYao
:o
嚓,e神没策反几个技术牛来BitShares Community ?

Offline ebit

  • Committee member
  • Hero Member
  • *
  • Posts: 1905
    • View Profile
  • BitShares: ebit
书接上文

一夜过去了…孤独虎精神抖擞的回来了!
【书记员注:上集说到独孤虎被龙博两次判零分,已经到了精神分裂的边缘。于是他决定回家休养生息,以图再战。果不其然,第二天,独孤虎首先跳出来,带来了他的第四种方案。我们的眼睛又一次被他的长微信轰炸。。。】

独孤虎:昨天给出的第三个方案存在如下两个问题:
1)没有考虑结构体的填充问题,struct结构内的数据要对齐,从而导致其数据占有更大的内存;
2)CAS的操作受限,目前gcc仅仅针对1,2,4或8字节长度的int类型提供了CAS以及原子性
的加减逻辑运算;
3)没有考虑数据的读写原子性问题,有可能这个元素在同时读写,从而导致问题;改进之后第四种方法的核心思想是每个线程仅仅操作一个固定范围的数组,确保一个元素最多仅有一个线程在操作,从而保证操作的原子性。

下面给出第四种方案:
a)每个Node为一个进程,每个进程内K个线程,K与node内的CPU数量*每颗CPU内的核数相关;
b)线程按照线程池组织,采用K个无锁的队列实现生产者和消费者模式,即一个线程负责通过非阻塞的MPI接收请求,并将请求放入特定的队列中,而其他每一个线程读取特定队列中的请求,并执行具体的持仓记录操作;
c)NUMA架构的数据存放策略采用firsttouch,即通过hash将持仓记录划分到每个节点,确保每个节点仅仅操作本地内存;
采用一个非常大的数组D作为Hash表,表中的每个元素值包括(持仓类型,股东代码,股票代码,记录数据,count),如果存在key值冲突,则相同key的值连续放置,其中count表示后继节点有多少与之具有相同key的元素。其中股东代码可以表示为一个字节字符和四个字节无符号整数,共5个字节,股票代码表示为2个字节的无符号整数,股票持仓为8个字节整数,持仓类型和count公用一个字节(分别占用四位),因此采用如下的结构保存
struct record {
unsigned long compoundKey;
unsigned long data;
}
其中data表示股票持仓数据,而compoundKey为(持仓类型,股东代码,股票代码,count)的复用,其中最低四位表示count。将数组D划分为K段,每段由一个线程负责操作,即根据hash值确定所在范围,然后放入对应的队列中由对应的线程处理,由于确保了每个元素仅有一个线程操作,从而整个操作过程无需CAS或者枷锁。

1)插入操作,根据(持仓类型,股东代码,股票代码)计算key:如果D[key]所在位置的compoundKey非零,则冲突,查看下一个位置,即key+1位置,直到不冲突为止,即compoundKey为0时,对所在位置的元素赋值。
2)删除操作,如果要删除一个hash值为key的元素,则首先找到该元素所在位置key+m,m大于等于0。a)如果key+m所在位置的count为0,则直接赋值为0,并跳转到步骤c); b)如果key+m所在位置的count大于0,则逐次向后操作,将此位置设置为后继的、并且hash值为key的元素,直到hash值为key并且count值为0时结束,并跳转到步骤c);c)从此位置向前一直到key,将所有具有相同key所在位置的count减1。
3)更改操作/读取操作:比较简单。

这个方法,仅仅需要多个无锁队列,其他的操作即无需锁,也无需CAS。对数据和请求进行了两次划分,第一个次是根据hash将数据和请求划分到不同的节点(每个节点具有多个CPU,共享本地内存),第二次是根据hash将数据和请求划分到数组的不同位置段,并由不同线程负责操作

龙博:@独孤虎在接近正确答案。“部分”思路正确了。不过你不用考虑生产者消费者这种复杂的模型。要考虑如果让多个进程无锁同步地访问同一个大数组(哈希表),不要分区。

独孤虎(相当开心):我跟团队又讨论了一个下午。

龙博解密
龙博:如果你能设计出完全的无锁结构,就没必要做这个划分了。所以能够设计出完全的无锁数据结构,是关键。作为compound key的三部分,我已经告诉你每个部分的特征了,你试试看。

龙博:其实这个题目在白老师的发言里面已经给了一个很大的提示,哈希表。别看这个提示很小,绝大部分人连这一步都跨不过去。无锁数据结构的关键是什么?就是 key不要超出字长 ...在我们现在的机器上,字长就是8字,64bit...提示到这里,该做出来了吧...
龙博:因为只要你的key不超出字长,哈希表的新增、删除、修改操作都可以是原子操作。就是机器指令直接支持的原子操作,也就是“无锁”操作。哈希表的新增,删除和修改操作就是对这个8字进行赋值而已。。。明白了么?

【书记员注:我其实蛮失望的,原来最关键的地方就是拼一个64bit以内的Key,感觉像是郭靖的亢龙有悔,最厉害的一招就是最平淡无奇的一招!】

龙博:这是最核心的,说出来其实也很简单。我在总结一下,最关键的几部分:
1. 开放地址探测的哈希(非链式哈希!)
2. 哈希表的key值压缩在一个8字以内
3. 稍微特别考虑一下哈希表的删除(你得维护key冲突的时候的链条)

龙博:实际测试结果,一亿条记录,在哈希表的装载率(load factor)为70%的情况下,平均查询次数为1.1次,最大查询次数不超过4次。。这应该是最好的结果了。key+value 共16字节。这应该是最高效的存储结构了。

帮主:这么来说,这题的难点在哪?地址探测,最坏情况可能是 O (n)。所以关键是将key编码成64bits?根据那三种信息,不是显而易见的吗?我倒觉得,线性探测是核心,但那玩意有worstcase。独孤虎居然花了那么多时间,那么严肃的研究,感觉龙博在逗我们玩。

【书记员注:呵呵,帮主跟我一样,心有不甘,觉得自己败在了最平凡的一招上。】

龙博:用开放地址探测的散列,要保证在一定步数内找到一个空位,你必须让数组长度为一个质数。在装载率为70%的情况下,一个质数长度的数组,基本就是几步之内你就一定能找到一个空位。

帮主:好吧。关键是你怎么能控制一天的交易数?一开始开多大数组?万一当天的订单数好几亿,超出了数组容量呢?

龙博:一天的交易数有上限,到目前为止,还没突破过。但即使突破,交易系统后台会返回一个“技术错误“告诉券商这笔交易无法执行,但交易系统一切正常。包括内存被分配光也是一样,你要保证在极端情况下系统可以正常反应。

帮主:你说的一天可能上亿,整个都可能是新增的,对吗?

龙博:可以,因为这个哈希表增加一个元素的操作开销跟查询没什么分别。

【独孤虎团队,经过一番修整,终于给出了最终的第五个完美方案】
独孤虎:现设计数据结构如下:
struct record {
unsigned long compoundKey;
unsigned long data;
}
其中data表示股票持仓数据,而compoundKey为(股东代码,股票代码,持仓类型,flag)的复合体,股东代码占用最63~27位(5位字符和四个字节无符号整数),股票代码占26~11位(两个字节),持仓类型占用10~6位(四个字节),isTail占用第5位,表示是否为尾部,即后继元素中没有相同hash值的元素。doWrite占用第4位,表示该key正在更改/写入,readerCount占用3~0为表示该key正在读的线程数量。
采用非常大的数组,数组中的每个元素为struct record

具体操作如下:
1)插入操作,根据(持仓类型,股东代码,股票代码)计算hashkey:
a)如果D[key]所在位置doWrite为1,则循环判断,直到其值为0为止(在循环中采用cache操作,直接从内存读取doWrite),继续执行;
b)采用CAS操作,将doWrite设置为1,如果操作失败,则跳转到步骤a),如果成功,则继续执行;
c)如果readerCount非0,则循环等待,直到readerCount为0(在循环中采用cache操作,直接从内存读取);
d)如果readerCount为0,则从key开始连续查找到key相同并且isTail为1的元素,然后将其设置为0,并从后继元素找到第一个compoundKey为0的位置,并写入;
e)将doWrite为0,并采用cache操作,将其写回内存。

2)删除操作:如果要删除一个hash值为key的元素,其操作类似与插入操作,不同的地方是在获取doWrite和readerCount之后:
a)如果被删除元素的isTail为1,则从该位置开始到key进行查找,找到第一个
hash值为key的元素,将其的isTail设置为1;
b)如果被删除的元素的isTail为0,则需要继续查找,将其isTail为1并且hash值为
key的元素拷贝到这里,然后将原来尾部元素的上一个元素的isTail设置为1;

独孤虎收获满满,一掷千金
独孤虎(兴奋道):我们团队上可证NP,下可写哈希。

独孤虎:感谢龙博慷慨地贡献出一个如此优秀系统的核心算法!比如做大规模流量交易平台,算法相当重要。如果一天要处理百亿千亿次交易,就需要考虑系统核心算法的性能,而不仅仅是拼机器的数量和硬件性能。

独孤虎:我发个红包给群里所有人!!

【书记员注:独孤虎乃真土豪也,群里平均每个人收到了¥50...独孤虎在此次论战中表现出了超级的持久作战力,强大的团队协作精神,堪称“中国互联网之铁血军魂”!】

【书记员注:最后,本群创始人,院长,出来总结陈词,论功行赏。院长是网络系统安全界的超级高手,尤其精通PowerPC、MIPS、ARM这些RISC计算机系统!】

院长总结陈词
院长:
1. 龙博在巨大项目压力下,靠straightsmart能想出算法,并在白老师的鼓励和指导下,实践完成,为8年后的股波波的到来立下了卓越贡献。建议中央军委给予龙博记一等功,花翅一枚。

2. 帮主基础扎实,算法雄厚。由于长期在search领域,对hash算法,retrivial系统了若熊掌。非常的脚工赞。但由于他打酱油太多。窃以为龙博略微牛一些。

3. 独孤虎,从理论界,再次横空跨界。身体力行,团队作战。令人泣血。方案里有链表,有cas,还考虑了cache。深感算法设计课需要重新设计。手工赞!

院长最后科普了一下“原子操作”的概念:
原子操作与cpu强相关。不同的cpu实现的方式不一样。由于现代cpu都是load store模型。基本上可以理解对一个变量赋值需要:load;寄存器操作一哈;写回。所以,这3个指令之间可能中断,并发线程都有touch那个变量的可能,形成并发冲突。

现代cpu都会提供一些相关的指令,从而操作系统可以提供一些atomic原语,例如,add,set,dec,test等等。其实现原理是通过一些特殊的指令可以监视其他逻辑对一个memoryspace是否有touch,通过监控bus上的transaction。

简单说来,就是,如果我想own,我reserve这个mem。一旦reserve失败或者被abort,来回try。

史上最强之技术聊天,持续了两天半,以独孤虎团队的胜利告终。台上选手高声论战,台下群友默默潜水,虽然台下也有许多“高手”,但都怕一出声,不着调,毁了自己半生清誉。这也算是一道有趣的风景吧。

本次讨论,难得众高手相聚于“美丽互联”,正如古人所云:

“今番良晤,豪兴不浅,若得山水重逢,再当把酒言欢。”

是夜,暖风轻,圆月明,朋友聚还散,路人停复行。
telegram:ebit521
https://weibo.com/ebiter

Offline BTSdac

  • Hero Member
  • *****
  • Posts: 1219
    • View Profile
  • BitShares: K1
J 神,你的ID 可以转让了
github.com :pureland
BTS2.0 API :ws://139.196.37.179:8091
BTS2.0 API 数据源ws://139.196.37.179:8091

Offline sudo

  • Hero Member
  • *****
  • Posts: 2255
    • View Profile
  • BitShares: ags
坚定持有,守得云开见月明。

Offline chamme

  • Full Member
  • ***
  • Posts: 66
    • View Profile
  • BitShares: chamme
看看,还是有很多人在踏踏实实做事的!高瞻远瞩,看好比特股!

Offline Musewhale

  • Hero Member
  • *****
  • Posts: 2881
  • 丑,实在是太丑了 !
    • View Profile
MUSE witness:mygoodfriend     vote for me

Offline wuyanren

  • Hero Member
  • *****
  • Posts: 589
    • View Profile

Offline ebit

  • Committee member
  • Hero Member
  • *
  • Posts: 1905
    • View Profile
  • BitShares: ebit
lmax介绍:http://martinfowler.com/articles/lmax.html
lmax源码:https://github.com/LMAX-Exchange
比特股2.0:每秒10万次转账的高性能和可扩展性
http://www.bts.hk/bts20-high-performance.html
每秒可以实现超过10万次转账

  为了给业界提供一个有可能代替现有的金融平台的方案,高性能的区块链技术对加密货币和智能合约平台来说是必须的。为了能够实现比VISA和MasterCard加起来每秒可以处理的交易数量更高的级别,比特股从底层开始重新设计。通过股份授权证明机制,比特股网络可以在平均一秒的时间内确认交易,唯一的限制只是光速。

 

总览

  要达到这个产业里面最顶级的性能,比特股借鉴了从LMAX交易所里面学到的经验。这个LMAX交易所可以在每秒内处理高达6百万次的交易。在这个经验里面,关键点是以下这些:
  1、将一切东西放在内存里面
  2、将核心的业务逻辑放到一个单线程里面
  3、将加密算法操作(哈希和签名)放在核心业务逻辑以外
  4、将校验的操作分成状态独立和状态依赖检查
  5、使用一种面向对象的数据模型

  通过遵守这些简单的规则,比特股在没有进行任何显著性优化工作的情况下就实现了每秒处理10万次转账的性能。如果有进一步的优化工作的话,会让比特股可以达到跟LMAX交易所相近的性能表现(即每秒600万次)。

  应该需要注意到,比特股达到的性能表现是高度依赖其中的一个兼容交易协议。如果想用业务逻辑运行在一个进行加密算法操作和用哈希识别器去调用所有对象的虚拟机上的话,是不可能去达到同样层级的性能表现的。区块链天生就是单线程的,而单核的CPU的性能是各种资源中最短缺的、最难扩展的一个方面。比特股设计成能够让这个单线程的执行达到极可能的高效。

 

背景
  区块链是一个下达关于确定去修改一个共享的全局状态交易的全球账本。这些交易中包含的命令可以改变其他交易的有效性。例如,你不能在你的支票存入生效前去从你的银行账户理解支取金钱。在能够影响一个特定的账户的所有先前交易都被处理之前,你不可能知道一个交易是否有效。

 
  如果两个无关联的账号没有共享任何通用的依赖关系的话,理论上这两个账号的交易可以是在同一时间进行处理的。实际上,在一个由具备仲裁条件的智能合约驱动的账本上识别哪些交易是真正独立存在的耗费是很棘手的。唯一的保证两个交易是真正独立存在的方法,是通过维护完全分离的账本,然后定期在它们之间传输价值。如果要用这种性能表现的权衡关系去打比方的话,可以像是非一致内存访问架构(Non-Uniform Memory Access ,NUMA)和一致内存访问架构(Uniform Memory Access ,UMA)之间的关系。

 
  实际上,一致内存访问架构对开发者来说是更容易去设计的,而且耗费更低。非一致内存访问架构通常是在建造超级计算机和大型计算机集群时作为不得已的方法去采用的。

 
  计算机产业逐渐意识到通过平行计算去实现性能的扩张并没有早期那么容易,毕竟那时候最需要做的事情只是提高处理器的频率而已。就是因为这个原因,处理器的设计者们在尝试去采用多线程设去提高性能之前都在拼命去提高单线程的性能。当多线程还不够的话,而且只有这样的话,集群计算这个方案才会被考虑。
很多加密货币产业的人在没有探索过在技术上一台电脑的单个核心能实现什么之前,就尝试通过用集群计算的方案去解决可扩展性的问题。

 

LMAX Disruptor分解器技术

  LMAX 分解器提供了一个在单线程上可以实现什么表现的学习例子。LMAX是一个针对终端顾客的交易平台,目标是成为世界上最快的交易所。它们一直很慷慨地将他们学到的东西公布出来。
这是它们架构的概要总览:

  业务逻辑处理器是所有顺序交易和订单匹配发生的地方。它是一个可以每秒处理百万级别订单的单线程。这个架构可以很容易地用在加密货币和区块链设计的领域。

  输入分解器扮演的角色是从很多来自不同源头的用户里面收集订单,然后分配给它们一个确定的顺序。当给它们分配好顺序后,它们会被复制、记录然后广播到很多冗余的业务逻辑处理器。输入分解器是高度并行的,而且容易分包到一个计算机集群系统中。

  当业务逻辑处理器处理完输入后,一个输出分解器负责通知那些关心结果的人。这也是一个高度并行的任务。

  最终,通过在业务逻辑处理器里使用单线程样品化处理器和Java虚拟机,LMAX可以在每秒内执行600万次交易。如果LMAX可以达到这个成绩,那么加密货币和智能合约平台平不需要在每秒连10个交易都不到的情况下去考虑集群网络方案。

 
高性能区块链

  要建造一个高性能的区块链,我们需要使用LMAX同样的技术。这是几个必须实现的事项:
将所有东西放在内存上,避免同步原语(锁定,原子操作),避免在业务逻辑处理器上不必要的计算。

  由于内存的设计是高度并行的,因此越来越便宜。追踪互联网上每个人的账户余额和权限所需要的数据量是可以放在小于1TB的RAM内存上,这用不到15000美元的价格就能买到了,而且可以装在商品化(高端)的服务器主板上。在这个系统被30亿人采用之前,这类硬件会在普通的桌面计算机里面看到。

 
  真正的瓶颈不是内存容量的需求,而是带宽的需求。在每秒100万次交易和每笔交易占256字节的情况下,网络会需要256MB每秒的数据量,即1Gbit/s的带宽。这样的带宽在普通的桌面计算机上并不是常见的。不过,这样的带宽只是二代互联网100Gbit/s带宽的一点而已。这个二代互联网被供应给超过210个美国教育机构、70家公司和45个非盈利机构和政府机构。

 
  另一句话说,区块链技术可以轻松将所有东西保存在内存里,而且如果设计的合理的话可以扩展到支持每秒百万级别的转账。

 

分配ID并避免哈希计算

  在单线程系统的系统里面,处理器周期是需要被保留的稀缺资源。传统的区块链设计使用加密算法基础上的哈希计算去生成一个全球独特的ID系统,以实现统计学上不会有碰撞的保证。进行这些哈希计算的问题是,它会耗用越来越多的内存和处理器周期。与一个直接的数组索引相比,这种方式会显著地占用更多处理器的时间去查找一个账户的记录。例如,64位的整数对比和操作起来都要比160位以上的ID更简单。更大的哈希ID机制意味着CPU缓存里面的空间更少了,而需要更多的内存。在现代的操作系统里不常访问的随机存储器是会被压缩的,不过哈希识别器是随机数,这是没法压缩的。

 
  幸好区块链给了我们一个在全球内分配独特的ID的方法,这些ID互相之间不会起冲突,因此完全避免使用像比特币地址那样的哈希算法为基础的识别器去引用一个账号、余额或者许可。

从业务逻辑处理器中去除签名校验

  所有在加密货币网络的交易依赖于用加密算法签名去校验权限。大部分情况下,请求的权限可以由其他交易的结果改变。这意味着在业务逻辑处理器里面,权限需要被定义成与加密算法计算无关的情况。

  要达到这个目的,所有的公钥需要分配一个独特的和不可代替的ID。当ID被分配后,输入分解器可以校验提供的签名与指定的ID是否匹配。当交易到达业务逻辑处理器后,只需要去检查ID就可以了。
这个同样的技术可以在拥有不可代替的静态ID的对象上实现去除前提条件检查。

为静态校验设计交易

  对交易来说,有很多特性是可以进行静态检查的,而不需要引用当前的全局状态。这些检查包括参数的范围检查、输入的去冗余和数组排序等。通常来说,有很多检查是可以被进行的,如果交易包含它“假设”是全局状态的数据的话。在这些检查被执行后,业务逻辑处理器必须要做的事情就只有去确保这些假设还是正确的,这个过程总结下来就是检查一个涉及交易签名时间的对象引用的修改时间戳。

 

智能合约

  很多区块链正在整合一种通用的脚本语言去定义所有的操作。这些设计最终将业务逻辑处理器定义为一个虚拟机,而所有的交易被定义为由这个虚拟机运行的脚本。这个方案有一个在真实处理器上的单线程性能极限,并且由于将所有东西强制通过一个虚拟处理器去执行,让问题更严重了。一个虚拟处理器即使用上了实施编译技术(JIT)也总会比一个真正的处理器要慢,不过计算速度并不是这种“任何东西都是一个脚本”方案的唯一问题。
当交易被定义在这么低的层次上,意味着静态检查和加密算法操作还是会被包含到业务逻辑处理的环节里,这也让会让整体的吞吐量降低。一个脚本引擎永远不应该要求执行一个加密算法签名检查的请求,即使这个请求是通过原生的机制实现的。

 
  根据我们从LMAX上学到的课程,我们知道一个为区块链设计的虚拟机应该考虑到单线程表现。这意味着在一开始就要为实施编译优化,而且最常用的智能合约应该通过区块链原生支持,而只有那些不常用的、定制的合约会运行在一个虚拟机上。这些定制的合约设计的时候要考虑性能,这意味着虚拟机应该将可以访问的内存范围限制到可以放在处理器缓存上的级别。

 

面向对象的数据模式

  在内存中保存所有东西的其中一个好处是,软件可以设计成模仿现实世界中数据的关系。这意味着业务逻辑处理器可以迅速根据内存内的指针去找到数据,而不是被迫去进行耗费高的数据库查询任务。这意味着数据不需要复制就能访问了,而且可以当场就被修改。这个优化提供了比任何数据库为基础的方案高一个数量级的性能表现。

 

交易大小

  一个每秒可以处理10万次交易的区块链在每一秒都会产生大量数据。在一些正在竞争的网络如瑞波和比特币里,平均交易的大小是250字节。而在比特股上,相似的交易仅仅是100个字节。换句话说,其他正在竞争的系统在同样数量的交易情况下需要2.5倍的带宽去处理。假设连接到互联网的带宽是1Gb/s,只需要0.1秒就可以将一个含有10万次交易的区块传播出去。竞争性的网络需要0.25秒。如果考虑到延迟和点对点网络的多次中转过程,很明显交易的大小会影响到区块的间隔,因此影响到确认的延迟。

 
  交易的大小通常是一个CPU必须在关键的通道上处理的数据数量的指标。因此,它可以显示出在在一个单线程里面CPU命中速度有多快。在所有的协议里面一些优化是可行的,如果假设所有的节点都有之前所有广播的交易,而且只需要一个转账ID的排序表去广播所有的区块。这将会是一个具体的实施细节。

 

结论

  设计一个高性能的区块链并不是什么火箭科学,而且既不需要复杂难懂的协议,也不需要在网络上的所有节点里分处理任务。反而,要建造一个高性能的区块链最需要的事情应该是在核心业务逻辑上去除与关键性、订单依赖性和评估无关的计算任务,并且设计一个可以帮助优化这些事项的协议。这就是比特股做了的事情。

原文:https://bitshares.org/technology/industrial-performance-and-scalability/

译者:打超人的小怪兽

稿源(译):比特股之家(http://www.bts.hk/bts20-high-performance.html)
telegram:ebit521
https://weibo.com/ebiter

Offline ebit

  • Committee member
  • Hero Member
  • *
  • Posts: 1905
    • View Profile
  • BitShares: ebit
telegram:ebit521
https://weibo.com/ebiter

Offline ebit

  • Committee member
  • Hero Member
  • *
  • Posts: 1905
    • View Profile
  • BitShares: ebit
http://mp.weixin.qq.com/s?__biz=MjM5ODIzNDQ3Mw==&mid=206981549&idx=1&sn=34e0fb7dd05b9b2db99ed49c1498aaee#rd
虽然下面的文字略有嘻哈的感觉,但我还是希望您在阅读之后,能够本着严肃的态度,来审视一番当今天下最有用的数据结构~哈希表(hash table)。因为,有人的地方就有江湖,有数据的地方就有哈希。

2015年,6月7日~6月9日,在史上最强计算机技术微信群里,发生了一场史诗级别的算法论战。

此战,因参与者阵容之强,脑洞之大,足可彪炳微信群聊史册。无论你是技艺精湛的码农,还是拼杀股市的大妈,这次讨论都可以令你受益匪浅。好了,在你准备浏览下述老少咸宜男女通杀的内容之前,请先记下这个微信群的大名~“美丽互联”。(有人问如何加入?此群逼格甚高,审核极严,但是关注“待字闺中”,你将离高手越来越近)

每场战争都有一个原因,管它是神仙打架,还是明星撕B。这场算法论战也无例外,起因嘛,很简单很money:上证指数突破5000点大关!

龙博下战书
上海证交所的白老师(白硕)在群聊里稍微夸奖了一下龙博当年设计的一个大数据查询系统,于是龙博兴奋地变身“龙霸”,在群里点燃了导火索。

龙博:虽然哈希算法是我做的事情里面极小的一部分,但确实是值得骄傲的一个小成就。我拿这个题目考了很多人,谷歌的,微软的,百度的,基本没有及格的,哈哈。曾经有一个谷歌的技术总监要挑战,方案直接被我判了零分。

【书记员(硅谷寒)注:龙博自我吹捧之形,已跃然纸上。要知道,群里谷歌微软的人不要太多,“帮主”本人就是Google出来的,刚好也混了个技术总监的头衔。】

龙博(开始下战书了):这个哈希算法和数据结构设计也有普适性,交易所内存大部分数据都用这个算法和数据结构进行管理。当上交所的方案是标准答案,看你们的答案与标准答案差异有多大。我就不提示了。有兴趣就挑战,做一个完整的方案出来,给我...

龙博:我稍微把这个哈希算法和数据结构希望解决的问题描述一下

上亿条持仓记录在内存里面需要进行管理,一个主机上可能有几十颗处理器,每个处理器绑定一个进程(可以看成是线程),这几十个进程需要同步地对这上亿条持仓记录进行查询、修改、删除和新增的操作,每个进程每秒需要做数百万次这样的操作。

每条持仓记录,由三个信息来定位(key):
持仓类型(一位字符,A~F),
股东代码(10位字符,第1位A~Z,后面9位是数字0~9),
股票代号(short类型)

被定位到的持仓记录是一个64bit的值(value)

帮主带头应战,哎...
帮主:就完美哈希了,剩下就是数组问题了,因为是有限集合和数值是预先知道的。【书记员注:这是本群陈帮主,搜索领域大牛。帮主在第一时间跳出来应战】

龙博:你计算一下你需要数据结构所需的内存资源,再评估一下运算开销,是否能达到性能要求。哈希算法本身没什么大不了,上交所现在用的哈希算法平均查找次数为1.1。关键是数据结构设计。【书记员注:龙博在此处已经提示了设计的关键点,但可惜的是,之后参与论战的人都忽略了。】

帮主: 1. (准备阶段)将已知的所有的 KEY 值传给PHF或MPHF生成算法,生成PHF或MPHF以及相应的数据;

2. (使用阶段)调用已有的PHF或MPHF以及相应的数据快速计算哈希值并进行相应的操作。使用MPHF,那么我们可以分配一个Long transactions[几亿],数组。

剩下的就是数组操作了。删除就是置零,其它就是修改Long的值。完毕。谢谢。
【书记员注:帮主一下子抛出来两个英文缩写PHF、MPHF,着实把龙博吓了一跳,其实就是“完美哈希函数”和“最小完美哈希函数”】
 
龙博:你把所有可能的KEY 都放进去了想想你要用多少内存?所以我给你零分。我们总共只有一亿条记录。

 
帮主:根据前一天的纪录,算一次MPHF,其它新增的放另一个hashtable。如果你说一天都是新增的,那么我们一个小时(x分钟),重算一次MPHF。其实龙博和我也没什么分歧,最后是不是转化为设计一个好的hash function?

【书记员注:不得不说,帮主是天分极强的人,其实,他现在的方案已经很接近最终上交所的方案了,只不过缺少了一点点“画龙点睛”的东西。下面,另一个大牛,独孤虎,要登场了。确切地说,是“大牛团队”,因为独孤虎不是一个人在战斗,他拉上了自己公司里的整个团队,来解答龙博的题目。】

独孤虎炫目登场,杯具了!
独孤虎:我给出的答案是:
1)采用hash:根据股票代码,将请求hash到特定CPU线程;
2)采用数组+hash+SkipList+hash:持仓类型数量固定,在每个线程(CPU)采用一个10个元素的数组,每个元素为针对于一个持仓类型的Skip List,Skip List的元素的key(用于排序)为股东代码。除了key之外,跳跃表中的每个元素包括一个hash,用于将股票代码映射到特定信息。

优化措施,根据访问热度为每个股票代码设置一个hot值,用于分散访问,但是会带来比较麻烦的数据同步问题。

算法的时间复杂度为O(1)+log(2*Mi/n)+O(1),其中Mi是特定持仓类型中股东代码的最大数量,n是线程或CPU数量。内存采用hash,文件采用B+树,所以采用hash是ok的,关键是采用何种数据结构降低操作的复杂度。只有完全采用数组,才会考虑稀疏性。这个是hash+数组+跳跃表+hash仅仅是针对于固定数量的持仓类型采用了数组。

需要额外的2*(持仓类型,股东代码,股票代码)数量的指针,每个指针64位计算,16*(持仓类型,股东代码,股票代码)个byte。

时间复杂度:O(1)+log(2*Mi/n)+O(1),其中Mi是特定持仓类型中股东代码的最大数量,n是线程或CPU数量空间复杂度:需要额外的2*(持仓类型,股东代码,股票代码)数量的指针,每个指针按照64位计算,需要16*(持仓类型,股东代码,股票代码)个byte实现hash的方法,我个人感觉这个不是重点,关键是降低复杂度,因为数量太庞大了,即使通过hash,数量依然很多,需要一种数据结构降低操作复杂度。

O(logN)是比较优化的了,能够做的就是通过何种方式降低这个N,比如通过数组或再加hash等。下面是pseudocodelonglong M=max((long long)持仓库类型.股东代码.股票代码);
1.
*p=malloc(M*sizeof(U));
memset(p,0,sizeof(U)*M);
while(Proc->lock(p))
do
read or write or change p
done

2. N=>CPU数
*p1=malloc(M/N*sizeof(U));
*p2=malloc(M/N*sizeof(U));
...
*p(N1)=
malloc(M/N*sizeof(U));
memset(p1,0,sizeof(U)*M/N);
memset(p2,0,sizeof(U)*M/N);
...
memset(p(n1),
0,sizeof(U)*M/N);
CPUi=>read or write or change p(((longlong)持仓库类型.股东代码.股票代码) mod M)

大型实时算法,就需要简单我估计他们的算法应该是hash+跳跃表,不同支出就是如何处理(持仓类型,股东代码,股票代码)这三个值作为hash和跳跃表的key

【书记员注:独孤虎用一篇超长微信,震撼登场,但杯具了...】
龙博(轻扫一眼):@独孤虎,你要回忆一下白老师讲过的,hash表每天只初始化一次。你用的数据结构太复杂了,而且锁的力度太大。你这种设计,如何做到每个进程(线程)与其他几十个线程同步地对这一亿条记录进行操作?没可能的。所以,我给你零分!

帮主(插话):用sharding保证无锁?

龙博(立刻否定):不用任何sharding,无锁的核心在数据结构设计。你可以想象一下,两个线程如何同步地对一个10个元素大小的数组进行无锁操作(增加、删除、修改、查询)。想通这个问题,你就知道我怎么做这个无锁设计的了。

帮主:一个是任务queue,然后thread pool。【书记员注:其实帮主偷偷地上微博,向广大网友征集答案,如何设计无锁结构,用两个线程操作10个元素的数组?】

龙博:我再给你们说一遍,数据是所有进程完全共享的,不做划分。任何一条记录在任何时候都可能被该物理机上的一个进程访问(包括修改、删除、新增)

擅长高性能多处理器系统设计的唐博登场
【书记员注:下面,另一大牛,唐博,要登场了。唐博在高性能多处理器系统的设计上,独树一帜。】

唐博:我们DDoS的处理也有类似的问题,早就有答案了。与之不同的是,hash key 是可变长的URL。可以理解为16150长度的字符。大家复习一下
1. atomic instruction
2. CAS primitive
然后再来讨论比较靠谱。

【书记员注:唐博一上来,就叫大家去复习功课。计算机系的小伙伴们,你们还记得原子指令和CAS原语吗?】

龙博:类似的内存数据管理技术,用到了交易系统的几乎所有的内存数据结构中。因此可以最大程度发挥CPU的运算能力,减小同步、进程切换的开销。全异步、无锁、用户态和核心态数据共享等技术。为了提高运算效率,我甚至连乘法都是自己实现。。。

书记员注:我硅谷寒搞了N年的芯片设计,觉得龙博这句“连乘法都是自己实现的”,有点儿吹牛了。他应该不知道怎么设计高速乘法器。估计他都不知道啥是booth multiplier?如何设计硬件pipeline?】

龙博:交易所交易系统,就是屠龙之技啊。。。呵呵。例如数组的查询,数据有key + payload。如果你把所有key放到一起,那么整个数组的key可能被装进cache中,这样查询效率就很高了。。。这个也经常要用

独孤虎回来了
独孤虎(憋了一下午,又和自己的团队有了新方案,再次发布超长微信):
整个问题划分为两个部分1)、2)和三个阶段a)、b)、c):
1)网络操作部分,负责接收请求和返回应答;
2)内存操作部分,负责内存持仓记录的操作;
a)接收服务请求>
b)操作持仓记录>
c)返回服务应答

对于网络操作部分:
因为a)为了避免操作的复杂性;b)采用非阻塞式,操作比较快,所以网络操作部分采用一个线程:a)监听、读取和写入三个socket操作采用EPOLL方式以非阻塞方式执行;b)一旦接收到服务请求,该线程根据服务请求中的(持仓类型,股东代码,股票代码)信息,通过hash将请求信息发送给对应的进程(节点),进程之间的通信方式采用非阻塞的MPI;c)在每个轮训周期内,通过MPI_Test过程测试是否返回操作应答,如果返回,则驱动执行socket写入操作。

对于内存操作部分,前提条件为NUMA架构。【书记员注:请大家复习NUMA】

a)每个Node为一个进程,每个进程内多个线程,线程数量与每个node内的CPU
数量*每颗CPU内的核数相关;
b)线程按照线程池组织,采用一个无锁的队列实现生产者和消费者模式,即一个线程负责通过非阻塞的MPI将请求放入队列中,而其他线程则分别读取,并执行具体的持仓记录操作;
c)NUMA架构的数据存放策略采用firsttouch,即通过hash将持仓记录划分到每个节点,确保每个节点仅仅操作本地内存;
由于分配到每个节点的记录数量还是非常庞大,需要有效的数据结构组织这些数据,可选方案有三种:
a)hash
b)balanced trees
c)Skip List

上述三种方案都有很多种不同lockfree的实现方式,只要拿来用就ok了,但是balanced trees的操作比较复杂一点,首先排除。只剩下hash和Skip List:a)hash的问题需要每个节点分配一个非常非常大的数组,并且保证hash表的负载比较合理,可以采用将持仓类型+股东代码+股票代码形成一个字符串,在采用Murmurhash3这类算法进行hash;b)采用Hash+Skip List,当难以保证hash表的负载比较平衡的时候,可以采用小一点的hash表,但是每个表的元素为一个Skip List。

两种方式,关键要考虑持仓记录的变动情况,如果变动情况,不影响hash的负载均衡,采用方案a)。否则,采用方案b)

无锁操作,采用CAS方式实现hash和skip list的方式很多,拿过来用就可以。无锁方案很多,如果采用java实现,比如生产和消费者模式,就可以采用disruptor。

龙博(估计没看完独孤虎的长文,一直攻击其数据结构设计):你说cas指令随便用,但前提是cas或者其他无锁的数据结构需要满足某些条件,你的数据结构能满足这些条件么?这些都是很重要的工程问题。不是说,有cas, 有很多无锁设计和实现,直接拿来用就行。。。

独孤虎(赞许道):龙博,你一招鲜,吃遍天。二十年后还靠无锁设计、CAS吃饭。

龙博:我现在已不靠这个吃饭,靠这个吹牛。。。

独孤虎(接着给方案):1)所有节点的操作的内存是本地的,无需操作其他节点内容;2)hash表是一个数组,数组中的不同元素可以并行操作;3)数组内的每一个元素是一个链表,仅仅在头部插入和内部删除,有多种无锁操作方案。

龙博(还是说独孤虎的数据结构不对):你想象一下,所有这些数据在共享内存里面。。。如果是链表,很难实现完全的无锁设计。~ 零分

独孤虎:一下午,还是零分,我哭!

独孤虎:如果不用链表:第一种方式是copy on write,hash包中的每个元素为指向一个数组的指针,当指向插入和删除操作时,采用内存copy这个数组操作,然后在这个副本上进行插入和删除操作,此种方式不是最优,但是最容易想到的。

第二种方式是采用无链表的hash,有两个数组,第一个数组H是一个Hash表,存放一个无符号整数,指向第二个数组的一个具体位置,第二个数组D是一个非常大的数组,数组中的每个元素包括(持仓类型,股东代码,股票代码,记录数据,next),其中next指向D中的另一个位置,从而模拟一个链表:
a)添加操作,一旦通过(持仓类型,股东代码,股票代码)计算出在数组A中key所指D的位置已经存在值,则在数组D中查到next为0的元素tail,并变化一下(持仓类型,股东代码,股票代码)重新计算自己的hash,并插入到D中,然后采用CAS方式将其位置添加到tail的next;
b)删除操作:删除一个位置d,则采用CAS方式将父亲p中的next指向自己的next即可。

Penny :独孤虎的角度基本是做一个erp系统的sense,不是做高性能系统的sense啊,链表内存分布都是飘的,咋缓存感知啊!【书记员注:Penny是新鲜出炉的清华计算机博士,其创办的公司,拥有世界上最多的人均IP数量。】

独孤虎:工作太努力容易精神分裂。你们知道吗?Jeff Hammerbacher在哈佛读书时就精神分裂,返校毕业后先是加入华尔街做量子码工,之后是Facebook的早期数据科学家,后来是cloudera的创始人,因为工作太疯狂,精神分裂了,现在投身于基于数据科学的疾病治疗,主要是免疫和药物及基因的关系,为病人做个性化治疗。

【书记员注:估计独孤虎快被龙博搞精神崩溃了,准备向Jeff Hammerbacher学习。独孤虎究竟有没有精神分裂呢?】

一夜过去了…孤独虎精神抖擞地回来了!
欲知后事如何,且听下回分解......
telegram:ebit521
https://weibo.com/ebiter