{"action":"created","issue":{"url":"https://api.github.com/repos/EFForg/privacybadger/issues/1531","repository_url":"https://api.github.com/repos/EFForg/privacybadger","labels_url":"https://api.github.com/repos/EFForg/privacybadger/issues/1531/labels{/name}","comments_url":"https://api.github.com/repos/EFForg/privacybadger/issues/1531/comments","events_url":"https://api.github.com/repos/EFForg/privacybadger/issues/1531/events","html_url":"https://github.com/EFForg/privacybadger/issues/1531","id":245284425,"number":1531,"title":"Better datastructure for storing domains","user":{"login":"cowlicks","id":598099,"avatar_url":"https://avatars0.githubusercontent.com/u/598099?v=4","gravatar_id":"","url":"https://api.github.com/users/cowlicks","html_url":"https://github.com/cowlicks","followers_url":"https://api.github.com/users/cowlicks/followers","following_url":"https://api.github.com/users/cowlicks/following{/other_user}","gists_url":"https://api.github.com/users/cowlicks/gists{/gist_id}","starred_url":"https://api.github.com/users/cowlicks/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cowlicks/subscriptions","organizations_url":"https://api.github.com/users/cowlicks/orgs","repos_url":"https://api.github.com/users/cowlicks/repos","events_url":"https://api.github.com/users/cowlicks/events{/privacy}","received_events_url":"https://api.github.com/users/cowlicks/received_events","type":"User","site_admin":false},"labels":[{"id":98184651,"url":"https://api.github.com/repos/EFForg/privacybadger/labels/low%20priority","name":"low priority","color":"eeeeee","default":false},{"id":570309696,"url":"https://api.github.com/repos/EFForg/privacybadger/labels/performance","name":"performance","color":"88166d","default":false}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":2,"created_at":"2017-07-25T04:45:00Z","updated_at":"2017-10-16T17:04:42Z","closed_at":null,"author_association":"MEMBER","body":"\r\nWe currently use javascript objects, like the `action_map`, or arrays like the sitesDisabled\r\nor the cookieblock list, to store domains.\r\n\r\nBut if, for example, we have a domain, and want to find if we have any of its\r\nsubdomains, we have to iterate over every key of the object, or element of the\r\narray. This is O(n).\r\n\r\nWe do this sometimes, like in #1507, or a recent migration, or [here](https://github.com/EFForg/privacybadger/blob/6c2ddbda8aba1761906c18145997ca2ecb07a0e1/src/js/heuristicblocking.js#L42), or in #1528.\r\n\r\nA better data structure for these would be a prefix tree, where each nodes are\r\nDNS \"labels\" (domain piece between dots). This would allow us to lookup domains\r\nin O(1), and get all subdomains for a domain in O(1). A quick example that would\r\nbe a drop in replacement for the current storage api:\r\n```javascript\r\nfunction Tree() {\r\n  this._base = {};\r\n}\r\n\r\nTree.prototype = {\r\n  sentinel: '.',  // because '.' can't appear in DNS labels\r\n\r\n  splitter: function(splitme) {\r\n    return // split string input into an array however you want\r\n  },\r\n};\r\n\r\nfunction setItem(tree, item, val) {\r\n  let parts = tree.splitter(item),\r\n    len = parts.length,\r\n    node = tree._base;\r\n\r\n  for (let i = 0; i < len; i++) {\r\n    let part = parts[i];\r\n    if (!node.hasOwnProperty(part)) {\r\n      node[part] = {};\r\n    }\r\n    node = node[part];\r\n  }\r\n  node[tree.sentinel] = val;\r\n};\r\n\r\nfunction getItem(tree, item) {\r\n  let parts = tree.splitter(item).concat(tree.sentinel),\r\n    len = parts.length,\r\n    node = tree._base;\r\n\r\n  for (let i = 0; i < len; i++) {\r\n    let part = parts[i];\r\n    if (!node.hasOwnProperty(part)) {\r\n      return undefined;\r\n    }\r\n    node = node[part];\r\n  }\r\n  return node;\r\n};\r\n```\r\n\r\nI think the performance improvements from using this would be minor. I think\r\nthe real gains will be from our ability to easily get subdomains. I think we\r\nhave deliberately architected this project around the idea that getting\r\nsubdomains from a domain is hard. This has resulted in use using\r\n`window.getBaseDomain` for everything that goes in storage, like `action_map`\r\nand `snitch_map`.\r\n\r\nThis makes it very hard to debug issues, since our information is very limited.\r\nWe usually cant' find the get the FQDN of the tracker *or* the sites where they\r\nwere seen tracking.\r\n\r\nWith a datastructure like this we'd be able to store the FQDN of the tracker,\r\nand the FQDN of the basedomain, and retreive them in an efficient way. **Having\r\nthis information readily available would allow us to fix broken site issues\r\nmuch more quickly.** \r\n\r\n**This would also help us know that we are actually fixing the right bugs.**\r\n\r\nWe are currently only blindly able to fix some site bugs, for examlpe in #1493\r\n* there is a blocked fqdn that is not tracking on the reported 1st party origin\r\n* the blocked domains' fqdn is different from its base domain\r\n* none of the basedomains in the snitch_map have the tracking basedomain. I don't even know if the snitch maps are derived from FQDN's. \r\n\r\nSo there is no obvious way to find where the original tracking actually happend\r\nand reproduce it. I could go wondering around the internet looking for it\r\nmyself. I could further interrogate the bug. So what usually happens is something\r\ngets added to the cookieblock list. None of these methods are sustainable.\r\n\r\nSo I think:\r\n\r\n**We need to have a better `action_map` to fix issues like this**\r\n\r\n<hr>\r\n\r\nI'd like to propose anotehr method for the api:\r\n\r\n```javascript\r\n/**\r\n * preform a reduction along a branch\r\n * Callback looks like:\r\n * function(node, finish)\r\n */\r\nfunction reduce(tree, memo, callback)\r\n```\r\n\r\nThese wolud let us aggregate information along a branch of the tree.  So for example we'd\r\nbe able get all the places a fqdn and all of its parent domains were seen\r\ntracking efficiently.\r\n\r\nI think a good place to introduce this data structure is in #1507, if it goes well\r\nwe can use it in storage. Related issues #1289, #1527, #963. This would also allow us\r\nto re-asses #1515\r\n"},"comment":{"url":"https://api.github.com/repos/EFForg/privacybadger/issues/comments/336954123","html_url":"https://github.com/EFForg/privacybadger/issues/1531#issuecomment-336954123","issue_url":"https://api.github.com/repos/EFForg/privacybadger/issues/1531","id":336954123,"user":{"login":"ghostwords","id":794578,"avatar_url":"https://avatars1.githubusercontent.com/u/794578?v=4","gravatar_id":"","url":"https://api.github.com/users/ghostwords","html_url":"https://github.com/ghostwords","followers_url":"https://api.github.com/users/ghostwords/followers","following_url":"https://api.github.com/users/ghostwords/following{/other_user}","gists_url":"https://api.github.com/users/ghostwords/gists{/gist_id}","starred_url":"https://api.github.com/users/ghostwords/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ghostwords/subscriptions","organizations_url":"https://api.github.com/users/ghostwords/orgs","repos_url":"https://api.github.com/users/ghostwords/repos","events_url":"https://api.github.com/users/ghostwords/events{/privacy}","received_events_url":"https://api.github.com/users/ghostwords/received_events","type":"User","site_admin":false},"created_at":"2017-10-16T17:04:42Z","updated_at":"2017-10-16T17:04:42Z","author_association":"MEMBER","body":"Related to #266."}}
{"actor":{"display_login":"ghostwords"}}