From W3C Wiki
Jump to: navigation, search

BotNet Benchmark, version 1.0

Orri Erling, Ivan Mikhailov, Yrjana Rankka OpenLink Software


BotNet Benchmark simulates an RDF OLTP backend of a website of a social network. The database executes a mix of queries of two sorts (interactive and analytic) and update transactions that reflects user activities. Users create and manage groups, become friends, read/write posts and post comments to posts on forum threads.

The benchmark spec is not stable, because the required functionality can not be expressed in SPARQL 1.0. It can be expressed in terms of SPARQL 1.1 Working Draft, but texts of some queries will not provide enough hints to the query optimizer, resulting in extremely bad performance.

Even if end users obviously do not know ACID abbreviation, they expect high availability of the service, durable storage and data integrity --- quite traditional requirements. However, there's some specific reaction on faults. The web server is driven by a user without a restrictive proxy. A traditional database client application may handle timeouts in some smart way, a web user may only retry the query and there is a risk that user get lost all his input on the last screen of the web app in case of severe problem with his transaction. So a realistic benchmark should penalize implementations that allow significant timeouts for some fraction of queries.

When user submits some data, the web application can make few retries in case of transaction deadlock. In case of cluster backend, the web app can also retry in case of death of a cluster node. Up to 10 retries are made without delays, then the error is reported to the user. All other errors are reported to the user immediately and thus penalized.

If transaction commits successfully but takes more than 3 seconds of physical time then it is penalized but counted as successfully executed. When user makes a query and it takes more than 3 seconds of physical time then it is penalized and not counted as successfully executed.

All other benchmark design ideas come from RDBMS traditions, basically unchanged. For price/performance calculation, the price of the system is calculated according to the TPC pricing specification,, that eliminates redundant paperwork if one set of hardware is used for both TPC benchmarks and BotNetBM.

The Simulated Activity

This version of the benchmark simulates random activities of very big number of users. A single user makes only ten operations per simulation day in average but the number of users is big and growing. It is impractical to make a true simulation, when one simulated hour takes exactly one hour of real time, so the test driver makes requests as frequently as the SUT can reply, but every transaction get simulated time as an argument. When a query mention time intervals like “posts during last day” it refers to datetimes in simulated time. In order to penalize fools who still can not solve Y2K problem, the simulated time begins 1999-01-01.

In this version of the benchmark, all users are equally active and queries of some user have no “meaningful” relation to each other. As a result, statistics are uniform and the database cache is equally “calm” for all users. This is not realistic and will be changed in future versions. This is intentionally not fixed right now because SPARQL optimization techniques are not mature enough and benchmark will become unusable on some systems. At the same time, some tags are much more popular than others, probably causing limited count of timeouts on some queries.

The read/write contention is unrealistically frequent when data set is small but decreases quickly as data set comes to reasonable size.

In addition to these users, there is a simulation of an on-site “analyst” that makes one “analytic report” every weekend of simulated time, first report is done at the beginning of the measurement interval. It is legal to adjust the test driver to make the report at some “convenient” time within the simulated weekend, e.g. to not make it during a checkpoint.

The benchmark has only one “official” parameter, the scale, defined as number of simulated user accounts at the beginning of the measurement interval. The measured value is the performance in (successful) clicks per minute. Data manipulation is successful if properly changed the data and not rolled back, “interactive” query is successful if response time was less than 3 seconds.

Data Dictionaries

The test driver needs some corpus of tag labels and random texts. Tag labels are borrowed from DBpedia 3.4 categories, file “categories_label_en.nt”. Random texts are random fragments of longabstract_en.nt with all backslash characters replaced with '[' (solely to simplify some maintainance scripts).

Data Structures

In the rest of the text, the following namespaces are assumed:

@prefix dc: <> .
@prefix dc: <> .
@prefix sioc: <> .
@prefix foaf: <> .
@prefix dcterms: <> .

Users, User accounts and Groups

A user has first and last name, a location IRI and an account. For an account, it has two forums for messages, named “wall” and “status”, first is for long handwritten messages and second for automated messages, hot links, mood etc. He moderates both forums and obviously subscriber of them. User tags his account on creation by 0 to 15 tags.

<http://sut/person/0> a foaf:Person ;
        foaf:firstName """Fbg""" ;
        foaf:lastName """Liagg""" ;
        foaf:based_near <http://sut/location/62290> .
<http://sut/user/fbg_liag> a <http://sut/user> , sioc:User ;
        sioc:account_of <http://sut/person/0> ;
        sioc:moderator_of <http://sut/forum/0>, <http://sut/forum/1> ;
        sioc:subscriber_of <http://sut/forum/0>, <http://sut/forum/1> ;
        dc:created "2000-01-01 00:00:00"^^xsd:dateTime .
<http://sut/forum/0> a sioc:Forum ;
        dc:created "2000-01-01 00:00:00"^^xsd:dateTime .
<http://sut/forum/1> a sioc:Forum ;
        dc:created "2000-01-01 00:00:00"^^xsd:dateTime .
<http://sut/user/fbg_liag> <http://sut/tag> """Unassessed Ajman articles""" .
<http://sut/user/fbg_liag> <http://sut/tag> """Rebreathers""" .

Group account is created by some user account that becomes its moderator and a moderator of group wall and group status forums. User tags the group account on creation by 0 to 15 tags.

<http://sut/group/except%20Sirenia%20have%205263213Group> a <http://sut/group> , sioc:Usergroup ;
        sioc:name """except Sirenia have 5263213Group""" ;
        sioc:subscriber_of <http://sut/forum/12664>, <http://sut/forum/12665> ;
        dc:created "2004-11-26 09:43:13"^^xsd:dateTime .
<http://sut/user/fhfc_ldbi> sioc:member_of <http://sut/group/except%20Sirenia%20have%205263213Group> ;
        sioc:moderator_of <http://sut/forum/12664>, <http://sut/forum/12665> .
<http://sut/forum/12664> a sioc:Forum ;
        dc:created "2004-11-26 09:43:13"^^xsd:dateTime .
<http://sut/forum/12665> a sioc:Forum ;
        dc:created "2004-11-26 09:43:13"^^xsd:dateTime .
<http://sut/group/except%20Sirenia%20have%205263213Group> <http://sut/tag> """Bridges in Italy""" .
<http://sut/group/except%20Sirenia%20have%205263213Group> <http://sut/tag> """Subdivisions of Dominica""" .

Group Memberships and Handshaking

Users enter and leave groups. For each membership, an auxiliary subject is created that track dates the user has entered (and optionally left) the group.

<http://sut/group/the%20Jimmy%20Rogers%20Jr.2300987Group> sioc:has_member <http://sut/user/ffca_ldde> .
<http://sut/membership/1/1000000000> <http://sut/member-of-membership> <http://sut/user/ffca_ldde> ;
        <http://sut/group-of-membership> <http://sut/group/the%20Jimmy%20Rogers%20Jr.2300987Group> ;
        <http://sut/added> "2000-01-13 20:04:21"^^xsd:dateTime .

User establish foaf:knows by a hadshaking (first A requests B, then B approve or reject, A may revoke any time after the request). An approved handshaking make a symmetric pair of foaf:knows predicates. The state of the handshaking is described by properties of a special subject.

If A have requested B then B will not request A.

Example of requested but not approved contact:

<http://sut/contact/0/8> <http://sut/memb> <http://sut/user/fbg_liag> , <http://sut/user/fedd_lhjd> ;
        <http://sut/initiator> <http://sut/user/fbg_liag> ;
        <http://sut/requested> "2000-04-07 05:12:00"^^xsd:dateTime ;
        <http://sut/declined> "2001-02-06 10:17:43"^^xsd:dateTime ;
        <http://sut/removed> "2001-02-12 08:31:03"^^xsd:dateTime .

Example of requested and approved contact:

<http://sut/contact/0/25> <http://sut/memb> <http://sut/user/fbg_liag> , <http://sut/user/fbhh_ldji> ;
        <http://sut/initiator> <http://sut/user/fbg_liag> ;
        <http://sut/requested> "2001-02-19 09:24:23"^^xsd:dateTime ;
        <http://sut/approved> "2004-10-10 04:48:33"^^xsd:dateTime .
<http://sut/user/fbg_liag> foaf:knows <http://sut/user/fbhh_ldji> . <http://sut/user/fbhh_ldji> foaf:knows <http://sut/user/fbg_liag> .

Once created, membership or handshaking subject continue to keep all its triples even if the membership or handshaking is dropped by a user, but predicates sioc:has_member and foaf:knows are replaced with sioc:had_member and foaf:known .

Threads, Posts and Comments

Thread is contained in a forum and contains nonempty collection of posts. Every post is created by an author user, it contains title (up to 80 chars) and body (of unevenly distibuted size, see below), 0 to 15 tags are associated with it (and same tags are associated with a newly created thread if a post is the first in thread).

<http://sut/forum/0/thread/9> a <http://sut/thread> , sioc:Thread ;
        dcterms:title """... 3 to 83 chars ...""" ;
 dc:created "2000-01-04 00:00:00"^^xsd:dateTime .
<http://sut/forum/0> sioc:container_of <http://sut/forum/0/thread/9> .
<http://sut/forum/0/thread/9> <http://sut/tag> """Lost BBC episodes""" .
<http://sut/forum/0/thread/9> <http://sut/tag> """Comics creator BLP pop""" .

Post is created by an author, is contained in a forum and is contained for zero or more comments. Any user may write posts to its own wall or status forum, to the status forum of group he moredates or to wall forum of some group he belongs to.

<http://sut/thread/0/post/0> a <http://sut/post> , sioc:Post ;
        dcterms:title """... 3 to 83 chars ...""" ;
        dc:created "2000-01-01 00:00:00"^^xsd:dateTime .
<http://sut/thread/0/post/0> sioc:content """... 50 to 20000 chars depending on type of forum ...“”” ;
<http://sut/forum/2/thread/0> sioc:container_of <http://sut/thread/0/post/0> .
<http://sut/user/ffca_ldde> sioc:creator_of <http://sut/thread/0/post/0> .
<http://sut/thread/0/post/0> <http://sut/tag> """Lost BBC episodes""" .
<http://sut/thread/0/post/0> <http://sut/tag> """Comics creator BLP pop""" .

Comment is also created by an author, it is contained in some post. A user can comment any post of any forum where he has write permission for posts.

<http://sut/post/472278/cmt/1125658> a <http://sut/comment> , sioc:Item ;
        dc:created "2005-01-02 10:52:53"^^xsd:dateTime ;
        sioc:content """...“”” .
<http://sut/thread/26273/post/472278> sioc:container_of <http://sut/post/472278/cmt/1125658> .
<http://sut/user/fgfc_lehb> sioc:creator_of <http://sut/post/472278/cmt/1125658> .


Test driver makes mix of transactions and mix of queries. In default benchmark configuration, 80% operations are “interactive” SPARQL queries and 20% are SPARUL transactions that write something to the RDF store. The experiment begins with an empty dataset and it grows to the desired state as actions add more users and other subjects. Results of queries are not used in transactions in any way so it is possible to perform only mix of transactions before the measurement and not waste resources for useless queries. It is advisable to backup a database of the needed scale for reuse in future experiments because the scale will grow during the measurement and there is no easy way of shrinking it back.

For convenience, actions and queries are identified by chars. Characters instead of numbers is the most significant deviation of this benchmark from RDBMS traditions.

User actions

A: Create new user. This is the only action that is not made by a randomly chosen existing user. B: Make a post in new or existing thread. C: Make a comment to an existing post. D: Delete a post / comment (deleting a post with comments deletes the comments as well) (postponed to the next version) E: Make a new social contact request F: Approve a social contact request (in next version it will be public event) G: Decline a social contact request H: Remove a social contact I: View events (postponed to the next version) J: Create group (and become its moderator and first member) K: Join group L: Leave group M: Create/Modify profile by adding/removing interests (postponed to the next version) N: Send a (private)message to other users (postponed to the next version) O: List private messages (postponed to the next version) P: Delete private messages (postponed to the next version) Q: View a page with relevant ads and log ad placement details (postponed to the next version). R: Block an event/message producer, i.e., a user or some sort of actions (postponed to the next version)

Action's probability in mix are as follows: for each 2 users added (2 actions A) there are 200 B, 500 C, 20 E, 16 F, 4 G, 1 H, 1 J, 6 K and 3 L. The exception is the very beginning of the run. While there are less then 10 user accounts, only actions A are performed. After that, while there are less then 2 group accounts, only actions J are performed.

Interactive query mix

A: All friends of<user>

select ?f
     ((select ?fname from <http://sut> where { ?f foaf:firstName ?fname } limit 1)) as ?fname
     ((select ?lname from <http://sut> where { ?f foaf:lastName ?lname } limit 1)) as ?lname
     from <http://sut> where { { select ?f where {
     {{ `iri(?::0)` foaf:knows ?f } UNION { ?f foaf:knows `iri(?::0)` }} } } }

B: Last 50 posts of type in<eventtypes>  of all friends of<user>

select ?post ?f ?c
      ((select ?title from <http://sut> where { ?post dcterms:title ?title } limit 1)) as ?title
      ((select ?body from <http://sut> where { ?post sioc:content ?body } limit 1)) as ?body
      from <http://sut> where { { select ?post ?f ?c where {
    `iri(?::0)` foaf:knows ?f .
    ?f sioc:creator_of ?post .
    ?post dc:created ?c . } order by desc (?c) limit 20 }}

C: Private messages

D: Notes (blog posts)

select ?post
      ((select ?title from <http://sut> where { ?post dcterms:title ?title } limit 1)) as ?title
      ((select ?body from <http://sut> where { ?post sioc:content ?body } limit 1)) as ?body
     from <http://sut> where { { select ?post where {
    `iri(?::0)` sioc:creator_of ?post .
    ?post a <http://sut/post> . } } }

E: What are the 10 most recent posts by somebody in my friends or their friends? This would be a typical dashboard item.

select ?post
      ((select ?title from <http://sut> where { ?post dcterms:title ?title } limit 1)) as ?title
      ((select ?body from <http://sut> where { ?post sioc:content ?body } limit 1)) as ?body
     from <http://sut> where { { select ?post where {
    ?a foaf:knows ?f option (TRANSITIVE, T_DISTINCT, T_NO_CYCLES, T_MAX (2)) .
    filter (?a = iri(?::0))
    ?f sioc:creator_of ?post .
    ?post a <http://sut/post> ; dc:created ?c . } order by desc (?c) limit 10 } }

F: What are the authoritative bloggers on topic x? This is a moderately complex ad-hoc query. Take posts tagged with the topic, count links to them, take the blogs containing them, show the 10 most cited blogs with the most recent posts with the tag. This would be typical of a stored query, like a parameterizable report.

G: How do I contact person x? Calculate the chain of common acquaintances best for reaching person x. For practicality, we do not do a full walk of anything but just take the distinct persons in 2 steps of the user and in 2 steps of x and see the intersection.

select distinct ?f from <http://sut> where {
    ?author foaf:knows ?f option (TRANSITIVE, T_DISTINCT, T_NO_CYCLES, T_MAX (2)) .
    filter (?author = iri(?::0))
    ?other foaf:knows ?f  option (TRANSITIVE, T_DISTINCT, T_NO_CYCLES, T_MAX (2)) .
    filter (?other = iri(?::1)) }

H: Who are the people like me? Find the top 10 people ranked by count of tags in common in the person's tag cloud. The tag cloud is the set of interests and the set of tags in blog posts of the person.

select ?other count (distinct ?tag) from <http://sut> where {
    { select distinct ?tag where { { `iri(?::0)` <http://sut/tag> ?tag } UNION { `iri(?::0)` sioc:creator_of ?post . ?post a <http://sut/post> ; <http://sut/tag> ?tag . } } }
    { { ?other <http://sut/tag> ?tag } UNION { ?other sioc:creator_of ?thread2 . ?thread2 a <http://sut/thread> ; <http://sut/tag> ?tag . } }
    ?other a <http://sut/user> .
    filter (?other != iri(?::0))
    } order by desc (2) limit 10

I: Who react to or talk about me? Count of replies to material by the user, grouped by the commenting user and the site of the comment, top 20, sorted by count descending.

select ?other ?site count (1) from <http://sut> where {
    `iri(?::0)` sioc:creator_of ?post .
    ?post a <http://sut/post> .
    ?post sioc:container_of ?comment .
    ?thread sioc:container_of ?post .
    ?site sioc:container_of ?thread .
    ?other sioc:creator_of ?comment .
    } order by desc (3) limit 20

J: Who are my fans that I do not know? Same as above, excluding people within 2 steps.

select ?other ?site count (1)
 from <http://sut> where {
    `iri(?::0)` sioc:creator_of ?post .
    ?post a <http://sut/post> .
    ?post sioc:container_of ?comment .
    ?thread sioc:container_of ?post .
    ?site sioc:container_of ?thread .
    ?other sioc:creator_of ?comment .
    filter (?other != iri(?::0))
    filter (!(ask where {
          ?a foaf:knows ?otr option (TRANSITIVE, T_DISTINCT, T_NO_CYCLES, T_MAX (2)) .
          filter ((?a = iri(?::0)) && (?otr = ?other)) } ))
    } order by desc (3) limit 20

K: Who are my competitors? Most prolific posters on topics of my interest that do not cite me.

L: Where is the action? On forums where I participate, what are the top 5 threads, as measured by posts in the last day. Show count of posts in the last day and the day before that.

M: How do I get there? Who are the people active around both topic x and y? This is defined by a person having participated during the last year in forums of x as well as of y. Forums are tagged by topics. The most active users are first. The ranking is proportional to the sum of the number of posts in x and y.

Queries are chosen at random, each query gets a random ID of some existing user as an argument, query G gets two such IDs as two arguments (?::0 and ?::1 indicate placeholders of these arguments in texts of queries). Probabilities are: for each 5 A there are 5 B, 5 D, 1 E, 1 G, 1 H, 1 I, 1 J, other queries are postponed for the next version. Query texts are given only for reference and not a normative part of the spec.

Analytic Mix

The mix runs one time per complete week of simulation time, usually it starts during the weekend and should complete before the end of weekend, with only one expection: one time should start despite day of the week at the very beginning of the measurement.

Every query is executed only once, they can be executed in any order or even placed into a stored procedure that will return all result sets in one go.

V: The fastest propagating idea - What is the topic with the most users who have joined in the last day? A user is considered to have joined if the user was not discussing this in the past 10 days.

W: Prime movers - What users start conversations? A conversation is the set of material in reply to or citing a post. The reply distance can be arbitrarily long, the citing distance is a direct link to the original post or a reply there to. The number and extent of conversations contribute towards the score.

X: Geography - Over the last 10 days, for each geographic area, show the top 50 tags. The location is the location of the poster.

Y: Social hubs - For each community, get the top 5 people who are central to it in terms of number of links to other members of the same community and in terms of being linked from posts. A community is the set of forums that have a specific topic.

Z: Trends - most posted links