[jira] [Comment Edited] (KAFKA-2092) New partitioning for better load balancing

["Gianmarco De Francisci Morales (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/KAFKA-2092?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14589634#comment-14589634 ] 

Gianmarco De Francisci Morales edited comment on KAFKA-2092 at 6/22/15 8:42 AM:
--------------------------------------------------------------------------------

Thanks for your comment [~jkreps].
Indeed, this uses the load estimated at the producer to infer the load at the consumer. You might think this does not work but indeed it does in most cases (see [1] for details). I am not sure whether the lifecycle of the producer has any impact here. The goal is simply to send balanced partitions out of the producer.

Regarding the key=>partition mapping, yes this breaks the 1 key to 1 partition mapping. That's exactly the point, to offer a new primitive for stream partitioning. If you are doing word count you need a final aggregator as you say, but the aggregation is O(1) rather than O(W) [where W is the number of workers, i.e., parallelism of the operator]. Also, if you imagine building views out of these partitions, you can query 2 views rather than 1 to obtain the final answer (again, compared to shuffle grouping where you need W queries).

I disagree with your last point (and the results do too). Given that you have 2 options, the imbalance is reduced much more than just by 2 times, because you create options to offload part of the load on a heavy partition to the second choice, thus creating a network of "backup/offload" options to move to when one key becomes hot. It's as creating interconnected pipes where you pump a fluid into.

What is true is that if the single heavy key is larger than (2/W)% of the stream, then this technique cannot help you to achieve perfect load balance.


was (Author: azaroth):
Thanks for your comment [~jkreps].
Indeed, this uses the load estimated at the producer to infer the load at the consumer. You might think this does not work but indeed it does in most cases (see [1] for details). I am not sure whether the lifecycle of the producer has any impact here. The goal is simply to send balanced partitions out of the producer.

Regarding the key=>partition mapping, yes this breaks the 1 key to 1 partition mapping. That's exactly the point, to offer a new primitive for stream partitioning. If you are doing word count you need a final aggregator as you say, but the aggregation is O(1) rather than O(W) [where W is the number of workers, i.e., parallelism of the operator]. Also, if you imagine building views out of these partitions, you can query 2 views rather than 1 to obtain the final answer (again, compared to shuffle grouping where you need p queries).

I disagree with your last point (and the results do too). Given that you have 2 options, the imbalance is reduced much more than just by 2 times, because you create options to offload part of the load on a heavy partition to the second choice, thus creating a network of "backup/offload" options to move to when one key becomes hot. It's as creating interconnected pipes where you pump a fluid into.

What is true is that if the single heavy key is larger than (2/W)% of the stream, then this technique cannot help you to achieve perfect load balance.

> New partitioning for better load balancing
> ------------------------------------------
>
>                 Key: KAFKA-2092
>                 URL: https://issues.apache.org/jira/browse/KAFKA-2092
>             Project: Kafka
>          Issue Type: Improvement
>          Components: producer 
>            Reporter: Gianmarco De Francisci Morales
>            Assignee: Jun Rao
>         Attachments: KAFKA-2092-v1.patch
>
>
> We have recently studied the problem of load balancing in distributed stream processing systems such as Samza [1].
> In particular, we focused on what happens when the key distribution of the stream is skewed when using key grouping.
> We developed a new stream partitioning scheme (which we call Partial Key Grouping). It achieves better load balancing than hashing while being more scalable than round robin in terms of memory.
> In the paper we show a number of mining algorithms that are easy to implement with partial key grouping, and whose performance can benefit from it. We think that it might also be useful for a larger class of algorithms.
> PKG has already been integrated in Storm [2], and I would like to be able to use it in Samza as well. As far as I understand, Kafka producers are the ones that decide how to partition the stream (or Kafka topic).
> I do not have experience with Kafka, however partial key grouping is very easy to implement: it requires just a few lines of code in Java when implemented as a custom grouping in Storm [3].
> I believe it should be very easy to integrate.
> For all these reasons, I believe it will be a nice addition to Kafka/Samza. If the community thinks it's a good idea, I will be happy to offer support in the porting.
> References:
> [1] https://melmeric.files.wordpress.com/2014/11/the-power-of-both-choices-practical-load-balancing-for-distributed-stream-processing-engines.pdf
> [2] https://issues.apache.org/jira/browse/STORM-632
> [3] https://github.com/gdfm/partial-key-grouping



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)