మెషిన్ లెర్నింగ్‌తో ఆప్టిమైజ్ చేయబడిన బ్లూమ్ ఫిల్టర్‌లతో స్పార్క్ జాయిన్ క్వెరీ ఖర్చులను రాబ్లాక్స్ ఎలా తగ్గిస్తుంది

సారాంశం

రోబ్‌లాక్స్‌లో ప్రతిరోజూ, 70 మిలియన్ల వినియోగదారులు మిలియన్ల కొద్దీ అనుభవాలతో నిమగ్నమవుతారు, ఇది త్రైమాసికానికి మొత్తం 16 బిలియన్ల గంటలకు చేరుకుంటుంది. ఈ పరస్పర చర్య ఒక పెటాబైట్-స్థాయి డేటా లేక్‌ను సృష్టిస్తుంది, ఇది విశ్లేషణ మరియు మెషిన్ లెర్నింగ్ (ML) ప్రయోజనాల కోసం సుసంపన్నం చేయబడుతుంది. మా డేటా లేక్‌లో ఫ్యాక్ట్ మరియు డైమెన్షన్ టేబుల్స్‌ను జోడించడం వనరులను అధికంగా వినియోగిస్తుంది, కాబట్టి దీనిని ఆప్టిమైజ్ చేయడానికి మరియు డేటా షఫిలింగ్‌ను తగ్గించడానికి, మేము లెర్న్డ్ బ్లూమ్ ఫిల్టర్‌లను [1] స్వీకరించాము—ఇవి MLని ఉపయోగించే స్మార్ట్ డేటా నిర్మాణాలు. ఉనికిని అంచనా వేయడం ద్వారా, ఈ ఫిల్టర్‌లు జాయిన్ డేటాను గణనీయంగా తగ్గిస్తాయి, తద్వారా సామర్థ్యాన్ని పెంచుతాయి మరియు ఖర్చులను తగ్గిస్తాయి. ఈ క్రమంలో, మేము మా మోడల్ ఆర్కిటెక్చర్‌లను కూడా మెరుగుపరిచాము మరియు ప్రాసెసింగ్ కోసం మెమరీ మరియు CPU గంటలను తగ్గించడం, అలాగే కార్యాచరణ స్థిరత్వాన్ని పెంచడంలో అవి అందించే గణనీయమైన ప్రయోజనాలను ప్రదర్శించాము.

పరిచయం

మా డేటా లేక్‌లో, ఫ్యాక్ట్ టేబుల్స్ మరియు డేటా క్యూబ్స్ సమర్థవంతమైన యాక్సెస్ కోసం కాలానుగుణంగా విభజించబడతాయి, అయితే డైమెన్షన్ టేబుల్స్‌లో అటువంటి విభజనలు ఉండవు, మరియు అప్‌డేట్‌ల సమయంలో వాటిని ఫ్యాక్ట్ టేబుల్స్‌తో జాయిన్ చేయడం వనరులను అధికంగా వినియోగిస్తుంది. జాయిన్‌లో ఉపయోగించే స్థలం, జాయిన్ చేయబడుతున్న ఫ్యాక్ట్ టేబుల్ యొక్క కాలానుగుణ విభజనపై ఆధారపడి ఉంటుంది. ఆ కాలపరమైన విభజనలో ఉన్న డైమెన్షన్ ఎంటిటీలు, మొత్తం డైమెన్షన్ డేటాసెట్‌లో ఉన్న వాటిలో ఒక చిన్న ఉపసమితి మాత్రమే. ఫలితంగా, ఈ జాయిన్‌లలో ఉన్న చాలా వరకు షఫుల్ చేయబడిన డైమెన్షన్ డేటా చివరికి పక్కన పెట్టబడుతుంది. ఈ ప్రక్రియను ఆప్టిమైజ్ చేయడానికి మరియు అనవసరమైన షఫులింగ్‌ను తగ్గించడానికి, మేము విభిన్న జాయిన్ కీలపై బ్లూమ్ ఫిల్టర్‌లను ఉపయోగించడాన్ని పరిగణించాము, కానీ ఫిల్టర్ పరిమాణం మరియు మెమరీ ఫుట్‌ప్రింట్ సమస్యలను ఎదుర్కొన్నాము.

వాటిని పరిష్కరించడానికి, మేము లెర్న్డ్ బ్లూమ్ ఫిల్టర్లను అన్వేషించాము, ఇది తక్కువ ఫాల్స్ పాజిటివ్ రేట్లను కొనసాగిస్తూనే బ్లూమ్ ఫిల్టర్ పరిమాణాన్ని తగ్గించే ఒక ML-ఆధారిత పరిష్కారం. ఈ ఆవిష్కరణ గణన ఖర్చులను తగ్గించడం మరియు సిస్టమ్ స్థిరత్వాన్ని మెరుగుపరచడం ద్వారా జాయిన్ ఆపరేషన్‌ల సామర్థ్యాన్ని పెంచుతుంది. మా పంపిణీ చేయబడిన కంప్యూటింగ్ వాతావరణంలో సాంప్రదాయ మరియు ఆప్టిమైజ్ చేయబడిన జాయిన్ ప్రక్రియలను క్రింది రేఖాచిత్రం వివరిస్తుంది.

లెర్న్డ్ బ్లూమ్ ఫిల్టర్లతో జాయిన్ సామర్థ్యాన్ని మెరుగుపరచడం

ఫ్యాక్ట్ మరియు డైమెన్షన్ టేబుల్స్ మధ్య జాయిన్‌ను ఆప్టిమైజ్ చేయడానికి, మేము లెర్న్డ్ బ్లూమ్ ఫిల్టర్ ఇంప్లిమెంటేషన్‌ను స్వీకరించాము. మేము ఫ్యాక్ట్ టేబుల్‌లో ఉన్న కీల నుండి ఒక ఇండెక్స్‌ను నిర్మించాము మరియు తదనంతరం జాయిన్ ఆపరేషన్‌కు ముందు డైమెన్షన్ డేటాను ప్రీ-ఫిల్టర్ చేయడానికి ఆ ఇండెక్స్‌ను ఉపయోగించాము. 

సాంప్రదాయ బ్లూమ్ ఫిల్టర్‌ల నుండి లెర్న్డ్ బ్లూమ్ ఫిల్టర్‌లకు పరిణామం

సాంప్రదాయ బ్లూమ్ ఫిల్టర్ సమర్థవంతమైనప్పటికీ, మనకు కావలసిన ఫాల్స్ పాజిటివ్ రేటును అందుకోవడానికి దానిని లోడ్ చేయాల్సిన ప్రతి వర్కర్ నోడ్‌కు అది 15-25% అదనపు మెమరీని జోడిస్తుంది. కానీ లెర్న్డ్ బ్లూమ్ ఫిల్టర్‌లను ఉపయోగించడం ద్వారా, అదే ఫాల్స్ పాజిటివ్ రేటును కొనసాగిస్తూ, మేము గణనీయంగా తగ్గిన ఇండెక్స్ పరిమాణాన్ని సాధించాము. బ్లూమ్ ఫిల్టర్‌ను ఒక బైనరీ క్లాసిఫికేషన్ సమస్యగా మార్చడం దీనికి కారణం. పాజిటివ్ లేబుల్స్ ఇండెక్స్‌లో విలువలు ఉన్నాయని సూచిస్తాయి, అయితే నెగటివ్ లేబుల్స్ అవి లేవని అర్థం.

విలువల కోసం ప్రారంభ తనిఖీని సులభతరం చేయడానికి ఒక ML మోడల్‌ను పరిచయం చేయడం, ఆ తర్వాత తప్పుడు నెగటివ్‌లను తొలగించడానికి బ్యాకప్ బ్లూమ్ ఫిల్టర్‌ను ఉపయోగించడం జరుగుతుంది. మోడల్ యొక్క సంక్షిప్త ప్రాతినిధ్యం మరియు బ్యాకప్ బ్లూమ్ ఫిల్టర్‌కు అవసరమైన కీల సంఖ్య తగ్గడం వల్ల ఈ పరిమాణం తగ్గుతుంది. ఇది సాంప్రదాయ బ్లూమ్ ఫిల్టర్ విధానం నుండి దీనిని వేరు చేస్తుంది. 

ఈ పనిలో భాగంగా, మా లెర్న్డ్ బ్లూమ్ ఫిల్టర్ విధానాన్ని మూల్యాంకనం చేయడానికి మేము రెండు కొలమానాలను ఏర్పాటు చేశాము: ఇండెక్స్ యొక్క తుది సీరియలైజ్డ్ ఆబ్జెక్ట్ పరిమాణం మరియు జాయిన్ క్వెరీల అమలు సమయంలో CPU వినియోగం. 

అమలు సవాళ్లను అధిగమించడం

ఫ్యాక్ట్ టేబుల్‌లో కొన్ని డైమెన్షన్ టేబుల్ కీలు మాత్రమే ఉన్న, అధిక పక్షపాతంతో కూడిన శిక్షణా డేటాసెట్‌ను పరిష్కరించడం మా ప్రారంభ సవాలు. అలా చేసేటప్పుడు, టేబుళ్ల మధ్య దాదాపు మూడింట ఒక కీ ఓవర్‌ల్యాప్ అవ్వడాన్ని మేము గమనించాము. దీనిని ఎదుర్కోవడానికి, మేము శాండ్‌విచ్ లెర్న్డ్ బ్లూమ్ ఫిల్టర్ విధానాన్ని [2] ఉపయోగించాము. ఇది ఫ్యాక్ట్ టేబుల్ నుండి లోపించిన మెజారిటీ కీలను తొలగించడం ద్వారా డేటాసెట్ పంపిణీని పునఃసమతుల్యం చేయడానికి ఒక ప్రారంభ సాంప్రదాయ బ్లూమ్ ఫిల్టర్‌ను ఏకీకృతం చేస్తుంది, తద్వారా డేటాసెట్ నుండి నెగటివ్ నమూనాలను సమర్థవంతంగా తొలగిస్తుంది. తదనంతరం, ప్రారంభ బ్లూమ్ ఫిల్టర్‌లో చేర్చబడిన కీలు, ఫాల్స్ పాజిటివ్‌లతో పాటు, "లెర్న్డ్ ఒరాకిల్" అని తరచుగా పిలువబడే ML మోడల్‌కు పంపబడ్డాయి. ఈ విధానం, లెర్న్డ్ ఒరాకిల్ కోసం ఒక చక్కగా సమతుల్యమైన శిక్షణా డేటాసెట్‌ను అందించి, పక్షపాత సమస్యను సమర్థవంతంగా అధిగమించింది.

రెండవ సవాలు మోడల్ ఆర్కిటెక్చర్ మరియు శిక్షణ ఫీచర్లపై కేంద్రీకృతమైంది. ఫిషింగ్ URLల [1] యొక్క సాంప్రదాయ సమస్యలా కాకుండా, మా జాయిన్ కీలు (చాలా సందర్భాలలో వినియోగదారులు/అనుభవాల కోసం ప్రత్యేక గుర్తింపులు) సహజంగా సమాచారభరితంగా లేవు. ఇది, ఒక డైమెన్షన్ ఎంటిటీ ఫ్యాక్ట్ టేబుల్‌లో ఉందో లేదో అంచనా వేయడంలో సహాయపడే సంభావ్య మోడల్ ఫీచర్లుగా డైమెన్షన్ అట్రిబ్యూట్‌లను అన్వేషించడానికి మమ్మల్ని ప్రేరేపించింది. ఉదాహరణకు, ఒక నిర్దిష్ట భాషలోని అనుభవాల కోసం వినియోగదారు సెషన్ సమాచారాన్ని కలిగి ఉన్న ఒక ఫ్యాక్ట్ టేబుల్‌ను ఊహించుకోండి. యూజర్ డైమెన్షన్ యొక్క భౌగోళిక స్థానం లేదా భాషా ప్రాధాన్యత గుణం, ఒక వ్యక్తిగత వినియోగదారు ఫ్యాక్ట్ టేబుల్‌లో ఉన్నాడా లేదా అనే దానికి మంచి సూచికలుగా ఉంటాయి.

మూడవ సవాలు—ఇన్ఫరెన్స్ లేటెన్సీ—తప్పుడు నెగటివ్‌లను (false negatives) తగ్గించి, వేగవంతమైన ప్రతిస్పందనలను అందించే మోడల్‌లను అవసరం చేసింది. ఈ కీలక కొలమానాల కోసం గ్రేడియంట్-బూస్టెడ్ ట్రీ మోడల్ సరైన ఎంపిక, మరియు కచ్చితత్వం (precision) మరియు వేగం (speed) మధ్య సమతుల్యతను సాధించడానికి మేము దాని ఫీచర్ సెట్‌ను కత్తిరించాము.

మేము నేర్చుకున్న బ్లూమ్ ఫిల్టర్‌లను ఉపయోగించి అప్‌డేట్ చేసిన జాయిన్ క్వెరీ కింద చూపిన విధంగా ఉంది:

ఫలితాలు

మా డేటా లేక్‌లో లెర్న్డ్ బ్లూమ్ ఫిల్టర్‌లతో మేము చేసిన ప్రయోగాల ఫలితాలు ఇక్కడ ఉన్నాయి. మేము వాటిని ఐదు ప్రొడక్షన్ వర్క్‌లోడ్‌లలో ఏకీకృతం చేసాము, వాటిలో ప్రతి ఒక్కటి విభిన్న డేటా లక్షణాలను కలిగి ఉంది. ఈ వర్క్‌లోడ్‌లలో అత్యంత గణన-పరంగా ఖరీదైన భాగం ఫ్యాక్ట్ టేబుల్ మరియు డైమెన్షన్ టేబుల్ మధ్య జాయిన్. ఫ్యాక్ట్ టేబుల్స్ యొక్క కీ స్పేస్, డైమెన్షన్ టేబుల్ పరిమాణంలో సుమారు 30% ఉంటుంది. మొదటగా, లెర్న్డ్ బ్లూమ్ ఫిల్టర్, తుది సీరియలైజ్డ్ ఆబ్జెక్ట్ పరిమాణం పరంగా సాంప్రదాయ బ్లూమ్ ఫిల్టర్లను ఎలా అధిగమించిందో చర్చిస్తాము. ఆ తర్వాత, మా వర్క్‌లోడ్ ప్రాసెసింగ్ పైప్‌లైన్‌లలో లెర్న్డ్ బ్లూమ్ ఫిల్టర్లను ఏకీకృతం చేయడం ద్వారా మేము గమనించిన పనితీరు మెరుగుదలలను చూపిస్తాము.

లెర్న్డ్ బ్లూమ్ ఫిల్టర్ పరిమాణ పోలిక

కింద చూపిన విధంగా, ఒక నిర్దిష్ట ఫాల్స్ పాజిటివ్ రేటును పరిశీలించినప్పుడు, సాంప్రదాయ బ్లూమ్ ఫిల్టర్‌లతో పోలిస్తే లెర్న్డ్ బ్లూమ్ ఫిల్టర్ యొక్క రెండు వేరియంట్లు మొత్తం ఆబ్జెక్ట్ పరిమాణాన్ని 17-42% మధ్య మెరుగుపరుస్తాయి.

అదనంగా, మా గ్రేడియంట్ బూస్టెడ్ ట్రీ ఆధారిత మోడల్‌లో ఫీచర్ల యొక్క చిన్న ఉపసమితిని ఉపయోగించడం ద్వారా, ఇన్ఫరెన్స్‌ను వేగంగా చేయడంతో పాటు మేము కేవలం కొద్ది శాతం ఆప్టిమైజేషన్‌ను మాత్రమే కోల్పోయాము.

అభ్యాసించిన బ్లూమ్ ఫిల్టర్ వినియోగ ఫలితాలు 

ఈ విభాగంలో, మేము బ్లూమ్ ఫిల్టర్-ఆధారిత జాయిన్‌ల పనితీరును అనేక కొలమానాలపై సాధారణ జాయిన్‌లతో పోల్చి చూస్తాము. 

కింది పట్టిక, లెర్న్డ్ బ్లూమ్ ఫిల్టర్‌లను ఉపయోగించిన మరియు ఉపయోగించని వర్క్‌లోడ్‌ల పనితీరును పోల్చి చూపుతుంది. రెండు జాయిన్ రకాలకు ఒకే క్లస్టర్ కాన్ఫిగరేషన్‌ను నిలుపుకుంటూ, 1% మొత్తం ఫాల్స్ పాజిటివ్ సంభావ్యత ఉన్న లెర్న్డ్ బ్లూమ్ ఫిల్టర్ కింద పోలికను ప్రదర్శిస్తుంది. 

మొదటగా, CPU గంటల పరంగా బ్లూమ్ ఫిల్టర్ అమలు సాధారణ జాయిన్ కంటే 60% వరకు మెరుగైన పనితీరును కనబరిచిందని మేము కనుగొన్నాము. బ్లూమ్ ఫిల్టర్‌ను మూల్యాంకనం చేయడానికి అదనంగా పట్టే కంప్యూట్ కారణంగా, లెర్న్డ్ బ్లూమ్ ఫిల్టర్ విధానం యొక్క స్కాన్ దశలో CPU వినియోగం పెరగడాన్ని మేము గమనించాము. అయితే, ఈ దశలో చేసే ప్రీఫిల్టరింగ్, షఫుల్ చేయబడుతున్న డేటా పరిమాణాన్ని తగ్గించింది, ఇది తర్వాతి దశల ద్వారా ఉపయోగించబడే CPUని తగ్గించడంలో సహాయపడింది, తద్వారా మొత్తం CPU గంటలు తగ్గాయి.

రెండవది, లెర్న్డ్ బ్లూమ్ ఫిల్టర్లు సాధారణ జాయిన్‌తో పోలిస్తే సుమారు 80% తక్కువ మొత్తం డేటా పరిమాణాన్ని మరియు సుమారు 80% తక్కువ మొత్తం షఫుల్ బైట్స్‌ను వ్రాస్తాయి. ఇది క్రింద చర్చించిన విధంగా మరింత స్థిరమైన జాయిన్ పనితీరుకు దారితీస్తుంది. 

మా ప్రయోగాలలో భాగంగా, మా ఇతర ప్రొడక్షన్ వర్క్‌లోడ్‌లలో కూడా వనరుల వినియోగం తగ్గడం మేము గమనించాము. ఐదు వర్క్‌లోడ్‌లన్నింటిలో రెండు వారాల కాలంలో, లెర్న్డ్ బ్లూమ్ ఫిల్టర్ విధానం సగటున రోజువారీ ఖర్చులలో 25% ఆదా చేసింది, ఇందులో మోడల్ శిక్షణ మరియు సూచిక సృష్టి కూడా ఉన్నాయి.

జాయిన్ చేసేటప్పుడు షఫుల్ చేసే డేటా పరిమాణం తగ్గడం వల్ల, మేము మా అనలిటిక్స్ పైప్‌లైన్ యొక్క కార్యాచరణ ఖర్చులను గణనీయంగా తగ్గించగలిగాము, అదే సమయంలో దానిని మరింత స్థిరంగా మార్చగలిగాము. మేము ప్రయోగం చేసిన ఐదు వర్క్‌లోడ్‌ల కోసం, రెండు వారాల కాలంలో, ఒక సాధారణ జాయిన్ వర్క్‌లోడ్ మరియు లెర్న్డ్ బ్లూమ్ ఫిల్టర్ ఆధారిత వర్క్‌లోడ్‌కు సంబంధించిన రన్ వ్యవధి (వాల్ క్లాక్ టైమ్)లో వైవిధ్యాన్ని (వేరియేషన్ కోఎఫీషియంట్ ఉపయోగించి) ఈ క్రింది చార్ట్ చూపుతుంది. లెర్న్డ్ బ్లూమ్ ఫిల్టర్లను ఉపయోగించి చేసే రన్‌లు మరింత స్థిరంగా—కాల వ్యవధిలో మరింత స్థిరంగా—ఉన్నాయి, ఇది వాటిని చౌకైన, తాత్కాలిక, నమ్మకం లేని కంప్యూట్ వనరులకు తరలించే అవకాశాన్ని కల్పిస్తుంది. 

సూచనలు

[1] T. Kraska, A. Beutel, E. H. Chi, J. Dean, మరియు N. Polyzotis. ది కేస్ ఫర్ లెర్న్డ్ ఇండెక్స్ స్ట్రక్చర్స్. https://arxiv.org/abs/1712.01208, 2017.

[2] M. Mitzenmacher. సాండ్‌విచింగ్‌ ద్వారా లెర్న్డ్ బ్లూమ్ ఫిల్టర్‌లను ఆప్టిమైజ్ చేయడం. 

https://arxiv.org/abs/1803.01474, 2018.

¹జూన్ 30, 2023తో ముగిసిన 3 నెలల వరకు

²జూన్ 30, 2023తో ముగిసిన 3 నెలల వరకు