{"action":"created","issue":{"url":"https://api.github.com/repos/arkgil/events/issues/3","repository_url":"https://api.github.com/repos/arkgil/events","labels_url":"https://api.github.com/repos/arkgil/events/issues/3/labels{/name}","comments_url":"https://api.github.com/repos/arkgil/events/issues/3/comments","events_url":"https://api.github.com/repos/arkgil/events/issues/3/events","html_url":"https://github.com/arkgil/events/pull/3","id":345786804,"node_id":"MDExOlB1bGxSZXF1ZXN0MjA0ODI2NDQz","number":3,"title":"ETS backend","user":{"login":"arkgil","id":11610769,"node_id":"MDQ6VXNlcjExNjEwNzY5","avatar_url":"https://avatars1.githubusercontent.com/u/11610769?v=4","gravatar_id":"","url":"https://api.github.com/users/arkgil","html_url":"https://github.com/arkgil","followers_url":"https://api.github.com/users/arkgil/followers","following_url":"https://api.github.com/users/arkgil/following{/other_user}","gists_url":"https://api.github.com/users/arkgil/gists{/gist_id}","starred_url":"https://api.github.com/users/arkgil/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/arkgil/subscriptions","organizations_url":"https://api.github.com/users/arkgil/orgs","repos_url":"https://api.github.com/users/arkgil/repos","events_url":"https://api.github.com/users/arkgil/events{/privacy}","received_events_url":"https://api.github.com/users/arkgil/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":8,"created_at":"2018-07-30T14:38:42Z","updated_at":"2018-08-03T14:23:56Z","closed_at":null,"author_association":"OWNER","pull_request":{"url":"https://api.github.com/repos/arkgil/events/pulls/3","html_url":"https://github.com/arkgil/events/pull/3","diff_url":"https://github.com/arkgil/events/pull/3.diff","patch_url":"https://github.com/arkgil/events/pull/3.patch"},"body":"This PR introduces an implementation based on ETS. In fact, there are two implementations, the second one being a slight improvement over the first one.\r\n\r\n### 1. Single ETS \r\n\r\nYou can find this implementation in `Events.Impl.Ets` module.\r\n\r\nEach handler is stored in a bag ETS table. The key is an event prefix the handler is attached to. All writes to a table go through a single Agent process to make sure that we don't get duplicate handler IDs.\r\n\r\nReads (`list_handlers_...`) on the ETS table are performed directly by the calling processes. When looking up handlers for event, first all the prefixes of event are built. Having those prefixes, a match spec is constructed to search for all handlers subscribed to these prefixes.\r\nSurprisingly (or maybe not?) ETS is so fast, that the bottleneck of `list_handlers_for_event/1`\r\nis the procedure of building all possible prefixes.\r\n\r\nWhen it comes to concurrency guarantess, there are simply none. When one process performs\r\nreads handlers for event, it might happen that another process deletes a handler from the table\r\n(because `:ets.select/2` is used which is not atomic).\r\n\r\n### 2. Single ETS + cache\r\n\r\nYou can find this implementation in `Events.Impl.EtsCached` module. It is based on two ETS tables: regular table for handlers as in `Ets` implementation, and a cache table.\r\n                                                                                                  \r\nIf the cache is disabled (more on when it's enabled later) the reads works exactly like in the `Ets` implementation.\r\n                                                                                                  \r\nThe cache is a set table with read concurrency. The key is an event name (not a prefix!) and\r\nthe value is a lists of handler records as stored in regular handler table. As you might suspect,\r\nthe list contains all handlers which should be invoked when the event stored as key is emitted.\r\n                                                                                                  \r\nWhen the cache is enabled, `list_handlers_for_event/1` first checks if the handlers which\r\nshould be invoked for this event are not already cached. If they are, then those handlers are\r\nreturned. If they are not, the handlers are looked up in regular table, exactly the same as\r\nin `Ets` implementation, and then they are cached and returned from the function.\r\n                                                                                                  \r\nIn this implementation Agent has been replaced with the GenServer. The same as in `Ets` backend,\r\nall writes go though this process. However in this case, the GenServer is also responsible for\r\nenabling and disabling the cache. The cache is enabled when there have been no writes for 500\r\nmilliseconds. When the cache is enabled and the write occurs, the whole cache is cleared and\r\nthe countdown starts again. The downside of this approach is that the cache will be cleared\r\nwhen handlers are detached due to their failure.\r\nThe improvement here would be to delete only these cache entries which would be affected by the\r\nwrite (fortunately this quite easy to achive and doesn't require computing the prefixes).\r\nWith such solution, the cache would be always enabled. It would probably be beneficial to\r\ndetach failing handlers in bathes to lower the number of writes to the table.\r\nThere is also another downside of this solution: all writes to cache table go through the GenServer.\r\nIt might happen that many processes emit the same event at once and all try to save handlers\r\nin cache which might flood the process with messages. On the other hand, if the processes would\r\ninsert entries into cache by themselves, we could run into all sorts of concurrency issues.\r\n                                                                                                  \r\nOne thing missing from this implementation is cache invalidation. I believe that the LFU (least\r\nfrequently used) scheme would be the most appropriate here, although some more elaborate techniques must be needed.\r\n\r\n### Discussion\r\n\r\nFrom the benchmarks I've run it turns out that ETS+cache is an order of magnitude faster (measured by iterations per second of `list_handlers_for_event/1` callback) than the bare ETS implementation. Also it looks like the Agent implementation is **faster** than the bare ETS. I've done some profiling and it happens most probably because the process of building all prefixes for the event is really expensive. Unfortunately, and quite expectedly, Agent implementation fails when there are more than 1000 processes running in the benchmark (with the default timeout of 5000ms).\r\n\r\nObviously the implementation with cache introduces all the cache-related problems, most notably how to evict records. I don't have more ideas on how to speed things up given the current API and semantics of attaching handlers to event prefixes. I know that @studzien has experimented with tree implementation, but as I understood it was still slower than the ETS+cache.\r\n\r\nI can post the results of benchmarks if anyone's interested. You can also run them by yourselves using the `mix bench.load_handlers_for_event` task (`MIX_ENV=bench mix help bench.list_handlers_for_event` might help here 🙂 ).\r\n\r\n/cc @josevalim @chrismccord @cloud8421 @studzien @mohamedalikhechine @rslota\r\n"},"comment":{"url":"https://api.github.com/repos/arkgil/events/issues/comments/410269559","html_url":"https://github.com/arkgil/events/pull/3#issuecomment-410269559","issue_url":"https://api.github.com/repos/arkgil/events/issues/3","id":410269559,"node_id":"MDEyOklzc3VlQ29tbWVudDQxMDI2OTU1OQ==","user":{"login":"cloud8421","id":537608,"node_id":"MDQ6VXNlcjUzNzYwOA==","avatar_url":"https://avatars0.githubusercontent.com/u/537608?v=4","gravatar_id":"","url":"https://api.github.com/users/cloud8421","html_url":"https://github.com/cloud8421","followers_url":"https://api.github.com/users/cloud8421/followers","following_url":"https://api.github.com/users/cloud8421/following{/other_user}","gists_url":"https://api.github.com/users/cloud8421/gists{/gist_id}","starred_url":"https://api.github.com/users/cloud8421/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cloud8421/subscriptions","organizations_url":"https://api.github.com/users/cloud8421/orgs","repos_url":"https://api.github.com/users/cloud8421/repos","events_url":"https://api.github.com/users/cloud8421/events{/privacy}","received_events_url":"https://api.github.com/users/cloud8421/received_events","type":"User","site_admin":false},"created_at":"2018-08-03T14:23:56Z","updated_at":"2018-08-03T14:23:56Z","author_association":"NONE","body":"@arkgil said:\r\n\r\n> I know that @studzien also experimented with generating prefixes at compile time which gave ~20% improvement to ips of ETS with lookup. The downside of this approach is that we need to know literal event name at compile time. Maybe the solution could be to generate prefixes at compile time when possible and at runtime when not?\r\n\r\nI would agree to optimize at compile time when possible provided that it doesn't become a complication which can be avoided for a first release (being aware of the performance impact seems enough for now)."}}
{"actor":{"display_login":"cloud8421"}}