Parallel computing

  • 常见的两种提升计算能力的方法:
    1. Scale up:即Vertical scaling,升级单机硬件
    2. Scale out:即Horizontal Scaling,增加更多机器,分散工作
  • 由于提升单机的性能逐渐遇到瓶颈(clock speed无法快速提高),scale up在计算需求不断增加时无法满足需求
  • 解决办法是
    1. More efficient Algorithm
    2. Data reduction
    3. 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
  • 共有两种分配方式:
    1. vertical partitioning:按columns/tables拆(拆开成多列属性)
    2. horizontal partitioning:按rows拆(拆开成多行对象)

Sharding

  • 将一条数据的key经过hashing得到hash value
  • 根据hash value的值决定属于哪个worker
  • h(k)%n

Replication

  • 复制数据,并把副本放在不同位置
  • 这样做有三个作用/副作用:
    1. redundancy:存在多个副本时,一个副本坏了还有其他副本
    2. scalability:不同的节点可以承担数据读取请求
    3. consistency:多个副本必须同步,以确保数据的一致性

Hadoop Distributed File System(HDFS)

  • HDFS是一种广泛使用的distributed file system,其特点为:
    1. Fixed-sized partitioning:将大的file拆成固定大小的partition/blocks
    2. 3-way replication:将blocks及副本分散到多个node中,即使其中一台机器故障也不会丢失
    3. 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

  • 只有当真正需要结果时dask才会真正计算,如
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

Create workers/Start out 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() #真正计算

链接