Spostamento dall'architettura Batch a Streaming mediante una struttura dati Graph

1

Il caso d'uso che sto cercando di risolvere è quello di assegnare milioni di utenti ai loro gruppi / segmenti. Ho migliaia di criteri diversi da cui vengono creati i bucket degli utenti. Per esempio. criteri del bucket:

All married males in NY or LA assign to Bucket/Segment 1;

Attualmente alla fine della giornata, interrogo gli utenti da una tabella della scala TB in cloud, un criterio bucket alla volta, basato su migliaia di criteri bucket differenti. Quindi generare un feed giornaliero per ciascuno di questi segmenti.

Uso il database ogni notte, ma il numero di segmenti / bucket è diventato così grande che non è più possibile interrogare in batch ogni criterio del bucket ogni notte e riempire i bucket.

Invece sto pensando di passare all'architettura di streaming in cui un utente viene assegnato al segmento mentre entra. Per questo sto cercando di caricare le definizioni dei segmenti in una struttura di dati del grafico direzionale (multi-edge) e determinare quale utente si qualifica per quale segmento viene visualizzato dall'utente. Esempio grafico sotto:

Nelcasotistiachiedendoperchéhobisognodipiùspigolitraduevertici,èdirappresentareandconditionpercriteridibucket.Ades.seilsegmento1è

AllmarriedmalesinNYorLAassigntoBucket/Segment1;

Eilsegmento2è:

AllmarriedmalesassigntoBucket/Segment2;

Seisegmenti1e2condividonolostessobordo,questosaràunproblemaperchéirisultatidelsegmento1sonosolounsottoinsiemedeirisultatidelsegmento2.Ilsegmento2nonhafiltridicittà.

Questograficorappresentateoricamentetuttelerelazioniperilmiousoallaperfezione,mailproblemaèchedopoaverimplementatoquestograficoleprestazionidell'algoritmodicreazionedelgraficosonostatedeludenti.Lamaggiorpartedeltempovieneimpiegatapercrearespigoliperiverticineicriteridiunbucketpertuttiipossibilipercorsifinoaquelbordo.

Alcunivaloridifiltrocomeicodicipostalipossonoaveredecinedimigliaiadivalorichesitraduconoinunaproliferazionedispigolitrainodi.Stocercandounmodoperottimizzarequestacreazionedelgrafico.

Modifica:forniscepiùdettaglicomedarispostadiseguito;

  1. Tecnologiachestousando:GoogleCloudDataflow(gestitoApacheBeam).Maggioridettaglisucomestoimplementandoquestosononelcommento qui
  2. Pulisci le regole impostate per utilizzare gli insiemi invece dei valori effettivi: utilizzo set per un sacco di regole come i codici di avviamento postale e l'ho già implementato come zip in {"98500", "98800", ....}. Ma per alcune regole per es. l'e-mail utente non può avere un set e rappresentare ogni e-mail utente nel grafico come un vertice.
  3. Implementa il grafico di propagazione della verità: guarderò più in dettaglio al momento, sto usando HashMap per il mio vertice e i miei bordi. Il mio vertice è v = {vertex_id, HashMap} e il mio bordo = {edge_id, edge_to_vertex}. E il mio grafico è implementato come HashMap
posta PUG 21.05.2017 - 02:29
fonte

1 risposta

1

Il problema in breve:

  • hai milioni di Users e migliaia di Rules per determinare il Segments a cui appartengono (può essere diverso);
  • ogni Rule è una combinazione di condizioni sulle proprietà User ;
  • desideri semplificare l'identificazione Segment per evitare di applicare ogni regola a ogni utente.
  • si verificano problemi di prestazioni

Cause potenziali

Sfortunatamente, siamo in qualche modo nell'oscurità delle tecnologie, e quindi su cosa potrebbe causare il problema di prestazioni che descrivi.

Uno dei problemi di prestazioni è sicuramente correlato ai lunghi elenchi di centinaia di codici postali, che appariranno come una lunga lista di elenchi non selezionati e inefficienti in qualsiasi grafico. Quindi inizia a pulire il set di regole riscrivendole utilizzando una logica impostata (ad esempio if zip in { "98500","98800",.... } anziché if zip=="98500" or zip=="98800" or ... ). Un problema simile è rendere gli intervalli più facilmente identificabili nelle regole (ad esempio if age in [21;49] anziché if age>=21 and age<=49)

Wayward

Dopo l'ottimizzazione di questa regola, puoi elaborare le tue regole e creare un grafico di propagazione della verità:

  • le proprietà di un utente stanno iniziando i nodi (ad esempio city , married , gender , ...)
  • sfoglia tutte le tue regole. Crea uno spigolo su un nodo intermedio per ogni singola condizione, cioè valore ( == ), intervallo e set
  • per ogni valore che deve essere combinato con and crea nuovamente un margine su un altro nodo intermedio, e lo stesso per le relazioni or , l'ultimo spigolo va quindi al segmento.

Con il tuo esempio, questo risulterebbe in un grafico:

city   ----> { NYC, LA }  -----+
                               &------> segment1
married ---> Y   --------------+
        ---> N   ...           |
                               &------> segment2
                               |
gender  ---> M   --------------+
        ---> F   ...

Quando si esegue questo tagger di segmento, le operazioni costose sono nei nodi iniziali. L'utilizzo delle operazioni set (che in Java o C ++ sono implementate con hash-tables o b-tree) farà una differenza significativa rispetto al% sequenziale -chains sequenziale. Dovrai quindi propagare la verità attraverso il grafico, fino a quando non sarà più possibile attivare un nuovo nodo.

Miglioramenti futuri

Potresti prendere in considerazione l'idea di ottimizzare i grafici. Questo è ciò che il compilatore fa per identificare una parte comune in diverse espressioni per calcolarle una sola volta. Tuttavia, questo è davvero un argomento difficile.

    
risposta data 21.05.2017 - 13:37
fonte