Tarantool development patches archive
 help / color / mirror / Atom feed
From: Vladislav Shpilevoy via Tarantool-patches <tarantool-patches@dev.tarantool.org>
To: tarantool-patches@dev.tarantool.org, olegrok@tarantool.org,
	yaroslav.dynnikov@tarantool.org
Subject: [Tarantool-patches] [PATCH 1/9] rlist: move rlist to a new module
Date: Wed, 10 Feb 2021 00:46:07 +0100
Message-ID: <61b0cc77c94dbaf8d74e04751fd19687f2feb2ae.1612914070.git.v.shpilevoy@tarantool.org> (raw)
In-Reply-To: <cover.1612914070.git.v.shpilevoy@tarantool.org>

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)


  reply	other threads:[~2021-02-09 23:46 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 ` Vladislav Shpilevoy via Tarantool-patches [this message]
2021-02-10  8:57   ` [Tarantool-patches] [PATCH 1/9] rlist: move rlist to a new module Oleg Babin via Tarantool-patches
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=61b0cc77c94dbaf8d74e04751fd19687f2feb2ae.1612914070.git.v.shpilevoy@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