When providing public access to data on the Semantic Web, publishers have various options that include downloadable dumps, Web APIs, and SPARQL endpoints. Each of these methods is most suitable for particular scenarios. SPARQL provides the richest access capabilities and is the most suitable option when granular access to the data is needed. However, SPARQL expressivity comes at the expense of high evaluation cost. The potentially large variance in the cost of di erent SPARQL queries makes guaranteeing consistently good quality of service a very di cult task. Current practices to enhance the reliability of SPARQL endpoints, such as query timeouts and limiting the number of results returned, are far from ideal. They can result in under utilisation of resources by rejecting some queries even when the available resources are sitting idle and they do not isolate \well-behaved" users from \illbehaved" ones and do not ensure fair sharing among di erent users. In similar scenarios, where unpredictable contention for resources exists, scheduling algorithms have proven to be e ective and to signi cantly enhance the allocation of resources. To the best of our knowledge, using scheduling algorithms to organise query execution at SPARQL endpoints has not been studied. In this paper, we study, and evaluate through simulation, the applicability of a few algorithms to scheduling queries received at a SPARQL endpoint.
When providing public access to data on the Semantic Web, publishers have
various options that include downloadable dumps, Web APIs, and SPARQL
endpoints. Each of these methods is most suitable for particular scenarios,
however none of them provides an ideal global solution [
However, supporting public SPARQL access to data is expensive. It has been
shown that evaluating SPARQL is PSPACE-complete in general and
coNPcomplete for well-de ned queries [
Existing SPARQL endpoints employ di erent measures to enhance their reliability and to ensure consistent quality of service. Such measures include query timeouts, refusing expensive SPARQL queries, limiting the number of triples returned or returning partial results. For example, 4Store supports a soft limit for execution time5 and Virtuoso allows setting a maximum threshhold on the expected query cost6. There are still a number of problems with these approaches: (i) they provide an inconsistent user experience and limit the expressiveness of allowed queries (ii) there is no clear way to communicate these non-standard shortcomings to the user (iii) they can result in under utilisation of resources by rejecting some queries even when the available resources are sitting idle (iv) they do not isolate \well-behaved" users from \ill-behaved" ones and do not ensure fair sharing among di erent users.
In similar scenarios, where unpredictable contention for resources exists,
scheduling algorithms have proven to be e ective and to signi cantly enhance the
allocation of resources. Scheduling has been utilised for data networks [
In this paper we argue for employing scheduling algorithms to organise query execution at a, possibly public, SPARQL endpoint. Giving the wide applicability of scheduling, there exists a large number of scheduling algorithms. In this paper, we study, and evaluate through a simulation, the applicability of a few algorithms to schedule queries received at some SPARQL endpoint. A number of scheduling algorithms, mainly from the data networks domain, are reviewd (Section 3.1). We then describe their applicability to scheduling SPARQL queries (Section 3.2) and study through a simulation their e ect on two popular SPARQL engines (Section 4).
We do not claim that scheduling solves the problem of providing a reliable publicly-accessible SPARQL endpoint. Nevertheless, our results show that scheduling enhances throughput and reduces the e ect of complex queries on simpler ones. We also note that scheduling has the extra advantages of rewarding socially-aware behaviour and achieving better utilisation and fairer allocation of the available resources. 2 http://sparqles.okfn.org/ 3 See for example http://answers.semanticweb.com/questions/14440/ can-the-economic-problem-of-shared-sparql-endpoints-be-solved 4 E.g. http://daverog.wordpress.com/2013/06/04/the-enduring-myth-of-the-sparql-endpoint/ and http://ruben.verborgh.org/blog/2013/09/30/ can-i-sparql-your-endpoint/ 5 http://4store.org/trac/wiki/SparqlServer 6 http://virtuoso.openlinksw.com/dataspace/doc/dav/wiki/Main/
VirtSPARQLEndpointProtection
Most current practices to enhance the reliability of SPARQL endpoints are based
on introducing ad-hoc measures and limits such as query timeouts, refusing
expensive SPARQL queries, limiting the number of triples returned or returning
partial results. These measures have a number of problems as discussed in the
introduction. Linked Data Fragments [
Scheduling has been extensively studied in data networks where the
capacity of a switch is shared by multiple senders [
Scheduling has also been used to organise jobs of shared Hadoop clusters. First In First Out (FIFO) Scheduler, Fair Scheduler7 and Capacity Scheduler8 are the most widely used schedulers in practice. Similar to our work, these schedulers re-use algorithms de ned for the data networks. Notice that, in contrast to SPARQL queries, Hadoop jobs are expected to take a long time and their execution can be pre-empted.
Moreover, scheduling has also been applied in wireless networks [
7 http://hadoop.apache.org/docs/r1.2.1/fair_scheduler.html 8 http://hadoop.apache.org/docs/r1.2.1/capacity_scheduler.html The scheduler decides which stream gets served at each moment and for how long. The goal is usually to maximise throughput while ensuring fair sharing of resources and avoiding long waiting times. Keeping a separate queue for each stream puts up \ rewalls" protecting well-behaved streams against streams that might otherwise saturate the server capacity and drive delays to unacceptable levels. 3.1
We next describe a number of scheduling algorithms used mainly for data
networks and then discuss their applicability to SPARQL endpoints.
Ideal Scheduler A mathematical idealization of queuing, which was originally
proposed as an idealization of time-slicing in computer systems (Kleinrock 1976
as cited in [
De cit Round-Robin Scheduler Described in [
We consider scheduling as a service running on top of SPARQL endpoints. The scheduler receives the queries and then decides in what order to send them to the endpoint. The goal is to: (i) minimize the e ect that expensive queries can have on other queries (ii) maximize the utilization of the available resources (iii) reward socially-aware behaviour (e.g., simpler queries that set a limit on the number of required results).
However, contrary to the typical scheduling scenario depicted in Figure 1, a SPARQL endpoint can handle multiple queries at a time. In fact, as triple stores, Web servers and the underlying operating systems each have their own resource utilisation and sharing facilities, it will be very ine cient to send only one query at a time to the endpoint. Therefore, SPARQL scheduler sends multiple queries to the endpoint as long as their total cost is under a con gured threshold. Upon the completion of processing some query, its cost is substracted from the tracked total cost. The threshold is necessary to avoid overwhelming the endpoint as sending many queries simultaneously to an endpoint results in rejecting to process many queries by the endpoint.
In practice, three further challenges need to be addressed: { E ciently estimating the cost of an incoming SPARQL query. The cost involves multiple paramters such as CPU, memory, network and I/O cost. The cost also depends on the query, the data and the triple store. However, this problem is beyond the scope of this paper. { Identifying the source of each query in order to de ne streams of inputs.
In the absence of user authentication, IP addresses and session detection techniques can be used. { Setting the threshold of total computing capacity. This can be set via experimenting. 4
We implemented three scheduling algorithms in Java 9: { FIFO: A First-In-First-Out queue. This scheduler serves input streams in order (one query at a time) while keeping track of the total cost of queries being processed at every point and ensuring that this cost is always kept lower than the computing capacity threshold. { De cit: Implements a de cit round-robin algorithm as described in Section 3.1.
{ Fair: Implements a fair scheduling algorithm as described in Section 3.1. 4.2
We experimented with two triple stores, Virtuoso Open-Source Edition 7.0.0 Release10 and Jena Fuseki 1.0.111. Both triple stores were run on a Mac with 8GB memory and a 2.9GHz Intel Core i7 CPU. Jena Fuseki was run in memory with a maximum heap size of 3GB.
We used the Semantic Web Dog Food12 data that contains information about papers published in the main conferences and workshops in the area of Semantic 9 The code is avaialble at
sparql-endpoints-scheduler 10 http://virtuoso.openlinksw.com/ 11 http://jena.apache.org/documentation/serving_data/ 12 http://data.semanticweb.org/
https://gitlab.insight-centre.org/Maali/ Web research. The data was downloaded13 from the Semantic Web Dog Food website in Februaury 2014.
The Web logs of the Semantic Web Dog Food were made available as part of the USEWOD 2013 Data Challenge14. To get real-world SPARQL queries for our experiment, we extracted SPARQL queries from these Web logs. We ran each query three times on Fuseki (without any added scheduling) and classi ed it as simple or complex based on the time it took. All simple queries took an average of less than 90ms, while complex queries took more than 450ms. We use these numbers (90 and 450) as a proxy for the query costs.
We simulated two concurrent ows of queries, one with simple queries and the other with complex queries. This simulates two applications with di erent needs. Queries were selected randomly from the set of simple and complex queries respectively. Both ows follow a Poisson distribution. We experimented with di ernet means of the Poisson distribution (a.k.a. interval) and with di erent thesholds for the computing capacity (i.e., total cost of queries being processed at a time). Each run was stopped after 5 minutes and logs were collected then.
We consider a query to be fully processed if it is sent to the endpoint and all results sent back from the endpoint are received (within the 5 minute cut-o ). For each query we measure two durations: Waiting Time: the time taken from the moment the query is received at the scheduler until it is sent to the endpoint.
Processing Time: the time taken from the moment the query is received at the scheduler until the moment at which the query is fully processed.
We wanted to include a no-scheduling setting as a baseline, however running these ows without any scheduling resulted in overwhelming the endpoint and therefore most of the queries were dropped without getting answered. 4.3
We experimented with intervals of 100, 200, 500 and 1000 milliseconds (ms). Queries sent with intervals 500 and 1000 ms were not frequent enough to require any waiting and therefore resulted in no scheduling. We report only on queries with intervals 100 and 200 ms. We experimented with di erent thresholds for the computing capacity. We report here only on the results when the threshold is set to 8000 because it showed the most e ective results for the three scheduling algorithms tested; all larger values overwhelmed the endpoint. Notice that 8000 is just a proxy for the computation capacity available and it needs to be interpreted together with the cost of the queries (we used 90 and 450 for simple and complex queries respectively).
Table 1 shows the percentage of queries completed when sent at a 100 ms interval on Fuseki. On Virtuoso all queries were fully processed, while on Fuseki it can be noticed that the FIFO algorithm processed equivalent percentages of 13 http://data.semanticweb.org/dumps/ 14 http://data.semanticweb.org/usewod/2013/challenge.html 100 200
Interval (milliseconds) 106 100 200
Interval (milliseconds) (c) Waiting time - simple queries
FIFO
Deficit Fair FIFO s snd Fair Deficit Fig. 2nd: Virtucooso - Proscessing anFdaiwraiting times
iseceonm 102 iiseenm 102 secondn both simple and co mit plex qtueries whieile10t2he other two algorithms \favoured" ry y simple queries and \peenalisered" complimex ones. De cit scheduling showed better throughput. uQ uQ trey
Figures 2 and Figure 3 show theuQprocessing and waiting times for simple and complex queries wh10e1n running against Virtuoso and Fuseki. Similar to the 101 throughput results, it can bQeuneroyt1iced hQouweryp2enalisiQnugercy3omplexQuqeurye4ries reQsuuelrtys5 in smaller waiting and processing timesQfoure1rs0yi1m1ple quQeurieersy2when uQsiunegryd3e cit orQfuaeirry4 scheduling. On the other hand, complex querQieuserhy1ave smQaluleerry2waitingQaunerdy3pro- Query4 cessing times using FIFO scheduling with 200 milliseconds interval. The higher processing time of complex queries using FIFO scheduling was surprising. Our interpretaion of this is that prioritising simple queries allowed better utilisaQuery5 100 200
Interval (milliseconds) 100 200
Interval (milliseconds)
Quer1y011 Query2 Query3 Query4 Query5
In summary, scheduling allowed geQtutien1r0gy11better tQhureoruyg2hput bQyudeerlya3ying quQeruieersy4 instead of rejecting them (recall that runningQwuietrhy1out schQeduuerlyin2g resuQltueedryi3n rejecting most of the queries). De cit and Fair scheduling algorithms favoured simpler queries. In general, de cit scheduling, the simpler algorithm, showed better results in our settings than fair scheduling.
Simple Queries Complex Queries FIFO 47.3% 47.4% De cit 100% 42%
Fair 77% 40%
Table 1: Percentage of fully processed queries on Fuseki (throughput) 5
We reported a simulation experiment to study the e ects di erent scheduling algorithms can have when used to organise execution of SPARQL queries received at some endpoint. We note that simple scheduling can be implemented with minimal overhead and has e ect only when queries are received at high frequency.
We consider this work as an initial step and hope to extend the experiment and deploy it in some real-world use case.
Acknowledgements. Fadi Maali is funded by the Irish Research Council, Embark Postgraduate Scholarship Scheme. This publication has emanated from research supported in part by a research grant from Science Foundation Ireland (SFI) under Grant Number SFI/12/RC/2289.