flink-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (FLINK-2590) DataSetUtils.zipWithUniqueID creates duplicate IDs
Date Mon, 31 Aug 2015 12:06:45 GMT

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

ASF GitHub Bot commented on FLINK-2590:
---------------------------------------

Github user StephanEwen commented on the pull request:

    https://github.com/apache/flink/pull/1075#issuecomment-136352327
  
    +1 for a test, otherwise this looks good!


> DataSetUtils.zipWithUniqueID creates duplicate IDs
> --------------------------------------------------
>
>                 Key: FLINK-2590
>                 URL: https://issues.apache.org/jira/browse/FLINK-2590
>             Project: Flink
>          Issue Type: Bug
>          Components: Java API, Scala API
>    Affects Versions: 0.10, master
>            Reporter: Martin Junghanns
>            Assignee: Martin Junghanns
>            Priority: Minor
>
> The function creates IDs using the following code:
> {code:java}
> shifter = log2(numberOfParallelSubtasks)
> id = counter << shifter + taskId;
> {code}
> As the binary function + is executed before the bitshift <<, this results in cases
where different tasks create the same ID. It essentially calculates
> {code}
> counter*2^(shifter+taskId)
> {code}
> which is 0 for counter = 0 and all values of shifter and taskID.
> Consider the following example.
> numberOfParallelSubtaks = 8 
> shifter = log2(8) = 4 (maybe rename the function?)
> produces:
> {code}
> start: 1, shifter: 4 taskId: 4 label: 256
> start: 2, shifter: 4 taskId: 3 label: 256
> start: 4, shifter: 4 taskId: 2 label: 256
> {code}
> I would suggest the following:
> {code}
> counter*2^(shifter)+taskId
> {code}
> which in code is equivalent to
> {code}
> shifter = log2(numberOfParallelSubtasks);
> id = (counter << shifter) + taskId;
> {code}
> and for our example produces:
> {code}
> start: 1, shifter: 4 taskId: 4 label: 20
> start: 2, shifter: 4 taskId: 3 label: 35
> start: 4, shifter: 4 taskId: 2 label: 66
> {code}
> So we move the counter to the left and add the task id. As there is space for 2^shifter
numbers, this prevents collisions.



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

Mime
View raw message