Parallel computing
- 常见的两种提升计算能力的方法:
- Scale up:即Vertical scaling,升级单机硬件
- Scale out:即Horizontal Scaling,增加更多机器,分散工作
- 由于提升单机的性能逐渐遇到瓶颈(clock speed无法快速提高),scale up在计算需求不断增加时无法满足需求
- 解决办法是
- More efficient Algorithm
- Data reduction
- Workload Allocation - 即parallel computing
From Multi-Core to Parallel Processing
- 尽管clock speed难以提升,但是可以通过增加CPU cores提升性能,这也意味着程序必须主动利用concurrency(并发能力)
- Multi-core processor即在同一块chip上放多个CPU cores,让这些cores可以并行执行计算
- shared memory model使得多个core可以访问同一块memory,但每个 core 是相对独立地执行指令的(拥有独立的local state)
- 然而parallel processing不等于性能成倍提升,cores之间的相互协调会产生coordination ahead,所以并行计算的难点在于让cores高效的合作
Bulk Operations
- 核心原则:尽量让多个worker对于不同数据执行相同的operation,并彼此独立
- 减少cores之间的频繁交流,提高效率
- Data parallelism = same instructions, multiple data items
Parallelism Mechanisms
Sharding/Partitioning
Partitioning
- 把一个大的dataset拆成多个较小部分,分配给不同的node/worker
- 共有两种分配方式:
- vertical partitioning:按columns/tables拆(拆开成多列属性)
- horizontal partitioning:按rows拆(拆开成多行对象)
Sharding
- 将一条数据的key经过hashing得到hash value
- 根据hash value的值决定属于哪个worker
h(k)%n
Replication
- 复制数据,并把副本放在不同位置
- 这样做有三个作用/副作用:
- redundancy:存在多个副本时,一个副本坏了还有其他副本
- scalability:不同的节点可以承担数据读取请求
- consistency:多个副本必须同步,以确保数据的一致性
Hadoop Distributed File System(HDFS)
- HDFS是一种广泛使用的distributed file system,其特点为:
- Fixed-sized partitioning:将大的file拆成固定大小的partition/blocks
- 3-way replication:将blocks及副本分散到多个node中,即使其中一台机器故障也不会丢失
- write-once read-many
Dask
- Dask是一个开源Python并行计算库,可以扩展传统packages如NumPy, Pandas的能力
Why Dask
- Familiar Interface:Dask的API格式类似于NumPy, Pandas,学习成本较低
- Scalability:可以扩展到大型计算集群进行计算而不局限于单台电脑
- Flexibility:可以与大型计算环境结合,并将普通python function转为并行任务
When Dask
- 并行计算会增加许多额外开销如task scheduling, communication, coordination
- 只有当数据太大无法放入RAM时才考虑使用Dask
Dask Collections
- Dask collections是Dask提供给用户使用的并行计算接口
- 分为high level collections和low level collections
High Level Collections
- 包含dask array, dask dataframe, dask bag
- 不仅可以并行计算,还可以处理无法一次性放进内存的大数据集
- 可以简单理解为NumPy, Pandas的并行版本
Low Level Collections
- 相对high level更底层且更自由
- 可以让user自定义并行任务和工作流,如
delayed和futures
Dynamic Task Scheduling
- 当计算任务提交后,Dask不会让单个worker从头做到尾,而是将大任务拆分成多个小任务。让不同worker同时工作,从而实现parallel computing
- Scheduler就负责这一组织和调度工作,它决定了:
- 哪个task给哪个worker
- 协调多个worker
- 管理任务执行顺序
- 收集计算成果
Dask Arrays
- 可以看作NumPy Array的并行版本,将大数组拆成较小的chunk
原始大数组
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
可以拆成
Chunk 1 Chunk 2
1 2 3 4
5 6 7 8
Chunk 3 Chunk 4
9 10 11 12
13 14 15 16
Lazy Evaluation
result = dask_array.sum() #作为中间态保存,不计算
- 因此,我们应当先用Dask将大数据压缩成小的结果(如平均值), 最后再
.compute()
Block Algorithms
- 其不仅把数据拆开,还把计算任务也跟着拆开
- 每个worker只需要处理属于自己的那部分chunk
import numpy as np
import dask.array as da
data = np.array([
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
])
#转化为dask array,按2*2的chunk size拆分
dask_arr = da.from_array(data, chunks=(2, 2))
#定义计算(lazy evaluation)
result = dask_arr.sum()
#实际运算(lazy evaluation)
print(result.compute())
Splitting chunks
- Dask Array怎么切chunk,会直接影响整体性能
- 可以使用
dask.array创建data array
dask_data = da.ones((10000, 12000), chunks=1)
#注意此处是chunk size=1,而不是chunk数量=1
Chunk的定义方式
chunks=1000代表在每个dimension上chunk大小为1000
chunks=(1000,2000)使用二维数组定义
chunks={0: 1000, 1: 2000}更为详细的指定,在axis 0上chunk size=1000/axis 1上chunk size=2000
Chunk size的权衡
- dask array在创建后也可以重新改变chunk的划分,这被称为Rechunk
- 但是这会导致数据需要重新组织,并增加额外的计算和communication overhead
- 所以dask中一般每个chunk介于100MB~1GB之间
Dask Client/Cluster
from dask.distributed import Client
client = Client(n_workers=2) #在本机启动一个dask cluster并创建2个workers
client
Dask delayed
@dask.delayed
def inc(x):
return x + 1
@dask.delayed
def double(x):
return x * 2
@dask.delayed
def add(x, y):
return x + y
x = 5
a = inc(x)
b = double(x)
c = add(a, b)
#假如没有@dask.delayed,普通python会立即执行计算
#而添加@dask.delayed后,如a会得到Delayed('inc-...'),标识一处待执行的计算
Dask DataFrame
- Dask dataframe是由多个pandas dataframe partitions组成的可以并行处理的大型dataframe,本质上并不是一种新的数据结构
- 由于pandas只能处理能放进内存中的数据,因此需要dask dataframe解决性能瓶颈问题
Read file
import dask.dataframe as dd
df = dd.read_csv(
'data.csv',
parse_dates='timestamp'
)
#同时dataframe也可以一次读取多个文件
import dask.dataframe as dd
df = dd.read_csv(
'data/*.csv', #匹配所有csv文件
parse_dates='timestamp'
)
- 在逻辑上可以将多个文件的数据视作一个dask dataframe再拆成多个partitions进行处理
- 注意读取时也有’lazy output’,并不会读取整个文件到内存中
Lazy Computation
df.x.mean() #得到lazy result:dd.Scalar<series-…, dtype=float64>
df.x.mean().compute() #真正计算
链接