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 83AD770361; Wed, 10 Feb 2021 11:57:41 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 83AD770361 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=tarantool.org; s=dev; t=1612947461; bh=lR2S5Bjk2HSzVZPYyaxvJ1G+APv4HoW7kQZGmLwqnE4=; 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=tgLYg12pRlTcu4GJVRiK5xZOsj/CoK5SeId7285QlyegmGD4nrxhnyc0pU9uspJS3 sJbnHzrpf29zNUX3Tc9CbTn+SRBqhG11p7oPZZ2F5lAexCN4rdRJyeZfr61jcaNo91 H0p5U1MZJ9IjyC/TMyPxmxQuycIjfFWzpgHYcn78= Received: from smtp31.i.mail.ru (smtp31.i.mail.ru [94.100.177.91]) (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 CB8BD70361 for ; Wed, 10 Feb 2021 11:57:40 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org CB8BD70361 Received: by smtp31.i.mail.ru with esmtpa (envelope-from ) id 1l9lJY-0007wX-0v; Wed, 10 Feb 2021 11:57:36 +0300 To: Vladislav Shpilevoy , tarantool-patches@dev.tarantool.org, yaroslav.dynnikov@tarantool.org References: <61b0cc77c94dbaf8d74e04751fd19687f2feb2ae.1612914070.git.v.shpilevoy@tarantool.org> Message-ID: <0032c742-0475-1dc2-a6d8-c77a4f3c2b1c@tarantool.org> Date: Wed, 10 Feb 2021 11:57:35 +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: <61b0cc77c94dbaf8d74e04751fd19687f2feb2ae.1612914070.git.v.shpilevoy@tarantool.org> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Content-Language: en-GB X-7564579A: 646B95376F6C166E X-77F55803: 4F1203BC0FB41BD953AC099BC0052A9CC9F923E808BA4A11AAD7C69F0036037C182A05F5380850407CE5EF45296280E4C74D98247711BE641B0C2B3CA4E0E35A34138EF0F5FCB6C1 X-7FA49CB5: FF5795518A3D127A4AD6D5ED66289B5278DA827A17800CE7195F30236A8D43B4EA1F7E6F0F101C67BD4B6F7A4D31EC0BCC500DACC3FED6E28638F802B75D45FF8AA50765F79006371D26D2A8652661258638F802B75D45FF5571747095F342E8C7A0BC55FA0FE5FC8767A9B625D33EB436F9E1369431802D561FA7D4D3AF50E1389733CBF5DBD5E913377AFFFEAFD269A417C69337E82CC2CC7F00164DA146DAFE8445B8C89999729449624AB7ADAF37F6B57BC7E64490611E7FA7ABCAF51C92176DF2183F8FC7C07E7E81EEA8A9722B8941B15DA834481F9449624AB7ADAF37BA3038C0950A5D3613377AFFFEAFD2691661749BA6B977358A17506121500BB37B076A6E789B0E97A8DF7F3B2552694A1E7802607F20496D49FD398EE364050F599709FD55CB46A645B9AC499A3C791CB3661434B16C20AC78D18283394535A975ECD9A6C639B01BC09775C1D3CA48CF704239268B1C12EC35872C767BF85DA22EF20D2F80756B5F40A5AABA2AD3711975ECD9A6C639B01B78DA827A17800CE70740AD75FEDF3C08731C566533BA786A40A5AABA2AD371193C9F3DD0FB1AF5EB82E77451A5C57BD33C9F3DD0FB1AF5EB4E70A05D1297E1BBCB5012B2E24CD356 X-B7AD71C0: AC4F5C86D027EB782CDD5689AFBDA7A24A6D60772A99906F8E1CD14B953EB46DCE317E522731C0DB355D89D7DBCDD132 X-C1DE0DAB: 0D63561A33F958A54EF9C258AB7CA9B0A2E5ABAF84EE1C5AFF20533E0A82CD39D59269BC5F550898D99A6476B3ADF6B47008B74DF8BB9EF7333BD3B22AA88B938A852937E12ACA75F04B387B5D7535DE410CA545F18667F91A7EA1CDA0B5A7A0 X-C8649E89: 4E36BF7865823D7055A7F0CF078B5EC49A30900B95165D34B8CF715B894FC711EB00388FEBF195A94CE0D27997AE9D61D1520F15921850037749188DA921A5811D7E09C32AA3244CB81765B95168B51F07D55BD24148E85260759606DA2E136AFACE5A9C96DEB163 X-D57D3AED: 3ZO7eAau8CL7WIMRKs4sN3D3tLDjz0dLbV79QFUyzQ2Ujvy7cMT6pYYqY16iZVKkSc3dCLJ7zSJH7+u4VD18S7Vl4ZUrpaVfd2+vE6kuoey4m4VkSEu530nj6fImhcD4MUrOEAnl0W826KZ9Q+tr5ycPtXkTV4k65bRjmOUUP8cvGozZ33TWg5HZplvhhXbhDGzqmQDTd6OAevLeAnq3Ra9uf7zvY2zzsIhlcp/Y7m53TZgf2aB4JOg4gkr2biojmMmQ+JvDeDGBgu4mhJBVww== X-Mailru-Sender: E02534FE7B43636DC6DBEBE964139794924158ACA85AC0E16200572E3E374700E96921E22FC340C223E75C7104EB1B885DEE61814008E47C7013064206BFB89F93956FB04BA385BE9437F6177E88F7363CDA0F3B3F5B9367 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" 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