[Tarantool-patches] [PATCH 1/9] rlist: move rlist to a new module
Oleg Babin
olegrok at tarantool.org
Thu Feb 11 09:50:01 MSK 2021
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
More information about the Tarantool-patches
mailing list