{"action":"created","issue":{"url":"https://api.github.com/repos/zevv/duc/issues/161","repository_url":"https://api.github.com/repos/zevv/duc","labels_url":"https://api.github.com/repos/zevv/duc/issues/161/labels{/name}","comments_url":"https://api.github.com/repos/zevv/duc/issues/161/comments","events_url":"https://api.github.com/repos/zevv/duc/issues/161/events","html_url":"https://github.com/zevv/duc/issues/161","id":197761291,"number":161,"title":"Indexing algorithm","user":{"login":"jbd","id":169483,"avatar_url":"https://avatars.githubusercontent.com/u/169483?v=3","gravatar_id":"","url":"https://api.github.com/users/jbd","html_url":"https://github.com/jbd","followers_url":"https://api.github.com/users/jbd/followers","following_url":"https://api.github.com/users/jbd/following{/other_user}","gists_url":"https://api.github.com/users/jbd/gists{/gist_id}","starred_url":"https://api.github.com/users/jbd/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jbd/subscriptions","organizations_url":"https://api.github.com/users/jbd/orgs","repos_url":"https://api.github.com/users/jbd/repos","events_url":"https://api.github.com/users/jbd/events{/privacy}","received_events_url":"https://api.github.com/users/jbd/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":2,"created_at":"2016-12-27T21:38:11Z","updated_at":"2016-12-28T16:35:03Z","closed_at":null,"body":"Hello,\r\n\r\nthis is more a suggestion than an issue.\r\n\r\nThe duc indexing is already quite fast but you might be interested in the filesystem crawling algorithm of [robinhood](https://github.com/cea-hpc/robinhood) also written in C, if you don't already know the project:\r\n\r\n`To go beyond the performance of classical scanning tools,\r\nrobinhood implements a multi-threaded version of depth-first\r\ntraversal[4]. To parallelize the scan, the namespace traversal\r\nis split into individual tasks that consist in reading single\r\ndirectories. A pool of worker threads performs these tasks\r\nfollowing a depth-first strategy (as illustrated on figure 3).`\r\n\r\nfrom [Taking back control of HPC file systems with Robinhood Policy Engine](https://arxiv.org/pdf/1505.01448.pdf) paper. See [here](https://github.com/cea-hpc/robinhood/wiki/Papers-%26-presentations) for more.\r\n\r\nIf the storage could handle parallel requests nicely, that's a huge win. Right now I don't have any metrics to compare the crawling performance between robinhood and duc, but I'm using robinhood on a petabyte filer through nfs3 with nearly 1 billion files on it, and the crawling algorithm performance scales quite linearly up to 8 threads. After that, I can't tell if the filer or the mysql database that holds the results is the bottleneck at this moment. "},"comment":{"url":"https://api.github.com/repos/zevv/duc/issues/comments/269502276","html_url":"https://github.com/zevv/duc/issues/161#issuecomment-269502276","issue_url":"https://api.github.com/repos/zevv/duc/issues/161","id":269502276,"user":{"login":"l8gravely","id":884433,"avatar_url":"https://avatars.githubusercontent.com/u/884433?v=3","gravatar_id":"","url":"https://api.github.com/users/l8gravely","html_url":"https://github.com/l8gravely","followers_url":"https://api.github.com/users/l8gravely/followers","following_url":"https://api.github.com/users/l8gravely/following{/other_user}","gists_url":"https://api.github.com/users/l8gravely/gists{/gist_id}","starred_url":"https://api.github.com/users/l8gravely/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/l8gravely/subscriptions","organizations_url":"https://api.github.com/users/l8gravely/orgs","repos_url":"https://api.github.com/users/l8gravely/repos","events_url":"https://api.github.com/users/l8gravely/events{/privacy}","received_events_url":"https://api.github.com/users/l8gravely/received_events","type":"User","site_admin":false},"created_at":"2016-12-28T16:35:03Z","updated_at":"2016-12-28T16:35:03Z","body":">>>>> \"Ico\" == Ico Doornekamp <notifications@github.com> writes:\n\nIco> Quoting jbd (2016-12-27 22:38:12)\n>> The duc indexing is already quite fast but you might be interested in the\n>> filesystem crawling algorithm of robinhood\n>> ([1]https://github.com/cea-hpc/robinhood) also written in C, if you don't\n>> already know the project:\n\nIco> Thanks for that. I didn't know about Robnhood, but it seems that they\nIco> have taken the idea a few steps further already, it's like Duc on mass\nIco> steroids with a hundred additional featuresr; these people are way ahead\nIco> of me.\n\nI've looked at this too, and I think they have a crucial flaw, which\nis using Mysql as the backend, instead of some dedicated and optimized\nDB like Duc is using.  Or even what philesight used, and duc was a big\nperformance and size improvement there.\n\nAs for the parallel code, it will help up until the backend (NFS on\nNetapp in my case mostly) hits it's limits I fear.  \n\nIco> Robinhood seems to have a different audience then Duc though; it is not\nIco> a simple tool you can setup in a few minutes, but it requires some\nIco> experience and knowledge to configure and run. I guess they pick up\nIco> where Duc hits its limits :)\n\nAnd they gloss over the performance issues of mysql in a big way! \n\n>> To go beyond the performance of classical scanning tools, robinhood\n>> implements a multi-threaded version of depth-first traversal[4]. To\n>> parallelize the scan, the namespace traversal is split into individual\n>> tasks that consist in reading single directories. A pool of worker\n>> threads performs these tasks following a depth-first strategy (as\n>> illustrated on figure 3).\n\nIco> Parallelization is on my wish list for a long time (second to\nIco> incremental indexing), I'm sure a lot of users will benefit\nIco> greatly from this. On a single spindle and a modern Linux kernel\nIco> multiple threads will not add too much performance, but as soon\nIco> as multiple physical disks are involved doing things in parallel\nIco> will speed up things a lot, especially on Lustre-scale file\nIco> systems.\n\nIco> I have made a proof of concept of a parallel indexing algorithm\nIco> for Duc a few years ago. The implementation was close to your\nIco> description above, but I was not too happy with the increased\nIco> complexity of the resulting code, so it never made it into Duc in\nIco> the end. I will definitely take a look at the internals of\nIco> robinhood to see if I can steal any good ideas!\n\nI did the same with Philesight in ruby, but ran into the big kernel\nlock issue of Ruby threading.  I don't know if they've fixed that in\nnewer versions or not.\n\n>> If the storage could handle parallel requests nicely, that's a huge\n>> win.\n\nIco> I guess that even with no concurrency on the database the speedup\nIco> will still be significant, since the overhead of reading metadata\nIco> from a file system is so much higher then writing out the results\nIco> to the database.\n\nExecpt if you do a crappy mysql setup... In my view, the use case is\nso specialized, that doing a dedicated DB tool makes the most sense.\nUsing a general SQL DB for storage just doesn't scale.  Look at the\ncrap that Bacula goes through.\n\n>> Right now I don't have any metrics to compare the crawling performance\n>> between robinhood and duc, but I'm using robinhood on a petabyte filer\n>> through nfs3 with nearly 1 billion files on it, and the crawling\n>> algorithm performance scales quite linearly up to 8 threads. After\n>> that, I can't tell if the filer or the mysql database that holds the\n>> results is the bottleneck at this moment.\n\nIco> I would be very interested in some numbers that compare Duc to\nIco> Robinhood though on a file system this size; if you ever get some\nIco> numbers on this, please let me know!\n\nI've just compiled robinhood 3.0, but I need to find and setup a mysql\nhost first.  Hopefully I'll get you some numbers in the next day or\nso.\n\nJohn\n"}}
{"actor":{"display_login":"l8gravely"}}