From: Oleg Babin via Tarantool-patches <tarantool-patches@dev.tarantool.org>
To: Vladislav Shpilevoy <v.shpilevoy@tarantool.org>,
tarantool-patches@dev.tarantool.org,
yaroslav.dynnikov@tarantool.org
Subject: Re: [Tarantool-patches] [PATCH 1/9] rlist: move rlist to a new module
Date: Wed, 10 Feb 2021 11:57:35 +0300 [thread overview]
Message-ID: <0032c742-0475-1dc2-a6d8-c77a4f3c2b1c@tarantool.org> (raw)
In-Reply-To: <61b0cc77c94dbaf8d74e04751fd19687f2feb2ae.1612914070.git.v.shpilevoy@tarantool.org>
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
next prev parent reply other threads:[~2021-02-10 8:57 UTC|newest]
Thread overview: 36+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-02-09 23:46 [Tarantool-patches] [PATCH 0/9] VShard Map-Reduce, part 1, preparations Vladislav Shpilevoy via Tarantool-patches
2021-02-09 23:46 ` [Tarantool-patches] [PATCH 1/9] rlist: move rlist to a new module Vladislav Shpilevoy via Tarantool-patches
2021-02-10 8:57 ` Oleg Babin via Tarantool-patches [this message]
2021-02-11 6:50 ` Oleg Babin via Tarantool-patches
2021-02-12 0:09 ` Vladislav Shpilevoy via Tarantool-patches
2021-02-09 23:46 ` [Tarantool-patches] [PATCH 2/9] Use fiber.clock() instead of .time() everywhere Vladislav Shpilevoy via Tarantool-patches
2021-02-10 8:57 ` Oleg Babin via Tarantool-patches
2021-02-10 22:33 ` Vladislav Shpilevoy via Tarantool-patches
2021-02-09 23:46 ` [Tarantool-patches] [PATCH 3/9] test: introduce a helper to wait for bucket GC Vladislav Shpilevoy via Tarantool-patches
2021-02-10 8:57 ` Oleg Babin via Tarantool-patches
2021-02-10 22:33 ` Vladislav Shpilevoy via Tarantool-patches
2021-02-11 6:50 ` Oleg Babin via Tarantool-patches
2021-02-09 23:46 ` [Tarantool-patches] [PATCH 4/9] storage: bucket_recv() should check rs lock Vladislav Shpilevoy via Tarantool-patches
2021-02-10 8:59 ` Oleg Babin via Tarantool-patches
2021-02-09 23:46 ` [Tarantool-patches] [PATCH 5/9] util: introduce yielding table functions Vladislav Shpilevoy via Tarantool-patches
2021-02-10 8:59 ` Oleg Babin via Tarantool-patches
2021-02-10 22:34 ` Vladislav Shpilevoy via Tarantool-patches
2021-02-11 6:50 ` Oleg Babin via Tarantool-patches
2021-02-09 23:46 ` [Tarantool-patches] [PATCH 6/9] cfg: introduce 'deprecated option' feature Vladislav Shpilevoy via Tarantool-patches
2021-02-10 8:59 ` Oleg Babin via Tarantool-patches
2021-02-10 22:34 ` Vladislav Shpilevoy via Tarantool-patches
2021-02-11 6:50 ` Oleg Babin via Tarantool-patches
2021-02-09 23:46 ` [Tarantool-patches] [PATCH 7/9] gc: introduce reactive garbage collector Vladislav Shpilevoy via Tarantool-patches
2021-02-10 9:00 ` Oleg Babin via Tarantool-patches
2021-02-10 22:35 ` Vladislav Shpilevoy via Tarantool-patches
2021-02-11 6:50 ` Oleg Babin via Tarantool-patches
2021-02-09 23:46 ` [Tarantool-patches] [PATCH 8/9] recovery: introduce reactive recovery Vladislav Shpilevoy via Tarantool-patches
2021-02-10 9:00 ` Oleg Babin via Tarantool-patches
2021-02-09 23:46 ` [Tarantool-patches] [PATCH 9/9] util: introduce binary heap data structure Vladislav Shpilevoy via Tarantool-patches
2021-02-10 9:01 ` Oleg Babin via Tarantool-patches
2021-02-10 22:36 ` Vladislav Shpilevoy via Tarantool-patches
2021-02-11 6:51 ` Oleg Babin via Tarantool-patches
2021-02-12 0:09 ` Vladislav Shpilevoy via Tarantool-patches
2021-03-05 22:03 ` Vladislav Shpilevoy via Tarantool-patches
2021-02-09 23:51 ` [Tarantool-patches] [PATCH 0/9] VShard Map-Reduce, part 1, preparations Vladislav Shpilevoy via Tarantool-patches
2021-02-12 11:02 ` Oleg Babin via Tarantool-patches
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=0032c742-0475-1dc2-a6d8-c77a4f3c2b1c@tarantool.org \
--to=tarantool-patches@dev.tarantool.org \
--cc=olegrok@tarantool.org \
--cc=v.shpilevoy@tarantool.org \
--cc=yaroslav.dynnikov@tarantool.org \
--subject='Re: [Tarantool-patches] [PATCH 1/9] rlist: move rlist to a new module' \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox