“Playing With Redis” series articles by Zxiaofan mainly tells the basic and advanced applications of Redis, interlaced with actual cases of enterprises. This is the first article in the Redis series [16]. Please visit the public account “Zxiaofan” or search for “Redis zxiaofan” on Baidu.

Key words: Redis, Lua script entry to actual combat, debugging Lua script, tree structure, tree structure of the storage scheme, “adjacency list”, “path enumeration”, find all superior departments of the department;

Past picks: “Play Redis- Kill nail Owners – Keys with no expiration Date set”

The outline

  • Common scenarios and solutions of tree structure
    • Common scenarios for tree structures
    • Tree solutions: “adjacency list”, “path enumeration”
  • Redis tree structure storage
  • How to use Lua script in Redis
    • Redis support Lua script command brief
    • Redis support Lua script command details
    • How does Redis debug Lua scripts
  • Lua script combat Redis tree structure
  • Lua scripts in Redis

Preface:

In toB company, I was in charge of the middle And Taiwan business, and the department relationship of many enterprises was a tree structure. Some time ago, I had a business demand that “efficiently query all the superior departments of a specified department under a large amount of data, and the department tree relationship of the enterprise may change at any time”. On the basis of MySQL then thought of using Redis cache tree structure and achieve efficient query.

1. Common scenarios and solutions of tree structure

1.1 common scenarios of tree structure

In daily life, we have many data scenarios with tree structure, such as:

  • National administrative region code;
  • Enterprise organizational structure;

Tree structure data is characterized by obvious ownership relationship. For example, “Chaoyang District” in the example of “administrative region code” belongs to “Beijing”, and “social Product Department” in the example of “Organizational structure” belongs to “product center”.

1.2. Tree structure solution

1.2.1 Adjacency list

The most commonly used scheme in the industry is probably “adjacency list”, in short, “adjacency list” each data store “superior data ID”.

Data ID The name of the data Upper-level data ID
cpzx Product center The head office ID
sjcpb Social Products Department cpzx
bgcpb Office Products Department cpzx
bgcpyz Office products group 1 bgcpb
bgcpez Office Products Group 2 bgcpb

Advantages of adjacency list:

  • Adding data efficiently;
  • Modify the data of the superior efficient;
  • Efficient deletion of leaf node data;

Disadvantages of adjacency list:

  • To delete an intermediate node, move its child node.
  • It is complicated to query all leaf nodes and all parent nodes of nodes.
    • MySQL, Oracle supports recursive queries;

1.2.2 path enumeration

Another popular scheme is “path enumeration”, the core idea of which is that each piece of data has fields that store all of its parent information.

Data ID The name of the data The path
1 China 1
11 The Beijing municipal 1,
110105 Chaoyang district 1,11,110105
51 Sichuan province 1 ploidy
5101 chengdu 1,51,5101
510104 Jinjiang district, 1,51,5101,510104

Advantages of path enumeration:

  • Query all parent nodes of the node efficiently;
    • Select path where ID = ‘node ID’;
  • Query all child nodes of a node efficiently;
    • Select ID where ID = 1,51%;

Disadvantages of path enumeration:

  • Rely on complex logic to maintain paths;
  • Path length may be out of control;
  • When a non-leaf node deletes or changes a parent node, all child nodes are changed.

In addition to “adjacency list” and “path enumeration”, there are also “nested set” that stores the scope of descendant nodes, and “closure table” that maintains an independent data table to store the relationship of all descendant nodes for storing tree structure data. Since it is not the focus of this article, I will not repeat it here.

In the actual production scheme, we do not need to stick to the above one scheme, the appropriate integration of the scheme, often get twice the result with half the effort. Our production system, for example, has a mix of “adjacency list” and “path enumeration” scenarios, and the comprehensive performance is quite good.

It doesn’t matter whether it’s black or white, but it’s a good cat when it catches mice.

2. Storage of tree structure under Redis

Before explaining the storage solution, we first review the existing service scenarios. All technologies serve services.

ToB system, there are many enterprises (company1 ~ company666) in the system, each enterprise has its own department tree. For example, under A0 of a company, there are 50 first-level departments from B1 to B50. Each first-level department has a number of second-level departments (for example, under B1, there are 30 second-level departments cb1-1 ~ CB1-30, and under B3, there are 40 second-level departments CB3-1 ~ CB3-40); Similarly, there are a number of tertiary departments under each secondary department. For large enterprises, there are thousands of departments. In addition, it should be noted that the departmental information of an enterprise may change at any time. But now our demand is: query the information of all superior departments of a department at level N.

In the MySQL scenario, we can use “adjacency list” or “path enumeration” schemes, or even mix schemes as mentioned above. According to the previous scheme analysis, “path enumeration” is a better scheme for the demand of “query all the parent nodes of the node”. But what if we need to further improve performance when QPS is high? Besides improving DB performance response, is there another way out?

High performance Redis has entered our vision, so how to use Redis to complete the storage of tree structure?

The Redis data structure used here is Hash. The Redis key is the enterprise ID (Depttree: enterprise ID), the field is the department ID, and the value corresponding to the field is the ID of the superior department corresponding to the department ID. The following is an example:

Business logic:

  • When all parent departments are queried, they are first queried from the cache. When the cache is missing, they are queried from DB and updated to Redis.
  • Delete the Redis cache when the department relationship changes.
  • When a department is deleted, the Redis cache is deleted.
  • Data storage in Redis adopts the way of “adjacency list”.
  • Because the parent of any department may change, data storage in Redis does not adopt the “path enumeration” scheme.

Note that:

  • HMSET key field value [field value…] ;
  • In actual production, we use the two-level cache, which is more complex and will not be expanded here.
HMSET DepTTREE: Enterprise 001 B1 A0 B2 A0 B3 A0 CB1-1 B1Copy the code

How to use Lua script in Redis

In the previous section, the department relationship data has been stored in Redis. According to the hash structure, it is impossible to query all the superior departments of the specified department at one time, so we need to use the Lua script. Before going into action, let’s learn how to use Lua scripts in Redis.

Redis 2.6.0 now supports Lua scripts. Lua scripts used in Redis should provide the body directly and do not need or define a function. Let’s get started with the Redis Lua script.

3.1 Brief description of Lua script commands supported by Redis

The command function parameter
EVAL Execute the Lua script EVAL script numkeys key [key …] arg [arg …]
SCRIPT LOAD Import the script content into Redis’ script cache SCRIPT LOAD script
EVALSHA The script is executed by importing the SHA1 digest value of the script EVALSHA sha1 numkeys key [key …] arg [arg …]
SCRIPT EXISTS Determines whether the script that specifies the SHA1 digest value exists SCRIPT EXISTS sha1 [sha1 …]
SCRIPT FLUSH Clear all Lua script caches SCRIPT FLUSH
SCRIPT KILL Kill Lua scripts that are executing without writing SCRIPT KILL
SCRIPT DEBUG Set the Lua script debug mode SCRIPT DEBUG YES | SYNC | NO

3.2 Explanation of Lua script commands supported by Redis

3.2.1, EVAL

  • parameter
    • EVAL script numkeys key [key …] arg [arg …]
  • function
    • Execute the Lua script
  • Version available
    • server
  • Time complexity
    • Depends on the script being executed;
  • Parameters that
    • Script: the content of a script;
    • Numkeys: indicates the number of keys.
    • [key …] : key value, the number of which must match numkeys.
    • [arg …] : Additional parameter, [key…] The latter are additional parameters and the number is not fixed.
  • The return value
    • Script execution result;
  • note
    • KEYS[1], KEYS[2], ARGV[1];
127.0.0.1:6379> eval "return redis. Call ('set',' public ','zxiaofan')" 0 OK 127.0.0.1:6379> eval "return redis.call('set',KEYS[1],'bar')" 1 foo OKCopy the code

3.2.2, SCRIPT LOAD

  • parameter
    • SCRIPT LOAD script
  • function
    • Import the script content into Redis script cache;
  • Version available
    • server
  • Time complexity
    • O(N), N depends on the length of the script bytes;
  • Parameters that
    • Script: the content of a script;
  • The return value
    • The SHA1 digest value of the imported script;
  • note
    • The SHA1 digest value returned by successive imports of the same script is the same.
    • Imported scripts will be stored in the Redis script cache unless deleted using the FLUSH command.
    • When using redis-CLI interaction, you can import lua scripts in the specified path with “$(cat./luascript/xxx.lua)”.
    • If you are already in the Redis interactive shell, you cannot use this method;
127.0.0.1:6379 > SCRIPT LOAD "return" 1 "e0e1f9fabfc9d4800c877a703b823ac0578ff8db"Copy the code
// redis-cli import lua script in the specified path, Zxiaofan./redis-cli -a password -p 6379 script load "$(cat./luascript/xxx.lua)" Warning: Using a password with '-a' or '-u' option on the command line interface may not be safe. "8144f1139110991cf3f085b70f807a4ef261b727"Copy the code

3.2.3, EVALSHA

  • parameter
    • EVALSHA sha1 numkeys key [key …] arg [arg …]
  • function
    • Execute the script by importing the SHA1 digest value of the script;
  • Version available
    • server
  • Time complexity
    • Depends on the script being executed;
  • Parameters that
    • Sha1: sha1 digest value of the imported script.
    • Numkeys: indicates the number of keys.
    • [key …] : key value, the number of which must match numkeys.
    • [arg …] : Additional parameter, [key…] The latter are additional parameters and the number is not fixed.
  • The return value
    • Script execution result;
127.0.0.1:6379 > evalsha e0e1f9fabfc9d4800c877a703b823ac0578ff8db 0 "1"Copy the code

3.2.4, SCRIPT EXISTS

  • parameter
    • SCRIPT EXISTS sha1 [sha1 …]
  • function
    • Determines whether the script that specifies the SHA1 digest value exists
  • Version available
    • server
  • Time complexity
    • O(N), N depends on the number of SHA1 summary values, and the time complexity of a single judgment is O(1).
  • Parameters that
    • [sha1 …] : SHA1 summary value list;
  • The return value
    • 1: The script exists.
    • 0: The script does not exist.
127.0.0.1:6379 > SCRIPT EXISTS e0e1f9fabfc9d4800c877a703b823ac0578ff8db e0e1f9fabfc9d4800c877a703b823ac0578ff8db2 1) (integer) 1 2) (integer) 0Copy the code

3.2.5, SCRIPT FLUSH

  • parameter
    • SCRIPT FLUSH
  • function
    • Clear all Lua script caches;
  • Version available
    • server
  • Time complexity
    • O(N), where N is the number of scripts in Redis script cache;
  • Parameters that
    • No parameters;
  • The return value
    • OK: The file is cleared successfully.
  • note
    • The FLUSH command is indiscriminately attacked and cannot FLUSH the specified script.
127.0.0.1:6379 > SCRIPT FLUSH OKCopy the code

3.2.6, SCRIPT to KILL

  • parameter
    • SCRIPT KILL
  • function
    • Kill executing Lua scripts with no write operations;
  • Version available
    • server
  • Time complexity
    • O(1)
  • Parameters that
    • No parameters;
  • note
    • The KILL command does not KILL the specified script.
127.0.0.1:6379> SCRIPT KILL
(error) NOTBUSY No scripts in execution right now.
Copy the code

3.2.7, SCRIPT DEBUG

  • parameter
    • SCRIPT DEBUG YES|SYNC|NO
  • function
    • Set the Lua script debug mode
  • Version available
    • 3.2.0.
  • Time complexity
    • O(1)
  • Parameters that
    • YES: Set the debug mode to asynchronous mode, debug scripts do not block, and all changes are rolled back after the dialog is closed.
    • SYNC: Set the debug mode to synchronous mode. Debug scripts will block and all changes will be saved to Redis.
    • NO: disables the script debugging mode.
  • The return value
    • OK
  • note
    • There is no way to view the current script debug mode;
// Specify debug mode to debug the script; ./redis-cli --ldb-sync-mode --eval /tmp/script.luaCopy the code

3.3. How does Redis debug Lua scripts

Redis includes a complete Lua debugger code-named LDB.

  • Debugging command s: single step execution;
  • Debugging command p: prints all variable values;
  • Redis.debug () was added to Lua scripts to print messages to the console during debugging;
  • The Lua script adds redis.breakpoint() to pause the next line when there is a breakpoint;

Other detailed debugging commands are described in the following comments:

[redis@redis redis]$./redis-cli --ldb --eval /tmp/script.lua mykey key1 arg1 arg2 Lua debugging session started, please use: quit -- End the session. restart -- Restart the script in debug mode again. help -- Show Lua script debugging commands. Zxiaofan lua debugger> help Redis lua debugger help: [h]elp Show this help. [s]tep Run current line and stop again. Single step execution; [n]ext Alias for step. [c]continue Run till next breakpoint. Execute to the next breakpoint; [l]list List source code around current line. Display the current line of source code; [l]list [line] List source code around [line]. line = 0 means: current position. Displays the source code of the specified line. [l]list [line] [ctx] In this form [ctx] specifies how many lines to show before/after [line]. Display [CTX] line source code, starting with [line]. [w]hole List all source code. Alias for 'list 1 1000000'. Display all source code; [p]rint Show all the local variables. Prints all variable values; [p]rint <var> Show the value of the specified variable. Can also show global vars KEYS and ARGV. Prints the specified variable value; [b]reak Show all breakpoints. [b]reak <line> Add a breakpoint to the specified line. Add a breakpoint on the specified line. [b]reak -<line> Remove breakpoint from the specified line. Removes the specified line breakpoint. [b]reak 0 Remove all breakpoints. Remove all breakpoints; [t]race Show a backtrace. [e]eval <code> Execute some Lua code (in a different callframe). Execute Lua code in a separate stack; [r]edis <cmd> Execute a Redis command. Execute a Redis command; [m]axlen [len] Trim logged Redis replies and Lua var dumps to len. Specifying zero as <len> means unlimited. [a]bort Stop the execution of the script. In sync mode dataset changes will be retained. If the script is terminated, data written in sync mode is retained. Debugger functions you can call from Lua scripts: redis.debug() Produce logs in the debugger console. redis.breakpoint() Stop execution like if there was a breakpoint in the next line of code.Copy the code

4, Lua script actual Redis tree structure

The previous “Storage of tree structure under Redis” has described the storage of tree result data under Redis, here mainly explains how to use Lua script to quickly query all the upper nodes of the specified node;

There are four script inputs:

  • Rediskey: Redis key whose data structure is Hash.
  • CurrentDeptNo: Specifies the department to be queried.
  • UtilDeptNo: utilDeptNo: to query a stop node of a superior department until it is utilDeptNo: utilDeptNo: to query a stop node of a superior department until it is utilDeptNo
  • MaxGetTimes: indicates the maximum number of iterated queries to avoid dirty data forming an infinite loop.
    • The maximum value is 100. If maxGetTimes passed in exceeds 100, the value is forcibly assigned to 100.
    • Because the actual department level is no more than 100;
// Data initialization, 1 is superior to 2, 2 is superior to 3, and 3 is superior to 4; The public zxiaofan no.

127.0. 01.:6378> HMSET depttree:001 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
OK

// Execute the script
// Query all superiors of node 1 up to node 3, up to 66 times.

[redis@redis redis]$ ./openredis.sh 6378 "--eval luascript/lua_getAllSupDept.lua depttree:001 1 3 66"
"1, 2, 3"
Copy the code

The lua_getAllSupDept. Lua script is now open source on Github.

In Lua scripts, when Redis returns a result of (nil), its real data type is Boolean, so the nonexistence of the data is determined by if(tempDept == false).

-- Redis Lua script: query all departments of the specified department
-- Save the script as lua_getAllSupDept. Lua;

--[[ luaScriptName: getAllSupDept; function: get all Super Dept of currentDeptNo; auther: zxiaofan.com; param: rediskey: the key of redis, the data structures is Hashes; currentDeptNo: the current DeptNo; utilDeptNo: query super dept until the utilDeptNo; maxGetTimes: the max times of query to prevent dead loop. result: a. the whole super detp data; b. the super detp data but not until specified dept(utilDeptNo);  c. return currentDeptNo when no data; d. return error "error: the times of query exceeded the maxGetTimes!"; --]]

local rediskey = KEYS[1];
local currentDeptNo = KEYS[2];
local utilDeptNo = KEYS[3];
local maxGetTimes = tonumber(KEYS[4]);

-- redis.debug("rediskey: %q",rediskey);
-- redis.debug("currentDeptNo: %q",currentDeptNo);
-- redis.debug("utilDeptNo: %q",utilDeptNo);
-- redis.debug("maxGetTimes: %q",maxGetTimes);


	if(currentDeptNo == utilDeptNo) then
		return currentDeptNo;
	end

	if(maxGetTimes > 100) then
		maxGetTimes = 100;
	end

	local time = 1;

	local result = currentDeptNo;
	local tempDept = currentDeptNo;

	while(tempDept ~= utilDeptNo)
	do
		if(time > maxGetTimes) then
			return "error: the times of query exceeded the maxGetTimes!";
		end

		tempDept = redis.call('hget',rediskey , tempDept);
		-- redis.debug("tempDept: %q",tempDept);

		if(tempDept == false or tempDept == "NULL") then
			return result;
		end

		result = result .. ",". tempDept;time = time + 1 ;
	end

	return result;
Copy the code

5. Precautions for using Lua scripts in Redis

  • A script is a program body and cannot define functions;
  • Script execution isatomicThe script is executed without other scripts or Redis commands.
    • Avoid using Lua slow scripts;
  • Variables in Lua scripts must be local variables;
  • The Lua script is available in redis.confLua-time-limit Sets the maximum running time;
    • Lua-time-limit: the default value is 5000 seconds.
    • When the script runs beyond the time limit, Redis will receive other instructions, but because of the atomicity of the script, the script will not be terminated, and other instructions will return a “BUSY” error;
    • You can KILL a running Lua SCRIPT by using “SCRIPT KILL”.
    • SCRIPT KILL cannot KILL scripts that contain modification operations. In this case, you need to run SHUTDOWN NOSAVE to forcibly stop Redis.
  • After the Lua script is executed, the command is appended to the AOF.
  • Import script content to Redis in advance, and use EVALSHA SHA1 to execute Lua scripts to improve performance. If the script is large, it can save bandwidth.

The difference between SHUTDOWN NOSAVE and SHUTDOWN NOSAVE is that the SHUTDOWN NOSAVE does not persist, that is, data changes made after the last snapshot are lost.

Eval 'while(true) do print("1") end' 0Copy the code
Eval "redis. Call ('set',' public ','zxiaofan') while true do end" 0Copy the code
// Lua script execution times out, there will be a warning in the log

Lua slow script detected: still in execution after 5000 milliseconds. You can try killing the script using the SCRIPT KILL command. Script SHA1 is: 3245e4edc1a1e2a9bac3c52e99466f9ccabf65c0
Copy the code
// Jedis displays a Lua script timeout message.

redis.clients.jedis.exceptions.JedisDataException: BUSY Redis is busy running a script. You can only call SCRIPT KILL or SHUTDOWN NOSAVE.
Copy the code

Lua scripts in Redis cluster mode

127.0. 01.:6379> eval "return {KEYS[1],KEYS[2],ARGV[1],ARGV[2]}" 2Key1 key2 public id Zxiaofan (error) CROSSSLOT Keys in request don't hash to the same slot
Copy the code

When the Redis Cluster operates multiple Keys, all Keys in the command must belong to the same slot. Otherwise, CROSSSLOT Keys in request don’t hash to the same slot will be thrown.

If the key contains {}, the string from the first {} will be used as the hash key, so in clustered mode we can wrap the same contents of the Redis key with {}.

Therefore, change the key1 key2 of the above statement to {key}1 {key}2.

127.0. 01.:6379> eval "return {KEYS[1],KEYS[2],ARGV[1],ARGV[2]}" 2 {key}1 {key}2The public zxiaofan no.1) "{key}1"
2) "{key}2"
3) "Public Account"
4) "zxiaofan"
Copy the code

Note that although the {} mode can hash different keys to the same SOLT, data skew is easily caused by a large amount of data, which affects system stability. Therefore, please fully analyze the evaluation data before use, and handle flexibly as needed.

// Cluster mode getSlot operation; Public id: Zxiaofan;
// Source code: https://github.com/redis/jedis/blob/6ed1441ca4c5de7e66648edfeafa16854707482c/src/main/java/redis/clients/jedis/util/Jedi sClusterCRC16.java

public static int getSlot(byte[] key) {
    if (key == null) {
      throw new JedisClusterOperationException("Slot calculation of null is impossible");
    }

    int s = -1;
    int e = -1;
    boolean sFound = false;
    for (int i = 0; i < key.length; i++) {
      if (key[i] == '{' && !sFound) {
        s = i;
        sFound = true;
      }
      if (key[i] == '} ' && sFound) {
        e = i;
        break; }}if (s > -1 && e > -1&& e ! = s +1) {
      return getCRC16(key, s + 1, e) & (16384 - 1);
    }
    return getCRC16(key) & (16384 - 1);
  }
Copy the code

Afterword.

Lua scripts are powerful, but they also need to be careful to avoid timeout blocks and data skew.

When Lua scripts are used in production environments, there must be a strict review mechanism.

IO /commands/ev… Redis. IO/switchable viewer/LDB;

【 Redis series of articles recently selected public account @zxiaofan】

Play Redis- Kill nail Owners – Keys with no expiration date

“Playing with RedIS-8 Data Elimination Strategies and Approximate LRU and LFU Principles”

Redis: How to Import, Export, and Delete Large Amounts of Data in a Production Environment

Redis- Deleted 2 million keys, why is the memory still not free?

Play with the Use and Principle of Bloom Filter in Redis

Check out the latest series of articles on zxiaofan. Life is all about choices! In the future, you will be grateful for your hard work now! 【CSDN】【GitHub】【OSCHINA】【 Nuggets 】【 words bird 】【 wechat public account (click to follow)】