Filter hit statistics backend

[sebastian]

Background

In #394 we will be implementing a mechanism to collect filter hits anonymously. We need a backend to receive, store and query that data.

What to change

Create new web backends in the ​sitescripts repository under sitescripts/filterhits/web. One should handle the URL https://filterhits.adblockplus.org/submit to receive POST requests in the format specified in #394. This data should be aggregated (number of hits per time interval averaged out for each filter/domain combination) and stored in a MySQL database. Additionally, the raw data submitted should be stored in files (including submission timestamp and query parameters but not IP addresses). One file per submission is a possible solution, however one has to create a directory hierarchy that will limit the number of files per directory.

Note that we can receive the data and store + process it immediately, even though this approach will delay processing of the request. The request is sent by the browser in the background, so the user doesn't care about processing times. We can still switch to a more elaborate approach later.

If storing the incoming data fails an error status code of 500 should be returned to the client. If the database processing fails however the transaction should be rolled back but a successful response should be returned to the client instead. This is to avoid re-transmission of the data, the error should be logged on the server however.

If the incoming data is invalid an error status code of 400 will be returned to the client and the data will not be logged. Possible reasons could include:

• Wrong content type (should be "application/json")
• Invalid JSON in request body.
• Data in request body is missing required fields / fields are not of the appropriate data type.

Aggregation approach is complicated by the fact that clients will submit data that was collected over different time intervals. We want to use geometrical mean for now, but this is merely a placeholder for a better approach. Let's say we have stored in the database (for a particular filter and domain): numclicks = 7, timestamp = 123. We receive numclicks = 2, timestamp = 128. So the timestamp difference is 5. We update the record: numclicks = 7 ^ (1 - 5 / interval) * 2 ^ (5 / interval) and timestamp = 128. Here interval is a constant that will determine how fast old values expire, it probably makes sense to set it equal to the push interval on the client (meaning e.g. 1 week).

The second web backend under https://filterhits.adblockplus.org/query should allow querying data from the database. Currently two types of queries should be implemented:

1. Query by filter: "For this filter show me which domains matched and how often" (used to test which domains are affected if a filter is changed/removed).
2. Query by domain: "For this domain show me which filters matched and how often" (used to investigate what our users see on a domain)

In both cases the results should be sorted by the number of hits (descending), it might also make sense to limit the number of results. Access protection for this URL should be implemented in the server configuration so it can be ignored here. Additional queries might be implemented later, for now all we want is the minimum viable product.

Finally a basic web interface should be made for the query API to allow the viewing, pagination and filtering of the available data. (These facilities should work on the server side due to the amount of data we are expecting.)

[trev]

Unassigning.

@sebastian: Please feel free to assign this to you when you actually start working on it.

[kzar]

@palant @fhd: Could you guys update this ticket with some more details? Expectations you have of how this will work etc? (I think if it's spec'd a bit more we could hopefully cut down some back and forth with long delays!)

• What format will the data come in, JSON straight from the extension?
• Should the back end process the data at all?
• Where do you want the data to be stored? (Postgres database somewhere, something else?)
• Does the back end need to provide an API for querying the data or any interface for viewing the data directly?
• Any other expectations you have?

[Kirill]

I clearly recommend using MongoDB to dump the json files there. The main advantages are:

• is is scalable
• you can just dump json there
• it provides query and aggregation framework
• you can do different database stuff with your dumped json files (indexing)
• it can easily run in a cluster of servers and is supports map-reduce
• it's very easy to implement and open source

[Kirill]

I don't think it's necessary for the server to provide some API. The application should run server-side and be able to query the aggregational data(base).

[kzar]

My remaining questions:

• Exactly how will the data be aggregated as it's stored in the MySQL database?
• What's structure exactly will the submitted data be in? Will there be any optional fields or anything extra?
• Does any querying of the raw data need to be provided? If so what?

[Kirill]

There is a good tutorial for MongoDB for DBAs. Please take a look at it, before rejecting it. ​Tutorials

[Kirill]

I think we can think of the exact aggregations after collecting some raw data. Querying should be provided (which can be done with some database like Mongo) and if there are optional fields some NoSQL DB could handle it, since you don't need to provide a datastructure.

[kzar]

@palant what was your estimate of how much data the back end might receive again? I guess the first step is to try to figure out if MongoDB can handle that type of load.

[kzar]

From a quick bit of research it appears Cassandra might be better suited to our needs than MongoDB. Does anyone else have an opinion about what we should use?

[kzar]

OK initially I will just log the data to a plain text file for now as @palant suggested, we can decide on using something more advanced if it becomes an issue. Sorry for the trac spam everyone.

[trev]

Replying to kzar:

• Exactly how will the data be aggregated as it's stored in the MySQL database?

Here is how you would do it with the geometrical mean (probably not the best approach, but we can start out with this one). Let's say we have stored in the database (for a particular filter and domain): numclicks = 7, timestamp = 123. We receive numclicks = 2, timestamp = 128. So the timestamp difference is 5. We update the record: numclicks = 7 ^ (1 - 5 / interval) * 2 ^ (5 / interval) and timestamp = 128. Here interval is a constant that will determine how fast old values expire, it probably makes sense to set it equal to the push interval on the client (meaning e.g. 1 week).

• What's structure exactly will the submitted data be in? Will there be any optional fields or anything extra?

The format is described in #394.

• Does any querying of the raw data need to be provided? If so what?

No, the raw data should only be kept in case we need to recalculate the aggregated data.

OK initially I will just log the data to a plain text file for now as @palant suggested, we can decide on using something more advanced if it becomes an issue.

@palant what was your estimate of how much data the back end might receive again?

As long as we don't promote that feature we should stay below 0.1% of our user base - meaning something on the magnitude of 50k users. That means 50k submissions per week. Data size is hard to guess, we will see it once we start collecting it in our own browsers - I would expect it to stay below 100kB however. So we have an upper limit of 5 GB per week (more likely in the area of 1 GB), with the usual load spikes on Mondays.

OK initially I will just log the data to a plain text file for now as @palant suggested, we can decide on using something more advanced if it becomes an issue.

I agree - I don't really see why it would become an issue, and I am generally reluctant to introduce unnecessary dependency.

[kzar]

So quick update for everyone as it's been a while:

• I've made [a simple API that logs the data](​https://github.com/kzar/adblockplus-hitstats-backend) as specced in the other ticket. @manvel if you want to play with it so far to test that data is sent OK [instructions for setting up a VM are here]​https://github.com/kzar/adblockplus-infrastructure/tree/495-hitstats.
• I wasted several days naively trying to put _all_ the raw data into Elasticsearch to allow @kirill to use the data freely as requested. Unfortunately there's just too much data. I generated some dummy data, a fraction of the expected volume, and Elasticsearch died quite a death!
• In case it helps anyone I've attached a little bit of dummy data above maybe useful for messing around with.
• I'm now working on a script to aggregate the data, to start with I'll try the geometrical mean approach @trev described. @kirill if you have better ideas for how to aggregate the data in ways that will be useful for you then let me know and I can try and incorporate them into the script too. I'm hoping this could still be useful to you even though the raw data is not directly query-able as you originally wanted.
• @c.dommers I want to make this easy to use for you guys, if you have any suggestions I'd like to hear them. Unfortunately as I mentioned making all the raw data query-able is just not feasible for now, but I'm still aiming to make something that benefits biz-dev.

[kzar]

At @kirill's request I've produced a JSON version of the dummy data above that has been flattened into the structure he wanted. I couldn't upload it to the ticket as it's too large but here's a link that should work for now ​http://static.kzar.co.uk/dummy-hitstats-flat.json.zip

[kzar]

1000 records of dummy data

[kzar]

(Just redone both sets of dummy data to include subscriptions.)

[Kirill]

I managed to load the data into MongoDB (one line of code), which took about 90 minutes. Aggregational queries(one line of code) take appr. 1 second (sic!) on unindexed data!
I assume that importing could be faster, if the datastructure is not completly flat, but nested as suggested by me earlier. This way we would save memory by avoiding redundancy.
Cheers!

[kzar]

@kirill I think monoDB is indexing the data as it's inserted, could explain why inserts are slow but queries quite fast. I tried to format the data as you wanted, how did you want it nested? Could you give an example?

[Kirill]

I checked with my testdata and the documentation, the only index which was done was the id field, which gets assigned to every document. Since I don't aggregate by id, no index was used! ​http://docs.mongodb.org/manual/core/index-single/

[Kirill]

@kzar, here is an example of the suggested data structure: https://issues.adblockplus.org/ticket/394#comment:18

[kzar]

Another update, so far I have written hopefully quite a nice tool for processing aggregations on the data. It works on huge log files and allows for doing things in a familiar map reduce fashion. I've implemented some code to interface with MySQL as well. Also I've been documenting and writing tests for it all as I go along. (Also been writing helper functions and utilities wherever possible.)

Still to do is:

• Have the processing tool use the db module to actually save the results of aggregations.
• Have the API provide a nice interface for querying out the aggregated results.
• Finish the geometrical mean aggregation and any others + write tests for them all.
• Have a go at making the mapping functions run concurrently.

I have to stop now for a while to focus on another ticket, when I return I shall do the above. In the mean time @kirill would you mind thinking about some useful aggregations and helping my to write some? If you could help me do that when we put the tool live hopefully it will generate you some useful data. The tool is documented so far here ​https://github.com/kzar/adblockplus-hitstats and you can see a (partially finished!) example of a job here ​https://github.com/kzar/adblockplus-hitstats/blob/master/hitstats/jobs/geometrical_mean.py .

[kzar]

Replying to trev:

Here is how you would do it with the geometrical mean (probably not the best approach, but we can start out with this one). Let's say we have stored in the database (for a particular filter and domain): numclicks = 7, timestamp = 123. We receive numclicks = 2, timestamp = 128. So the timestamp difference is 5. We update the record: numclicks = 7 ^ (1 - 5 / interval) * 2 ^ (5 / interval) and timestamp = 128. Here interval is a constant that will determine how fast old values expire, it probably makes sense to set it equal to the push interval on the client (meaning e.g. 1 week).

@palant Two questions with this:

1.) Supposing no new data has come in for one of the filter domain combinations since last time, what would the formula look like to lower the existing old data for that filter? (So that the hits for it are still weighted fairly relative to time.)
2.) For each domain filter combination there are often lots of separate hits that we're aggregating and lots of separate "latest" timestamps. At the moment I'm just taking the first "latest" timestamp I see as the new timestamp. Is that OK, should I average them all instead to come up with the new timestamp value? Or should I do something else? (I'm hoping to avoid the need of keeping hold of a huge list of timestamps until the end, but I can't see how else to provide an average of them.)

@kiril Still awaiting some ideas / guidance for aggregations you would find useful. Have you had any ideas yet?

[Kirill]

@kzar: First of all, I find your solution elegant, but I am afraid that it does not match with our requirement for it to be easily maintainable for the business side. For me it would be easier to work with proper database solutions on the raw data level, but we can start with your solution first and then, when we have the first data, find new/additional solutions in the next quarter.
Secondly, I have ideas for aggregations, but I want to learn how to write map reduce aggregations in your framework first. Maybe you could give me some guidance in private?

[kzar]

@kiril Well what I'm looking for at the moment is some specific examples of the aggregations you would like to run. You can explain them like @palant explained the geometrical mean idea above, here, in the ticket. I'm not asking you to write the code for it, only explain it for me so that I can. Having a few useful jobs at the outset will help me develop the system (it's still incomplete), ensure it works properly and t will ensure you have some useful data being produced right from the start.

(Each job will first map over and then reduce with the flattened data. The flattened data looks exactly the same as the sample flattened data I sent you and it's also documented in the project's README ​https://github.com/kzar/adblockplus-hitstats . That should be all you need to know for now to give me some example aggregations.)

@kiril Also please could you stop being so negative all the time? (In the tickets and in private messages.) I find it quite demotivating to be honest. If you want a different system, talk with @palant _on this ticket_ and come to some kind of a actionable conclusion. That way I know where I stand and that I'm not spending all this time making the wrong thing!

[Kirill]

Replying to kzar:

@kirill Well what I'm looking for at the moment is some specific examples of the aggregations you would like to run. You can explain them like @palant explained the geometrical mean idea above, here, in the ticket.

Maybe we can open another ticket for the aggregations? I then can give you some ideas. It's important for me, that the system is maintainable for me and not some kind black box, therefore I would appreciate if you could tie me in into the process more.

@kirill Also please could you stop being so negative all the time?

I don't think this is the right forum to discuss it, if you feel me being negative, tell me in private, I don't see how accusing me publicly contributes to the issue.

[philll]

@kirill: With the description of this issue, it is absolutely impossible to meet whatever kind of specific expectations. Formulations like "Aggregated data needs to be weighted somehow" are so vague that one just cannot implement them in the way that they meet the requester's expectations.
@kazar: To avoid such situations, you should make sure that an issue included a sufficient description before you start your first line of code. Unfortunately, this was marked as ready by trev.

In general, I would be fine, if we limit this issue to providing the raw data in a way accessible to kirill and create a "create concept" issue for him to find his actual desires, before we afterwards write a proper issue for the aggregation and filter implementations that he found.

[kzar]

OK so current status update (I'm away next week):

• Geometrical mean is now working and properly tested as far as I understand it. I still have a few questions though @palant:
  • When there is old data for a domain + filter combo but there is no new data, what would the formula look like to properly reduce the numclicks? (At the moment I just leave the numclicks alone but that seems wrong.)
  • Supposing a numclicks are reduced to zero by the calculation would you like that entry to be removed from the database or left in as zero? (At the moment they are left in the database.)
  • Each time you run a processing job you actually might have lots of different timestamps for each domain + filter combination. At the moment I am just using the first timestamp I see, another option might be to average it. Does it matter what we do? (I am trying to avoid keeping hold of a potentially huge list of timestamps during the calculation, which I worry calculating the average would require.)

• The processing script seems to have an intermittent bug when reading from stdin which I haven't managed to fix yet. (I also want to go through all the other scripts and make sure they still work with all the changes I've been making to the underlying code.)
• I've not written any of the aggregations Kiril wants yet, @kiril could you think of a couple whilst I'm away? (I don't mind if they're in a different ticket like you suggested or not. But if you could think of at least one for me it would help me ensure the system works with multiple jobs.) As I mentioned before if you could explain them in plain English with formulas where required like @palant did with the geometrical mean above that would be helpful. If you do write them in a different ticket could you post me a link here?
• I still need to write an API for querying the aggregated data back out of MySQL, I have not started that yet.
• I want to do a few very large tests with as many jobs as possible just to ensure the whole system really does work at the expected load end to end.

Otherwise it's pretty much there, so there's still work to do but we're making progress. Code is here still ​https://github.com/kzar/adblockplus-hitstats and I've done my best to keep the tests and documentation up to date.

[Kirill]

Replying to kzar:

@kirill could you think of a couple whilst I'm away?

Here you go, this are just some unripe, easy ideas, but it should be sufficient for you to test the data and for me to get an idea what is possible and a feeling for the data.

1. Sum hits of third party ads BY filter, date of submission and date of last submission
2. Sum hits BY website, submission date, party (first, third)
3. Sum hits and amount of subscriptions of third party ads BY subscriptions, GeoIP (country), filter
4. Sum hits and amount of AddonName/AddonVersion pairs BY addonName, addonVersion, submissions, last submission

Feel free to ask if the aggregations are not clear enough. The goal should be, that this aggregations serve as examples for me to learn from your code how to code them, so next time I can write the aggregations myself and you just review them.

• I still need to write an API for querying the aggregated data back out of MySQL, I have not started that yet.

I still don't understand why we need those. I can query MySQL myself.

[kzar]

@palant I could still do with some help regarding the geometrical mean. Here are all my questions (three from earlier and a new one):

1. When the time difference is larger than the interval constant the formula breaks down. I'm thinking we should just set the numclicks as the new numclicks. (IE the old data has more than expired so just use the new stuff.) What do you think?
2. When there is old data for a domain + filter combo but there is no new data, what would the formula look like to properly reduce the numclicks? (At the moment I just leave the numclicks alone but that seems wrong.)
3. Supposing numclicks are reduced to zero by the calculation would you like that entry to be removed from the database or left in as zero? (At the moment they are left in the database.)
4. Each time you run a processing job you actually might have lots of different timestamps for each domain + filter combination. At the moment I am just using the first timestamp I see, another option might be to average it. Does it matter what we do? (I am trying to avoid keeping hold of a potentially huge list of timestamps during the calculation, which I worry calculating the average would require.)

[trev]

When the time difference is larger than the interval constant the formula breaks down.

Are you certain? You get a negative power but it should still work.

I'm thinking we should just set the numclicks as the new numclicks.

You receive data from a number of users, how would you just replace the number of clicks? The only option I can see is to keep counters for each daily interval. So you would simply increase numcount every time and at the end of the day some cron job would reset the field to zero and move the old value into some archive table (I wonder how fast that archive will grow). I guess that kirill would also be in favor of that solution, I merely didn't want to start with this somewhat complicated setup.

At the moment I just leave the numclicks alone but that seems wrong.

I don't think that we can arrive at a good solution with the geometrical mean, the weighting is off no matter what you do. It's really merely a placeholder for a better approach.

Supposing numclicks are reduced to zero by the calculation would you like that entry to be removed from the database or left in as zero?

I don't see anything wrong with leaving it in the database. Then again, I don't really see how it could be reduced to zero with floating point calculations...

Each time you run a processing job you actually might have lots of different timestamps for each domain + filter combination.

How so? Isn't the processing job per-submission?

[kzar]

Replying to trev:

When the time difference is larger than the interval constant the formula breaks down.

Are you certain? You get a negative power but it should still work.

I'm thinking we should just set the numclicks as the new numclicks.

You receive data from a number of users, how would you just replace the number of clicks? The only option I can see is to keep counters for each daily interval. So you would simply increase numcount every time and at the end of the day some cron job would reset the field to zero and move the old value into some archive table (I wonder how fast that archive will grow). I guess that kirill would also be in favor of that solution, I merely didn't want to start with this somewhat complicated setup.

At the moment I just leave the numclicks alone but that seems wrong.

I don't think that we can arrive at a good solution with the geometrical mean, the weighting is off no matter what you do. It's really merely a placeholder for a better approach.

Supposing numclicks are reduced to zero by the calculation would you like that entry to be removed from the database or left in as zero?

I don't see anything wrong with leaving it in the database. Then again, I don't really see how it could be reduced to zero with floating point calculations...

Each time you run a processing job you actually might have lots of different timestamps for each domain + filter combination.

How so? Isn't the processing job per-submission?

No, the processing job is not per-submission.

The processing job might run once an hour, once a day or whatever. (The interval constant is that interval between runs of the processing job in seconds.) Each time the processing job runs it takes a log file with presumably multiple submissions. For each submission in the log file it flattens down the data like @kiril asked for [1] on the fly, creating a generator of all the flattened "hits" [2] in the file.

Then each processing job maps over those flattened hits, reduces the mapped data down and finally calculates a final result and updates the database.

In the case of the geometrical mean we take the reduced data for each domain+filter combo and combine it with the old data taken from the database. (Using your geometrical mean formula above.) We then update the database with that.

At least that's what I understood you both wanted and I've been working on. It sounds like there has been a fundamental misunderstanding, could you explain how you expected things to work?

Where do we go from here? (I have been keeping my work so far online, documented and tested as far as possible if you want to see how it works at the moment ​https://github.com/kzar/adblockplus-hitstats )

Cheers, Dave.

[1] - ​​http://static.kzar.co.uk/dummy-hitstats-flat.json.zip

[2] - Example flattened hit: {"application": "ie", "hits": 5, "applicationVersion": "8", "addonName": "adblockplusie", "subscriptions": ["EasyList Czech and Slovak", "Adblock Polska", "Prebake", "Filtros Nauscopicos", "Malware Domains", "EasyList China", "Estonian filters by Gurud.ee", "Spam404", "Icelandic ABP List", "EasyList Dutch", "Fanboy's Annoyances", "Xfiles", "Liste FR", "EasyList Germany", "hufilter"], "remote_addr": "163.59.81.50", "domain": "youtube.com", "filter": "

iwayafrica.co.zw/images/banners/", "platform": "trident", "version": 1, "logged_time": "22/Oct/2014:11:48:39 +0000", "platformVersion": "4.0", "party": "thirdParty", "addonVersion": "1.0", "timeSincePush": 579409742, "latest": 1413978518236}

[kzar]

@palant Oh, I think I just figured it out. I thought you wanted me to sum all the hits for a filter+domain and then run the geometrical mean calculation once at the end. Your idea is actually to run the geometrical mean calculation for every hit for the filter+domain, starting from the existing value in the database and keeping track of the change.

That way if the interval is less than the time difference the overall number of hits is reduced in a more sensible way.

[trev]

Replying to kzar:

@palant Oh, I think I just figured it out. I thought you wanted me to sum all the hits for a filter+domain and then run the geometrical mean calculation once at the end. Your idea is actually to run the geometrical mean calculation for every hit for the filter+domain, starting from the existing value in the database and keeping track of the change.

Yes, that was indeed the idea - and the goal was that we don't need to store all the data.

[kzar]

Some data generated by the hitstats collection tool during testing.

[kzar]

​https://hg.adblockplus.org/sitescripts/rev/30a8d03fae89