‘壹’ 技术解析Transwarp Inceptor是怎样炼成的
技术解析Transwarp Inceptor是怎样炼成的
当前Hadoop技术蓬勃发展，用于解决大数据的分析难题的技术平台开始涌现。Spark凭借性能强劲、高度容错、调度灵活等技术优势已渐渐成为主流技术，业界大部分厂商都提供了基于Spark的技术方案和产品。根据Databricks的统计，目前有11个商业的Spark版本。
在使用Spark作出计算平台的解决方案中，有两种主流编程模型，一类是基于SparkAPI或者衍生出来的语言，另一种是基于SQL语言。SQL作为数据库领域的事实标准语言，相比较用API(如MapReceAPI，SparkAPI等)来构建大数据分析的解决方案有着先天的优势：一是产业链完善，各种报表工具、ETL工具等可以很好的对接;二是用SQL开发有更低的技术门槛;三是能够降低原有系统的迁移成本等。因此，SQL语言也渐渐成为大数据分析的主流技术标准。本文将深入解析Inceptor的架构、编程模型和编译优化技术，并提供基准测试在多平台上的性能对比数据。
1.Inceptor架构
TranswarpInceptor是基于Spark的分析引擎，如图1所示，从下往上有三层架构：最下面是存储层，包含分布式内存列式存储(TranswarpHolodesk)，可建在内存或者SSD上;中间层是Spark计算引擎层，星环做了大量的改进保证引擎有超强的性能和高度的健壮性;最上层包括一个完整的SQL99和PL/SQL编译器、统计算法库和机器学习算法库，提供完整的R语言访问接口。
TranswarpInceptor可以分析存储在HDFS、HBase或者TranswarpHolodesk分布式缓存中的数据，可以处理的数据量从GB到数十TB，即使数据源或者中间结果的大小远大于内存容量也可高效处理。另外TranswarpInceptor通过改进Spark和YARN的组合，提高了Spark的可管理性。同时星环不仅仅是将Spark作为一个缺省计算引擎，也重写了SQL编译器，提供更加完整的SQL支持。
同时，TranswarpInceptor还通过改进Spark使之更好地与HBase融合，可以为HBase提供完整的SQL支持，包括批量SQL统计、OLAP分析以及高并发低延时的SQL查询能力，使得HBase的应用可以从简单的在线查询应用扩展到复杂分析和在线应用结合的混合应用中，大大拓展了HBase的应用范围。
2.编程模型
TranswarpInceptor提供两种编程模型：一是基于SQL的编程模型，用于常规的数据分析、数据仓库类应用市场;二是基于数据挖掘编程模型，可以利用R语言或者SparkMLlib来做一些深度学习、数据挖掘等业务模型。
2.1SQL模型
TranswarpInceptor实现了自己的SQL解析执行引擎，可以兼容SQL99和HiveQL，自动识别语法，因此可以兼容现有的基于Hive开发的应用。由于TranswarpInceptor完整支持标准的SQL 99标准，传统数据库上运行的业务可以非常方便的迁移到Transwarp Inceptor系统上。此外Transwarp Inceptor支持PL/SQL扩展，传统数据仓库的基于PL/SQL存储过程的应用(如ETL工具)可以非常方便的在Inceptor上并发执行。另外Transwarp Inceptor支持部分SQL 2003标准，如窗口统计功能、安全审计功能等，并对多个行业开发了专门的函数库，因此可以满足多个行业的特性需求。
2.2数据挖掘计算模型
TranswarpInceptor实现了机器学习算法库与统计算法库，支持常用机器学习算法并行化与统计算法并行化，并利用Spark在迭代计算和内存计算上的优势，将并行的机器学习算法与统计算法运行在Spark上。例如：机器学习算法库有包括逻辑回归、朴素贝叶斯、支持向量机、聚类、线性回归、关联挖掘、推荐算法等，统计算法库包括均值、方差、中位数、直方图、箱线图等。TranswarpInceptor可以支持用R语言或者SparkAPI在平台上搭建多种分析型应用，例如用户行为分析、精准营销、对用户贴标签、进行分类。
3.SQL编译与优化
TranswarpInceptor研发了一套完整的SQL编译器，包括HiveQL解析器、SQL标准解析器和PL/SQL解析器，将不同的SQL语言解析成中间级表示语言，然后经过优化器转换成物理执行计划。SQL语言解析后经过逻辑优化器生成中间级表示语言，而中间表示语言再经过物理优化器生成最终的物理执行计划。从架构上分，逻辑优化器和物理优化器都包含基于规则的优化模块和基于成本的优化模块。
为了和Hadoop生态更好的兼容，Inceptor为一个SQL查询生成MapRece上的执行计划和Spark上的执行计划，并且可以通过一个SET命令在两种执行引擎之间切换。
3.1SQL编译与解析
TranswarpInceptor的SQL编译器会根据输入的SQL查询的类型来自动选择不同的解析器，如PL/SQL存储过程会自动进入PL/SQL解析器并生成一个SparkRDD的DAG从而在Spark平台上并行计算，标准SQL查询会进入SQL标准解析器生成Spark或MapRece执行计划。由于HiveQL和标准的SQL有所出入，为了兼容HiveQL，Transwarp Inceptor保留了HiveQL解析器，并可以对非标准SQL的Hive查询生成Spark或者Map Rece执行计划。
3.1.1SQL标准解析器
TranswarpInceptor构建了自主研发的SQL标准解析器，用于解析SQL99& SQL 2003查询并生成Spark和Map Rece的执行计划。词法和语法分析层基于Antlr语法来构建词法范式，通过Antlr来生成抽象语义树，并会通过一些上下文的语义来消除冲突并生成正确的抽象语义树。语义分析层解析上层生成的抽象语义树，根据上下文来生成逻辑执行计划并传递给优化器。首先Transwarp Inceptor会将SQL解析成TABLE SCAN、SELECT、FILTER、JOIN、UNION、ORDER BY、GROUP BY等主要的逻辑块，接着会根据一些Meta信息进一步细化各个逻辑块的执行计划。如TABLE SCAN会分成块读取、块过滤、行级别过滤、序列化等多个执行计划。
3.1.2PL/SQL解析器
PL/SQL是Oracle对SQL语言的模块化扩展，已经在很多行业中有大规模的应用，是数据仓库领域的重要编程语言。
为了让存储过程在Spark上有较好的性能，PL/SQL解析器会根据存储过程中的上下文关系来生成SQLDAG，然后对各SQL的执行计划生成的RDD进行二次编译，通过物理优化器将一些没有依赖关系的RDD进行合并从而生成一个最终的RDDDAG。因此，一个存储过程被解析成一个大的DAG，从而stage之间可以大量并发执行，避免了多次执行SQL的启动开销并保证了系统的并发性能。
解析并生成SQL级别的执行计划
3.2SQL优化器
TranswarpInceptor使用Spark作为默认计算引擎，并且开发了完善的SQL优化器，因此在大量的客户案例性能测试中，TranswarpInceptor的性能领先MapRece 10-100倍，并超越部分开源MPP数据库。SQL优化器对平台性能的提升居功至伟。
3.2.1基于规则的优化器(RuleBasedOptimizer)
目前为止，TranswarpInceptor共实现了一百多个优化规则，并且在持续的添加新的规则。按照功能划分，这些规则主要分布在如下几个模块：
文件读取时过滤
在文件读取时过滤数据能够最大化的减少参与计算的数据量从而最为有效的提高性能，因此TranswarpInceptor提供了多个规则用于生成表的过滤条件。对于一些SQL中的显示条件，TranswarpInceptor会尽量将过滤前推到读取表中;而对于一些隐式的过滤条件，如可以根据joinkey生成的过滤规则，Inceptor会根据语义保证正确性的前提下进行规则生成。
过滤条件前置
TranswarpInceptor能够从复杂的组合过滤条件中筛选出针对特定表的过滤规则，然后通过SQL语义来确定是否能将过滤条件前推到尽量早的时候执行。如果有子查询，过滤条件可以递归前推入最低层的子查询中，从而保证所有的冗余数据被删除。
超宽表的读取过滤
对一些列超多的表进行处理的时候，TranswarpInceptor首先会根据SQL语义来确定要读取的列，并在读取表的时候进行跨列读取减少IO和内存消耗。而如果表有过滤条件，Inceptor会做进一步优化，首先只读取过滤条件相关的列来确定该行记录是否需要被选择，如果不是就跳过当前行的所有列，因此能够最大程度上的减少数据读取。在一些商业实施中，这些优化规则能够带来5x-10x的性能提升。
Shuffle Stage的优化与消除
Spark的shuffle实现的效率非常低，需要把结果写磁盘，然后通过HTTP传输。TranswarpInceptor添加了一些shuffle消除的优化规则，对SQL的DAG中不必要或者是可以合并的shufflestage进行消除或者合并。对于必须要做Shuffle的计算任务，Inceptor通过DAGScheler来提高shuffle的效率：MapTask会直接将结果返回给DAGScheler，然后DAGScheler将结果直接交给Rece Task而不是等待所有Map Task结束，这样能够非常明显的提升shuffle阶段的性能。
Partition消除
TranswarpInceptor提供单一值Partition和RangePartition，并且支持对Partition建Bucket来做多次分区。当Partition过多的时候，系统的性能会因为内存消耗和调度开销而损失。因此，Inceptor提供了多个规则用于消除不必要的Partition，如果上下文中有隐式的对Partition的过滤条件，Inceptor也会生成对partition的过滤规则。
3.2.2基于成本的优化器(CostBasedOptimizer)
基于规则的优化器都是根据一些静态的信息来产生的，因此很多和动态数据相关的特性是不能通过基于规则的优化来解决，因此TranswarpInceptor提供了基于成本的优化器来做二次优化。相关的原始数据主要来自Meta-store中的表统计信息、RDD的信息、SQL上下文中的统计信息等。依赖于这些动态的数据，CBO会计算执行计划的物理成本并选择最有效的执行计划。一些非常有效的优化规则包括如下几点：
JOIN顺序调优
在实际的案例中，join是消耗计算量最多的业务，因此对join的优化至关重要。在多表JOIN模型中，TranswarpInceptor会根据统计信息来预估join的中间结果大小，并选择产生中间数据量最小的join顺序作为执行计划。
JOIN类型的选择
TranswarpInceptor支持Left-mostJoinTree 和 Bush Join Tree，并且会根据统计信息来选择生成哪种Join模型有最佳性能。此外，Transwarp Inceptor会根据原始表或者中间数据的大小来选择是否开启针对数据倾斜模型下的特殊优化等。此外，针对HBase表是否有索引的情况，Transwarp Inceptor会在普通Join和Look-up Join间做个均衡的选择。
并发度的控制
Spark通过线程级并发来提高性能，但是大量的并发可能会带来不必要的调度开销，因此不同的案例在不同并发度下会有最佳性能。TranswarpInceptor通过对RDD的一些属性进行推算来选择最佳并发控制，对很多的案例有着2x-3x的性能提升。
4.TranswarpHolodesk内存计算引擎
为了有效的降低SQL分析的延时，减少磁盘IO对系统性能的影响，星环科技研发了基于内存或者SSD的存储计算引擎TranswarpHolodesk，通过将表数据直接建在内存或者SSD上以实现SQL查询全内存计算。另外TranswarpHolodesk增加了数据索引功能，支持对多个数据列建索引，从而更大程度的降低了SQL查询延时。
4.1存储格式
TranswarpHolodesk基于列式存储做了大量的原创性改进带来更高的性能和更低的数据膨胀率。首先数据被序列化后存储到内存或SSD上以节省者资源占用。如图3所示，每个表的数据被存储成若干个Segment，每个Segment被划分成若干个Block，每个Block按照列方式存储于SSD或内存中。另外每个Block的头部都加上Min-MaxFilter和BloomFilter用于过滤无用的数据块，减少不必要的数据进入计算阶段。
TranswarpHolodesk根据查询条件的谓词属性对每个数据块的对应列构建数据索引，索引列采用自己研发的Trie结构进行组织存储，非索引列采用字典编码的方式进行组织存储。Trie不仅能对具有公共前缀的字符串进行压缩，而且可以对输入的字符串排序，从而可以利用二分查找快速查询所需数据的位置，从而快速响应查询需求。
HDFS2.6支持StorageTier让应用程序可以选择存储层为磁盘或者SSD，但是没有专用的存储格式设计是无法有效利用SSD的读写吞吐量和低延，因此现有的Text以及行列混合(ORC/Parquet)都不能有效的利用SSD的高性能。为此验证存储结构对性能的影响，我们将HDFS构建在SSD上并选用某基准测试来做了进一步的性能对比，结果如图4所示：采用文本格式，PCI-ESSD带来的性能提升仅1.5倍;采用专为内存和SSD设计的Holodesk列式存储，其性能相比较SSD上的HDFS提升高达6倍。
4.2性能优势
某运营商客户在12台x86服务器上搭建了TranswarpInceptor，将TranswarpHolodesk配置在PCIE-SSD上，并与普通磁盘表以及DB2来做性能对比测试。最终测试数据如图5所示：
在纯粹的count测试一项，Holodesk性能相对于磁盘表最高领先32倍;对于join测试一项，TranswarpHolodesk最高领先磁盘表多达12倍;在单表聚合测试中，Holodesk提升倍数达10~30倍。另外TranswarpHolodesk在和DB2的对比中也表现优秀，两个复杂SQL查询在DB2数据库中需要运行1小时以上，但是在使用TranswarpHolodesk均是分钟级和秒级就返回结果。
内存的价格大约是同样容量SSD的十倍左右，为了给企业提供更高性价比的计算方案，TranswarpHolodesk针对SSD进行了大量的优化，使得应用在SSD上运行具有与在内存上比较接近的性能，从而为客户提供了性价比更高的计算平台。
在对TPC-DS的IO密集型查询的测试中，无论上构建在PCI-ESSD还是内存上，Holodesk对比磁盘表有一个数量级上的性能提升;而SSD上的Holodesk性能只比内存差10%左右。
5.稳定的Spark执行引擎
企业目前应用开源Spark的主要困难在稳定性、可管理性和功能不够丰富上。开源Spark在稳定性上还有比较多的问题，在处理大数据量时可能无法运行结束或出现Outofmemory，性能时快时慢，有时比Map/Rece更慢，无法应用到复杂数据分析业务中。
TranswarpInceptor针对各种出错场景设计了多种解决方法，如通过基于成本的优化器选择最合适的执行计划、加强对数据结构内存使用效率的有效管理、对常见的内存出错问题通过磁盘进行数据备份等方式，极大提高了Spark功能和性能的稳定性，上述问题都已经解决并经过商业案例的考验。TranswarpInceptor能稳定的运行7*24小时，并能在TB级规模数据上高效进行各种稳定的统计分析。
6.SQL引擎效能验证
TPC-DS是TPC组织为DecisionSupportSystem设计的一个测试集，包含对大数据集的统计/报表生成/联机查询/数据挖掘等复杂应用，测试用的数据有各种不同的分布与倾斜，与真实场景非常接近。随着国内外各代表性的Hadoop发行版厂商以TPC-DS为标准测评产品，TPC-DS也就逐渐成为了业界公认的Hadoop系统测试准则。
6.1验证对比的平台和配置
我们搭建了两个集群分别用于TranswarpInceptor与ClouderaDataHub/Impala的测试。
6.2TranswarpInceptorVS Cloudera Impala
TranswarpInceptor由于有完善的SQL支持，能够运行全部所有的99个SQL查询。而由于Cloudera官方发布的TPC-DS测试集只包含19个SQL案例，因此我们只能运行这19个SQL，实验证明这部分查询在Impala上全部正常运行完成。
6.3TranswarpInceptorVS Map Rece
我们使用了同样的硬件和软件配置完成和开源的Hive执行效率相比，TranswarpInceptor能够带来10x-100x的性能提升。图8是TPC-DS的部分SQL查询在Inceptor和CDH5.1Hive的性能提升倍数，其中最大的提升倍数竟可达到123倍。
7.结语
随着在大数据领域国内外开始处于同一起跑线，我们相信像星环科技这样国内具有代表性的Hadoop发行版厂商将在中国的广阔市场空间中获得长足发展，并且由于中国市场激烈的竞争与磨练，逐步打磨出超越国外先进厂商的技术与实力。
刘汪根。2013年加入星环，作为早期员工参与了星环大数据平台的构建，现担任数据平台部研发经理，主要负责与管理星环大数据平台数据平台的研发工作，如SQL编译器，Spark执行引擎等工作，产品涵括TranswarpInceptor/TranswarpStream等软件。
【编者按】星环科技从2013年6月开始研发基于Spark的SQL执行引擎，在2013年底推出TranswarpInceptor1.0，并落地了国内首个7x24小时的商用项目。经过1年多的持续创新与改进，星环已经在国内落地了数十个Inceptor的商用项目。这是一篇星环Spark解决方案的技术解析，也是Spark用户可以效仿的优化之道。
‘贰’ 为什么有人说弄懂了《算法导论》的90%，就超越了90%的程序员
其实计算机程序底层核心就是各种数学算法，剩下就是怎么用代码去实现数学，世界上有名的计算机程序大牛几乎都跟数学权威方面的专家有关。
从另一个角度回答，因为就算看懂百分百，也很难超越另外的百分之十
很多程序员没读过算法导论
其实不管是对于在校生来说还是已经工作的程序员，一般很少都会接触算法。
学生的话也只有计算机相关专业的开设了数据结构和算法相关课程的才需要用到，但如果只是对付期末考试的话也没啥难度。
但是如果在大学期间接触到算法竞赛就不一样了，需要花费比较多的精力。
的确在工资上任何公司都是10%的算法大佬拿的工资比其他90%的业务开发程序员或者其他的程序员都要高，不过就凭只懂《算法导论》这本书的话还是不太行的，算法离不开业务的。就算超越也是超越那10%的算法工程师里的90%，如果能达到这个境界别说BAT了，微软谷歌都是可以考虑的。
说这个话在我看来他可能是想卖课，卖完再慢慢告诉你，“学到90％也没有那么容易”，或者“在刷我这套题这件事上超越90％的程序员 并不等于收入上超越90％的程序员”。
你多去拼多多参加几个活动，在文字 游戏 和预期管理上你应该就懂了；要是还不懂，大概你也不是那么适合做这一行以及算法导论。
公式：弄懂+一本名着+百分比+超越+百分比+你的群体。
例句：
弄懂sicp的67.9%，你就超越了95%的程序员。
弄懂本草纲目的72%，你就超越了93.7%的中医。
弄懂冰箱说明书的83%，你就超越了99.9%的冰箱使用者（这也许是最真实的，虽然冰箱说明书不是名着……）
至于为什么这么说……个人觉得就是对xx东西的一种崇拜，很大程度上是人云亦云。
算法导论是本不会动的书，不同人读效果不一样的。不要神化某一本书，参差多态乃幸福本源。不看算法导论你也可以会算法，你也可以会数据结构，你也可以进大厂。没有算法导论的时候也依然有研究算法的科学家。你能通过他学会知识很好，但你觉得它晦涩，搞不懂，没有c的代码让你学的不舒服，那就不看他。
人生中见书，书中见人生。读书有时候不一定是为了学东西，可能更多的是一种享受。就像你没学看过csapp之前，通过各种课程，学了零零碎碎的知识。忽然有一天你看了csapp，你觉得好过瘾啊，好爽啊。你觉得你学习的第一天就看csapp能有这种效果吗？
好书不会变少只会变多，更何况帮到你的也未必需要是好书。也许一本书只是很普通的书，不严谨，还都是大白话，但未必就帮不到你。
学东西莫要搞崇拜。很多程序员学习的时候都不是通过算法导论这本书学的，可他们依然很杰出。
程序员来回答一下：
1.《算法导论》这本书理论来说90%程序员也没弄懂，所以你弄懂了就超过了90%。
2.其实程序员是一个大的行业，IT也是一个大的行业，门外人看着都是一群写程序的，修电脑的，更有人认为是装电脑系统的，你被别人交过去装过系统吗？
3.程序员架构上来说，嵌入式 协议栈 应用 网络 服务器 工具 系统 等等等！
4.有一些行业是不需要看算法导论的，更有一些转行过来的，应该更不太了解算法导论。
这本书在美国的大学被称为clrs, 是标准的本科高年级和研究生入门的算法课课本。优点是比较全面的讲解了常用和基本的算法，习题质量不错。问题是动态规划讲的不好，篇幅原因一些近代的算法没有概括。总的来说是本不错的算法入门教科书。
算法是计算机科学的核心。计算理论偏数学，编译原理和操作系统偏硬件，真正计算机科学的核心就是算法。无论做研究还是搞工程，都是必不可少的。
程序是给人看的，不是给机器。写给机器的程序谁都可以写出来，但不是每个程序员都能写出别人看懂的东西
程序是什么，程序就是数据结构和算法，弄懂了超90%的程序员不是很正常嘛
看懂2%就超过了80%，没必要看那么多
因为这本书翻译的很枯燥、也很理解，这种情况下你还理解了90%，说明你有耐心，有恒心，耐得住寂寞。我相信不只是做程序员，做其它行业也会很优秀。