미리보기가없는 버킷 간의 가중치 분포

Question

들어오는 데이터 배치를 처리해야하는 작업자가 N입니다. 각 작업자는 "worker X이 N"임을 알 수 있도록 구성됩니다.

데이터가 들어오는 각 배치에는 임의의 고유 한 ID (임의적이며 균일하게 분포 됨)이 있으며 크기가 다릅니다. 처리 시간은 크기에 비례합니다. 크기는 크게 다를 수 있습니다.

새로운 데이터 배치를 사용할 수있게되면 즉시 모든 N 직원이 ​​사용할 수있는 것으로 표시되지만 실제로 처리 할 사람은 입니다. 지금 당장은 각 작업자가 ID % N == X을 계산합니다. 작업자가 배치를 자체 지정하고 다른 작업자는 건너 뜁니다. 이것은 올바르게 작동하고 평균적으로 각 작업자가 같은 수의 배치를 처리하도록합니다. 불행하게도 배치 크기를 고려하지 않기 때문에 일부 작업자는 매우 큰 작업을 스스로 할당 할 수 있기 때문에 다른 작업보다 나중에 처리를 완료 할 수 있습니다.

각 작업자가 일괄 처리 크기를 고려한 방식으로 일괄 처리를 자체 배정하여 평균적으로 각 작업자가 동일한 총 작업 크기를 할당하도록 알고리즘을 변경할 수 있습니까 (예 : 다른 배치에서)?

Answer 1

//Using a queue to store the workers 
//This way we can dequeue and reenqueue workers when they accept jobs 
var _queue = new Queue<Worker>[numOfWorkers]; 

void Setup() { 
    for (int i = 0;i<numOfWorkers -1;i++) { 
     _queue.Enqueue(new Worker()); 
    } 
} 

//Assigns the job to the next worker in line and puts it at the end of queue 
void AcceptJob(Job j) { 
    var w = FindNextAvailableWorker(); 
    w.AssignNewJob(j); 
    _queue.Enqueue(_queue.RemoveAt(_queue.PositionOf(w))); 
} 

//Finds the first free worker or returns the front of queue 
Worker FindNextAvailableWorker() { 
    var w = _queue.front(); 

    while (int i=0;i<_queue.length-1<i++) { 
     if (_queue[i].isWorking==false){ 
      w = _queue[i]; 
      exit loop; 
     } 
    } 

    return w; 
} 

Answer 2

일반 아이디어 : 모든 노드가 각 노드가 지금까지 수행 한 작업을 계속하고이 그가 get.It 그래서 모든 노드가 동일한 결과를 얻을 것이다 결정 방법으로 수행 할 작업에 영향을 미치는, 의사 소통을 할 필요가 없습니다. 우리는 여전히 계수를 사용하지만, 적은 수의 노드는 더 큰 수의 범위를 갖습니다.

알고리즘 :

모든 근로자가 동일한 계산을한다. 각 노드는 모든 노드 ID를 보유한 요소와이 노드가 지금까지 수행 한 작업의 패 런지를 모든 노드의 총 작업과 비교하여 배열합니다 (총 작업의 5 %, 35 % ...). nodeProportion.

이 배열은 (100-nodeProportion) + 0.001 * Node_ID로 정렬됩니다. 일괄 처리가 도착하면 해시 계수 100을하고이 숫자를 K라고합니다.

정렬 된 배열을 검토하여 0 이하가 될 때까지 (100-nodeProportion)을 뺍니다. 우리는 그 노드에 작업을 넘깁니다.

모든 노드는 동일한 계산을 수행하므로 대화 할 필요가 없습니다.

Answer 3

좋아, 몇 가지 고려 사항 :

• 당신은 어떤 메타 데이터 홀더를하지 않으려는, 그래서, 유일한 좋은 방법 X = distributor(arguments)
• 가 이미 매우 간단한 종류의 기능이 일부 기능을 것 등의 통신 노드 X = ID % N하지만 크기, 외관상으로는 문제
• 동일한 작업자에게 똑같은 (큰) 크기가 지정되므로 함수의 크기는 S 인 경우에만 의존 할 수 없습니다.우리는 균일 한 결과를 생성한다 X = F(S, ID) % N
• 기능 같은 것을 찾고, 그래서 최종 모듈로 영업 이익은

이 간단한이

X = hash(ID * S) % N 

좋은 해시 함수, 곱셈 것 시도하는 기능을 균일 한 부하에게 제공 할 것이다 ID*S은 해시에 대한 일반적인 입력으로 바이트 배열을 생성하므로 같은 크기의 작업이 똑같이 분산됩니다. 사용해보기 ...