用户注册



邮箱:

密码:

用户登录


邮箱:

密码:
记住登录一个月忘记密码?

发表随想


还能输入:200字

机箱    -  云代码空间

——

算法无国界 国内算法同样牛

2013-01-12|3145阅||

摘要:1.算法无国界 国内算法同样牛 几天前,CSDN编译了国外AddThis公司的数据分析副总监Matt Abrams在High Scalability上发表的一篇文章,Matt Abrams在这篇文章中向读者介绍了AddThis仅用了1.5KB内存就计算了十亿个不同的对象,充

1.算法无国界 国内算法同样牛

几天前,CSDN编译了国外AddThis公司的数据分析副总监Matt Abrams在High Scalability上发表的一篇文章,Matt Abrams在这篇文章中向读者介绍了AddThis仅用了1.5KB内存就计算了十亿个不同的对象,充分展示了算法的魅力。

这篇文章在微博上得到了广泛关注,并得知一淘的算法也同样出彩。为此,CSDN采访了一淘数据部的张洋(他曾先后就读于烟台大学和北京航空航天大学,2011年在北京航空航天大学取得计算机理论硕士学位,同年加入淘宝,目前在一淘数据部工作),请他讲解一下一淘的相关算法。

图:一淘数据部工程师 张洋

张洋表示,在电子商务的数据分析领域有一些很关键的指标(例如unique visitor,简称UV,指在一定的时间空间维度约束下独立访客的数量)的计算是很常见的任务。一般来说我们首先会通过某种手段给每一个独立访客做一个标记(例如通过cookie),然后会在所有访问日志中记录下访客的标记,这样一来,UV的计算就等价为在一个可重复的用户标记集合中计算不重复元素的个数,也就是数学上的基数。基数的计算有两个难点:一是不利于实时流计算的实现第二点就是传统的基数计算方法无法有效合并

一淘使用的算法主要是Adaptive Counting算法,这个算法出现在 “Fast and accurate traffic matrix measurement using adaptive cardinality counting” 这篇论文里,但是一淘同时在ccard-lib里也实现了Linear Counting、LogLog Counting和HyperLogLog Counting等常见的基数估计算法。

这些算法是概率算法,就是通过牺牲一定的准确性(但是精度可控,并可以通过数学分析给出控制精度的方法),来大幅节省计算的资源使用。例如我们仅仅使用8k的内存就可以对一个数亿量级的UV进行估计,而误差不超过2%,这比使用B树或原始bitmap要大幅节省内存。同时基数估计算法用到了经过哈希变换的bitmap空间,在大幅节省内存的同时依然可以实现高效合并,这就同时解决了上面提到的两个难点。

2.Prismatic:用机器学习分析用户兴趣只需10秒钟

这篇文章主要描述的是Prismatic公司系统架构,作者是Todd Hoff,本文出自Todd对Prismatic的程序员Jason Wolfe的邮件专访。

关于Prismatic,首先有几个事情要说明下。他们的创业队伍很小,仅仅由4个计算机科学家构成,其中的三个都是年轻有为的斯坦福以及伯克利博士。他们是在用智慧解决信息超载这个问题,然而这些博士也同时担任着程序员的角色:开发网站、iOS程序、大数据以及机器学习需要的后台程序。Prismatic系统架构的亮点是如和使用机器学习实时地解决社交媒体流的处理问题。由于商业机密的原因,他没有透露他们的机器学习技术,但是我们可以通过架构看个大概。Prismatic创始人之一Bradford Cross把Prismatic的系统简洁地描述为:“它是一个提供大规模、实时以及动态的个性化信息排名、分类以及分组功能的综合系统。”接下来就把这个系统的架构展现给大家。

Prismatic主要功能是发现我们的兴趣,为我们推荐阅读

图:越来越多的应用开始关注用户的阅读推荐

今天你应该读点什么呢?任何一个现代人每天都会陷入这个困境,大家通常使用一些很隐秘的途径去找到自己想要读的东西:Twitter、RSS、Facebook、Pinterest、G+、email以及Techmeme等这些信息源。Prismatic回答了“今天我应该读什么?”的问题,Jason Wolfe慷慨的同意并且详细地描述下他们正在使用的解决方案,言语中包含了许多时髦的技术名词,例如机器学习,社交图谱,大数据,过程化编程以及事实需求等等。然而结果是他们的方法更隐秘,但和其他一些相似应用不一样的地方在于他们会发掘你的兴趣,无论这些兴趣在你的信息中藏得有多深。

正如大家预料的,他们的做法有点特别。他们选了Clojure做为开发语言,它是一个编译成Java bytecode的现代Lisp语言。主要目的是充分利用过程化语言去构建具有丰富粒度,结构自由的程序,从而满足各种问题带来的特殊需求。列举两个他们用到的过程化语言的优点的例子:第一个是他们几乎每个地方都使用图库。对于每个用户来说,他们的图形计算可以被称为低延迟,流程化的map-reduce任务集;另外一个例子是他们使用子图实现了模块化的服务配置。 

他们把系统设计的焦点放在过程化开发上来,避免了使用像Hadoop那样的巨型框架,转去使用小型的,这使得系统更可靠,更容易纠错,更容易扩展以及更容易理解。Prismatic的机器学习做法的难点在于要求一个非常长的训练周期。

3.三英战SQL:解析NoSQL的可靠性及扩展操作

NoSQL的高性能、易扩展及可靠性一直深受数据工作者的喜爱,然而对比传统关系型数据库NoSQL的优势究竟又在何处。Esen Sagynov在DZone上发布了一篇文章,从运行方面分析Cassandra,HBase以及MongoDB产品的扩展性和可靠性;详述了3个NoSQL数据库在故障恢复中的性能和可靠性,更谈及了扩展过程中带来的性能影响。

Cassandra

Cassandra提供高可用性的写操作,然而,它需要很长时间来从一个失败中恢复数据。这是因为Cassandra识别要恢复的所有数据,然后读和写每个数据的最新版本。它还因在响应服务请求添加新节点时,仍在恢复数据,导致错误的读取结果返回。此外,Read Repair会在读取数据用以恢复的时候运行两次。尽管它在新节点添加同时发生节点失败会有相对处理,但是如果在数据恢复之前进行读取仍然会返回错误的结果。因此一致性等级的性能不被提高,它仍然不能用于需要读操作的服务。

HBase

由于它的配置问题,HBase自身存在很多因素可能导致问题的产生。不过对比Cassandra节点失败时必须进行数据的恢复,HBase却不需要恢复数据,除非HDFS出现问题。这样HBase宕机时间就会很短,即使HDFS出现问题宕机时间也不会很长。虽然读性能在数据的恢复过程中会受到影响,但是数据的一致性完全可以得到保证。用这种方式,如果SPoF部分成为冗余,我们将从HBase获得很高的可靠性。

MongoDB提供了一个自动故障恢复并且发生宕机的时间很短。然而,异步复制方式在故障恢复的过程中很容易造成数据的丢失。

当然,在最终选择适合自己的数据库解决方案之前,应该对比每个产品的特点。举个例子,CUBRID 关系型数据库系统,为数据的一致性提供了同步的高可用性体系,虽然没有数据的丢失问题,但是它远远比不上NoSQL解决方案的性能。

4.比谷歌手表更酷!基于大数据分析的睡衣

大数据最具代表性的气质是收集和分析来自各类终端和应用的用户信息,通过组织或研究团队的智能分析,获得更多机会。其增长最快的区域毫无疑问是数字分析,有专家甚至认为,如果你是一个数据分析师,那你几乎可入任何你想要进入的领域(或者成为你希望的任何角色)。TNW上发表了Niall Harbison的一篇文章《大数据让“可能”实现:科技改变生活》,列出了大数据引领创新的三种应用模式,并分享了诸多颇富创意的企业。其中,Pebble手表比Google Time要早很多,但设计思路却有诸多重合,而SleepShirt更是让基于大数据的睡眠控制成为了可能。

无疑,这开创了应用的新格局。比如企业能够跟上第三世界国家食品涨价的趋势,政府及医疗部门能够预测流感爆发周期,健康与锻炼的自我追踪,以及预知更多与我们生活密切相关的及时信息。这些信息来自更多的终端和应用,PC、笔记本、智能手机、平板电脑、汽车、手表甚至眼镜等。有一天你会发现,生活中所有痕迹都可以被收集,并通过不同途径被分析和应用。

5.带你入门Map/Reduce

本篇文章来自Aurelien博客,用一个很简单的用例为初学者介绍了Map/Reduce的使用方法;希望为广大初学者带来帮助。

你可能已经知道:Map/Reduce是一种模式,非常适合令人烦恼的并行算法。但是什么是令人烦恼的并行算法?答案:这个算法非常适合被多重并行的执行。那么什么样的模式才会非常适合并行算法?答案:任何作用在数据上的算法都会被隔离。

如果你编写的程序经常会在同一个时刻执行多重事件,并且它们需要访问一些公用数据;那么将会出现冲突,你必须着手处理当一个事件修改某个数据时,而另一个事件正在读取这段数据。这就是并发操作。如果你事件作用的数据段没有被其它事件操作,那么做的将是并行操作。显而易见:你可以使用扩展来解决并发性问题。

简单的Map/Reduce入门希望能帮助弄清Map/Reduce任务的实现过程,下面附带用例代码:用例代码部分(Java)

6.谷歌布局亚太地区数据中心建设 服务响应速度有望提升30%

来自经济时报的消息称:谷歌将于今年晚些时候在台湾和新加坡建立数据中心,这将会使谷歌在亚太地区的服务响应速度提升30%。The Next Web的记者Josh Ong对此事件进行了报道,CSDN编译如下:

在2011年年底,谷歌在新加坡的数据中心动工,这是谷歌首次在东南亚地区建立数据中心。根据之前Google在2011年发布的消息,他们已在新加坡、台湾彰化县和香港九龙区分别购买了2.45公顷、15公顷及 2.7公顷土地以兴建数据中心,并将采用其自家的高技术和环保标准,预料有望成为亚洲区内最有效率与环保的数据中心之一。

谷歌表示,新加坡数据中心的建设将于今年提前完工,而台湾的数据中心将会在2013年下半年开始局部的测试工作。至于香港的数据中心也在策划进行之中,但是目前还没有给出准确的开工时间。据估算这三个数据中心的建设将耗费7亿多美元。

如果这三个数据中心进行正常的启动和运作,印度也将成为主要的受益者之一。

7.AWS被纳为“战略物资” 市值或可达到300亿美元?

awsrevgrowth2013

亚马逊网络服务在2013年预计将产生38亿美元的效益,Macquarie Capital分析师在一份研究报告中认为,如果把AWS拆分成一个单独的公司,其市值可能在190亿美元至300亿美元之间。

Macquarie的这份研究报告,源于其分析师Ben Schachter带领的研究小组的研究,他们假设AWS占亚马逊“其他”收入类别增长的全部。

在Macquarie研究报告发布的同一时间,摩根士丹利的分析师Scott Devitt基于AWS对国际增长和全球交付服务的重要性,称AWS是一种战略物资。

Schachter表示,AWS将会被更多的大企业使用,这一事实可能会促进经济增长。到目前为止,AWS还是更多的依赖于创业公司和小型公司。

Macquarie的Schachter估计,AWS的潜在市场规模为110亿美元,在2012年的实际收入约为20亿美元。在2013年,预计AWS的营收将达到38亿美元。



文章来源:http://www.csdn.net/article





顶 5踩 4收藏
文章评论
    发表评论