From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from [87.239.111.99] (localhost [127.0.0.1]) by dev.tarantool.org (Postfix) with ESMTP id 40E2D6C7D2; Thu, 11 Feb 2021 09:50:07 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 40E2D6C7D2 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=tarantool.org; s=dev; t=1613026207; bh=MSOrZ/Mw8miThPBfBUU7MmRP+wnQ+sd7jS2JiIHMjGc=; h=To:References:Date:In-Reply-To:Subject:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=Cq8srzkFMjavceTYUqzaKmJsP/cQ9aHRwxCXLjAiVVtAzf1b4y5zmdfjjIYpXzz5R mY0gKjDuxcRfoMgb6pSsfRXg4uoAPoUniwBFWQhgditKmQcgEqLBtFJJ8p3b4LmrZ+ jOTO8/NSfm+vDg+Arjm+Uad26e8THGAb5vkoA8AE= Received: from smtp61.i.mail.ru (smtp61.i.mail.ru [217.69.128.41]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id 8EC136C7D2 for ; Thu, 11 Feb 2021 09:50:06 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 8EC136C7D2 Received: by smtp61.i.mail.ru with esmtpa (envelope-from ) id 1lA5nd-0000DO-OK; Thu, 11 Feb 2021 09:50:02 +0300 To: Vladislav Shpilevoy , tarantool-patches@dev.tarantool.org, yaroslav.dynnikov@tarantool.org References: <61b0cc77c94dbaf8d74e04751fd19687f2feb2ae.1612914070.git.v.shpilevoy@tarantool.org> <0032c742-0475-1dc2-a6d8-c77a4f3c2b1c@tarantool.org> Message-ID: <8528606a-2753-171c-3556-484c8aba3809@tarantool.org> Date: Thu, 11 Feb 2021 09:50:01 +0300 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:78.0) Gecko/20100101 Thunderbird/78.7.0 MIME-Version: 1.0 In-Reply-To: <0032c742-0475-1dc2-a6d8-c77a4f3c2b1c@tarantool.org> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-Language: en-GB X-7564579A: 646B95376F6C166E X-77F55803: 4F1203BC0FB41BD953AC099BC0052A9CAEF2BF42A2A7729330F8028A4C0D8125182A05F538085040558C60129C4EBAEC07E0BBCF14CADBEDF3613B0D274F89E61C20D0818D2AC8F5 X-7FA49CB5: FF5795518A3D127A4AD6D5ED66289B5278DA827A17800CE7180ADF26E81B0C77EA1F7E6F0F101C67BD4B6F7A4D31EC0BCC500DACC3FED6E28638F802B75D45FF8AA50765F7900637ED2BA022FBF94AB68638F802B75D45FF5571747095F342E8C7A0BC55FA0FE5FC7BF04B2A11D85FC6BFFD5C178B69A4FAFDEF0E45404D3378389733CBF5DBD5E913377AFFFEAFD269A417C69337E82CC2CC7F00164DA146DAFE8445B8C89999729449624AB7ADAF37F6B57BC7E64490611E7FA7ABCAF51C92176DF2183F8FC7C07E7E81EEA8A9722B8941B15DA834481F9449624AB7ADAF37BA3038C0950A5D3613377AFFFEAFD2691661749BA6B9773579BFA6CF9373C92F7B076A6E789B0E97A8DF7F3B2552694A1E7802607F20496D49FD398EE364050FC24E1E72F37C03A0287C8E22D4AE2A51B3661434B16C20AC78D18283394535A975ECD9A6C639B01BC09775C1D3CA48CF1BC22E60DA9664CB089D37D7C0E48F6CCF19DD082D7633A0E7DDDDC251EA7DABAAAE862A0553A39223F8577A6DFFEA7C4BA12F1FBF68C58B43847C11F186F3C5E7DDDDC251EA7DABCC89B49CDF41148FA8EF81845B15A4842623479134186CDE6BA297DBC24807EABDAD6C7F3747799A X-B7AD71C0: 14C14B24D00AF5AC321EF223B8115265C69B993890792DF82CDD5689AFBDA7A24A6D60772A99906F8E1CD14B953EB46DCFD04DB074F676EE355D89D7DBCDD132 X-C1DE0DAB: 0D63561A33F958A5162BF954F142CF30823F2EBDE5DCE6855B51422A74296338D59269BC5F550898D99A6476B3ADF6B47008B74DF8BB9EF7333BD3B22AA88B938A852937E12ACA75448CF9D3A7B2C848410CA545F18667F91A7EA1CDA0B5A7A0 X-C8649E89: 4E36BF7865823D7055A7F0CF078B5EC49A30900B95165D343C45ADCD169245FACDCC186DBD92D9C94847E6431CBD8C42344BCEB6E0337DC6CFAE24CC4F27B0BE1D7E09C32AA3244C05869FF5E0EAD8E5A10F7AA8D5CF708555E75C8D0ED9F6EEFACE5A9C96DEB163 X-D57D3AED: 3ZO7eAau8CL7WIMRKs4sN3D3tLDjz0dLbV79QFUyzQ2Ujvy7cMT6pYYqY16iZVKkSc3dCLJ7zSJH7+u4VD18S7Vl4ZUrpaVfd2+vE6kuoey4m4VkSEu530nj6fImhcD4MUrOEAnl0W826KZ9Q+tr5ycPtXkTV4k65bRjmOUUP8cvGozZ33TWg5HZplvhhXbhDGzqmQDTd6OAevLeAnq3Ra9uf7zvY2zzsIhlcp/Y7m53TZgf2aB4JOg4gkr2biojmjFTaBTEi1bfsa2YWREeyg== X-Mailru-Sender: 583F1D7ACE8F49BD9317CE1922F30C7E467A6D86E1E1EE3C2260E72747A92CD23CC7438F9FAE1BC723E75C7104EB1B885DEE61814008E47C7013064206BFB89F93956FB04BA385BE9437F6177E88F7363CDA0F3B3F5B9367 X-Mras: Ok Subject: Re: [Tarantool-patches] [PATCH 1/9] rlist: move rlist to a new module X-BeenThere: tarantool-patches@dev.tarantool.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , From: Oleg Babin via Tarantool-patches Reply-To: Oleg Babin Errors-To: tarantool-patches-bounces@dev.tarantool.org Sender: "Tarantool-patches" I've noticed that you've missed to add new file to vshard/CMakeList.txt [1] It will break the build. [1] https://github.com/tarantool/vshard/blob/master/vshard/CMakeLists.txt#L9 On 10/02/2021 11:57, Oleg Babin via Tarantool-patches wrote: > Hi! Thanks for your patch. LGTM. > > On 10/02/2021 02:46, Vladislav Shpilevoy wrote: >> Rlist in storage/init.lua implemented a container similar to rlist >> in libsmall in Tarantool core. Doubly-linked list. >> >> It does not depend on anything in storage/init.lua, and should >> have been done in a separate module from the beginning. >> >> Now init.lua is going to grow even more in scope of map-reduce >> feature, beyond 3k lines if nothing would be moved out. It was >> decided (by me) that it crosses the border of when it is time to >> split init.lua into separate modules. >> >> The patch takes the low hanging fruit by moving rlist into its >> own module. >> --- >>   test/unit/rebalancer.result   |  99 ----------------------------- >>   test/unit/rebalancer.test.lua |  27 -------- >>   test/unit/rlist.result        | 114 ++++++++++++++++++++++++++++++++++ >>   test/unit/rlist.test.lua      |  33 ++++++++++ >>   vshard/rlist.lua              |  53 ++++++++++++++++ >>   vshard/storage/init.lua       |  68 +++----------------- >>   6 files changed, 208 insertions(+), 186 deletions(-) >>   create mode 100644 test/unit/rlist.result >>   create mode 100644 test/unit/rlist.test.lua >>   create mode 100644 vshard/rlist.lua >> >> diff --git a/test/unit/rebalancer.result b/test/unit/rebalancer.result >> index 2fb30e2..19aa480 100644 >> --- a/test/unit/rebalancer.result >> +++ b/test/unit/rebalancer.result >> @@ -1008,105 +1008,6 @@ build_routes(replicasets) >>   -- the latter is a dispenser. It is a structure which hands out >>   -- destination UUIDs in a round-robin manner to worker fibers. >>   -- >> -list = rlist.new() >> ---- >> -... >> -list >> ---- >> -- count: 0 >> -... >> -obj1 = {i = 1} >> ---- >> -... >> -rlist.remove(list, obj1) >> ---- >> -... >> -list >> ---- >> -- count: 0 >> -... >> -rlist.add_tail(list, obj1) >> ---- >> -... >> -list >> ---- >> -- count: 1 >> -  last: &0 >> -    i: 1 >> -  first: *0 >> -... >> -rlist.remove(list, obj1) >> ---- >> -... >> -list >> ---- >> -- count: 0 >> -... >> -obj1 >> ---- >> -- i: 1 >> -... >> -rlist.add_tail(list, obj1) >> ---- >> -... >> -obj2 = {i = 2} >> ---- >> -... >> -rlist.add_tail(list, obj2) >> ---- >> -... >> -list >> ---- >> -- count: 2 >> -  last: &0 >> -    i: 2 >> -    prev: &1 >> -      i: 1 >> -      next: *0 >> -  first: *1 >> -... >> -obj3 = {i = 3} >> ---- >> -... >> -rlist.add_tail(list, obj3) >> ---- >> -... >> -list >> ---- >> -- count: 3 >> -  last: &0 >> -    i: 3 >> -    prev: &1 >> -      i: 2 >> -      next: *0 >> -      prev: &2 >> -        i: 1 >> -        next: *1 >> -  first: *2 >> -... >> -rlist.remove(list, obj2) >> ---- >> -... >> -list >> ---- >> -- count: 2 >> -  last: &0 >> -    i: 3 >> -    prev: &1 >> -      i: 1 >> -      next: *0 >> -  first: *1 >> -... >> -rlist.remove(list, obj1) >> ---- >> -... >> -list >> ---- >> -- count: 1 >> -  last: &0 >> -    i: 3 >> -  first: *0 >> -... >>   d = dispenser.create({uuid = 15}) >>   --- >>   ... >> diff --git a/test/unit/rebalancer.test.lua >> b/test/unit/rebalancer.test.lua >> index a4e18c1..8087d42 100644 >> --- a/test/unit/rebalancer.test.lua >> +++ b/test/unit/rebalancer.test.lua >> @@ -246,33 +246,6 @@ build_routes(replicasets) >>   -- the latter is a dispenser. It is a structure which hands out >>   -- destination UUIDs in a round-robin manner to worker fibers. >>   -- >> -list = rlist.new() >> -list >> - >> -obj1 = {i = 1} >> -rlist.remove(list, obj1) >> -list >> - >> -rlist.add_tail(list, obj1) >> -list >> - >> -rlist.remove(list, obj1) >> -list >> -obj1 >> - >> -rlist.add_tail(list, obj1) >> -obj2 = {i = 2} >> -rlist.add_tail(list, obj2) >> -list >> -obj3 = {i = 3} >> -rlist.add_tail(list, obj3) >> -list >> - >> -rlist.remove(list, obj2) >> -list >> -rlist.remove(list, obj1) >> -list >> - >>   d = dispenser.create({uuid = 15}) >>   dispenser.pop(d) >>   for i = 1, 14 do assert(dispenser.pop(d) == 'uuid', i) end >> diff --git a/test/unit/rlist.result b/test/unit/rlist.result >> new file mode 100644 >> index 0000000..c8aabc0 >> --- /dev/null >> +++ b/test/unit/rlist.result >> @@ -0,0 +1,114 @@ >> +-- test-run result file version 2 >> +-- >> +-- gh-161: parallel rebalancer. One of the most important part of >> the latter is >> +-- a dispenser. It is a structure which hands out destination UUIDs >> in a >> +-- round-robin manner to worker fibers. It uses rlist data structure. >> +-- >> +rlist = require('vshard.rlist') >> + | --- >> + | ... >> + >> +list = rlist.new() >> + | --- >> + | ... >> +list >> + | --- >> + | - count: 0 >> + | ... >> + >> +obj1 = {i = 1} >> + | --- >> + | ... >> +list:remove(obj1) >> + | --- >> + | ... >> +list >> + | --- >> + | - count: 0 >> + | ... >> + >> +list:add_tail(obj1) >> + | --- >> + | ... >> +list >> + | --- >> + | - count: 1 >> + |   last: &0 >> + |     i: 1 >> + |   first: *0 >> + | ... >> + >> +list:remove(obj1) >> + | --- >> + | ... >> +list >> + | --- >> + | - count: 0 >> + | ... >> +obj1 >> + | --- >> + | - i: 1 >> + | ... >> + >> +list:add_tail(obj1) >> + | --- >> + | ... >> +obj2 = {i = 2} >> + | --- >> + | ... >> +list:add_tail(obj2) >> + | --- >> + | ... >> +list >> + | --- >> + | - count: 2 >> + |   last: &0 >> + |     i: 2 >> + |     prev: &1 >> + |       i: 1 >> + |       next: *0 >> + |   first: *1 >> + | ... >> +obj3 = {i = 3} >> + | --- >> + | ... >> +list:add_tail(obj3) >> + | --- >> + | ... >> +list >> + | --- >> + | - count: 3 >> + |   last: &0 >> + |     i: 3 >> + |     prev: &1 >> + |       i: 2 >> + |       next: *0 >> + |       prev: &2 >> + |         i: 1 >> + |         next: *1 >> + |   first: *2 >> + | ... >> + >> +list:remove(obj2) >> + | --- >> + | ... >> +list >> + | --- >> + | - count: 2 >> + |   last: &0 >> + |     i: 3 >> + |     prev: &1 >> + |       i: 1 >> + |       next: *0 >> + |   first: *1 >> + | ... >> +list:remove(obj1) >> + | --- >> + | ... >> +list >> + | --- >> + | - count: 1 >> + |   last: &0 >> + |     i: 3 >> + |   first: *0 >> + | ... >> diff --git a/test/unit/rlist.test.lua b/test/unit/rlist.test.lua >> new file mode 100644 >> index 0000000..db52955 >> --- /dev/null >> +++ b/test/unit/rlist.test.lua >> @@ -0,0 +1,33 @@ >> +-- >> +-- gh-161: parallel rebalancer. One of the most important part of >> the latter is >> +-- a dispenser. It is a structure which hands out destination UUIDs >> in a >> +-- round-robin manner to worker fibers. It uses rlist data structure. >> +-- >> +rlist = require('vshard.rlist') >> + >> +list = rlist.new() >> +list >> + >> +obj1 = {i = 1} >> +list:remove(obj1) >> +list >> + >> +list:add_tail(obj1) >> +list >> + >> +list:remove(obj1) >> +list >> +obj1 >> + >> +list:add_tail(obj1) >> +obj2 = {i = 2} >> +list:add_tail(obj2) >> +list >> +obj3 = {i = 3} >> +list:add_tail(obj3) >> +list >> + >> +list:remove(obj2) >> +list >> +list:remove(obj1) >> +list >> diff --git a/vshard/rlist.lua b/vshard/rlist.lua >> new file mode 100644 >> index 0000000..4be5382 >> --- /dev/null >> +++ b/vshard/rlist.lua >> @@ -0,0 +1,53 @@ >> +-- >> +-- A subset of rlist methods from the main repository. Rlist is a >> +-- doubly linked list, and is used here to implement a queue of >> +-- routes in the parallel rebalancer. >> +-- >> +local rlist_mt = {} >> + >> +function rlist_mt.add_tail(rlist, object) >> +    local last = rlist.last >> +    if last then >> +        last.next = object >> +        object.prev = last >> +    else >> +        rlist.first = object >> +    end >> +    rlist.last = object >> +    rlist.count = rlist.count + 1 >> +end >> + >> +function rlist_mt.remove(rlist, object) >> +    local prev = object.prev >> +    local next = object.next >> +    local belongs_to_list = false >> +    if prev then >> +        belongs_to_list = true >> +        prev.next = next >> +    end >> +    if next then >> +        belongs_to_list = true >> +        next.prev = prev >> +    end >> +    object.prev = nil >> +    object.next = nil >> +    if rlist.last == object then >> +        belongs_to_list = true >> +        rlist.last = prev >> +    end >> +    if rlist.first == object then >> +        belongs_to_list = true >> +        rlist.first = next >> +    end >> +    if belongs_to_list then >> +        rlist.count = rlist.count - 1 >> +    end >> +end >> + >> +local function rlist_new() >> +    return setmetatable({count = 0}, {__index = rlist_mt}) >> +end >> + >> +return { >> +    new = rlist_new, >> +} >> diff --git a/vshard/storage/init.lua b/vshard/storage/init.lua >> index 5464824..1b48bf1 100644 >> --- a/vshard/storage/init.lua >> +++ b/vshard/storage/init.lua >> @@ -13,12 +13,13 @@ if rawget(_G, MODULE_INTERNALS) then >>           'vshard.consts', 'vshard.error', 'vshard.cfg', >>           'vshard.replicaset', 'vshard.util', >>           'vshard.storage.reload_evolution', >> -        'vshard.lua_gc', >> +        'vshard.lua_gc', 'vshard.rlist' >>       } >>       for _, module in pairs(vshard_modules) do >>           package.loaded[module] = nil >>       end >>   end >> +local rlist = require('vshard.rlist') >>   local consts = require('vshard.consts') >>   local lerror = require('vshard.error') >>   local lcfg = require('vshard.cfg') >> @@ -1786,54 +1787,6 @@ local function >> rebalancer_build_routes(replicasets) >>       return bucket_routes >>   end >>   --- >> --- A subset of rlist methods from the main repository. Rlist is a >> --- doubly linked list, and is used here to implement a queue of >> --- routes in the parallel rebalancer. >> --- >> -local function rlist_new() >> -    return {count = 0} >> -end >> - >> -local function rlist_add_tail(rlist, object) >> -    local last = rlist.last >> -    if last then >> -        last.next = object >> -        object.prev = last >> -    else >> -        rlist.first = object >> -    end >> -    rlist.last = object >> -    rlist.count = rlist.count + 1 >> -end >> - >> -local function rlist_remove(rlist, object) >> -    local prev = object.prev >> -    local next = object.next >> -    local belongs_to_list = false >> -    if prev then >> -        belongs_to_list = true >> -        prev.next = next >> -    end >> -    if next then >> -        belongs_to_list = true >> -        next.prev = prev >> -    end >> -    object.prev = nil >> -    object.next = nil >> -    if rlist.last == object then >> -        belongs_to_list = true >> -        rlist.last = prev >> -    end >> -    if rlist.first == object then >> -        belongs_to_list = true >> -        rlist.first = next >> -    end >> -    if belongs_to_list then >> -        rlist.count = rlist.count - 1 >> -    end >> -end >> - >>   -- >>   -- Dispenser is a container of routes received from the >>   -- rebalancer. Its task is to hand out the routes to worker fibers >> @@ -1842,7 +1795,7 @@ end >>   -- receiver nodes. >>   -- >>   local function route_dispenser_create(routes) >> -    local rlist = rlist_new() >> +    local rlist = rlist.new() >>       local map = {} >>       for uuid, bucket_count in pairs(routes) do >>           local new = { >> @@ -1873,7 +1826,7 @@ local function route_dispenser_create(routes) >>           --    the main applier fiber does some analysis on the >>           --    destinations. >>           map[uuid] = new >> -        rlist_add_tail(rlist, new) >> +        rlist:add_tail(new) >>       end >>       return { >>           rlist = rlist, >> @@ -1892,7 +1845,7 @@ local function route_dispenser_put(dispenser, >> uuid) >>           local bucket_count = dst.bucket_count + 1 >>           dst.bucket_count = bucket_count >>           if bucket_count == 1 then >> -            rlist_add_tail(dispenser.rlist, dst) >> +            dispenser.rlist:add_tail(dst) >>           end >>       end >>   end >> @@ -1909,7 +1862,7 @@ local function route_dispenser_skip(dispenser, >> uuid) >>       local dst = map[uuid] >>       if dst then >>           map[uuid] = nil >> -        rlist_remove(dispenser.rlist, dst) >> +        dispenser.rlist:remove(dst) >>       end >>   end >>   @@ -1952,9 +1905,9 @@ local function route_dispenser_pop(dispenser) >>       if dst then >>           local bucket_count = dst.bucket_count - 1 >>           dst.bucket_count = bucket_count >> -        rlist_remove(rlist, dst) >> +        rlist:remove(dst) >>           if bucket_count > 0 then >> -            rlist_add_tail(rlist, dst) >> +            rlist:add_tail(dst) >>           end >>           return dst.uuid >>       end >> @@ -2742,11 +2695,6 @@ M.route_dispenser = { >>       pop = route_dispenser_pop, >>       sent = route_dispenser_sent, >>   } >> -M.rlist = { >> -    new = rlist_new, >> -    add_tail = rlist_add_tail, >> -    remove = rlist_remove, >> -} >>   M.schema_latest_version = schema_latest_version >>   M.schema_current_version = schema_current_version >>   M.schema_upgrade_master = schema_upgrade_master