Shuffle no Spark

Quando falamos em shuffle de dados, estamos falando em redistribuir entre os nós os dados de acordo com uma coluna para facilitar o processamento de acordo com a necessidade.

Precisamos ter atenção pois o shuffle exige muito da rede: a troca de dados entre todos os nós envolvidos é muito grande e há grande uso do disco com muitas escritas e serializações ocorrendo no processo.

Diagrama

flowchart LR
    subgraph Stage1["Estágio 1 (antes do shuffle)"]
        direction TB
        E1["Executor 1\nchaves: A, B, C, D"]
        E2["Executor 2\nchaves: B, A, D, C"]
    end

    subgraph SW["Shuffle Write (disco local)"]
        direction TB
        W1B0["Executor 1\nbucket 0: A, A"]
        W1B1["Executor 1\nbucket 1: B, C, D"]
        W2B0["Executor 2\nbucket 0: A"]
        W2B1["Executor 2\nbucket 1: B, C, D"]
    end

    subgraph SR["Shuffle Read (rede)"]
        direction TB
        N1["Reducer 0\nbusca bucket 0 em todos"]
        N2["Reducer 1\nbusca bucket 1 em todos"]
    end

    subgraph Stage2["Estágio 2 (após o shuffle)"]
        direction TB
        R1["Executor A\nA, A, A agrupados"]
        R2["Executor B\nB, C, D, B, C, D agrupados"]
    end

    E1 -->|"hash(key)"| W1B0 & W1B1
    E2 -->|"hash(key)"| W2B0 & W2B1
    W1B0 -->|fetch| N1
    W2B0 -->|fetch| N1
    W1B1 -->|fetch| N2
    W2B1 -->|fetch| N2
    N1 --> R1
    N2 --> R2

O ponto central que o diagrama mostra: cada executor escreve N arquivos no disco (um por bucket de destino), e cada reducer vai buscar o seu bucket em todos os executores pela rede. É esse tráfego all-to-all que torna o shuffle a operação mais cara do spark.

Particularmente, acho o termo shuffle confuso. Quando embaralhamos cartas esperamos que elas fiquem mais bagunçadas. Mas a ideia aqui é agrupar os dados por uma determinada coluna, como organizar um baralho por naipes.

Conexões

• spark-arquitetura: onde o shuffle se encaixa no modelo Job/Stage/Task
• spark-sort: variação do shuffle que usa RangePartitioner em vez de HashPartitioner
• spark-tamanho-blocos: tamanho das partições afeta diretamente o custo do shuffle
• sistemas-distribuidos-particionamento: estratégias de particionamento que influenciam o shuffle

Referências

• Spark Shuffle documentation