史上最全“大数据”学习资源整理

  当前,整个互联网正在从IT时代向DT时代演进,大数据技术也正在助力企业和公众敲开DT世界大门。当今“大数据”一词的重点其实已经不仅在于数据规模的定义,它更代表着信息技术发展进入了一个新的时代,代表着爆炸性的数据信息给传统的计算技术和信息技术带来的技术挑战和困难,代表着大数据处理所需的新的技术和方法,也代表着大数据分析和应用所带来的新发明、新服务和新的发展机遇。

 

为了帮助大家更好深入了解大数据,云栖社区组织翻译了GitHub Awesome Big Data资源,供大家参考。本资源类型主要包括:大数据框架、论文等实用资源集合。\

 

资源列表:

 

关系数据库管理系统(RDBMS)

 

MySQL:世界最流行的开源数据库;

PostgreSQL:世界最先进的开源数据库;

Oracle 数据库:对象-关系型数据库管理系统。

 

框架

 

Apache Hadoop:分布式处理架构,结合了 MapReduce(并行处理)、YARN(作业调度)和HDFS(分布式文件系统);

Tigon:高吞吐量实时流处理框架。

 

分布式编程

 

AddThis Hydra :最初在AddThis上开发的分布式数据处理和存储系统;

AMPLab SIMR:用在Hadoop MapReduce v1上运行Spark;

Apache Beam:为统一的模型以及一套用于定义和执行数据处理工作流的特定SDK语言;

Apache Crunch:一个简单的Java API,用于执行在普通的MapReduce实现时比较单调的连接、数据聚合等任务;

Apache DataFu:由LinkedIn开发的针对Hadoop and 和Pig的用户定义的函数集合;

Apache Flink:具有高性能的执行时间和自动程序优化;

Apache Gora:内存中的数据模型和持久性框架;

Apache Hama:BSP(整体同步并行)计算框架;

Apache MapReduce :在集群上使用并行、分布式算法处理大数据集的编程模型;

Apache Pig :Hadoop中,用于处理数据分析程序的高级查询语言;

Apache REEF :用来简化和统一低层大数据系统的保留性评估执行框架;

Apache S4 :S4中流处理与实现的框架;

Apache Spark :内存集群计算框架;

Apache Spark Streaming :流处理框架,同时是Spark的一部分;

Apache Storm :Twitter流处理框架,也可用于YARN;

Apache Samza :基于Kafka和YARN的流处理框架;

Apache Tez :基于YARN,用于执行任务中的复杂DAG(有向无环图);

Apache Twill :基于YARN的抽象概念,用于减少开发分布式应用程序的复杂度;

Cascalog:数据处理和查询库;

Cheetah :在MapReduce之上的高性能、自定义数据仓库;

Concurrent Cascading :在Hadoop上的数据管理/分析框架;

Damballa Parkour :用于Clojure的MapReduce库;

Datasalt Pangool :可选择的MapReduce范例;

DataTorrent StrAM :为实时引擎,用于以尽可能畅通的方式、最小的开支和对性能最小的影响,实现分布式、异步、实时的内存大数据计算;

Facebook Corona :为Hadoop做优化处理,从而消除单点故障;

Facebook Peregrine :MapReduce框架;

Facebook Scuba :分布式内存数据存储;

Google Dataflow :创建数据管道,以帮助其分析框架;

Netflix PigPen :为MapReduce,用于编译成Apache Pig;

Nokia Disco :由Nokia开发的MapReduc获取、转换和分析数据;

Google MapReduce :MapReduce框架;

Google MillWheel :容错流处理框架;

JAQL :用于处理结构化、半结构化和非结构化数据工作的声明性编程语言;

Kite :为一组库、工具、实例和文档集,用于使在Hadoop的生态系统上建立系统更加容易;

Metamarkets Druid :用于大数据集的实时e框架;

Onyx :分布式云计算;

Pinterest Pinlater :异步任务执行系统;

Pydoop :用于Hadoop的Python MapReduce和HDFS API;

Rackerlabs Blueflood :多租户分布式测度处理系统;

Stratosphere :通用集群计算框架;

Streamdrill :用于计算基于不同时间窗口的事件流的活动,并找到最活跃的一个;

Tuktu :易于使用的用于分批处理和流计算的平台,通过Scala、 Akka和Play所建;

Twitter Scalding:基于Cascading,用于Map Reduce工作的Scala库;

Twitter Summingbird :在Twitter上使用Scalding和Storm串流MapReduce;

Twitter TSAR :Twitter上的时间序列聚合器。

 

分布式文件系统

 

Apache HDFS:在多台机器上存储大型文件的方式;

BeeGFS:以前是FhGFS,并行分布式文件系统;

Ceph Filesystem:设计的软件存储平台;

Disco DDFS:分布式文件系统;

Facebook Haystack:对象存储系统;

Google Colossus:分布式文件系统(GFS2);

Google GFS:分布式文件系统;

Google Megastore:可扩展的、高度可用的存储;

GridGain:兼容GGFS、Hadoop内存的文件系统;

Lustre file system:高性能分布式文件系统;

Quantcast File System QFS:开源分布式文件系统;

Red Hat GlusterFS:向外扩展的附网存储(Network-attached Storage)文件系统;

Seaweed-FS:简单的、高度可扩展的分布式文件系统;

Alluxio:以可靠的存储速率在跨集群框架上文件共享;

Tahoe-LAFS:分布式云存储系统;

 

文件数据模型

 

Actian Versant:商用的面向对象数据库管理系统;

Crate Data:是一个开源的大规模可扩展的数据存储,需要零管理模式;

Facebook Apollo:Facebook的Paxos算法,类似于NoSQL数据库;

jumboDB:基于Hadoop的面向文档的数据存储;

LinkedIn Espresso:可横向扩展的面向文档的NoSQL数据存储;

MarkLogic:模式不可知的企业版NoSQL数据库技术;

MongoDB:面向文档的数据库系统;

RavenDB:一个事务性的,开源文档数据库;

RethinkDB:支持连接查询和群组依据等查询的文档型数据库。

 

Key Map 数据模型

 

注意:业内存在一些术语混乱,有两个不同的东西都叫做“列式数据库”。这里列出的有一些是围绕“key-map”数据模型而建的分布式、持续型数据库,其中所有的数据都有(可能综合了)键,并与映射中的键-值对相关联。在一些系统中,多个这样的值映射可以与键相关联,并且这些映射被称为“列族”(具有映射值的键被称为“列”)。

另一组也可称为“列式数据库”的技术因其存储数据的方式而有别于前一组,它在磁盘上或在存储器中——而不是以传统方式,即所有既定键的键值都相邻着、逐行存储。这些系统也彼此相邻来存储所有列值,但是要得到给定列的所有值却不需要以前那么繁复的工作。

前一组在这里被称为“key map数据模型”,这两者和Key-value 数据模型之间的界限是相当模糊的。后者对数据模型有更多的存储格式,可在列式数据库中列出。若想了解更多关于这两种模型的区分,可阅读Daniel Abadi的博客:Distinguishing two major types of Column Stores。

Apache Accumulo:内置在Hadoop上的分布式键/值存储;

Apache Cassandra:由BigTable授权,面向列的分布式数据存储;

Apache HBase:由BigTable授权,面向列的分布式数据存储;

Facebook HydraBase:Facebook所开发的HBase的衍化品;

Google BigTable:面向列的分布式数据存储;

Google Cloud Datastore:为完全管理型的无模式数据库,用于存储在BigTable上非关系型数据;

Hypertable:由BigTable授权,面向列的分布式数据存储;

InfiniDB:通过MySQL的接口访问,并使用大规模并行处理进行并行查询;

Tephra:用于HBase处理;

Twitter Manhattan:Twitter的实时、多租户分布式数据库。

 

键-值数据模型

 

Aerospike:支持NoSQL的闪存优化,数据存储在内存。开源,“’C'(不是Java或Erlang)中的服务器代码可精确地调整从而避免上下文切换和内存拷贝”。

Amazon DynamoDB:分布式键/值存储,Dynamo论文的实现;

Edis:为替代Redis的协议兼容的服务器;

ElephantDB:专门研究Hadoop中数据导出的分布式数据库;

EventStore:分布式时间序列数据库;

GridDB:适用于存储在时间序列中的传感器数据;

LinkedIn Krati:简单的持久性数据存储,拥有低延迟和高吞吐量;

Linkedin Voldemort:分布式键/值存储系统;

Oracle NoSQL Database:Oracle公司开发的分布式键值数据库;

Redis:内存中的键值数据存储;

Riak:分散式数据存储;

Storehaus:Twitter开发的异步键值存储的库;

Tarantool:一个高效的NoSQL数据库和Lua应用服务器;

TiKV:由Google Spanner和HBase授权,Rust提供技术支持的分布式键值数据库;

TreodeDB:可复制、共享的键-值存储,能提供多行原子写入。

 

图形数据模

 

Apache Giraph:基于Hadoop的Pregel实现;

Apache Spark Bagel:可实现Pregel,为Spark的一部分;

ArangoDB:多层模型分布式数据库;

DGraph:一个可扩展的、分布式、低时延、高吞吐量的图形数据库,旨在为Google生产水平规模和吞吐量提供足够的低延迟,用于TB级的结构化数据的实时用户查询;

Facebook TAO:TAO是facebook广泛用来存储和服务于社交图形的分布式数据存储;

GCHQ Gaffer:GCHQ中的Gaffer是一个易于存储大规模图形的框架,其中节点和边缘都有统计数据;

Google Cayley:开源图形数据库;

Google Pregel :图形处理框架;

GraphLab PowerGraph:核心C ++ GraphLab API和建立在GraphLab API之上的高性能机器学习和数据挖掘工具包的集合;

GraphX:Spark中的弹性分布式图形系统;

Gremlin:图形追踪语言;

Infovore:以RDF为中心的Map / Reduce框架;

Intel GraphBuilder:在Hadoop上构建大规模图形的工具;

MapGraph:用于在GPU上大规模并行图形处理;

Neo4j:完全用Java写入的图形数据库;

OrientDB:文档和图形数据库;

Phoebus:大型图形处理框架;

Titan:建于Cassandra的分布式图形数据库;

Twitter FlockDB:分布式图形数据库。

 

NewSQL数据库

 

Actian Ingres:由商业支持,开源的SQL关系数据库管理系统;

Amazon RedShift:基于PostgreSQL的数据仓库服务;

BayesDB:面向统计数值的SQL数据库;

CitusDB:通过分区和复制横向扩展PostgreSQL;

Cockroach:可扩展、地址可复制、交易型的数据库;

Datomic:旨在产生可扩展、灵活的智能应用的分布式数据库;

FoundationDB:由F1授意的分布式数据库;

Google F1:建立在Spanner上的分布式SQL数据库;

Google Spanner:全球性的分布式半关系型数据库;

H-Store:是一个实验性主存并行数据库管理系统,用于联机事务处理(OLTP)应用的优化;

Haeinsa:基于Percolator,HBase的线性可扩展多行多表交易库;

HandlerSocket:MySQL/MariaDB的NoSQL插件;

InfiniSQL:无限可扩展的RDBMS;

MemSQL:内存中的SQL数据库,其中有优化的闪存列存储;

NuoDB:SQL / ACID兼容的分布式数据库;

Oracle TimesTen in-Memory Database:内存中具有持久性和可恢复性的关系型数据库管理系统;

Pivotal GemFire XD:内存中低延时的分布式SQL数据存储,可为内存列表数据提供SQL接口,在HDFS中较持久化;

SAP HANA:是在内存中面向列的关系型数据库管理系统;

SenseiDB:分布式实时半结构化的数据库;

Sky:用于行为数据的灵活、高性能分析的数据库;

SymmetricDS:用于文件和数据库同步的开源软件;

Map-D:为GPU内存数据库,也为大数据分析和可视化平台;

TiDB:TiDB是分布式SQL数据库,基于谷歌F1的设计灵感;

VoltDB:自称为最快的内存数据库。

 

列式数据库

 

注意:请在键-值数据模型 阅读相关注释。

Columnar Storage:解释什么是列存储以及何时会需要用到它;

Actian Vector:面向列的分析型数据库;

C-Store:面向列的DBMS;

MonetDB:列存储数据库;

Parquet:Hadoop的列存储格式;

Pivotal Greenplum:专门设计的、专用的分析数据仓库,类似于传统的基于行的工具,提供了一个列式工具;

Vertica:用来管理大规模、快速增长的大量数据,当用于数据仓库时,能够提供非常快的查询性能;

Google BigQuery :谷歌的云产品,由其在Dremel的创始工作提供支持;

Amazon Redshift :亚马逊的云产品,它也是基于柱状数据存储后端。

 

时间序列数据库

 

Cube:使用MongoDB来存储时间序列数据;

Axibase Time Series Database:在HBase之上的分布式时间序列数据库,它包括内置的Rule Engine、数据预测和可视化;

Heroic:基于Cassandra和Elasticsearch的可扩展的时间序列数据库;

InfluxDB:分布式时间序列数据库;

Kairosdb:类似于OpenTSDB但会考虑到Cassandra;

OpenTSDB:在HBase上的分布式时间序列数据库;

Prometheus:一种时间序列数据库和服务监测系统;

Newts:一种基于Apache Cassandra的时间序列数据库。

 

类SQL处理

 

Actian SQL for Hadoop:高性能交互式的SQL,可访问所有的Hadoop数据;

Apache Drill:由Dremel授意的交互式分析框架;

Apache HCatalog:Hadoop的表格和存储管理层;

Apache Hive:Hadoop的类SQL数据仓库系统;

Apache Optiq:一种框架,可允许高效的查询翻译,其中包括异构性及联合性数据的查询;

Apache Phoenix:Apache Phoenix 是 HBase 的 SQL 驱动;

Cloudera Impala:由Dremel授意的交互式分析框架;

Concurrent Lingual:Cascading中的类SQL查询语言;

Datasalt Splout SQL:用于大数据集的完整的SQL查询工具;

Facebook PrestoDB:分布式SQL查询工具;

Google BigQuery:交互式分析框架,Dremel的实现;

Pivotal HAWQ:Hadoop的类SQL的数据仓库系统;

RainstorDB:用于存储大规模PB级结构化和半结构化数据的数据库;

Spark Catalyst:用于Spark和Shark的查询优化框架;

SparkSQL:使用Spark操作结构化数据;

Splice Machine:一个全功能的Hadoop上的SQL RDBMS,并带有ACID事务;

Stinger:用于Hive的交互式查询;

Tajo:Hadoop的分布式数据仓库系统;

Trafodion:为企业级的SQL-on-HBase针对大数据的事务或业务工作负载的解决方案。

 

数据摄取

 

Amazon Kinesis:大规模数据流的实时处理;

Apache Chukwa:数据采集系统;

Apache Flume:管理大量日志数据的服务;

Apache Kafka:分布式发布-订阅消息系统;

Apache Sqoop:在Hadoop和结构化的数据存储区之间传送数据的工具;

Cloudera Morphlines:帮助 Solr、HBase和HDFS完成ETL的框架;

Facebook Scribe:流日志数据聚合器;

Fluentd:采集事件和日志的工具;

Google Photon:实时连接多个数据流的分布式计算机系统,具有高可扩展性和低延迟性;

Heka:开源流处理软件系统;

HIHO:用Hadoop连接不同数据源的框架;

Kestrel:分布式消息队列系统;

LinkedIn Databus:对数据库更改捕获的事件流;

LinkedIn Kamikaze:压缩已分类整型数组的程序包;

LinkedIn White Elephant:日志聚合器和仪表板;

Logstash:用于管理事件和日志的工具;

Netflix Suro:像基于Chukwa 的Storm和Samza一样的日志聚合器;

Pinterest Secor:是实现Kafka日志持久性的服务;

Linkedin Gobblin:LinkedIn的通用数据摄取框架;

Skizze:是一种数据存储略图,使用概率性数据结构来处理计数、略图等相关的问题;

StreamSets Data Collector:连续大数据采集的基础设施,可简单地使用IDE。

 

服务编程

 

Akka Toolkit:JVM中分布性、容错事件驱动应用程序的运行时间;

Apache Avro:数据序列化系统;

Apache Curator:Apache ZooKeeper的Java库;

Apache Karaf:在任何OSGi框架之上运行的OSGi运行时间;

Apache Thrift:构建二进制协议的框架;

Apache Zookeeper:流程管理集中式服务;

Google Chubby:一种松耦合分布式系统锁服务;

Linkedin Norbert:集群管理器;

OpenMPI:消息传递框架;

Serf:服务发现和协调的分散化解决方案;

Spotify Luigi:一种构建批处理作业的复杂管道的Python包,它能够处理依赖性解析、工作流管理、可视化、故障处理、命令行一体化等等问题;

Spring XD:数据摄取、实时分析、批量处理和数据导出的分布式、可扩展系统;

Twitter Elephant Bird:LZO压缩数据的工作库;

Twitter Finagle:JVM的异步网络堆栈。

 

调度

 

Apache Aurora:在Apache Mesos之上运行的服务调度程序;

Apache Falcon:数据管理框架;

Apache Oozie:工作流作业调度程序;

Chronos:分布式容错调度;

Linkedin Azkaban:批处理工作流作业调度;

Schedoscope:Hadoop作业敏捷调度的Scala DSL;

Sparrow:调度平台;

Airflow:一个以编程方式编写、调度和监控工作流的平台。

 

机器学习

 

Apache Mahout:Hadoop的机器学习库;

brain:JavaScript中的神经网络;

Cloudera Oryx:实时大规模机器学习;

Concurrent Pattern:Cascading的机器学习库;

convnetjs:Javascript中的机器学习,在浏览器中训练卷积神经网络(或普通网络);

Decider:Ruby中灵活、可扩展的机器学习;

ENCOG:支持多种先进算法的机器学习框架,同时支持类的标准化和处理数据;

etcML:机器学习文本分类;

Etsy Conjecture:Scalding中可扩展的机器学习;

Google Sibyl:Google中的大规模机器学习系统;

GraphLab Create:Python的机器学习平台,包括ML工具包、数据工程和部署工具的广泛集合;

H2O:Hadoop统计性的机器学习和数学运行时间;

MLbase:用于BDAS堆栈的分布式机器学习库;

MLPNeuralNet:针对iOS和Mac OS X的快速多层感知神经网络库;

MonkeyLearn:使文本挖掘更为容易,从文本中提取分类数据;

nupic:智能计算的Numenta平台,它是一个启发大脑的机器智力平台,基于皮质学习算法的精准的生物神经网络;

PredictionIO:建于Hadoop、Mahout和Cascading上的机器学习服务器;

SAMOA:分布式流媒体机器学习框架;

scikit-learn:scikit-learn为Python中的机器学习;

Spark MLlib:Spark中一些常用的机器学习(ML)功能的实现;

Vowpal Wabbit:微软和雅虎发起的学习系统;

WEKA:机器学习软件套件;

BidMach:CPU和加速GPU的机器学习库。

 

基准测试

 

Apache Hadoop Benchmarking:测试Hadoop性能的微基准;

Berkeley SWIM Benchmark:现实大数据工作负载基准测试;

Intel HiBench:Hadoop基准测试套件;

PUMA Benchmarking:MapReduce应用的基准测试套件;

Yahoo Gridmix3:雅虎工程师团队的Hadoop集群基准测试。

 

安全性

 

Apache Knox Gateway:Hadoop集群安全访问的单点;

Apache Sentry:存储在Hadoop的数据安全模块。

 

 

系统部署

 

Apache Ambari:Hadoop管理的运作框架;

Apache Bigtop:Hadoop生态系统的部署框架;

Apache Helix:集群管理框架;

Apache Mesos:集群管理器;

Apache Slider:一种YARN应用,用来部署YARN中现有的分布式应用程序;

Apache Whirr:运行云服务的库集;

Apache YARN:集群管理器;

Brooklyn:用于简化应用程序部署和管理的库;

Buildoop:基于Groovy语言,和Apache BigTop类似;

Cloudera HUE:和Hadoop进行交互的Web应用程序;

Facebook Prism:多数据中心复制系统;

Google Borg:作业调度和监控系统;

Google Omega:作业调度和监控系统;

Hortonworks HOYA:可在YARN上部署HBase集群的应用;

Marathon:用于长期运行服务的Mesos框架。

 

 

应用程序

 

Adobe spindle:使用Scala、Spark和Parquet处理的下一代web分析;

Apache Kiji:基于HBase,实时采集和分析数据的框架;

Apache Nutch:开源网络爬虫;

Apache OODT:用于NASA科学档案中数据的捕获、处理和共享;

Apache Tika:内容分析工具包;

Argus:时间序列监测和报警平台;

Countly:基于Node.js和MongoDB,开源的手机和网络分析平台;

Domino:运行、规划、共享和部署模型——没有任何基础设施;

Eclipse BIRT:基于Eclipse的报告系统;

Eventhub:开源的事件分析平台;

Hermes:建于Kafka上的异步消息代理;

HIPI Library:在Hadoop’s MapReduce上执行图像处理任务的API;

Hunk:Hadoop的Splunk分析;

Imhotep:大规模分析平台;

MADlib:RDBMS的用于数据分析的数据处理库;

Kylin:来自eBay的开源分布式分析工具;

PivotalR:Pivotal HD / HAWQ和PostgreSQL中的R;

Qubole:为自动缩放Hadoop集群,内置的数据连接器;

Sense:用于数据科学和大数据分析的云平台;

SnappyData:用于实时运营分析的分布式内存数据存储,提供建立在Spark单一集成集群中的数据流分析、OLTP(联机事务处理)和OLAP(联机分析处理);

Snowplow:企业级网络和事件分析,由Hadoop、Kinesis、Redshift 和Postgres提供技术支持;

SparkR:Spark的R前端;

Splunk:用于机器生成的数据的分析;

Sumo Logic:基于云的分析仪,用于分析机器生成的数据;

Talend:用于YARN、Hadoop、HBASE、Hive、HCatalog和Pig的统一开源环境;

Warp:利用大数据(OS X app)的实例查询工具。

 

搜索引擎与框架

 

Apache Lucene:搜索引擎库;

Apache Solr:用于Apache Lucene的搜索平台;

ElasticSearch:基于Apache Lucene的搜索和分析引擎;

Enigma.io:为免费增值的健壮性web应用,用于探索、筛选、分析、搜索和导出来自网络的大规模数据集;

Facebook Unicorn:社交图形搜索平台;

Google Caffeine:连续索引系统;

Google Percolator:连续索引系统;

TeraGoogle:大型搜索索引;

HBase Coprocessor:为Percolator的实现,HBase的一部分;

Lily HBase Indexer:快速、轻松地搜索存储在HBase的任何内容;

LinkedIn Bobo:完全由Java编写的分面搜索的实现,为Apache Lucene的延伸;

LinkedIn Cleo:为一个一个灵活的软件库,使得局部、无序、实时预输入的搜索实现了快速发展;

LinkedIn Galene:LinkedIn搜索架构;

LinkedIn Zoie:是用Java编写的实时搜索/索引系统;

Sphinx Search Server:全文搜索引擎

 

MySQL的分支和演化

 

Amazon RDS:亚马逊云的MySQL数据库;

Drizzle:MySQL的6.0的演化;

Google Cloud SQL:谷歌云的MySQL数据库;

MariaDB:MySQL的增强版嵌入式替代品;

MySQL Cluster:使用NDB集群存储引擎的MySQL实现;

Percona Server:MySQL的增强版嵌入式替代品;

ProxySQL:MySQL的高性能代理;

TokuDB:用于MySQL和 MariaDB的存储引擎;

WebScaleSQL:运行MySQL时面临类似挑战的几家公司,它们的工程师之间的合作。

 

PostgreSQL的分支和演化

 

Yahoo Everest – multi-peta-byte database / MPP derived by PostgreSQL.

HadoopDB:MapReduce和DBMS的混合体;

IBM Netezza:高性能数据仓库设备;

Postgres-XL:基于PostgreSQL,可扩展的开源数据库集群;

RecDB:完全建立在PostgreSQL内部的开源推荐引擎;

Stado:开源MPP数据库系统,只针对数据仓库和数据集市的应用程序;

Yahoo Everest:PostgreSQL可以推导多字节P比特数据库/MPP。

 

Memcached的分支和演化

 

Facebook McDipper:闪存的键/值缓存;

Facebook Memcached:Memcache的分支;

Twemproxy:Memcached和Redis的快速、轻型代理;

Twitter Fatcache:闪存的键/值缓存;

Twitter Twemcache:Memcache的分支。

 

嵌入式数据库

 

Actian PSQL:Pervasive Software公司开发的ACID兼容的DBMS,在应用程序中嵌入了优化;

BerkeleyDB:为键/值数据提供一个高性能的嵌入式数据库的一个软件库;

HanoiDB:Erlang LSM BTree存储;

LevelDB:谷歌写的一个快速键-值存储库,它提供了从字符串键到字符串值的有序映射;

LMDB:Symas开发的超快、超紧凑的键-值嵌入的式数据存储;

RocksDB:基于性LevelDB,用于快速存储的嵌入式持续性键-值存储。

商业智能

BIME Analytics:商业智能云平台;

Chartio:精益业务智能平台,用于可视化和探索数据;

datapine:基于云的自助服务商业智能工具;

Jaspersoft:功能强大的商业智能套件;

Jedox Palo:定制的商业智能平台;

Microsoft:商业智能软件和平台;

Microstrategy:商业智能、移动智能和网络应用软件平台;

Pentaho:商业智能平台;

Qlik:商业智能和分析平台;

Saiku:开源的分析平台;

SpagoBI:开源商业智能平台;

Tableau:商业智能平台;

Zoomdata:大数据分析;

Jethrodata:交互式大数据分析。

 

数据可视化

 

Airpal:用于PrestoDB的网页UI;

Arbor:利用网络工作者和jQuery的图形可视化库;

Banana:对存储在Kibana中Solr. Port的日志和时戳数据进行可视化;

Bokeh:一个功能强大的Python交互式可视化库,它针对要展示的现代web浏览器,旨在为D3.js风格的新奇的图形提供优雅简洁的设计,同时在大规模数据或流数据集中,通过高性能交互性来表达这种能力;

C3:基于D3可重复使用的图表库;

CartoDB:开源或免费增值的虚拟主机,用于带有强大的前端编辑功能和API的地理空间数据库;

chartd:只带Img标签的反应灵敏、兼容Retina的图表;

Chart.js:开源的HTML5图表可视化效果;

Chartist.js:另一个开源HTML5图表可视化效果;

Crossfilter:JavaScript库,用于在浏览器中探索多元大数据集,用Dc.js和D3.js.效果很好;

Cubism:用于时间序列可视化的JavaScript库;

Cytoscape:用于可视化复杂网络的JavaScript库;

DC.js:维度图表,和Crossfilter一起使用,通过D3.js呈现出来,它比较擅长连接图表/附加的元数据,从而徘徊在D3的事件附近;

D3:操作文件的JavaScript库;

D3.compose:从可重复使用的图表和组件构成复杂的、数据驱动的可视化;

D3Plus:一组相当强大的可重用的图表,还有D3.js的样式;

Echarts:百度企业场景图表;

Envisionjs:动态HTML5可视化;

FnordMetric:写SQL查询,返回SVG图表,而不是表;

Freeboard:针对IOT和其他Web混搭的开源实时仪表盘构建;

Gephi:屡获殊荣的开源平台,可视化和操纵大型图形和网络连接,有点像Photoshop,但是针对于图表,适用于Windows和Mac OS X;

Google Charts:简单的图表API;

Grafana:石墨仪表板前端、编辑器和图形组合器;

Graphite:可扩展的实时图表;

Highcharts:简单而灵活的图表API;

IPython:为交互式计算提供丰富的架构;

Kibana:可视化日志和时间标记数据;

Matplotlib:Python绘图;

Metricsgraphic.js:建立在D3之上的库,针对时间序列数据进行最优化;

NVD3:d3.js的图表组件;

Peity:渐进式SVG条形图,折线和饼图;

Plot.ly:易于使用的Web服务,它允许快速创建从热图到直方图等复杂的图表,使用图表Plotly的在线电子表格上传数据进行创建和设计;

Plotly.js:支持plotly的开源JavaScript图形库;

Recline:简单但功能强大的库,纯粹利用JavaScript和HTML构建数据应用;

Redash:查询和可视化数据的开源平台;

Shiny:针对R的Web应用程序框架;

Sigma.js:JavaScript库,专门用于图形绘制;

Vega:一个可视化语法;

Zeppelin:一个笔记本式的协作数据分析;

Zing Charts:用于大数据的JavaScript图表库。

 

物联网和传感器

 

TempoIQ:基于云的传感器分析;

2lemetry:物联网平台;

Pubnub:数据流网络;

ThingWorx:ThingWorx 是让企业快速创建和运行互联应用程序平台;

IFTTT:IFTTT 是一个被称为 “网络自动化神器” 的创新型互联网服务,它的全称是 If this then that,意思是“如果这样,那么就那样”;

Evrythng:Evrythng则是一款真正意义上的大众物联网平台,使得身边的很多产品变得智能化。

 

文章推荐

 

NoSQL Comparison(NoSQL 比较)- Cassandra vs MongoDB vs CouchDB vs Redis vs Riak vs HBase vs Couchbase vs Neo4j vs Hypertable vs ElasticSearch vs Accumulo vs VoltDB vs Scalaris comparison;

Big Data Benchmark(大数据基准)- Redshift, Hive, Shark, Impala and Stiger/Tez的基准;

The big data successor of the spreadsheet(电子表格的大数据继承者) – 电子表格的继承者应该是大数据。

 

论文

 

2015 – 2016

2015 – Facebook – One Trillion Edges: Graph Processing at Facebook-Scale.(一兆边:Facebook规模的图像处理)

2013 – 2014

2014 – Stanford – Mining of Massive Datasets.(海量数据集挖掘)

2013 – AMPLab – Presto: Distributed Machine Learning and Graph Processing with Sparse Matrices. (Presto: 稀疏矩阵的分布式机器学习和图像处理)

2013 – AMPLab – MLbase: A Distributed Machine-learning System. (MLbase:分布式机器学习系统)

2013 – AMPLab – Shark: SQL and Rich Analytics at Scale. (Shark: 大规模的SQL 和丰富的分析)

2013 – AMPLab – GraphX: A Resilient Distributed Graph System on Spark. (GraphX:基于Spark的弹性分布式图计算系统)

2013 – Google – HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm. (HyperLogLog实践:一个艺术形态的基数估算算法)

2013 – Microsoft – Scalable Progressive Analytics on Big Data in the Cloud.(云端大数据的可扩展性渐进分析)

2013 – Metamarkets – Druid: A Real-time Analytical Data Store. (Druid:实时分析数据存储)

2013 – Google – Online, Asynchronous Schema Change in F1.(F1中在线、异步模式的转变)

2013 – Google – F1: A Distributed SQL Database That Scales. (F1: 分布式SQL数据库)

2013 – Google – MillWheel: Fault-Tolerant Stream Processing at Internet Scale.(MillWheel: 互联网规模下的容错流处理)

2013 – Facebook – Scuba: Diving into Data at Facebook. (Scuba: 深入Facebook的数据世界)

2013 – Facebook – Unicorn: A System for Searching the Social Graph. (Unicorn: 一种搜索社交图的系统)

2013 – Facebook – Scaling Memcache at Facebook. (Facebook 对 Memcache 伸缩性的增强)

  2011 – 2012

2012 – Twitter – The Unified Logging Infrastructure for Data Analytics at Twitter. (Twitter数据分析的统一日志基础结构)

2012 – AMPLab –Blink and It’s Done: Interactive Queries on Very Large Data. (Blink及其完成:超大规模数据的交互式查询)

2012 – AMPLab –Fast and Interactive Analytics over Hadoop Data with Spark. (Spark上 Hadoop数据的快速交互式分析)

2012 – AMPLab –Shark: Fast Data Analysis Using Coarse-grained Distributed Memory. (Shark:使用粗粒度的分布式内存快速数据分析)

2012 – Microsoft –Paxos Replicated State Machines as the Basis of a High-Performance Data Store. (Paxos的复制状态机——高性能数据存储的基础)

2012 – Microsoft –Paxos Made Parallel. (Paxos算法实现并行)

2012 – AMPLab – BlinkDB:BlinkDB: Queries with Bounded Errors and Bounded Response Times on Very Large Data.(超大规模数据中有限误差与有界响应时间的查询)

2012 – Google –Processing a trillion cells per mouse click.(每次点击处理一兆个单元格)

2012 – Google –Spanner: Google’s Globally-Distributed Database.(Spanner:谷歌的全球分布式数据库)

2011 – AMPLab –Scarlett: Coping with Skewed Popularity Content in MapReduce Clusters.(Scarlett:应对MapReduce集群中的偏向性内容)

2011 – AMPLab –Mesos: A Platform for Fine-Grained Resource Sharing in the Data Center.(Mesos:数据中心中细粒度资源共享的平台)

2011 – Google –Megastore: Providing Scalable, Highly Available Storage for Interactive Services.(Megastore:为交互式服务提供可扩展,高度可用的存储)

  2001 – 2010

2010 – Facebook – Finding a needle in Haystack: Facebook’s photo storage.(探究Haystack中的细微之处: Facebook图片存储)

2010 – AMPLab – Spark: Cluster Computing with Working Sets.(Spark:工作组上的集群计算)

2010 – Google – Storage Architecture and Challenges.(存储架构与挑战)

2010 – Google – Pregel: A System for Large-Scale Graph Processing.(Pregel: 一种大型图形处理系统)

2010 – Google – Large-scale Incremental Processing Using Distributed Transactions and Notifications base of Percolator and Caffeine.(使用基于Percolator 和 Caffeine平台分布式事务和通知的大规模增量处理)

2010 – Google – Dremel: Interactive Analysis of Web-Scale Datasets.(Dremel: Web规模数据集的交互分析)

2010 – Yahoo – S4: Distributed Stream Computing Platform.(S4:分布式流计算平台)

2009 – HadoopDB:An Architectural Hybrid of MapReduce and DBMS Technologies for Analytical Workloads.(混合MapReduce和DBMS技术用于分析工作负载的的架构)

2008 – AMPLab – Chukwa: A large-scale monitoring system.(Chukwa: 大型监控系统)

2007 – Amazon – Dynamo: Amazon’s Highly Available Key-value Store.(Dynamo: 亚马逊的高可用的关键价值存储)

2006 – Google – The Chubby lock service for loosely-coupled distributed systems.(面向松散耦合的分布式系统的锁服务)

2006 – Google – Bigtable: A Distributed Storage System for Structured Data.(Bigtable: 结构化数据的分布式存储系统)

2004 – Google – MapReduce: Simplied Data Processing on Large Clusters.(MapReduce: 大型集群上简化数据处理)

2003 – Google – The Google File System.(谷歌文件系统)

https://github.com/mayunlei/awesome-bigdata  

深入理解Presto(1) : Presto的架构

简介

Presto是一个facebook开源的分布式SQL查询引擎,适用于交互式分析查询,数据量支持GB到PB字节。presto的架构由关系型数据库的架构演化而来。presto之所以能在各个内存计算型数据库中脱颖而出,在于以下几点:

  1. 清晰的架构,是一个能够独立运行的系统,不依赖于任何其他外部系统。例如调度,presto自身提供了对集群的监控,可以根据监控信息完成调度。
  2. 简单的数据结构,列式存储,逻辑行,大部分数据都可以轻易的转化成presto所需要的这种数据结构。
  3. 丰富的插件接口,完美对接外部存储系统,或者添加自定义的函数。

本文从外到内,依次来介绍presto。

架构

image.png

Presto采用典型的master-slave模型:

  1. coordinator(master)负责meta管理,worker管理,query的解析和调度
  2. worker则负责计算和读写。
  3. discovery server, 通常内嵌于coordinator节点中,也可以单独部署,用于节点心跳。在下文中,默认discovery和coordinator共享一台机器。

在worker的配置中,可以选择配置:

  1. discovery的ip:port。
  2. 一个http地址,内容是service inventory,包含discovery地址。


    {
    "environment": "production",
    "services": [
    {
    "id": "ffffffff-ffff-ffff-ffff-ffffffffffff",
    "type": "discovery",
    "location": "/ffffffff-ffff-ffff-ffff-ffffffffffff",
    "pool": "general",
    "state": "RUNNING",
    "properties": {
    "http": "http://192.168.1.1:8080"
    }
    }
    ]
    }

  3. 一个本地文件地址,内容同2。

2和3的原理是基于service inventory, worker 会动态监听这个文件,如果有变化,load出最新的配置,指向最新的discovery节点。

在设计上,discovery和coordinator都是单节点。如果有多个coordinator同时存活,worker 会随机的向其中一个汇报进程和task状态,导致脑裂。调度query时有可能会发生死锁。

discovery和coordinator可用性设计。由于service inventory的使用,监控程序可以在发现discovery挂掉后,修改service inventory中的内容,指向备机的discovery。无缝的完成切换。coordiantor的配置必须要在进程启动时指定,同一个集群中无法存活多个coordinator。因此最好的办法是和discovery配置到一台机器。 secondary机器部署备用的discovery和coordinator。在平时,secondary机器是一个只包含一台机器的集群,在primary宕机时,worker的心跳瞬间切换到secondary。

数据模型

presto采取三层表结构:

  1. catalog 对应某一类数据源,例如hive的数据,或mysql的数据
  2. schema 对应mysql中的数据库
  3. table 对应mysql中的表

image.png

presto的存储单元包括:

  1. Page: 多行数据的集合,包含多个列的数据,内部仅提供逻辑行,实际以列式存储。
  2. Block:一列数据,根据不同类型的数据,通常采取不同的编码方式,了解这些编码方式,有助于自己的存储系统对接presto。

不同类型的block:

  1. array类型block,应用于固定宽度的类型,例如int,long,double。block由两部分组成
    • boolean valueIsNull[]表示每一行是否有值。
    • T values[] 每一行的具体值。
  2. 可变宽度的block,应用于string类数据,由三部分信息组成
    • Slice : 所有行的数据拼接起来的字符串。
    • int offsets[] :每一行数据的起始便宜位置。每一行的长度等于下一行的起始便宜减去当前行的起始便宜。
    • boolean valueIsNull[] 表示某一行是否有值。如果有某一行无值,那么这一行的便宜量等于上一行的偏移量。
  3. 固定宽度的string类型的block,所有行的数据拼接成一长串Slice,每一行的长度固定。
  4. 字典block:对于某些列,distinct值较少,适合使用字典保存。主要有两部分组成:
    • 字典,可以是任意一种类型的block(甚至可以嵌套一个字典block),block中的每一行按照顺序排序编号。
    • int ids[] 表示每一行数据对应的value在字典中的编号。在查找时,首先找到某一行的id,然后到字典中获取真实的值。

插件

了解了presto的数据模型,就可以给presto编写插件,来对接自己的存储系统。presto提供了一套connector接口,从自定义存储中读取元数据,以及列存储数据。先看connector的基本概念:

  1. ConnectorMetadata: 管理表的元数据,表的元数据,partition等信息。在处理请求时,需要获取元信息,以便确认读取的数据的位置。Presto会传入filter条件,以便减少读取的数据的范围。元信息可以从磁盘上读取,也可以缓存在内存中。
  2. ConnectorSplit: 一个IO Task处理的数据的集合,是调度的单元。一个split可以对应一个partition,或多个partition。
  3. SplitManager : 根据表的meta,构造split。
  4. SlsPageSource : 根据split的信息以及要读取的列信息,从磁盘上读取0个或多个page,供计算引擎计算。

插件能够帮助开发者添加这些功能:

  1. 对接自己的存储系统。
  2. 添加自定义数据类型。
  3. 添加自定义处理函数。
  4. 自定义权限控制。
  5. 自定义资源控制。
  6. 添加query事件处理逻辑。

Presto提供了一个简单的connector : local file connector ,可用于参考如何实现自己的connector。不过local file connector中使用的遍历数据的单元是cursor,即一行数据,而不是一个page。 hive 的connector中实现了三种类型,parquet connector, orc connector, rc file connector。
image.png

上文从宏观上介绍了presto的一些原理,接下来几篇文章让我们深入presto 内部,了解一些内部的设计,这对性能调优会有比较大的用处,也有助于添加自定义的operator。

 

libeasy原理,架构和使用方法

libeasy 原理、架构和使用方法

简介

libeasy提供一个处理tcp连接的事件驱动的网络框架。框架本身封装好了底层的网络操作,只需要开发者处理其中的各种事件。本文介绍libeasy的一些实现原理,整体框架,以及使用的样例。本文是经过一系列摸索,以及wireshark抓包,再结合一些互联网上一些仅有的资料整理完成,如有理解不当的地方,烦请指出。

基本概念

libeasy 的基本概念有:easy_connection_t(连接), easy_message_t(消息), easy_request_t(请求)。每个连接上有可以有多个消息,通过链表连起来,每个消息可以由多个请求组成,也通过链表连起来。

easy_request_t就相当于应用层的一个具体的包, 多个请求组合起来形成一个完整的消息。在一次长连接中,用户可以接受多次消息。每个request 只属于一个connection。

处理模型

libeasy是基于epoll的事件模型,程序收到事件后,回调注册的事件的函数。调用回调函数的线程池称为IO Thread , 线程的个数在创建eaay事件时指定。

extern easy_io_t *easy_eio_create(easy_io_t *eio, int io_thread_count);

一些简单的请求,可以直接在io thread中处理完成,并且直接返回,这种处理模型称为同步模型。

在一些情况下,处理逻辑比较复杂,比如需要读取磁盘数据,这种情况下,IO Thread会封装成一个请求,放入后端队列,经由另外一个线程池进行处理,同时IO Thread会把当前的事件挂起,等待后端线程唤醒后继续处理当前事件。这种模型称为异步模型。

这里写图片描述

这里写图片描述

注册事件的回调

开发者注册一系列回调函数,供libeasy在接受请求时回调。按照回调的顺序,回调函数包括:

  1. on_connect
    接受tcp连接时,回调该函数,可以在该事件中做密码验证等事情。
  2. decode
    从网络上读取一段文本,并且按照定义的协议,解析成数据结构,供之后处理。
  3. process
    处理从decode中解析出的结构,可以是同步处理,也可以是异步处理。
  4. encode
    把process的结果,转化成字符串(如果process的结果是要输出的结果,则不需要转化)。然后把结果挂载到request的输出上。r -> opacket = buf;
  5. clean_up
    在连接断开前执行的操作,如果在之前的操作中分配了一些内存,需要在这里释放。
  6. on_disconnect
    连接断开时的操作。

使用方法

libeasy有一些基本的数据结构

  1. easy_pool_t:共享内存池。在一次请求中,一次性分配大块内存,当用户使用小内存的时候,从pool中分配,从而达到避免分配大量小块内存的情况。因为大量小块内存会非常浪费CPU。

    void * ptr = easy_pool_alloc(req->ms->pool,1024);

    分配好的内存可以用于初始化任何对象。例如:以下例子中的new不会分配新内存,而是使用ptr指向的内存,并且传入1作为构造函数的参数。

    UserInfo * infoPtr = new (ptr)UserInfo(1);
  2. easy_buf_t

    管理输入输出缓冲区,用于逐段消费字符串,或分批把结果放入buf进行输出。其中pos指向当前位置,last指向已使用的内存的结束位置,end指向全部内存的结束位置。

    easy_buf_t* buf = reinterpret_cast<easy_buf_t*>(easy_pool_alloc(req->ms->pool, 2*1024*1024));
    char *data_buffer = reinterpret_cast<char *>(buf + sizeof(easy_buf_t));
    buffer_length = 2*1024*1024 - sizeof(easy_buf_t);  
    buf -> pos = buf -> last =  data_buffer;
    buf->end = buf->last + buffer_length; 
    buf->cleanup = NULL;
    easy_list_init(&buf->node); 

一个同步处理的样例

#include <iostream>
#include "easy/easy_io_struct.h"
#include "easy/easy_io.h"
using namespace std;
struct MyMessage
{
    int mLen;
    int mSeq;
    string mMessage;
public :
    MyMessage(int len,int seq,const string & msg):
        mLen(len),mSeq(seq),mMessage(msg)
    {}

};
int  my_on_connect (easy_connection_t *c)
{
    return 0;
}

int my_easy_io_process_pt(easy_request_t *r)
{
    MyMessage * msg = (MyMessage*)r -> ipacket;
    char buffer[1024];
    sprintf(buffer,"i got you message,len:%d,seq:%d,message:%s",msg ->mLen,msg ->mSeq,msg ->mMessage.c_str());
    string ret(buffer);
    MyMessage * outMsg = new MyMessage(ret.size(),msg ->mSeq+1,ret);
    r -> opacket = outMsg;
    delete msg;
    return 0;
}
int my_on_disconnect (easy_connection_t * c)
{
    return 0;
}
void * my_easy_decode_pt(easy_message_t *m)
{
    int len = (*((uint32_t*)m -> input->pos)) >> 8;
    int seq = (*((uint32_t*)m -> input->pos)) && 0xff;
    MyMessage * msg = new MyMessage(len,seq,string(m ->input->pos+4,len));
    m ->input->pos= m ->input -> last;
    return msg;
}
int my_easy_encode_pt(easy_request_t *r, void *packet)
{
    MyMessage * msg = (MyMessage*) packet;
    easy_buf_t * buf =easy_buf_create(r ->  ms -> pool, msg ->mMessage.size());
    easy_buf_set_data(r ->ms ->pool, buf, msg ->mMessage.c_str(),msg ->mMessage.size());
    easy_request_addbuf(r, buf); //加入输出队列
    delete msg;
    return 0;
}
int main(int argc,char ** argv)
{
    easy_io_handler_pt handler;
    memset(&handler, 0, sizeof(easy_io_handler_pt));
    handler.on_connect = my_on_connect;
    handler.decode = my_easy_decode_pt;
    handler.encode= my_easy_encode_pt;
    handler.on_disconnect = my_on_disconnect;
    handler.process = my_easy_io_process_pt;
    easy_io_t *eio = new easy_io_t();
    memset(eio,0,sizeof(easy_io_t));
    eio = easy_eio_create(eio,10);//创建10个线程
    eio->tcp_defer_accept = 0;
    easy_listen_t* listen = easy_connection_add_listen(eio, NULL, 3308, &handler);//侦听3308端口
    int rc = easy_eio_start(eio);
    easy_eio_wait(eio);
}

异步使用方法

异步模型,最主要的区别是在process 函数中。

这里写图片描述

在process 中,把请求放入后端队列,并且return EASY_AGAIN 表示将请求挂起,不会继续调用接下来的 encode和clean_up ,直到被后端线程唤醒。encode函数和同步模型一致,把req -> opacket放入输出缓存中。
process再次回调的的函数实现如下:

if (EASY_AGAIN == r->retcode)  //wakeup request thread called when send result set sync
    {   
        //EASY_AGAIN说明后续服务器端还有包需要发给客户端
        if (NULL != r->client_wait)
        {
            if (r->ms->c->conn_has_error == 1)
            {   
                r->client_wait->status = EASY_CONN_CLOSE;
            }
            easy_client_wait_wakeup_request(r);
            ret = EASY_AGAIN;
        }
        //else no more data send
        ret = EASY_OK;
}

后端线程的实现:

  req->opacket=buf;//把结果挂载到opacket上
  easy_client_wait_t wait_obj;
  if(shouldWait)
  {
      wait_obj.done_count = 0;
      //用于IO线程唤醒工作线程
      easy_client_wait_init(&wait_obj);
      req->client_wait = &wait_obj;
      req->retcode = -11;
      req->waiting = 1;
  }
  //io线程被唤醒,r->opacket被挂过去,send_response->easy_connection_request_done
  easy_request_wakeup(req);
  // IO线程回调 process(easy_request_t* r)的时候唤醒工作线程
    if(shouldWait)
    {   
        wait_client_obj(wait_obj);//工作线程在此处阻塞,等待唤醒
        if(wait_obj.status==3){
            ret=-124;
        }
        easy_client_wait_cleanup(&wait_obj);
        req->client_wait = NULL;
    }

[usaco]4.3.1 最长递减子序列 和超级整型数

Buy Low, Buy Lower

The advice to “buy low” is half the formula to success in the stock market. But to be considered a great investor you must also follow this problems’ advice:

“Buy low, buy lower”
That is, each time you buy a stock, you must purchase more at a lower price than the previous time you bought it. The more times you buy at a lower price than before, the better! Your goal is to see how many times you can continue purchasing at ever lower prices.

You will be given the daily selling prices of a stock over a period of time. You can choose to buy stock on any of the days. Each time you choose to buy, the price must be lower than the previous time you bought stock. Write a program which identifies which
days you should buy stock in order to maximize the number of times you buy.

By way of example, suppose on successive days stock is selling like this:

 Day   1  2  3  4  5  6  7  8  9 10 11 12
Price 68 69 54 64 68 64 70 67 78 62 98 87

In the example above, the best investor (by this problem, anyway) can buy at most four times if they purchase at a lower price each time. One four day sequence (there might be others) of acceptable buys is:

Day    2  5  6 10
Price 69 68 64 62

PROGRAM NAME: buylow
INPUT FORMAT
Line 1:  N (1 <= N <= 5000), the number of days for which stock prices are available.

Line 2..etc:  A series of N positive space-separated integers (which may require more than one line of data) that tell the price for that day. The integers will fit into 32 bits quite nicely.

SAMPLE INPUT (file buylow.in)
12
68 69 54 64 68 64 70 67
78 62 98 87

OUTPUT FORMAT
Two integers on a single line:

the length of the longest sequence of decreasing prices
the number of sequences that have this length
In counting the number of solutions, two potential solutions are considered the same (and would only count as one solution) if they repeat the same string of decreasing prices, that is, if they “look the same” when the successive prices are compared. Thus,
two different sequence of “buy” days could produce the same string of decreasing prices and be counted as only a single solution.

SAMPLE OUTPUT (file buylow.out)
4 2

 

———————————————————–
求最长递减子序列。
参考算法:http://blog.pfan.cn/rickone/13086.html
上述算法是求最长递增子序列,而且只需要求长度,并不需要求数量。
因此需要添加一个数组记录每一个长度对应的数目。
此外,某个长度可能是一个非常大的整数。因此需要定义一个整数类:

class big{
public :
 int s[bit];
 big  operator+ (big &b){
 }
 big & operator =(const big &a)
 big & operator =(const int a)
 friend ostream & operator <<(ostream & input,big & b)
};
我所遇到的testcase8就有这么长:1606938044258990275541962092341162602522202993782792835301376
USER: Ma yunlei [yunleis2]
TASK: buylow
LANG: C++

Compiling…
Compile: OK

Executing…
   Test 1: TEST OK [0.000 secs, 3328 KB]
   Test 2: TEST OK [0.000 secs, 3328 KB]
   Test 3: TEST OK [0.000 secs, 3328 KB]
   Test 4: TEST OK [0.000 secs, 3328 KB]
   Test 5: TEST OK [0.000 secs, 3328 KB]
   Test 6: TEST OK [0.000 secs, 3328 KB]
   Test 7: TEST OK [0.000 secs, 3328 KB]
   Test 8: TEST OK [0.000 secs, 3328 KB]
   Test 9: TEST OK [0.054 secs, 3328 KB]
   Test 10: TEST OK [0.189 secs, 3328 KB]

——————————————————————

 

/*
ID:yunleis2
PROG:buylow
LANG:C++
*/

#include<iostream>
#include<fstream>
#include<cmath>
#include<iomanip>
using namespace std;
const int maxn=5001;
const int base=1000000;
			   
const int bit=13;
class big{
public :
	int s[bit];
	big  operator+ (big &b){
		big bt;
		int carry=0;
		for(int i=bit-1;i>=0;--i){
			bt.s[i]=(s[i]+b.s[i]+carry)%base;
			carry=(s[i]+b.s[i]+carry)/base;
		}
		return bt;
	}
	big & operator =(const big &a){
		for(int i=0;i<bit;++i)
			this->s[i]=a.s[i];
		return *this;
	}
	big & operator =(const int a){
		for(int i=0;i<bit;++i)
			this->s[i]=0;
		this->s[bit-1]=a;
		return *this;
	}
	friend ostream & operator <<(ostream & input,big & b){
		bool flag=false;
		bool flag1=false;
		for(int i=0;i<bit;++i)
		{	
			if(b.s[i]!=0)
				flag=true;
			
			if(flag){
				if(!flag1)
				{
					input<<b.s[i];
					flag1=true;
				}
				else
					input<<setw(6)<<setfill('0')<<b.s[i];
				
			}
		}
		return input;
	}
};
//seq seqs[maxn];
int ptr=0;
int n;
int stock[maxn];
int size[maxn];
big num[maxn];
bool flag[maxn];
int main()
{
	fstream fin("buylow.in",ios::in );
	fin>>n;
	for(int i=0;i<n;++i)
		fin>>stock[i];
	//seqs[ptr++]
	size[0]=1;
	num[0]=1;
	flag[0]=true;
	for(int i=1;i<n;i++){
		size[i]=1;
		num[i]=1;
		flag[i]=true;
		for(int j=0;j<i;j++){
			if(!flag[j])
				continue;
			if(stock[i]<stock[j])
			{
				if(size[j]>size[i]-1)
				{
					size[i]=size[j]+1;
					num[i]=num[j];
				}
				else if(size[j]==(size[i]-1))
					num[i]=num[i]+num[j];
			}
			else if(stock[i]==stock[j]){
#if 0
				if(size[j]==1){
					size[i]=0;
					num[i]=0;
				}
				else{
					size[i]=1;
					num[i]=1;
				}
#endif
				flag[j]=false;
				if(size[j]>size[i])
				{
					size[i]=size[j];
					num[i]=num[j];
				}
				else if(size[j]==(size[i]))
					num[i]=num[j];
 
			}
		}
	}
	int maxlength=0;
	big num1;
	num1=0;
	for(int i=n-1;i>=0;--i){
		//cout<<"("<<size[i]<<"~"<<num[i]<<") ";
		if(!flag[i])
			continue;
		if(maxlength<size[i])
		{
			maxlength=size[i];
			num1=num[i];
		}
		else if(maxlength==size[i])
			num1=num1+num[i];
	}
 
	//int num2=num1.s[bit-1];
	fstream fout("buylow.out",ios::out);
	fout<<maxlength<<" ";
	fout<<num1<<endl;
	//system("pause");
}

libcurl在ipv6被禁止的情况下的性能下降

最近我们的集群业务量增加了3T/天。然后发现集群的cpu使用率和load上升的非常高,load最高达到了60。团队分析了性能原因,发现发送结果数据到另一个集群的逻辑消耗了大部分的cpu,于是对这部分发送逻辑进行了优化。

在优化发送逻辑后,cpu下降了一半,load也下降了。但是效果并不明显。有一个机器,load仍然很高。持续的调查发现,在load较高的机器上出现间隔出现多个modprob -q — net-pf-10进程(其中net-pf-10为ipv6模块的别名),行为上似乎在不断的重新加载ipv6模块,但是由于32内核机器modprobe.d中配置了disable_ipv6,因此该模块是被禁止,所以每次加载都无法成功。

对于modprob应该是网络链接访问过程中尝试解析ip地址,涉及网络通信的只有调用libcurl访问存储集群。而且大量modprobe进程的出现与写存储的qps的变化大致吻合。由此怀疑libcurl初始化时会尝试用IPv4和IPv6两种协议对地址解析并在IPv6模块未加载的情况下初始化时会增加额外的延时(大概5-8ms),modprobe命令或许是由于libcurl触发产生。

对比libcurl解析ip地址的代码,调用ioctl(dummy, SIOCGIFADDR, &req)函数对地址进行解析,该函数在判断ipv6模块已经安装的情况下加载相关模块,会触发内核在workqueue中加入modprobe任务尝试加载相关模块,因此在每次curl的调用都会导致modprobe调用产生。这种情形发生在安装了ipv6,但是ipv6被禁止的机器上。而在未安装ipv6的机器,并不存在这个问题。

最终的结论是,libcurl存在一个bug,如果机器安装了ipv6,而且禁止了ipv6,那么libcurl每次调用都会尝试加载ipv6。而这个加载的过程延时非常高,以至于引发了性能问题。

fork 和 sigchld 坑

最近有个项目,一个deamon进程,一个干活进程。deamon 进程会捕获SIGCHLD信号如果干活进程down掉了,deamon会收到这个信号并且重新fork干活进程。

最近发现一个问题是 deamon进程fork了好几个干活进程。团队的人调查问题,一度怀疑是不同的linux内涵对信号处理不同。后来我发现如果干活进程调用了system函数,system会fork一个子进程,这个子进程昨晚事情就退出了,导致deamon进程收到一次SIGCHLD信号。

[usaco] 海明码

Hamming Codes
Rob Kolstad
Given N, B, and D: Find a set of N codewords (1 <= N <= 64), each of length B bits (1 <= B <= 8), such that each of the codewords is at least Hamming distance of D (1 <= D <= 7) away from each of the other codewords. The Hamming distance between a pair of codewords
is the number of binary bits that differ in their binary notation. Consider the two codewords 0x554 and 0x234 and their differences (0x554 means the hexadecimal number with hex digits 5, 5, and 4):

        0x554 = 0101 0101 0100
        0x234 = 0010 0011 0100
Bit differences: xxx  xx

Since five bits were different, the Hamming distance is 5.

PROGRAM NAME: hamming
INPUT FORMAT
N, B, D on a single line

SAMPLE INPUT (file hamming.in)
16 7 3

OUTPUT FORMAT
N codewords, sorted, in decimal, ten per line. In the case of multiple solutions, your program should output the solution which, if interpreted as a base 2^B integer, would have the least value.

SAMPLE OUTPUT (file hamming.out)
0 7 25 30 42 45 51 52 75 76
82 85 97 102 120 127

—————————————————————————–
关键之处在于:
求两个数字键的海明距离。
x=a xor b ,其中为1的位即表示a和b不同的地方。
只需要计算x中1的个数即可。
对于8位二进制数,计算1的个数的方法是:
 x=(x & 0x55555555)+((x>>1)& 0x55555555); 
 x=(x & 0x33333333)+((x>>2)& 0x33333333); 
 x=(x & 0x0F0F0F0F)+((x>>4)& 0x0F0F0F0F); 
 x=(x & 0x00FF00FF)+((x>>8)& 0x00FF00FF); 
 x=(x & 0x0000FFFF)+((x>>16)& 0x0000FFFF); 
经过以上步骤之后,x就是1的个数。

我的程序:
———————————– ———————————————————————-
/*
ID: yunleis2
PROG: hamming
LANG: C++
*/
#include<iostream>
#include<fstream>
#include <cmath>
using namespace std;
int N, B, D;
typedef unsigned int uint;
int distance1(uint a,uint b);
int main()
{
 fstream fin(“hamming.in”,ios::in);
 fin>>N>>B>>D;
 uint src;
 uint end=(1<<B)-1;
 uint  *result= new uint[N];
 result[0]=0;
 int ptr=1;
 for(uint i=1;i<=end;i++)
 {
  bool  flag=true;
  for(int j=0;j<ptr;j++)
  {
   if(distance1(i,result[j])<D)
   {
    flag=false;
    break;
   }
  }
  if(flag)
  {
   result[ptr++]=i;
  }
  if(ptr==N)
   break;
 }
 fstream fout(“hamming.out”,ios::out);
 for(int i=0;i<ptr;i++)
 {
  fout<<result[i];
  if(((i+1)%10)==0||i==(ptr-1))
   fout<<endl;
  else fout<<” “;
 }
 
}
int distance1(uint a,uint b)
{
 uint x=a^b;
 x=(x & 0x55555555)+((x>>1)& 0x55555555); 
 x=(x & 0x33333333)+((x>>2)& 0x33333333); 
 x=(x & 0x0F0F0F0F)+((x>>4)& 0x0F0F0F0F); 
 x=(x & 0x00FF00FF)+((x>>8)& 0x00FF00FF); 
 x=(x & 0x0000FFFF)+((x>>16)& 0x0000FFFF); 
 return x;

}

[usaco]5.4.5 Big Barn题解

5
 
Big Barn

A Special Treat
Farmer John wants to place a big square barn on his square farm. He hates to cut down trees on his farm and wants to find a location for his barn that enables him to build it only on land that is already clear of trees. For our purposes, his land is divided
into N x N parcels. The input contains a list of parcels that contain trees. Your job is to determine and report the largest possible square barn that can be placed on his land without having to clear away trees. The barn sides must be parallel to the horizontal
or vertical axis.

EXAMPLE
Consider the following grid of Farmer John’s land where `.’ represents a parcel with no trees and `#’ represents a parcel with trees:

          1 2 3 4 5 6 7 8
        1 . . . . . . . .
        2 . # . . . # . .
        3 . . . . . . . .
        4 . . . . . . . .
        5 . . . . . . . .
        6 . . # . . . . .
        7 . . . . . . . .
        8 . . . . . . . .

The largest barn is 5 x 5 and can be placed in either of two locations in the lower right part of the grid.

PROGRAM NAME: bigbrn
INPUT FORMAT
Line 1:  Two integers: N (1 <= N <= 1000), the number of parcels on a side, and T (1 <= T <= 10,000) the number of parcels with trees 

Lines 2..T+1: Two integers (1 <= each integer <= N), the row and column of a tree parcel 

SAMPLE INPUT (file bigbrn.in)
8 3
2 2
2 6
6 3

OUTPUT FORMAT
The output file should consist of exactly one line, the maximum side length of John’s barn.

SAMPLE OUTPUT (file bigbrn.out)
5

 

——————————————————————————–

以前做过类似的题,所以这次特别的快。
算法很简单,记录每一个节点向左上方能够延伸出来的最大的方块的大小,以及能够向左延伸的最大距离,还有向上延伸的最大距离。
这样一来,如果某个节点是树木,那么这个节点的2个变量置0,否则left和up分别是上一个节点累加1,而squre取左上方一个节点+1,和left还有up相比较,取最小值,就是当前节点的squre。

还有个节省空间的办法,left,up还有squre三个矩阵并不需要n×n,因为有些行用过之后就没有用了,因此只需要保存两行就行了。

USER: Ma yunlei [yunleis2]
TASK: bigbrn
LANG: C++

Compiling…
Compile: OK

Executing…
   Test 1: TEST OK [0.000 secs, 4024 KB]
   Test 2: TEST OK [0.000 secs, 4024 KB]
   Test 3: TEST OK [0.000 secs, 4024 KB]
   Test 4: TEST OK [0.000 secs, 4024 KB]
   Test 5: TEST OK [0.000 secs, 4024 KB]
   Test 6: TEST OK [0.000 secs, 4024 KB]
   Test 7: TEST OK [0.000 secs, 4024 KB]
   Test 8: TEST OK [0.000 secs, 4024 KB]
   Test 9: TEST OK [0.000 secs, 4024 KB]
   Test 10: TEST OK [0.027 secs, 4024 KB]
   Test 11: TEST OK [0.027 secs, 4024 KB]
   Test 12: TEST OK [0.027 secs, 4024 KB]
   Test 13: TEST OK [0.027 secs, 4024 KB]
   Test 14: TEST OK [0.027 secs, 4024 KB]
   Test 15: TEST OK [0.027 secs, 4024 KB]

All tests OK.
YOUR PROGRAM (‘bigbrn’) WORKED FIRST TIME!  That’s fantastic
— and a rare thing.  Please accept these special automated
congratulations.

—————————————————————————

/*
ID:yunleis3
PROG:bigbrn
LANG:C++
*/

#include <fstream>
#include<iostream>

using namespace std;
const int maxn=1001;
const int maxt=10001;
bool metri[maxn][maxn];
int up[2][maxn];
int left1[2][maxn];
int squr[2][maxn];
int n,t;
int large=0;
#define rowindex(row)  ((row)%2)
#define min(x,y)   (x<y?x:y)
#define trimin(x,y,z)  (min(min(x,y),z))
int main()
{
	ifstream fin("bigbrn.in");
	fin>>n>>t;
	for(int i=0;i<t;++i){
		int a,b;
		fin>>a>>b;
		metri[a][b]=true;
	}
	for(int row=1;row<=n;++row){
		for(int col=1;col<=n;++col){
			if(metri[row][col]){
				up[rowindex(row)][col]=0;
				left1[rowindex(row)][col]=0;
				squr[rowindex(row)][col]=0;
			}else {
				up[rowindex(row)][col]=up[rowindex(row-1)][col]+1;
				left1[rowindex(row)][col]=left1[rowindex(row)][col-1]+1;
				squr[rowindex(row)][col]=trimin(up[rowindex(row)][col],left1[rowindex(row)][col],squr[rowindex(row-1)][col-1]+1);
				if(large<squr[rowindex(row)][col])
					large=squr[rowindex(row)][col];
			}
		}
	}
	ofstream fout("bigbrn.out");
	fout<<large<<endl;
	//system("pause");
}

 

syslog 引发死锁

主线程在写 syslog,同时在信号处理函数中也在写syslog,当主线程在写的时候,如果同时触发了信号,那么将会导致死锁。

$pstack 4289

#0 0x00000036768df9ee in __lll_lock_wait_private () from /lib64/libc.so.6

#1 0x000000367688d0dd in _L_lock_1685 () from /lib64/libc.so.6

#2 0x000000367688ce27 in __tz_convert () from /lib64/libc.so.6

#3 0x00000036768cff7d in __vsyslog_chk () from /lib64/libc.so.6

#4 0x00000036768d0580 in syslog () from /lib64/libc.so.6

#5 0x00000000004c8c81 in SigChldHandler ()

#6

#7 0x000000367688d2ad in __tzfile_compute () from /lib64/libc.so.6

#8 0x000000367688ce5f in __tz_convert () from /lib64/libc.so.6

#9 0x00000036768cff7d in __vsyslog_chk () from /lib64/libc.so.6

#10 0x00000036768d0580 in syslog () from /lib64/libc.so.6

#11 0x00000000004c5c21 in HandleNewBinRequest ()


根本原因是syslog内部会调用malloc,而malloc是不可重入函数,在信号处理函数中调用不可重入函数会导致死锁问题。