More Web Proxy on the site http://driver.im/

research-article

Photon: fault-tolerant and scalable joining of continuous data streams

Authors:

Rajagopal Ananthanarayanan,

Venkatesh Basker,

Alexey Reznichenko,

Deomid Ryabkov,

Manpreet Singh,

Shivakumar VenkataramanAuthors Info & Claims

SIGMOD '13: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data

Pages 577 - 588

https://doi.org/10.1145/2463676.2465272

Published: 22 June 2013 Publication History

Abstract

Web-based enterprises process events generated by millions of users interacting with their websites. Rich statistical data distilled from combining such interactions in near real-time generates enormous business value. In this paper, we describe the architecture of Photon, a geographically distributed system for joining multiple continuously flowing streams of data in real-time with high scalability and low latency, where the streams may be unordered or delayed. The system fully tolerates infrastructure degradation and datacenter-level outages without any manual intervention. Photon guarantees that there will be no duplicates in the joined output (at-most-once semantics) at any point in time, that most joinable events will be present in the output in real-time (near-exact semantics), and exactly-once semantics eventually.

Photon is deployed within Google Advertising System to join data streams such as web search queries and user clicks on advertisements. It produces joined logs that are used to derive key business metrics, including billing for advertisers. Our production deployment processes millions of events per minute at peak with an average end-to-end latency of less than 10 seconds. We also present challenges and solutions in maintaining large persistent state across geographically distant locations, and highlight the design principles that emerged from our experience.

References

[1]

D. J. Abadi et al. "The Design of the Borealis Stream Processing Engine". Proc. of CIDR 2005, pp.277--289.

[2]

J. Baker et al. "Megastore: Providing scalable, highly available storage for interactive devices". Proc. of CIDR 2011, pp.223--234.

[3]

S. Blanas et al. "A comparison of join algorithms for log processing in Mapreduce". Proc. of SIGMOD 2010, pp.975--986.

Digital Library

[4]

T. D. Chandra, R. Griesemer, and J. Redstone. "Paxos made live: an engineering perspective". Proc. of ACM PODC 2007, pp.398--407.

Digital Library

[5]

S. Chandrasekaran and M. J. Franklin. "Streaming queries over streaming data". Proc. of VLDB 2002, pp.203--214.

Digital Library

[6]

F. Chang et al. "Bigtable: A Distributed Storage System for Structured Data". ACM TOCS 2008, 26.2, pp.4:1-4:26.

Digital Library

[7]

E. F. Codd. "A Relational Model of Data for Large Shared Data Banks", Communications of the ACM 13 (6): p377--387, 1970.

Digital Library

[8]

J. C. Corbett et al. "Spanner: Google's Globally-Distributed Database". Proc. of OSDI 2012.

Digital Library

[9]

A. Das, J. Gehrke, and M. Riedewald. "Approximate join processing over data streams". Proc. of SIGMOD 2003, pp.40--51.

Digital Library

[10]

J. Dean and S. Ghemawat. "MapReduce: Simplified data processing on large clusters". Proc. of OSDI 2004, pp.137--149.

Digital Library

[11]

G. DeCandia et al. "Dynamo: Amazon's Highly Available Key-value Store". Proc. of SOSP. 2007, pp. 205--220.

Digital Library

[12]

B. Fitzpatrick. "Distributed Caching with Memcached". Linux Journal, Issue 124, 2004, pp.5.

Digital Library

[13]

B. Gedik, P. S. Yu, and R. R. Bordawekar. "Executing stream joins on the cell processor", Proc. of VLDB 2007, pp.363--374.

Digital Library

[14]

S. Ghemawat, H. Gobioff, and S-T Leung. "The Google File System". 19th Symposium on Operating Systems Principles 2003, pp.20--43.

Digital Library

[15]

M. A. Hammad, W. G. Aref, and A. K. Elmagarmid. "Joining multiple data streams with window constraints". Computer Science Technical Reports, #02-115.

[16]

J. Kang, J. F. Naughton, and S. D. Viglas. "Evaluating window joins over unbounded streams". Proc. of VLDB 2002, pp.341--352.

[17]

D. Karger et al. "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web". Proc. of ACM SOTC 1997, pp.654--663.

Digital Library

[18]

L. Lamport. "The part-time parliament", ACM TOCS 16.2 1998, pp.133--169.

Digital Library

[19]

P. Mishra and M. H. Eich. "Join processing in relational databases". ACM Computing Surveys 1992, 24(1), pp.63--113.

Digital Library

[20]

L. Neumeyer et al. "S4: Distributed Stream Computing Platform". Proc. of KDCloud 2010.

Digital Library

[21]

J. Rao, E. J. Shekita, and S. Tata. "Using Paxos to Build a Scalable, Consistent, and Highly Available Datastore". Proc. of VLDB 2011, pp.243--254.

Digital Library

[22]

F. B. Schneider. "Implementing fault-tolerant services using the state machine approach: A tutorial", ACM Computing Surveys 22 1990, pp.299--319 (1990).

Digital Library

[23]

D. Shasha and P. Bonnet. "Database Tuning: Principles, Experiments, and Troubleshooting Techniques". Proc. of SIGMOD 2004, pp.115--116.

Digital Library

[24]

J. Teubner and R. Mueller. "How soccer players would do stream joins". Proc. of SIGMOD 2011, pp.625--636.

Digital Library

[25]

J. Xie and J. Yang. "A survey of join processing in data streams". Data Streams - Models and Algorithms 2007, pp.209--236.

[26]

M. Zaharia et al. "Discretized Streams: An Efficient and Fault-tolerant Model for Stream Processing on Large Clusters". Proc. of HotCloud 2012, pp.10--10.

Digital Library

Cited By

Wang QZuo DZhang ZShu YLiu XHe M(2024)Low-Latency Adaptive Distributed Stream Join System Based on a Flexible Join ModelProceedings of the ACM on Management of Data10.1145/36549532:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654953
Wang QZuo DZhang ZChen SLiu T(2023)SepJoin: A Distributed Stream Join System with Low Latency and High Throughput2022 IEEE 28th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS56603.2022.00088(633-640)Online publication date: Jan-2023
https://doi.org/10.1109/ICPADS56603.2022.00088
Redreev GChervenchuk VKiyko P(2023)Modeling and Study of Maintenance Service SystemAdvances in Automation IV10.1007/978-3-031-22311-2_26(262-268)Online publication date: 20-Jan-2023
https://doi.org/10.1007/978-3-031-22311-2_26
Show More Cited By

Index Terms

Photon: fault-tolerant and scalable joining of continuous data streams
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Parallel and distributed DBMSs
  2. World Wide Web
    1. Web applications
    2. Web services

Recommendations

A load shedding framework for XML stream joins
DEXA'10: Proceedings of the 21st international conference on Database and expert systems applications: Part I

Joining data streams using various types of windows is an established method of stream processing. The limitation of window size due to memory constraint takes a heavy toll on the accuracy of the query result. Through this paper, we propose a unique ...
Weighted Reservoir Sampling from Distributed Streams
PODS '19: Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

We consider message-efficient continuous random sampling from a distributed stream, where the probability of inclusion of an item in the sample is proportional to a weight associated with the item. The unweighted version, where all weights are equal, is ...
Dcell: a scalable and fault-tolerant network structure for data centers

A fundamental challenge in data center networking is how to efficiently interconnect an exponentially increasing number of servers. This paper presents DCell, a novel network structure that has many desirable features for data center networking. DCell ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '13: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data

June 2013

1322 pages

ISBN:9781450320375

DOI:10.1145/2463676

General Chairs:
Kenneth Ross
Columbia University
,
Divesh Srivastava
AT&T Research
,
Program Chair:
Dimitris Papadias
HKUST

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS'13

Sponsor:

SIGMOD

SIGMOD/PODS'13: International Conference on Management of Data

June 22 - 27, 2013

New York, New York, USA

Acceptance Rates

SIGMOD '13 Paper Acceptance Rate 76 of 372 submissions, 20%;

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

111
Total Citations
View Citations
1,092
Total Downloads

Downloads (Last 12 months)50
Downloads (Last 6 weeks)6

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang QZuo DZhang ZShu YLiu XHe M(2024)Low-Latency Adaptive Distributed Stream Join System Based on a Flexible Join ModelProceedings of the ACM on Management of Data10.1145/36549532:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654953
Wang QZuo DZhang ZChen SLiu T(2023)SepJoin: A Distributed Stream Join System with Low Latency and High Throughput2022 IEEE 28th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS56603.2022.00088(633-640)Online publication date: Jan-2023
https://doi.org/10.1109/ICPADS56603.2022.00088
Redreev GChervenchuk VKiyko P(2023)Modeling and Study of Maintenance Service SystemAdvances in Automation IV10.1007/978-3-031-22311-2_26(262-268)Online publication date: 20-Jan-2023
https://doi.org/10.1007/978-3-031-22311-2_26
Markov IWang HKasturi NSingh SGarrard MHuang YYuen STran SWang ZGlotov IGupta TChen PHuang BXie XBelkin MUryasev SHowie SBakshy EZhou NZhang ARangwala H(2022)Looper: An End-to-End ML Platform for Product DecisionsProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3534678.3539059(3513-3523)Online publication date: 14-Aug-2022
https://dl.acm.org/doi/10.1145/3534678.3539059
Gulisano VNajdataei HNikolakopoulos YPapadopoulos APapatriantafilou MTsigas P(2022)STRETCH: Virtual Shared-Nothing Parallelism for Scalable and Elastic Stream ProcessingIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.318197933:12(4221-4238)Online publication date: 1-Dec-2022
https://doi.org/10.1109/TPDS.2022.3181979
Koudas NLi RXarchakos I(2022)Video Monitoring QueriesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.304860634:10(5023-5036)Online publication date: 1-Oct-2022
https://doi.org/10.1109/TKDE.2020.3048606
Xu XLi WXu RQi HLi KZhou XChen S(2022)Trading Cost and Throughput in Geo-Distributed Analytics With A Two Time Scale ApproachIEEE Transactions on Cloud Computing10.1109/TCC.2020.299419510:3(2163-2177)Online publication date: 1-Jul-2022
https://doi.org/10.1109/TCC.2020.2994195
Wang QZuo DZhang ZChen SLiu T(2022)An adaptive non-migrating load-balanced distributed stream window join systemThe Journal of Supercomputing10.1007/s11227-022-04991-679:8(8236-8264)Online publication date: 15-Dec-2022
https://doi.org/10.1007/s11227-022-04991-6
Moniz HLeitão JDias RGehrke JPreguiça NRodrigues R(2022)Achieving Low Latency Transactions for Geo-Replicated Storage with BlotterEncyclopedia of Big Data Technologies10.1007/978-3-319-63962-8_158-2(1-11)Online publication date: 24-Feb-2022
https://doi.org/10.1007/978-3-319-63962-8_158-2
Cai WBernstein PWu WChandramouli B(2021)Optimization of threshold functions over streamsProceedings of the VLDB Endowment10.14778/3447689.344769314:6(878-889)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.14778/3447689.3447693
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents