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 E28736AABA; Wed, 10 Feb 2021 02:46:47 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org E28736AABA DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=tarantool.org; s=dev; t=1612914407; bh=CyiBpC3vbMm9ouDkWHMFa106C2y/qIKClAHSrnMYec0=; h=To:Date:In-Reply-To:References:Subject:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=oOhx4ALYV2I59H9MENa1VHVXPWiunzjSk4g9aTL1sXqDURLAwnLS0C3mUIo1BSUI4 INraOrp32fFgGNUUSr5c3QsWSm9MlVrqlHpf94KoRgTnlOTa2paTrvZIHKtX6i0giT R+rMPLZqdbopPBQ0bnx4rMGK+1ynM6yOP9Siu0C4= Received: from smtpng3.m.smailru.net (smtpng3.m.smailru.net [94.100.177.149]) (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 5FD196AABA for ; Wed, 10 Feb 2021 02:46:21 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 5FD196AABA Received: by smtpng3.m.smailru.net with esmtpa (envelope-from ) id 1l9ci1-0002gH-0U; Wed, 10 Feb 2021 02:46:17 +0300 To: tarantool-patches@dev.tarantool.org, olegrok@tarantool.org, yaroslav.dynnikov@tarantool.org Date: Wed, 10 Feb 2021 00:46:07 +0100 Message-Id: <61b0cc77c94dbaf8d74e04751fd19687f2feb2ae.1612914070.git.v.shpilevoy@tarantool.org> X-Mailer: git-send-email 2.24.3 (Apple Git-128) In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-7564579A: 646B95376F6C166E X-77F55803: 4F1203BC0FB41BD953AC099BC0052A9C4647521586BE7E6324520D2A088600D8182A05F538085040DE6B917F94554141E11D7E5EE58D3C3E59A7AD26FCEBEDFD3C7CC8F3DC52B8DB X-7FA49CB5: FF5795518A3D127A4AD6D5ED66289B5278DA827A17800CE7952C4D7BD0BF3359EA1F7E6F0F101C67BD4B6F7A4D31EC0BCC500DACC3FED6E28638F802B75D45FF8AA50765F7900637EEA194BB48C104EF8638F802B75D45FF5571747095F342E8C7A0BC55FA0FE5FCA6073DB25481D6C50507567822F742B93DF00A63A4214BB7389733CBF5DBD5E913377AFFFEAFD269A417C69337E82CC2CC7F00164DA146DAFE8445B8C89999729449624AB7ADAF37F6B57BC7E64490611E7FA7ABCAF51C92176DF2183F8FC7C0A29E2F051442AF778941B15DA834481F9449624AB7ADAF3735872C767BF85DA29E625A9149C048EE0A3850AC1BE2E73525A4AB119743A3B34AD6D5ED66289B524E70A05D1297E1BB35872C767BF85DA227C277FBC8AE2E8BEBEE3B39F980227375ECD9A6C639B01B4E70A05D1297E1BBC6867C52282FAC85D9B7C4F32B44FF57E8FBB06288C1946000306258E7E6ABB4E4A6367B16DE6309 X-C1DE0DAB: C20DE7B7AB408E4181F030C43753B8186998911F362727C414F749A5E30D975CFE63F531D4BE5B71C962B2892E07DBECFA54DF3EDA4D29A19C2B6934AE262D3EE7EAB7254005DCED114C52B35DBB74F4E7EAB7254005DCEDEC0BC6DB5D5D7B8B1E0A4E2319210D9B64D260DF9561598F01A9E91200F654B047F3662BFF48AA648E8E86DC7131B365E7726E8460B7C23C X-C8649E89: 4E36BF7865823D7055A7F0CF078B5EC49A30900B95165D34B9F55CA4D2956E305C744AFE53E61BA73C30251679BCD238DBA749E5E8BB6E79A054969088AA4E0B1D7E09C32AA3244CF37A1CF4C46095E855A556C18694DCD5408A6A02710B7304FACE5A9C96DEB163 X-D57D3AED: 3ZO7eAau8CL7WIMRKs4sN3D3tLDjz0dLbV79QFUyzQ2Ujvy7cMT6pYYqY16iZVKkSc3dCLJ7zSJH7+u4VD18S7Vl4ZUrpaVfd2+vE6kuoey4m4VkSEu530nj6fImhcD4MUrOEAnl0W826KZ9Q+tr5ycPtXkTV4k65bRjmOUUP8cvGozZ33TWg5HZplvhhXbhDGzqmQDTd6OAevLeAnq3Ra9uf7zvY2zzsIhlcp/Y7m53TZgf2aB4JOg4gkr2biojmMmQ+JvDeDGBX4aqJLr7tw== X-Mailru-Sender: 689FA8AB762F73936BC43F508A063822C8A5BEE0F6EF22B7D947110BD8F777413841015FED1DE5223CC9A89AB576DD93FB559BB5D741EB963CF37A108A312F5C27E8A8C3839CE0E267EA787935ED9F1B X-Mras: Ok Subject: [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: Vladislav Shpilevoy via Tarantool-patches Reply-To: Vladislav Shpilevoy Errors-To: tarantool-patches-bounces@dev.tarantool.org Sender: "Tarantool-patches" 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 -- 2.24.3 (Apple Git-128)