이벤트를 효율적으로 연관 시키십시오.

Question

저는 C++ Windows 응용 프로그램에서 작업 중이며 상관 기능을 추가해야합니다. 현재 두 개의 이벤트 프로듀서가 있으며 각 프로듀서는 비슷한 이벤트를 생성합니다. 이벤트 생성의 평균 결합 속도는 두 제작자 모두에서 2k/초입니다. 그러나 부하가 걸리면 300-500 k/sec로 점프합니다. 이 이벤트의 단순화 된 버전으로 (

Event 
    ProcessId // e.g. 1234 
    Action // e.g. 0, 1, 2 
    Timestamp // e.g. LARGE_INTEGER Windows timestamp 

같은 ProcessId를을 나는 약

• 해시 맵을 생각이

  Filter 
  
      // events are from the same process 
      ev1.ProcessId == ev2.ProcessId 
  
      && 
  
      // events have specific types 
      (ev1.Action == 0 && ev2.Action == 1) 
  
      && 
  
      // they are less than 2 secs apart 
      (abs(ev1.Timestamp - ev2.Timestamp) < 2 seconds) 
  

  같은 외모를 구축 할 필요가 상관 관계 규칙을 보는 방법입니다 키) 대기열 포함 (시간 및 동작 상관 관계)

• 부스트 파이프 라인 (예 : github)

그러나 CPU 및 메모리 사용률을 낮게 유지해야하므로 빠른 이벤트 축출을 처리하는 방법을 잘 모르겠습니다.

누구든지 이벤트를 효율적으로 상관시킬 수있는 솔루션을 제안하십시오 (CPU 영향 최소화 및 메모리 사용 공간 최소화)?

Answer 1

상관 관계가 매우 작기 때문에 데이터를 쉽게 분리하여 시작할 수 있습니다.

스트림 1 (느린/더 작은 스트림)의 모든 개체를 세 개의 해시 맵의 순환 버퍼에 저장합니다. 방금받은 이벤트의 타임 스탬프가 가장 최근의 해시 맵에 넣은 첫 번째 타임 스탬프보다 2 초 이상 오래된 경우 가장 오래된 해시 맵을 비우고 맨 앞에 놓고 나머지는 모두 한 단계 아래로 이동합니다. 또한이 버켓에 넣고있는 첫 번째 항목의 "시작 시간"을 기록합니다.

이렇게하면 스트림 1에서 대략 4-6 초의 데이터 순환 버퍼를 유지할 수 있습니다. 그러면 올바른 순서로 전달되지 않는 메시지에 대해 약간의 버퍼가 제공됩니다.

스트림 2 (크고 빠른 스트림)의 경우 모든 해시 맵에서 간단히 조회를 수행합니다. 일치하는 항목이 있으면 상관 관계 함수를 사용하여 실제로 일치하는지 확인합니다. 이 메시지는 해시 맵 (버킷)의 경우 O(m+b*n log k/b)이고 n 및 m 개의 스트림의 경우 n 스트림의 초당 k 개의 메시지로 실행됩니다. b=3의 경우 스트림 n에서 초당 k 개의 메시지에 대해 O(m + n log k)이 있습니다. 공간 요구 사항은 약 6k이어야합니다.

세 개의 해시 맵만 사용하면 성능이 너무 높아집니다 (메모리 사용량과 CPU 사용량 (해시 맵 비우기에 다소 시간이 걸립니다)), 더 많은 해시 맵을 사용할 수 있습니다 (b 증가). 기억을 유지할 필요가있을 때, 1 ~ 2 개의 시간을 유지하고, 늦은 도착을 위해 작은 버퍼를 기억하십시오.