百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 编程字典 > 正文

大规模数据处理初体验:怎样实现大型电商热销榜?

toyiye 2024-09-02 02:27 3 浏览 0 评论

你好,我是蔡元楠, 目前在 Google Brain 担任 AI Healthcare (人工智能的健康医疗应用) 领域资深工程师,也是极客时间《大规模数据处理实战》的专栏作者,这篇文章便出自这个专栏的第三篇文章。

我在Google面试过很多优秀的候选人,应对普通的编程问题coding能力很强,算法数据结构也应用得不错。

可是当我追问数据规模变大时该怎么设计系统,他们却并不能给出很好的答案,这说明他们缺乏必备的规模增长的技术思维(mindset of scaling)。这会限制这些候选人的职业成长。因为产品从1万用户到1亿用户,技术团队从10个人到1000个人,你的技术规模和数据规模都会完全不一样。

今天我们就以大型电商热销榜为例,来谈一谈从1万用户到1亿用户,从GB数据到PB数据系统,技术思维需要怎样的转型升级?

同样的问题举一反三,可以应用在淘宝热卖,App排行榜,抖音热门,甚至是胡润百富榜,因为实际上他们背后都应用了相似的大规模数据处理技术。

真正的排序系统非常复杂,仅仅是用来排序的特征(features)就需要多年的迭代设计。

为了便于这一讲的讨论,我们来构想一个简化的玩具问题来帮助你理解。

假设你的电商网站销售10亿件商品,已经跟踪了网站的销售记录:商品id和购买时间 {product_id, timestamp},整个交易记录是1000亿行数据,TB级。作为技术负责人,你会怎样设计一个系统,根据销售记录统计去年销量前10的商品呢?

举个例子,假设我们的数据是:

product_id

timestamp

1

1553721167

2

1553721199

3

1553721220

1

1553721241

我们热销榜可以按 product_id 排名,顺序为:1, 2, 3。

小规模的经典算法

如果上过极客时间的《数据结构与算法之美》,你可能一眼就看出来,这个问题的解法分为两步:

第一步,统计每个商品的销量。你可以用哈希表(hashtable)数据结构来解决,这是一个O(n)的算法,这里的n是1000亿。

第二步,找出销量前十,这里可以用经典的Top K算法,也是O(n)的算法。如果你考虑到了这些,先恭喜你答对了。在小规模系统中,我们确实完全可以用经典的算法简洁漂亮地解决。以Python编程的话可能是类似这样的:

def CountSales(sale_records):
 """Calculate number of sales for each product id. 
 
 Args:
 sales_records: list of SaleRecord, SaleRecord is a named tuple, 
 e.g. {product_id: “1”, timestamp: 1553721167}.
 Returns:
 dict of {product_id: num_of_sales}. E.g. {“1”: 1, “2”: 1}
 """
 sales_count = {}
 for record in sale_records:
 sales_count[record[product_id]] += 1
 
 return sales_count
def TopSellingItems(sale_records, k=10): 
 """Calculate the best selling k products. 
 
 Args:
 sales_records: list of SaleRecord, SaleRecord is a named tuple, 
 e.g. {product_id: “1”, timestamp: 1553721167}.
 K: num of top products you want to output.
 Returns:
 List of k product_id, sorted by num of sales.
 """
 sales_count = CountSales(sale_records)
 return heapq.nlargest(k, sales_count, key=sales_count.get)

但在任何系统中,随着尺度的变大,很多方法就不再适用。

比如,在小尺度经典物理学中适用的牛顿力学:

在高速强力的物理系统中就不再适用,在狭义相对论中有另外的表达:

在社会系统中也是一样,管理10个人的团队,和治理14亿人口的国家,复杂度也不可同日而语。

具体在我们这个问题中,同样是Top K算法,当数据规模变大时,会遇到哪些问题呢?

第一,内存占用。

对于TB级的交易记录数据,很难找到单台计算机能够容纳那么大的哈希表了。

你可能想到,那我不要用哈希表去统计商品销售量了,我把销量计数放在磁盘里完成好了。比如,就用一个1000亿行的文件或者表,然后再把销量统计结果一行一行读进后面的堆树/优先级队列。

理论上听起来不错,实际上是否真的可行呢?那我们看下一点。

第二,磁盘I/O等延时问题。

当数据规模变大,我们难以避免地需要把一些中间结果存进磁盘,以应对单步任务出错等问题。

一次磁盘读取大概需要10ms的时间。如果按照上一点提到的文件替代方法,时间会很长。因为我们是一个O(n * log k)的算法,这就需要10ms * 10^9 = 10 ^ 7 s = 115 天的时间。你可能需要贾跃亭附体,才能忽悠老板接受这样的设计方案了。

这些问题怎么解决呢?你可能已经想到,当单台机器已经无法适应我们数据或者问题的规模,我们需要横向扩展。

大规模分布式解决方案

之前的思路依然没错。但是我们需要把每一步从简单的函数算法,升级为计算集群的分布式算法。

统计每个商品的销量

我们需要的第一个计算集群,就是统计商品销量的集群。

例如,1000台机器,每台机器一次可以处理1万条销售记录。对于每台机器而言,它的单次处理又回归到了我们熟悉的传统算法,数据规模大大缩小。

下图就是一个例子,图中每台机器输入的是2条销售记录,输出的是对于他们的本地输入而言的产品销量计数。

找出销量前K

我们需要的第二个计算集群,则是找出销量前十的集群。

这里我们不妨把问题抽象一下,抽象出的是销量前K的产品。因为你的老板随时可能把产品需求改成前20销量,而不是前10了。

在上一个统计销量集群得到的数据输出,将会是我们这个处理流程的输入。所以这里需要把分布在各个机器上分散的产品销量汇总出来。例如,把所有product_id = 1的销量全部叠加。

下图示例是K = 1的情况,每台机器先把所有product_id = 1的销量叠加在了一起,再找出自己机器上销量前K = 1的商品。你可以看到,对于每台机器而言,他们的输出就是最终排名前K = 1的商品候选者。

汇总最终结果

到了最后一步,你需要把在“销量前K集群”中的结果汇总出来。也就是说,从所有排名前K=1的商品候选人中找出真正的销量前K=1的商品。

这时候完全可以用单一机器解决了。因为实际上你汇总的就是这1000台机器的结果,规模足够小。

看到这里,你已经体会到处理超大规模数据的系统是很复杂的。

当你辛辛苦苦设计了应对1亿用户的数据处理系统时,可能你就要面临另一个维度的规模化(scaling)。那就是应用场景数量从1个变成1000个。每一次都为不同的应用场景单独设计分布式集群,招募新的工程师维护变得不再“可持续发展”。

这时,你需要一个数据处理的框架

大规模数据处理框架的功能要求

在「02篇 怎样设计下一代数据处理技术?」中,我们对于数据处理框架已经有了基本的方案。这里这个实际的例子其实为我们的设计增加了新的挑战。

很多人面对问题,第一个想法是找有没有开源技术可以用一下。

但我经常说服别人不要先去看什么开源技术可以用,而是从自己面对的问题出发独立思考,忘掉MapReduce,忘掉Apache Spark,忘掉Apache Beam。

如果这个世界一无所有,你会设计怎样的大规模数据处理框架?你要经常做一些思维实验,试试带领一下技术的发展,而不是永远跟随别人的技术方向。

在我看来,两个最基本的需求是:

  1. 高度抽象的数据处理流程描述语言。作为小白用户,我肯定再也不想一一配置分布式系统的每台机器了。作为框架使用者,我希望框架是非常简单的,能够用几行代码把业务逻辑描述清楚。
  2. 根据描述的数据处理流程,自动化的任务分配优化。这个框架背后的引擎需要足够智能,简单地说,要把那些本来手动配置的系统,进行自动任务分配。

那么理想状况是什么?对于上面的应用场景,我作为用户只想写两行代码。

第一行代码:

sales_count = sale_records.Count()

这样简单的描述,在我们框架设计层面,就要能自动构建成上文描述的“销量统计计算集群”。

第二行代码

top_k_sales = sales_count.TopK(k)

这行代码需要自动构建成上文描述的“找出销量前K集群”。

看到这里,你能发现这并不复杂。我们到这里就已经基本上把现代大规模数据处理架构的顶层构造掌握了。而背后的具体实现,我会在后面的专栏章节中为你一一揭晓。

小结

接下来我为这一讲做个小结。这一讲中,我们粗浅地分析了一个电商排行榜的数据处理例子。

从GB数据到TB数据,我们从小规模算法升级到了分布式处理的设计方案;从单一TB数据场景到1000个应用场景,我们探索了大规模数据处理框架的设计。

这些都是为了帮助你更好地理解后面所要讲的所有知识。比如,为什么传统算法不再奏效?为什么要去借助抽象的数据处理描述语言?希望在后面的学习过程中,你能一直带着这些问题出发。

拓展阅读:

为什么MapReduce会被硅谷一线公司淘汰?

MapReduce后谁主沉浮:怎样设计下一代数据处理技术?

更多内容点击了解更多

相关推荐

# Python 3 # Python 3字典Dictionary(1)

Python3字典字典是另一种可变容器模型,且可存储任意类型对象。字典的每个键值(key=>value)对用冒号(:)分割,每个对之间用逗号(,)分割,整个字典包括在花括号({})中,格式如...

Python第八课:数据类型中的字典及其函数与方法

Python3字典字典是另一种可变容器模型,且可存储任意类型对象。字典的每个键值...

Python中字典详解(python 中字典)

字典是Python中使用键进行索引的重要数据结构。它们是无序的项序列(键值对),这意味着顺序不被保留。键是不可变的。与列表一样,字典的值可以保存异构数据,即整数、浮点、字符串、NaN、布尔值、列表、数...

Python3.9又更新了:dict内置新功能,正式版十月见面

机器之心报道参与:一鸣、JaminPython3.8的热乎劲还没过去,Python就又双叒叕要更新了。近日,3.9版本的第四个alpha版已经开源。从文档中,我们可以看到官方透露的对dic...

Python3 基本数据类型详解(python三种基本数据类型)

文章来源:加米谷大数据Python中的变量不需要声明。每个变量在使用前都必须赋值,变量赋值以后该变量才会被创建。在Python中,变量就是变量,它没有类型,我们所说的"类型"是变...

一文掌握Python的字典(python字典用法大全)

字典是Python中最强大、最灵活的内置数据结构之一。它们允许存储键值对,从而实现高效的数据检索、操作和组织。本文深入探讨了字典,涵盖了它们的创建、操作和高级用法,以帮助中级Python开发...

超级完整|Python字典详解(python字典的方法或操作)

一、字典概述01字典的格式Python字典是一种可变容器模型,且可存储任意类型对象,如字符串、数字、元组等其他容器模型。字典的每个键值key=>value对用冒号:分割,每个对之间用逗号,...

Python3.9版本新特性:字典合并操作的详细解读

处于测试阶段的Python3.9版本中有一个新特性:我们在使用Python字典时,将能够编写出更可读、更紧凑的代码啦!Python版本你现在使用哪种版本的Python?3.7分?3.5分?还是2.7...

python 自学,字典3(一些例子)(python字典有哪些基本操作)

例子11;如何批量复制字典里的内容2;如何批量修改字典的内容3;如何批量修改字典里某些指定的内容...

Python3.9中的字典合并和更新,几乎影响了所有Python程序员

全文共2837字,预计学习时长9分钟Python3.9正在积极开发,并计划于今年10月发布。2月26日,开发团队发布了alpha4版本。该版本引入了新的合并(|)和更新(|=)运算符,这个新特性几乎...

Python3大字典:《Python3自学速查手册.pdf》限时下载中

最近有人会想了,2022了,想学Python晚不晚,学习python有前途吗?IT行业行业薪资高,发展前景好,是很多求职群里严重的香饽饽,而要进入这个高薪行业,也不是那么轻而易举的,拿信工专业的大学生...

python学习——字典(python字典基本操作)

字典Python的字典数据类型是基于hash散列算法实现的,采用键值对(key:value)的形式,根据key的值计算value的地址,具有非常快的查取和插入速度。但它是无序的,包含的元素个数不限,值...

324页清华教授撰写【Python 3 菜鸟查询手册】火了,小白入门字典

如何入门学习python...

Python3.9中的字典合并和更新,了解一下

全文共2837字,预计学习时长9分钟Python3.9正在积极开发,并计划于今年10月发布。2月26日,开发团队发布了alpha4版本。该版本引入了新的合并(|)和更新(|=)运算符,这个新特性几乎...

python3基础之字典(python中字典的基本操作)

字典和列表一样,也是python内置的一种数据结构。字典的结构如下图:列表用中括号[]把元素包起来,而字典是用大括号{}把元素包起来,只不过字典的每一个元素都包含键和值两部分。键和值是一一对应的...

取消回复欢迎 发表评论:

请填写验证码