Tarantool development patches archive
 help / color / mirror / Atom feed
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: Thu, 11 Feb 2021 09:50:01 +0300
Message-ID: <8528606a-2753-171c-3556-484c8aba3809@tarantool.org> (raw)
In-Reply-To: <0032c742-0475-1dc2-a6d8-c77a4f3c2b1c@tarantool.org>

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

  reply	other threads:[~2021-02-11  6:50 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
2021-02-11  6:50     ` Oleg Babin via Tarantool-patches [this message]
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=8528606a-2753-171c-3556-484c8aba3809@tarantool.org \
    --to=tarantool-patches@dev.tarantool.org \
    --cc=olegrok@tarantool.org \
    --cc=v.shpilevoy@tarantool.org \
    --cc=yaroslav.dynnikov@tarantool.org \
    /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

Tarantool development patches archive

This inbox may be cloned and mirrored by anyone:

	git clone --mirror https://lists.tarantool.org/tarantool-patches/0 tarantool-patches/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 tarantool-patches tarantool-patches/ https://lists.tarantool.org/tarantool-patches \
		tarantool-patches@dev.tarantool.org.
	public-inbox-index tarantool-patches

Example config snippet for mirrors.


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git