Publicera/prenumerera system har visat förmåga att skala till ett stort antal användare och höga datahastigheter när de tillhandahåller innehållsbaserade dataspridningstjänster på Internet. Deras tjänster begränsas dock av de datasemantik och frågeuttryck som de stöder. Å andra sidan, det senaste arbetet med selektiv spridning av XML-data har gjort betydande framsteg i övergången från XML-filtrering till den rikare funktionaliteten av omvandling för resultatanpassning, men i allmänhet har ignorerat utmaningarna med att distribuera sådana XML-baserade tjänster på en Internet-skala. I detta dokument tar vi itu med dessa utmaningar i samband med införlivandet av XML-dataspridningens rika funktionalitet i ett mycket skalbart system. Vi presenterar den arkitektoniska designen av ONYX, ett system baserat på ett overlay nätverk. Vi identifierar de betydande tekniska utmaningarna i att stödja XML-filtrering och omvandling i denna miljö och föreslår tekniker för att lösa dem. Ett stort antal nya applikationer, såsom mobila tjänster, aktiekort, sportkort, personlig tidningsgenerering, nätverksövervakning, trafikövervakning och elektroniska auktioner, har ökat intresset för ContentBased Data Dissemination (CBDD). CBDD är en tjänst som levererar information till användare (likvärdigt, applikationer eller organisationer) baserat på korrespondensen mellan informationens innehåll och användarnas dataintressen. Figur 1 visar i vilket sammanhang ett system för dataspridning som tillhandahåller denna tjänst fungerar. Användarna prenumererar på tjänsten genom att tillhandahålla profiler som uttrycker deras dataintressen. Datakällor publicerar sina data genom att skicka meddelanden till systemet. Systemet levererar till varje användare de meddelanden som matchar hennes dataintressen; dessa meddelanden presenteras i det format som krävs av användaren. Under de senaste åren har XML snabbt blivit populärt som standard för datautbyte i företags intranät och på Internet. Förmågan att öka data med semantisk och strukturell information med XML-baserad kodning ökar potentialen för mer exakt och användbar leverans av data. I samband med XML-baserad dataspridning kan användarprofiler innebära begränsningar av både XML-fragmentens struktur och värde, vilket kan leda till en mer exakt filtrering av XML-meddelanden. I många nya applikationer behöver de relevanta XML-meddelandena också omvandlas för data- och applikationsintegration, personalisering och anpassning till trådlösa enheter. Medan. Att integrera XML-behandling i sådana distribuerade miljöer verkar vara ett naturligt sätt att stödja storskalig XML-spridning. Distribuerade pub/sub-system partitionerar profilpopulationen till flera noder och styr meddelandeflödet till noderna hosting profiler baserat på innehållet i meddelanden (kallas innehållsdriven routing). Att integrera XML i innehållsdriven routing medför dock följande viktiga utmaningar. Eftersom XML blandar strukturell och värdebaserad information måste innehållsdriven routing stödja begränsningar för båda. Den inneboende upprepning och rekursion av elementnamn i XML-data besegrar också välkända routing, en multi-query processor som vi byggt tidigare, representerar en uppsättning profiler med hjälp av ett operatörsnätverk ovanpå en icke-deterministisk Finite Automaton (NFA) för att dela behandling mellan dessa profiler. Att använda YFilter för distribuerad XML-spridning väcker frågor om distribution av det NFA-baserade operatörsnätet och effektiv schemaläggning av operatörerna för både profilbehandling och innehållsdriven routing. I detta dokument presenterar vi den ursprungliga utformningen av ONYX (Operator Network med hjälp av YFilter för XML-spridning), ett storskaligt spridningssystem som levererar XML-meddelanden baserade på användarspecifikationer för filtrering och omvandling. Bidragen från vårt arbete är bland annat följande: Vi utnyttjar YFilter-processorn för innehållsdriven routing. I synnerhet använder vi det NFA-baserade operatörsnätet för att representera routingtabeller, och ger en första lösning för att bygga routingtabellerna från den distribuerade profilpopulationen. Vi tar upp frågan om hur man utför inkrementell meddelandetransformering under routing. För att öka effektiviteten i routing tillhandahåller vi en algoritm som partitionerar profilpopulationen baserat på exklusivitet av dataintressen. Vi utvecklar holistisk meddelandebehandling för att dela arbetet mellan olika bearbetningsuppgifter på en nod (dvs. innehållsdriven routing, inkrementell omvandling och användarprofilbehandling). Beroende-medveten prioritering schemaläggning används för att stödja sådan delning samtidigt som en snabb väg för routing. Vi undersöker olika format för effektiv XML-överföring. Sist men inte minst tillhandahåller vi en arkitektonisk utformning av systemet och mekanismer för att bygga ett sådant system. Tidningen går vidare enligt följande. I avsnitt 2 beskrivs kraven och motivationen. Avsnitt 3 beskriver vår systemmodell. Kärnteknik som tar itu med de olika utmaningarna presenteras i avsnitt 4, följt av en detaljerad mäklare arkitektur design i avsnitt 5. I avsnitt 6 ingår utökat arbete i samband med detta. Avsnitt 7 avslutar dokumentet. I detta avsnitt presenterar vi kraven för storskalig XML-spridning och ger en kort översikt över befintliga lösningar, vilket motiverar vårt arbete som presenteras i detta dokument. En utgångspunkt för våra krav är användningen av XML som datamodell och en delmängd av XQuery [7] som profilmodell. Användarprofiler kan innehålla begränsningar över både struktur (med hjälp av sökvägsuttryck) och värde (med hjälp av värdebaserade predikat) av XML-fragment. Till exempel, om en användare är intresserad av lagerinformation som distribueras i San Francisco och under ämnet "Stock", kan hon uttrycka sitt intresse med hjälp av frågan nedan (baserat på NITF DTD [23]). Den anger att rotelementet nitf måste (1) ha ett barnelement huvud som i sin tur innehåller ett barn element pubdata vars attribut edition.area har värdet "SF", och (2) har en ättling element tobject. subject vars attribut tobject. subject.type har värdet "Stock". Användarprofiler kan också innehålla specifikationer för resultatanpassning. Till exempel kan en användare använda frågan nedan för att ange att för varje NITF-artikel som matchar för och där klausuler (som är likvärdiga med frågan ovan), omvandla den till en ny artikel med rotelementet stock_news som innehåller element som valts från den ursprungliga artikeln med hjälp av sökvägen uttryck "body/body.head/hedline", och "body/body. innehåll". För $n i $msg/nitf där $n/head/pubdata/@edition.area = "SF" och $n//tobject. subject/@tobject. subject.type = "Stock" retur <stock_news> {$n/body/body.head/hedline} {$n/body/body.content} </stock_news> Eftersom profilmodellen är baserad på XQuery-språket, använder vi i uppföljaren termerna profil och fråga utbytbart. Den andra dimensionen av kraven är skalbarhet. Mer specifikt måste tjänsten skalas utmed följande dimensioner. Datavolym. Datavolymen bestäms av antalet meddelanden per sekund som anländer till systemet och meddelandestorleken. Beroende på ansökan varierar antalet meddelanden per sekund från flera till tusentals. Till exempel, NASDAQ realtid dataflöden inkluderar 3000 till 6000 meddelanden per sekund i pre-market timmar [43] ; Nätverk och program övervakningssystem som NetLogger kan också ta emot upp till tusen meddelanden per sekund [44]. Meddelandestorleken kan variera från 1 KB (t.ex. XML-kodade lagercitatuppdateringar) till 20 KB (t.ex. XML-nyhetsartiklar). Fråga befolkning. Frågepopulationen i ett spridningssystem kan också spänna över ett brett spektrum, nå miljontals frågor för applikationer såsom personlig tidningsgenerering och mobiloperatörer som tillhandahåller lager citat uppdateringar. Frekvens av frågeuppdateringar. En tredje skalbarhetsfråga är hur ofta användarna uppdaterar sina dataintressen. I vissa tillämpningar ändras frågor dagligen, men i vissa andra kan de förändras mycket oftare. Resultatvolym. När resultat anpassning stöds, kan volymen av resultat som ska levereras vara enorm. Detta beror på att för varje meddelande, punkt-till-punkt leverans behövs för varje fråga matchas av meddelandet. Ta till exempel en uppdateringstjänst för aktiekurser. Antag att den maximala meddelandehastigheten från en datakälla är 5000 per sekund, varje meddelande är 1 KB, användarpopulationen är 10 miljoner, och den genomsnittliga frågeselektiviteten är så låg som 0,001%. En back-of-theenvelope beräkning ger en uppskattning av resultatvolymen som 4 Gb per sekund. Att distribuera denna datavolym från en central server kan vara oöverkomligt dyrt. Efter att ha beskrivit problemet med storskalig XML-baserad dataspridning presenterar vi därefter positionen för vårt arbete inom det stora antalet relaterade arbeten. Publicera, en multi-query processor som vi byggt tidigare, stöder också resultat anpassning med hjälp av en delmängd av XQuery. Även om dessa XML-filtrerings- och omvandlingssystem ger högre expressivitetsnivåer, begränsar deras centraliserade bearbetningsstil deras skalbarhet. Revisiting Figur 2, dagens XML-filtrering och omvandlingssystem kan bäst beskrivas av nedre högra hörnet av matrisen som kombinerar lägre skalbarhet och högre expressivitet. Vårt arbete med innehållsbaserad dataspridning antar paradigmet för distribuerad bearbetning för att utnyttja aggregerad bandbredd och processkraft. Som anges i figur 2 innehåller vårt system ONYX den höga expressiviteten av XML-filtrering och omvandling till en distribuerad dataspridningstjänst. I detta avsnitt presenterar vi de operativa funktionerna i ONYX. ONYX tillhandahåller innehållsbaserad många-till-många dataspridning från utgivare till slutanvändare. Den består av ett overlay nätverk av noder. De flesta noderna fungerar som informationsmäklare (eller mäklare, för kort) som hanterar meddelanden och användarfrågor, medan några av dem samarbetar för att tillhandahålla en registreringstjänst. Översikten illustreras i figur 3. Det tjänstegränssnitt som tillhandahålls av ONYX består av flera metoder (av vilka några liknar dem i [3]): Registrera en datakälla: En datakälla registrerar med ONYX genom att kontakta registreringstjänsten och tillhandahålla information om dess plats, det schema som används, den förväntade meddelandehastigheten och meddelandestorleken, etc. (som illustreras av meddelande 1 i figur 3). Registreringstjänsten tilldelar datakällan ett ID och väljer en mäklare som rotmäklare för datakällan. Valet av rotmäklaren baseras på dess topologiska avstånd till datakällan, den tillgängliga bandbredden och den datavolym som förväntas från den källan. Efter tjänsten vidarebefordrar informationen om den nya datakällan till rotmäklaren (meddelande 2), returnerar den tilldelade ID och adressen till rotmäklaren till datakällan (meddelande 3). Publicera data: Efter registreringen publicerar en datakälla sina data genom att bifoga sitt ID till varje meddelande och skjuta meddelandet till dess rotmäklare (meddelande 4). Registrera ett dataintresse: För att prenumerera kontaktar användaren registreringstjänsten och tillhandahåller sin profil och nätverksadress (meddelande 5). Registreringstjänsten tilldelar ett ID till denna profil och väljer en mäklare som värdmäklare för denna profil baserat på användarens plats och/eller profilens innehåll. I slutet av registreringen vidarebefordrar tjänsten profilen och tillhörande information till värdmäklaren (meddelande 6) och returnerar profil-ID- och värdmäklaradressen till användaren (meddelande 7). Därefter kommer värdmäklaren att hantera alla användarförfrågningar om den profilen. Uppdatera ett dataintresse: Senare ändringar av en profil (inklusive uppdateringar och radering) skickas direkt till värdmäklaren (meddelande 8). Observera att användare inte behöver en metod för att hämta meddelanden som matchar deras intressen, eftersom dessa meddelanden trycks till dem från systemet (t.ex. meddelande 9). Ytterligare metoder finns för datakällor för att uppdatera schemat och annan information som skickats tidigare. Feltolerans kan uppnås genom att ha backup noder för registreringstjänsten och mäklare eller med hjälp av andra tekniker. Denna diskussion ligger utanför ramen för detta dokument. ONYX är ett nätverk för överlagring på applikationsnivå. Den består av två lager av funktionalitet. Det lägre skiktet, som kallas kontrollplanet, handlar om programnivå sändningsträd och ger varje mäklare ett sändningsträd rotat på den mäklare som når alla andra mäklare i nätverket. Figur 4 visar ett sådant träd i ett nätverk bestående av sex mäklare. Algoritmer för att bygga ut sändningsträd har tillhandahållits på annat håll (t.ex. [14] ). I detta avsnitt fokuserar vi på det högre lagret av funktionalitet i ONYX -innehållsbaserad bearbetning, vilket är den viktigaste frågan i detta papper. Vi bryter ner verksamheten i det här skiktet i två plan för bearbetning - dataplanet och frågeplanet. Dataplanet fångar flödet av meddelanden i systemet medan frågeplanet fångar flödet av frågor och frågerelaterade uppdateringar i systemet. Som vi kommer att se är dualiteten av data och fråga en genomträngande egenskap hos ONYX. Vi diskuterar nu de tre uppgifter som utförs i detta lager - innehållsdriven routing, inkrementell omvandling, och användare frågebehandling. Innehållsstyrd routing är nödvändig för att undvika översvämningar av meddelanden till alla mäklare i nätverket. Den bygger ovanpå det ovan beskrivna sändningsträdet. Den routing är innehållsdriven eftersom i stället för att vidarebefordra ett meddelande till alla barn i sändningsträdet, skickar en mäklare det till endast delmängd som är "intressant" i meddelandet. Detta routing system, som matchar ett meddelande innehåll med routing tabellposter (eller routing frågor) som representerar intressen barn mäklare, är i skarp kontrast till adress-baserade IP routing systemet. Figur 4 visar ett exempel på routing ett meddelande baserat på dess innehåll. Rutborden för Broker 1 och 4 visas konceptuellt. Tabellen vid Broker 1 anger en routingfråga "/nitf/head/pubdata[@edition.area= "NY"]" för Broker 2, och en liknande "/nitf/head/pubdata[@edition.area= "SF"]" för Broker 4. Matchning av ett nytt meddelande anländer till Broker 1 med antingen routing fråga resulterar i routing meddelandet till motsvarande barn. Byggandet av sådana routing tabeller genom att sammanfatta frågor nedströms mäklare är en subtask i frågeplanet. Matchning av meddelanden mot routing frågor förekommer i dataplanet. Inkrementell omvandling är den andra uppgiften i det innehållsbaserade bearbetningsskiktet. Intressanta fall av transformering av meddelanden under routing inkluderar 1) tidig projektion, dvs. borttagning av data, och 2) tidig omstrukturering. Ett exempel på tidig projektion är följande. En datakälla publicerar meddelanden som innehåller flera nyhetsartiklar. Om alla användarfrågor nedströms från en länk endast är intresserade av en delmängd av artiklarna (t.ex. de som distribueras i området "SF"), kan meddelanden projiceras på de artiklar av intresse innan de vidarebefordras längs denna länk med hjälp av följande fråga: <batched-nitf> { för $n i $msg/batched-nitf/nitf där $n/head/pubdata/@edition.area = "SF" returnera $n} </batched-nitf> Ett exempel på omstrukturering är meddelandeomkodning baserad på profiler av trådlösa användare, säger, när alla användare nedströms från en länk kräver bilder och kommentarer som ska tas bort och tabeller som ska konverteras till listor. Inkrementell omvandling hjälper till att minska meddelandestorlekar och undviker upprepade arbete på flera mäklare. Vi möjliggör inkrementell omvandling genom att bifoga omvandlingsförfrågningar till utdata länkar av mäklare på vägen av routing. Användarfrågor nedströms från en länk är aggregerade och allmängiltigheten i deras omvandlingskrav extraheras för att bilda omvandlingsfrågan. Dessa underuppgifter händer i frågeplanet. Motsvarande deluppgift i dataplanet består av att omvandla meddelanden med hjälp av dessa frågor, innan meddelandena skickas till utdatalänkarna. Användarförfrågan behandling är uppgiften att matcha och omvandla meddelanden mot enskilda användarfrågor hos deras värdmäklare. För användarfrågor som är bosatta hos en viss mäklare, är detta det sista steget i meddelandebehandling (även om ankommande meddelanden kan dirigeras och omvandlas för andra nedströmsanvändare frågor). Deluppgiften i frågeplanet består av frågor som indexering av användarfrågor för vilka mäklaren är värdmäklare, och deluppgiften i dataplanet består av matchande meddelanden mot dessa index. Tabell 1 sammanfattar de innehållsbaserade bearbetningsuppgifterna i ONYX och deras deluppgifter över fråge- och dataplanen.
Pub-sub-system som ONYX-systemet REF möjliggör registrering av komplexa krav på servrar och fokuserar främst på avvägningen mellan databehandlingseffektivitet och uttryckligheten i de frågor som kan behandlas av systemet.
Towards an Internet-Scale XML Dissemination Service
{'venue': 'VLDB', 'journal': None, 'mag_field_of_study': ['Computer Science']}