{"push_id":1285816825,"size":2,"distinct_size":2,"ref":"refs/heads/master","head":"c4e3ff67b14954f00570b65861fc9bdbd61e7999","before":"352605dbb1ddd9fe63a106ab0047089b579705df","commits":[{"sha":"2f12d83a8bcdf7015ba50bc02917e215837f3c9a","author":{"name":"Todd Lipcon","email":"dd5965a1ccaca30b2dd5053f256a6d9b88ca567f@apache.org"},"message":"compaction_policy: fix bound calculation\n\nThe upper-bound calculator for the knapsack problem maintains a heap\nwhich is supposed to keep no more than one item beyond the maximum\nweight allowed.\n\nThis invariant got broken in some cases when an item was added to the\nheap -- in some cases a single addition actually requires removing\nmultiple old items.\n\nA regression test for this fix is included in the following commit\n(\"Optimize budgeted compaction policy with an approximation\")\n\nChange-Id: I76364c17debd7293b36884d64c7747f8c604ae12\nReviewed-on: http://gerrit.cloudera.org:8080/4152\nReviewed-by: David Ribeiro Alves <dralves@apache.org>\nTested-by: Kudu Jenkins","distinct":true,"url":"https://api.github.com/repos/cloudera/kudu/commits/2f12d83a8bcdf7015ba50bc02917e215837f3c9a"},{"sha":"c4e3ff67b14954f00570b65861fc9bdbd61e7999","author":{"name":"Todd Lipcon","email":"dd5965a1ccaca30b2dd5053f256a6d9b88ca567f@apache.org"},"message":"KUDU-1582. Optimize budgeted compaction policy with an approximation\n\nOn a server with ~5.5TB of data, I noticed that the maintenance manager\nwas spending tens of seconds computing optimal compactions, and most of\nthe time was in knapsack solving.\n\nThis patch implements a \"first pass\" solution to the compaction policy\nusing an approximation algorithm that is significantly faster than the\nactual knapsack solver. The approximation algorithm gives a lower bound\nsolution which is at least 50% as good as the optimal solution (i.e. it\nis a '2-approximation'). In practice, it is often optimal or nearly\noptimal.\n\nTo test, I dumped the bounds and sizes of rowsets from a 200+GB YCSB\ntablet from a real cluster that has been inserting for a few days, and\nwrote a test which imported that layout back in as mock rowsets in order\nto run the policy.\n\nThe result (with the default 5% max approximation error) is between a 6x\nand 20x speedup (depending on the budget size). The resulting loss in\nsolution quality is less than 1%.\n\nBefore:\n  Time spent Computing compaction with 128MB budget: real 0.965s        user 0.964s     sys 0.000s\n   quality=0.118006\n  Time spent Computing compaction with 256MB budget: real 1.202s        user 1.204s     sys 0.000s\n   quality=0.254289\n  Time spent Computing compaction with 512MB budget: real 2.233s        user 2.232s     sys 0.000s\n   quality=0.524391\n  Time spent Computing compaction with 1024MB budget: real 4.202s       user 4.200s     sys 0.000s\n   quality=1.06674\n\nAfter:\n  Time spent Computing compaction with 128MB budget: real 0.148s        user 0.148s     sys 0.000s\n   quality=0.117985\n  Time spent Computing compaction with 256MB budget: real 0.162s        user 0.160s     sys 0.000s\n   quality=0.252118\n  Time spent Computing compaction with 512MB budget: real 0.174s        user 0.176s     sys 0.000s\n   quality=0.524391\n  Time spent Computing compaction with 1024MB budget: real 0.206s       user 0.208s     sys 0.000s\n   quality=1.06674\n\nChange-Id: I4e611f161d66ddc47e97e3b5328bc1778a4ac958\nReviewed-on: http://gerrit.cloudera.org:8080/4153\nReviewed-by: David Ribeiro Alves <dralves@apache.org>\nTested-by: Kudu Jenkins","distinct":true,"url":"https://api.github.com/repos/cloudera/kudu/commits/c4e3ff67b14954f00570b65861fc9bdbd61e7999"}]}
{"actor":{"display_login":"cloudera-gerrit"}}