What we'll cover
Our server now supports Strings, albeit not all string commands are implemented, Lists and Hashes. Redis supports three more native data types, Sets, Sorted Sets and Streams. Streams being a recent addition to Redis, and being a fairly complicated topic, will not be covered in this book. Other data types exists, such as Bitmaps, HyperLogLog and Geospatial items, but all of these are implemented on top of the String native type.
In this chapter we will add support for the Set type. Conceptually a Set is a collection of unique items, and can therefore not contain duplicates. A common operation for Sets, beside the ability to add items to a set, is testing for the presence of an item. Such operation would ideally require constant time, that is a complexity of O(1).
Wikipedia defines a set as:
In computer science, a set is an abstract data type that can store unique values, without any particular order.
Sets, in computer science are very similar to Finite Sets in Mathematics. Redis Sets only store strings.
Given these constraints, it looks like our Dict data structure would be a great fit to implement an API for Sets. The Dict class stores key/value pairs, where keys are strings, so we wouldn't even need to add any values in the dict, adding key/value pairs with nil values would be sufficient.
It is interesting to consider that many data structures can be used to provide a set API. For instance Ruby arrays can be used as set with the following methods:
def new_set
[]
end
def include?(set, member)
set.include?(member)
end
def add(set, member)
if include?(set, member)
false
else
set << member
true
end
end
listing 9.1 A Set using a Ruby array
These three methods do provide the API for a set, but the performance, especially in the worst case scenario, will degrade quickly as the set grows. The include? method needs to iterate over the entire array to return false, so calling include? for a member that is not in the array, will always require a full iteration of the array.
The List class we created in Chapter 7 could also be used to implement a set but would suffer from the exact same performance issues.
Ruby has a Set class, but we will not use it to follow the "build from scratch" approach we've been using so far.
Redis supports sixteen set commands:
- SADD: Add one or more members to a set, creating it if necessary
- SCARD: Return the cardinality of the set, the number of members
- SDIFF: Compute the difference of sets, from left to right
- SDIFFSTORE: Same as SDIFF but store the result in another key instead of returning it
- SINTER: Compute the intersection of all given sets
-
SINTERSTORE: Same as
SINTERbut store the result in another key instead of returning it - SUNION: Compute the union of all given sets
-
SUNIONSTORE: Same as
SUNIONbut store the result in another key instead of returning it -
SISMEMBER: Return
0or1depending on whether or not the given member is in the given set - SMEMBERS: Return all the members of the given set
-
SMISMEMBER (new in 6.2.0): Variadic version of
SISMEMBER, that is, it accepts multiple arguments and returns an array - SMOVE: Move a member from one set to another
- SPOP: Remove a member from the given set
- SRANDMEMBER: Return a member from the given set, but leave it in the set
- SREM: Remove the given member from the given set
-
SSCAN: Similar to
SCAN,HSCAN&ZSCAN. We will not implement it for the same reason we did not implementHSCANin Chapter 8
How does Redis do it?
As mentioned in the previous chapter, the set commands are implemented in the t_set.c file, in which Redis uses two different data structures to store the data. As long as the elements, also called members in a set, can be represented as integers, and that the size of the set if below the set-max-intset-entries config value, which has a default value of 512, Redis uses an intset, and otherwise uses the dictionary from dict.c. We already created the Dict class in Chapter 6, but the intset is a new data structure.
Using an IntSet provides two interesting benefits, the memory footprint of the set is smaller, and most set operations will be faster than with a dict when the number of members is small. Note that while sets do not have to be ordered, int sets are actually ordered, which is how it provides a reasonably fast way to check for the existence of an element in a set, through binary search.
Everything is a string in a dict, this means that the number 1 would be stored as the character '1', which uses one byte of memory, eight bits, and the number 1,000 would be stored as the string '1000' and use four bytes, thirty two bits. This means that large numbers, such as, 1,000,000,000,000, one trillion, which is composed of thirteen digits, would use thirteen bytes, one hundred and four bits.
Storing these values as 64-bit integers would improve things for large numbers, one trillion would only require sixty four bits instead of one hundred and four, but it would actually make things worse for small numbers. If we were to store the number one as a 64-bit integer, it would use sixty four bits instead of eight if we stored it as a character.
Redis' intset type uses an encoding variable, which determine the size of the integers stored. Because the intset structure uses an array, it has to use the same underlying type for all elements. This is what allows indexed access in O(1) time. If we want to access the element at index i, we can multiply i by the size of the variables stored in the array, and we'll land on the i-th element. The content of the intset is an array of int8_t, so that each element uses exactly one byte. This allows Redis to store all the integers in this array, in 8-bit chunks, the actual length of each integer is determined by the encoding of the intset.
Redis uses three possible encoding values, int16_t, int_32_t & int64_t, respectively 16-bit integers, 32-bit integers, and 64-bit integers. When an intset is created, its encoding is set to 16-bit integers. Whenever new members are added to the set, Redis tries to find the smallest encoding that can hold the value. int16_t can range from -2^15 to 2^15 - 1, -32,768 to 32,767, int32_t from -2^31 to 2^31 - 1, -2,147,483,648 to 2,147,483,647 and int64_t from -2^63 to 2^63 - 1, -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807.
With this approach, storing numbers between 0 & 9 would still be more expensive, because they would be store as 16-bit integers, but we're already breaking even for negative numbers from -1 to -9, and we're saving space for numbers lower than or equal to -10, which would use three bytes as strings, and only use two as 16-bit integers, and for numbers greater than or equal to 100. The benefits become even greater as the number grow in either direction.
Speed wise, the benefits are the same that what we discussed in the previous chapter in the ziplist vs dict section. Using an intset will gradually become slower as the intset grows, but all operations will be really fast when the number of members is small. Large intset structure suffer from the same issues than ziplists and become slow to manipulate as they grow, because the whole memory chunk needs to be reallocated and items within it moved, to make space for new elements.
The intset functionalities are implemented in intset.c. An intset is essentially a sorted array of integers. We already implemented a sorted array, the SortedArray class, but the requirements are a little bit different here so we will create an IntSet class to mimic the Redis behavior.
As mentioned in the previous section, a dictionary provide a solid foundation to implement the Set API. It turns out that this is exactly what Redis does. When handling the SADD command, if the underlying data structure is a dict, it calls the dictAdd function with the member as the key, and nothing as the value, this is done in the setTypeAdd function.
Our Dict class already exists, and will only require a few changes, to make sure that it handles entries with nil values without any hiccups, on the other hand, we need to build an IntSet class from scratch, so let's get to it.
The IntSet data structure
Because the intset structure uses a sorted array, this makes the time complexity of a lookup O(logn), which will be worse than O(1) when the array gets bigger. Additionally, because arrays are contiguous chunks of memory, inserting an element requires a lot of work, to shift all the elements to the right of the new element. This makes arrays more and more expensive to manipulate as they grow in size, and explains why Redis only uses it if sets contain 512 items or less.
Redis stores all values in little endian in an intset. This means that the number 1, which has the following binary representation as a 16-bit integer:
irb(main):025:0> ('%016b' % 1).chars.each_slice(8).map { |byte| byte.join }.join(' ')
=> "00000000 00000001"
The two bytes, \x00 & \x01 need to be reversed in little endian, because the least significant bytes come first, so the bytes of 1, in little endian are [ "\x01", "\x00" ].
Let's look at a larger example, the representation of 1,000,000 as a 32-bit integer:
irb(main):027:0> ('%032b' % 1_000_000).chars.each_slice(8).map { |byte| byte.join }.join(' ')
=> "00000000 00001111 01000010 01000000"
The big endian bytes are [ "\x00", "\x0F", "\x42", "\x40" ], and [ "\x40", "\x42", "\x0F", "\x00 ] as little endian.
Another way to play with these values is to use the Array#pack method, with the l format, which is the format for signed 32-bit integer, which uses the native endianness of the platform by default, but can be forced to use big endian with l> and little endian with l<:
irb(main):043:0> [1_000_000].pack('l')
=> "@B\x0F\x00"
irb(main):044:0> [1_000_000].pack('l>')
=> "\x00\x0FB@"
irb(main):045:0> [1_000_000].pack('l<')
=> "@B\x0F\x00"
This example illustrates that the default endianness of my machine, a macbook pro, is little endian. Note that some of these bytes don't look like the others, "@" & "B" vs "\x0F" and "\x00". This is because Ruby attempts to display the characters as ASCII by default, and it turns out that "\x42" is the hex representation of the decimal 66, the character 'B' in ASCII and "\x40" is the hex representation of the decimal 64, the character '@' in ASCII.
Our class will implement the following public methods:
add(member)cardinalityeachcontains?(member)memberspoprandom_memberempty?remove(member)
The methods above will allow us to implement all the Set related commands. All the following methods are implemented in the int_set.rb file, under the BYORedis::IntSet class, let's start with the constructor and the add method:
module BYORedis
class IntSet
INT16_MIN = -2**15 # -32,768
INT16_MAX = 2**15 - 1 # 32,767
INT32_MIN = -2**31 # -2,147,483,648
INT32_MAX = 2**31 - 1 # 2,147,483,647
INT64_MIN = -2**63 # -9,223,372,036,854,775,808
INT64_MAX = 2**63 - 1 # 9,223,372,036,854,775,807
# Each of the constant value represents the number of bytes used to store an integer
ENCODING_16_BITS = 2
ENCODING_32_BITS = 4
ENCODING_64_BITS = 8
def initialize
@underlying_array = []
@encoding = ENCODING_16_BITS
end
def add(member)
raise "Member is not an int: #{ member }" unless member.is_a?(Integer)
# Ruby's Integer can go over 64 bits, but this class can only store signed 64 bit integers
# so we use this to reject out of range integers
raise "Out of range integer: #{ member }" if member < INT64_MIN || member > INT64_MAX
encoding = encoding_for_member(member)
return upgrade_and_add(member) if encoding > @encoding
# search always returns a value, either the position of the item or the position where it
# should be inserted
position = search(member)
return false if get(position) == member
move_tail(position, position + 1) if position < size
set(position, member)
true
end
private
def set(position, member)
@encoding.times do |i|
index = (position * @encoding) + i
@underlying_array[index] = ((member >> (i * 8)) & 0xff).chr
end
end
def move_tail(from, to)
@underlying_array[(to * @encoding)..-1] = @underlying_array[(from * @encoding)..-1]
end
def search(member)
min = 0
max = size - 1
mid = -1
current = -1
# the index is always 0 for an empty array
return 0 if empty?
if member > get(max)
return size
elsif member < get(min)
return 0
end
while max >= min
mid = (min + max) >> 1
current = get(mid)
if member > current
min = mid + 1
elsif member < current
max = mid - 1
else
break
end
end
if member == current
mid
else
min
end
end
def get(position)
get_with_encoding(position, @encoding)
end
def get_with_encoding(position, encoding)
return nil if position >= size
bytes = @underlying_array[position * encoding, encoding]
# bytes is an array of bytes, in little endian, so with the small bytes first
# We could iterate over the array and "assemble" the bytes into in a single integer,
# by performing the opposite we did in set, that is with the following
#
# bytes.lazy.with_index.reduce(0) do |sum, (byte, index)|
# sum | (byte << (index * 8))
# end
#
# But doing do would only work if the final result was positive, if the first bit of the
# last byte was a 1, then the number we're re-assembling needs to be a negative number, we
# could do so with the following:
#
# negative = (bytes[-1] >> 7) & 1 == 1
#
# And at the end of the method, we could apply the following logic to obtain the value,
# get the 1 complement, with `~` and add 1. We also need to apply a mask to make sure that
# the 1 complement result stays within the bounds of the current encoding
# For instance, with encoding set to 2, the mask would be 0xffff, which is 65,535
#
# if negative
# mask = (2**(encoding * 8) - 1)
# v = -1 * ((~v & mask) + 1)
# end
#
# Anyway, we can use the pack/unpack methods to let Ruby do that for us, calling
# bytes.pack('C*') will return a string of bytes, for instance, the number -128 is stored
# in the intset as [ 128, 255 ], calling, `.pack('C*')` returns "\x80\xFF". Next up, we
# pick the right format, 's' for 16-bit integers, 'l' for 32 and 'q' for 64 and we let
# Ruby put together the bytes into the final number.
# The result of unpack is an array, but we use unpack1 here, which is a shortcut to
# calling unpack() followed by [0]
#
# What this whole thing tells us is that we could have used `.pack('s').bytes` in the
# set method, but using >> 8 is more interesting to understand actually what happens!
format = case encoding
when ENCODING_16_BITS then 's'
when ENCODING_32_BITS then 'l'
when ENCODING_64_BITS then 'q'
end
bytes.join.unpack1(format)
end
def encoding_for_member(member)
if member < INT32_MIN || member > INT32_MAX
ENCODING_64_BITS
elsif member < INT16_MIN || member > INT16_MAX
ENCODING_32_BITS
else
ENCODING_16_BITS
end
end
def upgrade_and_add(member)
current_encoding = @encoding
current_size = size
new_size = current_size + 1
@encoding = encoding_for_member(member)
prepend = member < 0 ? 1 : 0
@underlying_array[(new_size * @encoding) - 1] = nil # Allocate a bunch of nils
# Upgrade back to front
while (current_size -= 1) >= 0
value = get_with_encoding(current_size, current_encoding)
# Note the use of the prepend variable to shift all elements one cell to the right in
# the case where we need to add the new member as the first element in the array
set(current_size + prepend, value)
end
if prepend == 1
set(0, member)
else
set(size - 1, member)
end
true
end
end
end
listing 9.2 The IntSet#add method, and all the private methods it requires
The add method starts with a few checks to make sure that we can indeed add the given member to the set. If the value is not an integer or is out of range, we reject it right away. The next step is to find the smallest encoding that can fit member. Once we found the encoding, either 2, 4 or 8, we compare it to the current encoding of the set. If the new encoding is greater, then we know that member is either going to be the smallest entry in the set, or the largest, because it would otherwise have used the same encoding.
The upgrade_and_add method takes care of migrating all current elements to the new encoding, and inserts the new member, either at index 0 or as the last element in the array.
Let's look at the three main steps of the upgrade_and_add method, first it increases the size of the array, with @underlying_array[(new_size * @encoding) - 1] = nil, which pads the array to the right with nil values until the new size, let's look at an example:
irb(main):029:0> l = ["\x01", "\x00", "\x02", "\x00"]
This array is what the @underlying_array of an IntSet storing the values 1 and 2 would be. "\x01" and "\x00" is the little endian representation of the number 1 in a 16-bit integer, 0000 0001 0000 0000. The first byte, 0000 0001, written as 0x01 in the Ruby hex literal syntax is the byte for the number 1, since 2^0 == 1. The second byte, the most significant one only contains zeroes: 0000 0000. If the number had been 258, the two bytes would have been 0000 0010 0000 0001. The first byte is the least significant one, 0000 0010, these are the bits between index 0 and 7, representing the number 2, and the most significant one is 0000 0001, the bits between index 8 and 15, representing the number 1. Putting it all together we get 2^1 + 2^8 == 258. Another way to write this number is "\x02\x01"
"\x02", "\x00", is the little endian representation of the number 2, 0000 0010 0000 0000, written as 0x0002 as a hex literal. Note that hex literals in Ruby follow the "natural" order and assume big-endian. So 0x0002 returns 1, whereas 0x0200 returns 512, because 0000 0010 0000 0000 is 512 in big endian, 2^9 == 512.
If we were to increase the encoding to 32-bit, to store numbers larger than 32,767, each number would now need to use four bytes, so the array would now need to be 12 item long, 4 bytes x 3 members, as we can see, calling l[11] adds all the nil values:
irb(main):030:0> l[11] = nil
irb(main):031:0> l
=> ["\x01", "\x00", "\x02", "\x00", nil, nil, nil, nil, nil, nil, nil, nil]
The next step, upgrading all the elements, is done in the while loop. In our previous example, current_size would be 1. Calling get_with_encoding(2, 2) would read the numbers 2 and 0, and return 2. Calling set(1 + 0, 2) would insert the four bytes representing 2 at the right place in the array. If we were to add 32,768, then prepend would be 0.
The set method splits the number into the number of bytes for the encoding, with the new encoding being 4, to store numbers as 32-bit integer, we would iterate four times with the @encoding.times loop. In the first iteration index would be (1 * 4) + 0, 4 and the value would be "\x01" because ((member >> 0) 0xff).chr returns "\x01" if member is 1.
0xFF acts as a mask here, it is the hex literal for the number 255, a byte of only ones, we could have written 0b11111111, it just happens to be easier to use 0xff, but they're identical. We use 0xff in combination of the bitwise AND operator, &, which effectively only selects the rightmost byte of any numbers.
We call .chr, which is equivalent to calling .pack('C'). This allows us transform the Integer instance into a one-byte string. As we've already discussed, Ruby has a special handling for numbers, which is why it can handle numbers greater than what a 64-bit integer can handle, but it also means that we don't have any direct visibility in what is actually allocated when we have an instance of the Integer class. Using .pack('C') treats the number in the array as an 8-bit integer, a byte. What we get in return is a one-character string, representing the byte value. Let's look at an example:
irb(main):001:0> [1].pack('C')
=> "\x01"
irb(main):002:0> 1.chr
=> "\x01"
irb(main):003:0> [255].pack('C')
=> "\xFF"
irb(main):004:0> 255.chr
=> "\xFF"
irb(main):005:0> [128].pack('C')
=> "\x80"
irb(main):006:0> [1].pack('C')
=> "\x01"
irb(main):007:0> [255].pack('C')
=> "\xFF"
irb(main):008:0> [128].pack('C')
=> "\x80"
irb(main):009:0> [128].pack('C').size
=> 1
irb(main):010:0> [128].pack('C').chars
=> ["\x80"]
Even though it looks like the strings returned by pack/chr contains four characters, a double-quoted Ruby string handles the \x prefix in a special way, and as we can see with the last two examples, it only contains a single character.
The next iteration would give index the value 5, and set the value 0 at index 5. The last two iterations would set the value 0 for index 6 and 7.
Back to upgrade_and_add, the while loop would run one more time with current_size == 0 and upgrade the encoding of 1. After the while loop the array would contain the following, the existing inters have been migrated from 16-bit integers to 32-bit integers, in little endian, which result in right padding them with bytes containing zeroes:
[
"\x01", "\x00", "\x00", "\x00",
"\x02", "\x00", "\x00", "\x00",
nil, nil, nil, nil,
]
The last step of the method is to add the new member, in this example prepend is not set to 1 and it is inserted as the last item with set(size - 1, member), where size == 3. set will split 32,768 into four bytes, which would be represented in big endian as the four bytes: 0x00, 0x00, 0x80, & 0x00:
# '%032b' % 32_768 =>
MSB LSB (Most Significant Byte/Least Significant Byte)
|-------| |-------| |-------| |-------|
7 0 7 0 7 0 7 0 (indices within each byte)
∨ ∨ ∨ ∨ ∨ ∨ ∨ ∨
0000 0000 0000 0000 1000 0000 0000 0000
∧ ∧ ∧ ∧ ∧
31 15 11 3 0 (indices within a 32-bit integer)
The only 1 in the previous binary number is at index 15, 2^15 = 32,768. The four bytes have the decimal values, 0, 0, 128 & 0. The second byte from the right have the value 128 because within that byte, the only 1 is at index 7 and 2^7 = 128.
Redis stores these numbers in little endian, so we store them in reverse order with the least significant bytes first: [ 0, 128, 0, 0 ]. The hex literal representation of 128 is 0x80.
With that, the final value of @underlying_array is:
[
"\x01", "\x00", "\x00", "\x00",
"\x02", "\x00", "\x00", "\x00",
"\x00", "\x80", "\x00", "\x00",
]
The next step in add is to search for member in the array, which we do with the search method. The method always returns an integer, which is either the position of member in the array or the position where it should be inserted.
The search method uses a divide and conquer approach to find the element. First, it checks if the element should go at the front of the array, if the new member is smaller than the element at index 0, or at the end of the array if it is greater than the last element in array.
If neither of these checks are true, we look at the value at index mid, because we know that the array is sorted, we compare that value with member, if it is greater than member, then we know that member will either be on the left side, or not present and we set the max to mid - 1, effectively narrowing the range to the left side of the array. We perform the opposite operation if the value at index mid is lower than member, then we want to keep searching on the right half of the array, and we do so with min = mid + 1. We stop iterating if neither of these checks are true, that is, if current == member, in which case mid is the index of member.
The other condition causing the loop to exit is if min becomes greater than max, which means that we did not find member in the array, in which case min is the index where it should be inserted. Let's look at an example to illustrate this:
array = [10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65]
The variable array contains twelve elements, so min will start at 0, max at 11 and mid & current at -1.
If we were to search for 56, we would enter the while loop and set mid to (min + max) >> 1, which is (0 + 11) >> 1, 5, this is because 11 is 0b1011 in binary, and shifting it to the right one time results in 101, 2^0 + 2^2, 5. array[5] == 35, so member > current and we set min to mid + 1, 6.
Using a bitwise right shift of 1 is a "trick" to divide a number by two. Let's look at an example to illustrate it. With the previous example, min is 0, max is 11. Given that the array has an even number of items, there's no index where there would be the same number of elements to the left and to the right, but we can still use the integer division to find an index that is close to that, 11 / 2 == 5, so far so good.
1011 (11)
>> 1
----
0101 (5)
This property, that shifting by one to the right is the same as dividing by two happens to be the result from how we represent numbers in binary. A 1 in binary represent a power of two, so 11 is binary is really the sum of 2^0, 2^1 & 2^3. Shifting by one to the right returns the number that is the sum of 2^0 and 2^1, which happens to be the result of an integer division by two.
This also works with even numbers:
1100 (10)
>> 1
----
0110 (6)
Tada!
If it feels a little bit like magic, I encourage you to experiment with different numbers, either on paper or with irb, it took me a little while until it "clicked".
Back to the search method.
On the next iteration mid becomes 8, because (6 + 11) >> 1 is 0b10001 >> 1, which is 0b1000, 8. array[8] == 50, so we set min to 9.
On the next iteration, mid becomes 10, because (9 + 11) >> 1 is 0b10100 >> 1, 0b1010, 10. array[10] == 60, so this time we set max to mid - 1, 9.
On the next and last iteration, mid is 9, because (9 + 9) >> 1 is 0b10010 >> 1, 0b1001, 9. array[9] == 55, so min becomes 10, and the loop exits because min > max.
9 happens to be the index where 56 should be inserted to maintain the array sorted.
Reading values from the array, which is what the get method does, is more complicated than in a regular array. Our set members span across multiple cells in the array, because each cell contains one byte. So a member spans across two cells with the 16-bit encoding, four with the 32-bit encoding and eight with the 64-bit encoding.
The get_with_encoding method grabs all the bytes and uses the unpack1 method to reconstruct the integer from its byte parts. Ruby knows how to convert the bytes based on the format string, s means signed short integer, int16_t, l means signed long integer, int32_t and q means signed long long integer, int64_t.
These methods give us the foundation to write the remaining methods, let's look at each, members, empty? & size:
module BYORedis
class IntSet
# ...
def empty?
@underlying_array.empty?
end
def each(&block)
members.each(&block)
end
def members
size.times.map do |index|
get(index)
end
end
def size
@underlying_array.size / @encoding
end
alias cardinality size
alias card cardinality
private
# ...
end
end
listing 9.3 The empty?, each, members and size methods in the IntSet class
The empty? method relies on the Array#empty? method, we don't need to change anything to its default behavior. The size method uses Array#size and divides the result by the size of encoding. This is because with the 16-bit encoding each integer will be split over two elements in the array, four elements with 32-bit and eight elements with 64-bit.
members uses size to determine how many times to iterate with the Integer#times method and passes the index to the get method we wrote earlier, which knows how to reassemble multiple array items into integers. Doing this in the block to map returns an array of Integer instances.
Finally the each method forwards its block argument to Array#each on the result of members.
An important method of the IntSet class is the include? method, which we can express in terms of search and get:
module BYORedis
class IntSet
# ...
def include?(member)
return false if member.nil?
index = search(member)
get(index) == member
end
alias member? include?
# ...
end
end
listing 9.4 The IntSet#include? method, aliased to member?
pop and rand_member are very similar, we use Kernel#rand with size as the exclusive upper boundary, which returns an index we can feed to get to return any elements of the set. In the pop case we do want to remove the item from the set and we do so with Array#slice!. This method takes two argument, the first one is the start index of the range we wish to delete and the second one is the length of the range.
remove uses Array#slice! in a similar way to how pop does it:
module BYORedis
class IntSet
# ...
def pop
rand_index = rand(size)
value = get(rand_index)
@underlying_array.slice!(rand_index * @encoding, @encoding)
value
end
def random_member
rand_index = rand(size)
get(rand_index)
end
def remove(member)
index = search(member)
if get(index) == member
@underlying_array.slice!(index * @encoding, @encoding)
true
else
false
end
end
private
# ...
end
end
listing 9.5 The pop, random_member and remove methods in the IntSet class
And with this the IntSet class is now feature complete.
Adding Set commands
Creating a Set with SADD
Let's start the same way we started in the previous in chapters, with the ability to create a new element in the main keyspace. Sets are created with the SADD command, which usually adds members to a set, if necessary, and creates a set if the key is not already used by a value of a different type.
require_relative './redis_set'
module BYORedis
class SAddCommand < BaseCommand
def call
Utils.assert_args_length_greater_than(1, @args)
key = @args.shift
new_member_count = 0
set = @db.lookup_set_for_write(key)
@args.each do |member|
added = set.add(member)
new_member_count += 1 if added
end
RESPInteger.new(new_member_count)
end
def self.describe
Describe.new('sadd', -3, [ 'write', 'denyoom', 'fast' ], 1, 1, 1,
[ '@write', '@set', '@fast' ])
end
end
end
listing 9.6 The SAddCommand class
The structure of the call method for the SAddCommand class is similar to HSet in the previous chapter. The first argument is the key for the hash, and the following arguments are the members to add to the set. Once the set is loaded, we iterate over the argument and use the RedisSet#add method.
In the previous chapter we created the RedisHash class, so let's create the RedisSet class, with the add method:
module BYORedis
class RedisSet
attr_reader :underlying
def initialize
@underlying = IntSet.new
end
def add(member)
case @underlying
when IntSet
int_member = convert_to_int_or_nil(member)
if int_member
added = @underlying.add(int_member)
if added && cardinality + 1 > Config.get_config(:set_max_intset_entries)
convert_intset_to_dict
end
added
else
convert_intset_to_dict
@underlying.set(member, nil)
end
when Dict then @underlying.set(member, nil)
else
raise "Unknown type for structure: #{ @underlying }"
end
end
private
def convert_intset_to_dict
dict = Dict.new
@underlying.each do |member|
dict[Utils.integer_to_string(member)] = nil
end
@underlying = dict
end
def convert_to_int_or_nil(member)
Utils.string_to_integer(member)
rescue InvalidIntegerString
nil
end
end
end
listing 9.7 The RedisSet#add method
We are going to use the same case/when pattern we introduced in the previous chapter but for IntSet and Dict instead of List and Dict. In the add method, if @underlying is an IntSet then we start by checking if the new member is a string that represents an integer by calling the convert_to_int_or_nil method. This method uses the Utils.string_to_integer method we introduced in the previous chapter.
If member can be converted to an integer, then we proceed with the IntSet instance and call the IntSet#add method. If the element was added to the set, that is, if it was not already in the set, then we check the cardinality of the set to see if it exceeded the set_max_intset_entries config value. If it did, the set is now too big to be an IntSet and we convert it to a Dict.
Luckily the conversion from IntSet to Dict, which we perform in the convert_intset_to_dict private method, does not require a lot of steps. We create a new Dict instance, and then iterate through all the IntSet members with the IntSet#each method and use the Dict#set method through its []= alias to add the members to the Dict. We only need the keys, so we set the value to nil for each new DictEntry we add.
If @underlying is an IntSet, but the new member cannot be represented as an integer, such as the string 'abc', then we convert the IntSet to a Dict, regardless of its current size, and add the new member with Dict#set. We don't use the []= alias here because doing so ignores the method's return value, and we want RedisSet#add to return the boolean returned by Dict#set, indicating whether or not the member was added to the set.
Finally, if @underlying is a Dict, which would be true in two cases, the set is either too big to be an IntSet, more than 512 members by default, or a member that cannot be converted to an integer was previously added. Regardless, we're now dealing with a Dict and we call Dict#set to add the member to the set.
Back to SAddCommand, we now need to add the lookup_set_for_write method to the DB class:
module BYORedis
class DB
# ...
def lookup_set(key)
set = @data_store[key]
raise WrongTypeError if set && !set.is_a?(RedisSet)
set
end
def lookup_set_for_write(key)
set = lookup_set(key)
if set.nil?
set = RedisSet.new
@data_store[key] = set
end
set
end
end
end
listing 9.8 The DB#lookup_set_for_write method
Now that we introduced a new type, set, we need to update the TypeCommand:
module BYORedis
class TypeCommand < BaseCommand
def call
Utils.assert_args_length(1, @args)
key = @args[0]
ExpireHelper.check_if_expired(@db, key)
value = @db.data_store[key]
case value
when nil then RESPSimpleString.new('none')
when String then RESPSimpleString.new('string')
when List then RESPSimpleString.new('list')
when RedisHash then RESPSimpleString.new('hash')
when RedisSet then RESPSimpleString.new('set')
else raise "Unknown type for #{ value }"
end
end
# ...
end
end
listing 9.9 Adding set to the TypeCommand class
In the next section we will add the six commands implementing set operations, namely difference, union and intersection, and their *STORE variants.
Set operations with SDIFF, SINTER, SUNION and their *STORE variants
Set difference
module BYORedis
# ...
class SDiffCommand < BaseCommand
def call
Utils.assert_args_length_greater_than(0, @args)
sets = @args.map { |other_set| @db.lookup_set(other_set) }
RESPArray.new(RedisSet.difference(sets).members)
end
def self.describe
Describe.new('sdiff', -2, [ 'readonly', 'sort_for_script' ], 1, -1, 1,
[ '@read', '@set', '@slow' ])
end
end
end
listing 9.10 The SDiffCommand class
The SDIFF command performs the "set difference" operation, starting with the leftmost set, it then iterates through all the other sets and removes their members from the first set, if it contained them, let's look at some examples:
127.0.0.1:6379> SADD s1 2 4 6 8 10 12
(integer) 6
127.0.0.1:6379> SADD s2 1 2 3 4
(integer) 4
127.0.0.1:6379> SADD s3 5 6 7 8 9 10 11 12 13
(integer) 9
127.0.0.1:6379> SDIFF s1
1) "2"
2) "4"
3) "6"
4) "8"
5) "10"
6) "12"
127.0.0.1:6379> SDIFF s1 s2
1) "6"
2) "8"
3) "10"
4) "12"
127.0.0.1:6379> SDIFF s1 s2 s3
(empty array)
127.0.0.1:6379> TYPE s4
none
127.0.0.1:6379> SDIFF s1 s4
1) "2"
2) "4"
3) "6"
4) "8"
5) "10"
6) "12"
Set difference is also called relative complement in set theory.
The difference of single set always returns the same set, you can compare it to subtracting 0 to any number, the result is always the same number. In the second example, we compute the difference of s1 and s2, in other words we subtract all the elements in s2 from s1, so we remove 1, 2, 3, & 4 from s1. We end up with 6, 8, 10 & 12. 2 & 4 were removed and 1 & 3 were ignored since they were not present in s1.
In the last example, we start with the same operation from the second example, we subtract s2 from s1, and we subtract s3 from that result. Removing 5, 6, 7, 8, 9, 10, 11, 12 & 13 from the intermediary set containing 6, 8, 10 & 12 yields an empty set.
Non existing sets are treated as empty sets, which are ignored in the difference operation, similar to a subtraction by zero.
The difference operation is performed on multiple sets, and return a new set, which makes implementing it as an instance method a little bit odd since it operates on multiple sets, as opposed to a single set like most other instance methods. We therefore implement it as a class method on the RedisSet class:
module BYORedis
class RedisSet
# ...
def self.difference(sets)
first_set = sets[0]
return RedisSet.new if first_set.nil?
# Decide which algorithm to use
#
# Algorithm 1 is O(N*M) where N is the size of the element first set
# and M the total number of sets.
#
# Algorithm 2 is O(N) where N is the total number of elements in all
# the sets.
algo_one_work = 0
algo_two_work = 0
sets.each do |other_set|
algo_one_work += sets[0].cardinality
algo_two_work += other_set ? other_set.cardinality : 0
end
# Directly from Redis:
# Algorithm 1 has better constant times and performs less operations
# if there are elements in common. Give it some advantage:
algo_one_work /= 2
diff_algo = (algo_one_work <= algo_two_work) ? 1 : 2
if diff_algo == 1
if sets.length > 1
sets[0..0] + sets[1..-1].sort_by! { |s| -1 * s.cardinality }
end
difference_algorithm1(sets)
else
difference_algorithm2(sets)
end
end
end
end
listing 9.11 The RedisSet.difference class method
Redis uses two different algorithms to perform the set difference operation, while it not possible to know for sure which one will be more efficient, it tries to guess, depending on the size of the sets, which one will be faster.
The first algorithm works by iterating through the first set, and for each element, we look into each other set, as soon we find the element, we stop and move to the next element in the first set. If we make it through all the other sets without finding the element, we add the member to a new set, acting the result set. In other words, the main criteria dictating the "cost" of this algorithm is the size of the first set. The bigger the first set, the more iteration we'll have to perform.
The second algorithm works by creating a new set with all the elements from the first set and then iterate through all the elements in all the other sets, removing each member from the new set. The "cost" of this algorithm is the sum of the cardinalities of all the sets, given that each set will be iterated once.
Redis gives the first algorithm an edge because it seems like it tends to be faster, what this means in practice is that algorithm 2 will only be picked if the first set is significantly bigger than every other sets, in which case we know that its performance would not be ideal by having to iterate over all the items in the first set no matter what and through all the other sets for each member in the first set, and we have a potential shortcut with algorithm 2.
module BYORedis
class RedisSet
# ...
def self.difference_algorithm1(sets)
return RedisSet.new if sets.empty? || sets[0].nil?
dest_set = RedisSet.new
sets[0].each do |element|
i = 0
other_sets = sets[1..-1]
while i < other_sets.length
other_set = other_sets[i]
# There's nothing to do when one of the sets does not exist
next if other_set.nil?
# If the other set contains the element then we know we don't want to add element to
# the diff set
break if other_set == self
break if other_set.member?(element)
i += 1
end
if i == other_sets.length
dest_set.add(element)
end
end
dest_set
end
private_class_method :difference_algorithm1
def self.difference_algorithm2(sets)
return self if sets.empty? || sets[0].nil?
dest_set = RedisSet.new
# Add all the elements from the first set to the new one
sets[0].each do |element|
dest_set.add(element)
end
# Iterate over all the other sets and remove them from the first one
sets[1..-1].each do |set|
set.each do |member|
dest_set.remove(member)
end
end
dest_set
end
private_class_method :difference_algorithm2
def include?(member)
return false if member.nil?
case @underlying
when IntSet then
if member.is_a?(Integer)
member_as_int = member
else
member_as_int = Utils.string_to_integer_or_nil(member)
end
if member_as_int
@underlying.member?(member_as_int)
else
false
end
when Dict then @underlying.member?(member)
else raise "Unknown type for structure #{ @underlying }"
end
end
alias member? include?
# ...
end
end
listing 9.12 The difference_algorithm1 & difference_algorithm2 class methods in RedisSet
Each of these two methods does not need to be exposed and we make them private with private_class_method.
The difference_algorithm1 method implements the first algorithm described above where the first set is iterated over, and all the other sets are iterated over as long as the current member of the first set is not found. We need to add the include? method, aliased to member? to check for the presence of a member in a set.
The IntSet case of include? needs to account for the fact that the argument might already be an Integer or might be a String representing an Integer. We add the Utils.string_to_integer_or_nil method to help for this:
module BYORedis
module Utils
# ...
def self.string_to_integer_or_nil(string)
begin
string_to_integer(string)
rescue InvalidIntegerString
nil
end
end
# ...
end
end
listing 9.13 The string_to_integer_or_nil method in the Utils module
In the Dict case of RedisSet#include? we delegate to the Dict#include? method, through its member? alias, which implements the exact interface we need, so let's add the alias:
module BYORedis
class Dict
# ...
def include?(key)
!get_entry(key).nil?
end
alias member? include?
# ...
end
end
listing 9.14 Adding the Dict#member? aliased to Dict#include?
The second algorithm intends to provide an alternative in case the first set is significantly larger than the other sets.
The next command, SDIFFSTORE is similar to SDIFF, with the difference being that the result is stored in the given key, and the return value is the cardinality of that set.
We have two other very similar methods coming next with SINTERSTORE & SUNIONSTORE so we're using a helper method with the shared logic:
module BYORedis
module SetUtils
# ...
def self.generic_set_store_operation(db, args)
Utils.assert_args_length_greater_than(1, args)
destination_key = args.shift
sets = args.map { |other_set| db.lookup_set(other_set) }
new_set = yield sets
if new_set.empty?
db.data_store.delete(destination_key)
else
db.data_store[destination_key] = new_set
end
RESPInteger.new(new_set.cardinality)
end
end
# ...
class SDiffStoreCommand < BaseCommand
def call
SetUtils.generic_set_store_operation(@db, @args) do |sets|
RedisSet.difference(sets)
end
end
def self.describe
Describe.new('sdiffstore', -3, [ 'write', 'denyoom' ], 1, -1, 1,
[ '@write', '@set', '@slow' ])
end
end
end
listing 9.15 The SDiffStoreCommand class
The SDiffStoreCommand class is extremely similar to SDiffCommand, with the exception that it needs to handle an extra argument at the beginning of the argument list, for the destination key. It then stores the result set at that key, or delete what was there before if the result set is empty. Finally, it returns the cardinality of the result set.
Set Union
The next set operation we will implement is set union, which is defined as:
The union of two sets A and B is the set of elements which are in A, in B, or in both A and B
Let's start by creating the SUnionCommand class:
module BYORedis
# ...
class SUnionCommand < BaseCommand
def call
Utils.assert_args_length_greater_than(0, @args)
sets = @args.map { |set_key| @db.lookup_set(set_key) }.compact
RESPArray.new(RedisSet.union(sets).members)
end
def self.describe
Describe.new('sunion', -2, [ 'readonly', 'sort_for_script' ], 1, -1, 1,
[ '@read', '@set', '@slow' ])
end
end
end
listing 9.16 The SUnionCommand class
We are implementing the union method as a class method on RedisSet for the same reasons we decided to implement difference as a class method.
module BYORedis
class RedisSet
# ...
def self.union(sets)
if sets.empty?
RedisSet.new
else
union_set = RedisSet.new
sets.each do |set|
set.each { |member| union_set.add(member) }
end
union_set
end
end
# ...
end
end
The set union operation is simpler, we iterate over all sets, over all of their members and add each member to a new set, once we're done, we return the set.
Similarly to how we first added the SDIFF command followed by the SDIFFSTORE command, we're now adding the SUnionStoreCommand class.
module BYORedis
# ...
class SUnionStoreCommand < BaseCommand
def call
SetUtils.generic_set_store_operation(@db, @args) do |sets|
RedisSet.union(sets)
end
end
def self.describe
Describe.new('sunionstore', -3, [ 'write', 'denyoom' ], 1, -1, 1,
[ '@write', '@set', '@slow' ])
end
end
end
listing 9.17 The SUnionStoreCommand class
Set Intersection
The final set operation we're going to implement is set intersection, with the SINTER command.
Set intersection is defined as:
In mathematics, the intersection of two sets A and B, denoted by A ∩ B, is the set containing all elements of A that also belong to B (or equivalently, all elements of B that also belong to A).
module BYORedis
module SetUtils
def self.generic_sinter(db, args)
sets = args.map do |set_key|
set = db.lookup_set(set_key)
return RedisSet.new if set.nil?
set
end
RedisSet.intersection(sets)
end
end
# ...
class SInterCommand < BaseCommand
def call
Utils.assert_args_length_greater_than(0, @args)
intersection = SetUtils.generic_sinter(@db, @args)
RESPArray.new(intersection.members)
end
def self.describe
Describe.new('sinter', -2, [ 'readonly', 'sort_for_script' ], 1, -1, 1,
[ '@read', '@set', '@slow' ])
end
end
end
listing 9.18 The SInterCommand class
The logic in SInterCommand shares a lot of logic with SInterStoreCommand, which we'll create next, so we go ahead and create a method with the shared logic BYORedis::SetUtils.generic_sinter. In order to implement this method, we need the intersection class method on the RedisSet class, but before calling this method, we do return early if any of the given keys does not exist. This is an important shortcut, when computing the intersection of sets, if any of the sets is empty, we know that the final result will be an empty sets, and non existing sets are treated as empty sets.
module BYORedis
class RedisSet
# ...
def self.intersection(sets)
# Sort the sets smallest to largest
sets.sort_by!(&:cardinality)
intersection_set = RedisSet.new
# Iterate over the first set, if we find a set that does not contain it, discard
sets[0].each do |member|
present_in_all_other_sets = true
sets[1..-1].each do |set|
unless set.member?(member)
present_in_all_other_sets = false
break
end
end
# Otherwise, keep
intersection_set.add(member) if present_in_all_other_sets
end
intersection_set
end
# ...
end
end
listing 9.19 The RedisSet.intersection class method
Set intersection is not as straightforward as set union but is not at complicated as set difference. We start by sorting all the sets from smallest to largest. Doing the sorting is a small optimization because we have to iterate over all the elements of at least one set, so we might as well pick the smaller one for that.
Once the sets are sorted, we pick the first one, the smallest one, and iterate over all its members, for each member we check its presence in all other sets, as soon as this check is false, we continue to the next member. This is because the result set of the intersection only contains elements present in all the sets.
If we make it through all the sets, then the member is indeed present in all sets and we add it to the result set.
The last set operation command on our list is SINTERSTORE, we've seen this pattern two times already by now. We use the SetUtils.generic_set_store_operation method the same way we did previously:
module BYORedis
# ...
class SInterStoreCommand < BaseCommand
def call
SetUtils.generic_set_store_operation(@db, @args) do
SetUtils.generic_sinter(@db, @args)
end
end
def self.describe
Describe.new('sinterstore', -3, [ 'write', 'denyoom' ], 1, -1, 1,
[ '@write', '@set', '@slow' ])
end
end
end
listing 9.20 The SInterStoreCommand class
With SInterStoreCommand completed, we've now implemented all the set operation commands, SUNION, SINTER & SDIFF, and their *STORE variants.
Membership related operations
SMEMBERS
The SMEMBERS command returns all the members of a set. Sets do not guarantee ordering, so we can just return members without having to worry about ordering. Let's create the SMembersCommand:
module BYORedis
# ...
class SMembersCommand < BaseCommand
def call
Utils.assert_args_length(1, @args)
set = @db.lookup_set(@args[0])
RESPArray.new(set.members)
end
def self.describe
Describe.new('smembers', 2, [ 'readonly', 'sort_for_script' ], 1, 1, 1,
[ '@read', '@set', '@slow' ])
end
end
end
listing 9.21 The SMembersCommand class
We need to add the RedisSet#members command:
module BYORedis
class RedisSet
# ...
def members
case @underlying
when IntSet then @underlying.members.map { |i| Utils.integer_to_string(i) }
when Dict then @underlying.keys
else raise "Unknown type for structure #{ @underlying }"
end
end
# ...
end
end
listing 9.22 The RedisSet#members method
In the IntSet case we call the IntSet#members methods, and convert all in Integer instances to String with the Utils.integer_to_string method. In the Dict case we can directly return from the already existing Dict#keys method.
The conversion to strings in the IntSet case is to follow the behavior of the Redis command, as the following example shows, even if the set is an intset, Redis converts the value to RESP strings before returning them:
127.0.0.1:6379> SADD s 1 2 3
(integer) 3
127.0.0.1:6379> DEBUG OBJECT s
Value at:0x7f88e7004130 refcount:1 encoding:intset serializedlength:15 lru:11187844 lru_seconds_idle:3
127.0.0.1:6379> SMEMBERS s
1) "1"
2) "2"
3) "3"
The quotes around the numbers show us that the array members are indeed strings, and redis-cli would prefix them with (integer) otherwise, but we can use nc to confirm the type of the elements of the array:
> echo "SMEMBERS s" | nc -c localhost 6379
*3
$1
1
$1
2
$1
3
SISMEMBER
SISMEMBER returns an integer acting as a boolean, 1 for true and 0 for false, depending on the presence of the given member in the set:
module BYORedis
# ...
class SIsMemberCommand < BaseCommand
def call
Utils.assert_args_length(2, @args)
set = @db.lookup_set(@args[0])
if set
presence = set.member?(@args[1]) ? 1 : 0
RESPInteger.new(presence)
else
RESPInteger.new(0)
end
end
def self.describe
Describe.new('sismember', 3, [ 'readonly', 'fast' ], 1, 1, 1,
[ '@read', '@set', '@fast' ])
end
end
end
listing 9.23 The SIsMemberCommand class
We delegate the actual work of checking if the set contains the given member to the RedisSet#member? method which we added earlier when adding the SDIFF command.
SMISMEMBER (New in 6.2.0)
module BYORedis
# ...
class SMIsMemberCommand < BaseCommand
def call
Utils.assert_args_length_greater_than(1, @args)
set = @db.lookup_set(@args.shift)
members = @args
if set.nil?
result = Array.new(members.size, 0)
else
result = members.map do |member|
set.member?(member) ? 1 : 0
end
end
RESPArray.new(result)
end
def self.describe
Describe.new('smismember', -3, [ 'readonly', 'fast' ], 1, 1, 1,
[ '@read', '@set', '@fast' ])
end
end
end
listing 9.24 The SMIsMemberCommand class
This command uses the same method from RediSet we used in SIsMemberCommand, but inside the map method, which we use to return an array of integers acting as booleans, 1 if the member is in the set, 0 if it isn't.
SCARD
module BYORedis
# ...
class SCardCommand < BaseCommand
def call
Utils.assert_args_length(1, @args)
set = @db.lookup_set(@args[0])
cardinality = set.nil? ? 0 : set.cardinality
RESPInteger.new(cardinality)
end
def self.describe
Describe.new('scard', 2, [ 'readonly', 'fast' ], 1, 1, 1,
[ '@read', '@set', '@fast' ])
end
end
end
listing 9.25 The SCardCommand class
The command delegates to the RedisSet#cardinality method:
module BYORedis
class RedisSet
# ...
def cardinality
case @underlying
when IntSet then @underlying.cardinality
when Dict then @underlying.used
else raise "Unknown type for structure #{ @underlying }"
end
end
# ...
end
end
listing 9.26 The RedisSet#cardinality method
Both IntSet and Dict already have methods that return what we need here, so we call them and return their results directly.
SRANDMEMBER
module BYORedis
# ...
class SRandMemberCommand < BaseCommand
def call
Utils.assert_args_length_greater_than(0, @args)
raise RESPSyntaxError if @args.length > 2
count = Utils.validate_integer(@args[1]) if @args[1]
set = @db.lookup_set(@args[0])
if set
if count.nil?
random_members = set.random_member
else
random_members = set.random_members_with_count(count)
end
RESPSerializer.serialize(random_members)
elsif count.nil?
NullBulkStringInstance
else
EmptyArrayInstance
end
end
def self.describe
Describe.new('srandmember', -2, [ 'readonly', 'random' ], 1, 1, 1,
[ '@read', '@set', '@slow' ])
end
end
end
listing 9.27 The SRandMemberCommand class
Getting a random element from an IntSet does not require as many steps as it does for a Dict. Given that the structure behind an IntSet is an array, we can pick a random index, between 0 and size - 1, and return the element at that index. As long as the random function we use is "random enough", the element returned will be random. We're using quotes here because the topic of randomness if fairly complicated, luckily Ruby does a lot of the heavy lifting for us, with the Kernel.rand method and the SecureRandom module. The difference between the two different approaches is a little bit out of scope for now, and we'll be using Kernel.rand since it is sufficient for our needs.
On the other hand, getting a random entry for a set using a Dict is way more complicated. It might seem similar at first glance, the data structure powering a hash table is also an array, but some buckets might be empty, so we cannot "just" pick a random index and return the value stored there, given that it could be empty. This problem is not insurmountable, we can add some form of retry logic, until a non empty bucket is found. We also need to take into account that the Dict might be in the middle of the rehashing process, in which case the buckets will be split across two different hash tables. Finally, even if we dealt with these issues, there is still a major issue, buckets contain zero or more entries, and given the nature of the SipHash algorithm, there is no way to expect the distribution of entries across buckets.
In practical terms, this means for a hash of size 8, containing 6 entries, it is entirely possible that five buckets are empty, two contain one element each and that the last bucket contain the other four elements. This means that even after finding a non empty bucket, we now need to select a random entry within that bucket if it contains more than one. Doing so works in the sense of being able to potentially return any of the values contained in the hash, but it completely obliterates the distribution of the result.
Ideally, as we call SRANDMEMBER multiple times, the distribution of the returned element should trend towards the perfect proportion. Using the example from above, if a set contains six elements, each element should have a probability of 1/6 to be returned, but the approach described above might be completely off, let's look at an example.
Note that these examples assume that the Kernel.rand has a perfect distribution, which is not the case, computers cannot be perfectly random, but it is pretty close as the following example shows:
distribution = Hash.new { |h, k| h[k] = 0 }
times = 100_000
times.times do
distribution[rand(1..6)] += 1
end
p Hash[distribution.map { |k, v| [k, v / times.to_f] }]
The previous script returned the following on my machine, the result should be different but pretty close on another machine, or as you run it multiple times:
{1=>0.17011, 2=>0.16645, 6=>0.16604, 5=>0.16696, 4=>0.1657, 3=>0.16474}
The perfect distribution would be 0.166666667, so it's not that far. For example, running the same example with times = 1_000_000 instead returned closer results as expected, the more we run it, the more the results will get closer to the perfect distribution:
{3=>0.166954, 4=>0.16658, 5=>0.16693, 2=>0.166722, 1=>0.166075, 6=>0.166739}
Back to the distribution problem in a hash table, the previous example we mentioned looked like the following, five empty buckets, two with one member each and one with four.
s = { nil, nil, nil, nil, nil, < 1 >, < 2 >, < 3, 4, 5, 6 > }
Each of the bucket has about 1/6 chance of getting picked, but we'll retry as long we pick an empty bucket, so given that there are three non-empty buckets, each of these has about 1/3 change of getting picket. The problem is if the last one get picked, then we need to roll the die one more time, and this time each item will have about 1/4 chance of getting picked, bringing the probabilities of each elements to the following:
1 => 1/3 ~= 0.333333333
2 => 1/3 ~= 0.333333333
3 => 1/3 * 1/4 = 1/24 ~= 0.083333333
4 => 1/3 * 1/4 = 1/24 ~= 0.083333333
5 => 1/3 * 1/4 = 1/24 ~= 0.083333333
6 => 1/3 * 1/4 = 1/24 ~= 0.083333333
To attempt addressing this problem Redis uses two functions, dictGetSomeKeys and dictGetFairRandomKey. It also uses a third function, dictGetRandomKey, which implements the logic we described previously, only as a backup, in case dictGetSomeKeys fails to return any keys.
This approach alleviates some of the issues we described earlier by first randomly selecting keys through the dictionary, putting them in a flat array, and only then picking one random index in this array.
Let's add these methods to our Dict class
module BYORedis
class Dict
# ...
GETFAIR_NUM_ENTRIES = 15
def fair_random_entry
entries = get_some_entries(GETFAIR_NUM_ENTRIES)
if entries.empty?
random_entry
else
entries[rand(0...entries.size)]
end
end
private
def get_some_entries(count)
entries = []
stored = 0
count = used if count > used
maxsteps = count * 10
count.times { rehash_step } if rehashing?
tables = rehashing? ? 2 : 1
maxsizemask = main_table.sizemask
if tables > 1 && rehashing_table.sizemask > maxsizemask
maxsizemask = rehashing_table.sizemask
end
i = rand(0..maxsizemask)
empty_len = 0
while stored < count && maxsteps
iterate_through_hash_tables_unless_rehashing do |hash_table|
# If we're in the process of rehashing, up to the indexes already visited in the main
# table during the rehashing, there are no populated buckets so we can skip in the
# main table, all the indexes between 0 and @rehashidx - 1
if rehashing? && hash_table == main_table && i < @rehashidx
if i >= rehashing_table.size
i = @rehashidx
else
next
end
end
next if i >= hash_table.size # Out of range for this table
hash_entry = hash_table.table[i]
# Count contiguous empty bucket and jump to other locations if they reach 'count'
# with a minimum of 5
if hash_entry.nil?
empty_len += 1
if empty_len >= 5 && empty_len > count
i = rand(0..maxsizemask)
empty_len = 0
end
else
empty_len = 0
while hash_entry
entries << hash_entry
hash_entry = hash_entry.next
stored += 1
return entries if stored == count
end
end
end
i = (i + 1) & maxsizemask # increment and wraparound if needed
maxsteps -= 1
end
entries
end
def random_entry
return if used == 0
rehash_step if rehashing?
hash_entry = nil
if rehashing?
# There are no elements indexes from 0 to rehashidx-1 so we know the only places we can
# find an element are in main_table[rehashidx..-1] and anywhere in the rehashing table
# We generate the random_index between the total number of slots (the two sizes), minus
# the rehashing index. An example, we're growing from 8 to 16 buckets, that's 24 total
# slots, now let's imagine that @rehashidx is 4, we generate an index between 0 and 20
# (excluded), and we add 4 to it, that means that we _never_ have a value under 4.
# If the random index is 8 or more, we need to look in the rehashing table, but we need
# adjust it by removing 8, the size of the main table to it, so say it was initially 19,
# plus four, that' 23, minus 8, that's 15, the last bucket in the rehashing table.
# If the random index is between 4 and 7, then we look directly in the main table
while hash_entry.nil?
max = slots - @rehashidx
random_index = @rehashidx + SecureRandom.rand(max)
hash_entry =
if random_index >= main_table.size
rehashing_table.table[random_index - main_table.size]
else
main_table.table[random_index]
end
end
else
while hash_entry.nil?
random_index = SecureRandom.rand(main_table.size)
hash_entry = main_table.table[random_index]
end
end
# Now that we found a non empty bucket, we need to pick a random element from it, but if
# there's only one item, we can save some time and return right away
return hash_entry if hash_entry.next.nil?
list_length = 0
original_hash_entry = hash_entry
while hash_entry
list_length += 1
hash_entry = hash_entry.next
end
random_list_index = SecureRandom.rand(list_length)
hash_entry = original_hash_entry
random_list_index.times do
hash_entry = hash_entry.next
end
hash_entry
end
end
end
listing 9.28 The new random methods in the Dict class
The three methods we just added to the Dict class implement this better approach to retrieving a random key/value pair. fair_random_entry is the only public one and attempts to use the result from get_some_entries, but due to the nature of the hash table, it is possible that get_some_keys fails to return any keys, in which case we fall back to random_entry, which suffers from the distribution above outlined above, but still returns a random element, just not that random.
Now that Dict is updated, we can implement random_member and random_members_with_count in the RedisSet class:
module BYORedis
class RedisSet
# How many times bigger should be the set compared to the requested size
# for us to don't use the "remove elements" strategy? Read later in the
# implementation for more info.
# See: https://github.com/antirez/redis/blob/6.0.0/src/t_set.c#L609-L612
SRANDMEMBER_SUB_STRATEGY_MUL = 3
# ...
def random_members_with_count(count)
return [] if count.nil? || count == 0
# Case 1: Count is negative, we return that many elements, ignoring duplicates
if count < 0
members = []
(-count).times do
members << random_member
end
return members
end
# Case 2: Count is positive and greater than the size, we return the whole thing
return self if count >= cardinality
# For both case 3 & 4 we need a new set
new_set_content = Dict.new
# Case 3: Number of elements in the set is too small to grab n random distinct members
# from it so we instead pick random elements to remove from it
# Start by creating a new set identical to self and then remove elements from it
if count * SRANDMEMBER_SUB_STRATEGY_MUL > cardinality
size = cardinality
each { |member| new_set_content.add(member, nil) }
while size > count
random_entry = new_set_content.fair_random_entry
new_set_content.delete(random_entry.key)
size -= 1
end
return new_set_content.keys
end
# Case 4: The number of elements in the set is big enough in comparison to count so we
# do the "classic" approach of picking count distinct elements
added = 0
while added < count
member = random_member
added += 1 if new_set_content.add(member, nil)
end
new_set_content.keys
end
def random_member
case @underlying
when IntSet then Utils.integer_to_string(@underlying.random_member)
when Dict then @underlying.fair_random_entry.key
else raise "Unknown type for structure #{ @underlying }"
end
end
# ...
end
end
listing 9.29 The random_member and random_member_with_count methods in the RedisSet class
The random_members_with_count method breaks down the possible scenarios in four different possibilities. "Case 1" is for a negative count value, in which case duplicates are allowed, so we can iterate as many times as needed and select a random member at each step, without having to worry about anything else.
"Case 2" is if count is greater than the size of the set, in which case we don't actually need to select any random members and we can return the whole set.
We differentiate between "Case 3" and "Case 4" depending on how close count is to the size of the set. The idea being that because we can't return duplicates, it might take a while to pick n random members if n is really close to the size of the set. Let's look at an example with a set of size 10, the numbers 1 to 10. If we call SRANDMEMBER set 9, we want to return nine random members, but doing so would require many tries.
Each of the member has a 1/10 change of getting picked, so the first pick will get a random member, but on the second try we have a 1/10 chance of picking the same element, in which case we'd need to try again. As we fill up the result dict, the odds of picking only one of the few non selected members will be really small.
This case if avoided with the if count * SRANDMEMBER_SUB_STRATEGY_MUL > cardinality condition. The constant is set to 15, so with a count value of 10 and a set containing 15 elements, the condition will be true, 10 * 15 > 15.
The condition would only be false with a large enough set and a small enough count value, such as 100 and 2, 2 * 15 > 100 == false.
So, in "Case 3", we instead create a new dict with all the elements from the set, and remove random members until its size reaches count.
"Case 4" is the most straightforward approach, we keep looping and picking random members, until we've picked count unique members.
Removing elements
SPOP
module BYORedis
# ...
class SPopCommand < BaseCommand
def call
Utils.assert_args_length_greater_than(0, @args)
raise RESPSyntaxError if @args.length > 2
if @args[1]
count = Utils.validate_integer(@args[1])
return RESPError.new('ERR index out of range') if count < 0
end
key = @args[0]
set = @db.lookup_set(key)
if set
popped_members = @db.pop_from_set(key, set, count)
RESPSerializer.serialize(popped_members)
elsif count.nil?
NullBulkStringInstance
else
EmptyArrayInstance
end
end
def self.describe
Describe.new('spop', -2, [ 'write', 'random', 'fast' ], 1, 1, 1,
[ '@write', '@set', '@fast' ])
end
end
end
listing 9.30 The SPopCommand class
Similarly to SRANDMEMBER, SPOP accepts a count argument, describing how many items can be returned, contrary to SRANDMEMBER, SPOP does not accept negative count values, and a value of 0 is effectively a no-op, no members are popped.
Let's start with the DB#pop_from_set method:
module BYORedis
class DB
# ...
def pop_from_set(key, set, count)
popped_members = if count.nil?
set.pop
else
set.pop_with_count(count)
end
@data_store.delete(key) if set.empty?
popped_members
end
# ...
end
end
listing 9.31 The DB#pop_from_set method
We now need to add RedisSet#pop and RedisSet#pop_with_count:
module BYORedis
class RedisSet
# ...
# How many times bigger should be the set compared to the remaining size
# for us to use the "create new set" strategy? Read later in the
# implementation for more info.
# See: https://github.com/antirez/redis/blob/6.0.0/src/t_set.c#L413-416
SPOP_MOVE_STRATEGY_MUL = 5
# ...
def pop
case @underlying
when IntSet then @underlying.pop.to_s
when Dict then
random_entry = @underlying.fair_random_entry
@underlying.delete(random_entry.key)
random_entry.key
else raise "Unknown type for structure #{ @underlying }"
end
end
def pop_with_count(count)
return [] if count.nil? || count == 0
# Case 1: count is greater or equal to the size of the set, we return the whole thing
if count >= cardinality
all_members = members
clear
return all_members
end
remaining = cardinality - count
if remaining * SPOP_MOVE_STRATEGY_MUL > count
# Case 2: Count is small compared to the size of the set, we "just" pop random elements
count.times.map { pop }
else
# Case 3: count is big and close to the size of the set, and remaining is small, we do
# the reverse, we pick remaining elements, and they become the new set
new_set = RedisSet.new
remaining.times { new_set.add(pop) }
# We have removed all the elements that will be left in the set, so before swapping
# them, we store all the elements left in the set, which are the ones that will end up
# popped
result = members
# Now that we have saved all the members left, we clear the content of the set and copy
# all the items from new_set, which are the ones left
clear
new_set.each { |member| add(member) }
result
end
end
# ...
end
end
listing 9.32 The pop & pop_with_count methods in RedisSet
pop is straightforward in the IntSet case given that we already implemented the IntSet#pop method, we can call it and directly return from it.
On the other hand, the Dict case is trickier and we now use the newly created Dict#fair_random_entry method, to find which entry to delete from the set.
pop_with_count is optimized to handle a few different edge cases elegantly. We label "Case 1" the case where the count value is greater than or equal to the cardinality of the set, and can return all the members, and clear the set.
In the case where count is anywhere between 1 and cardinality - 1, we do need to find random elements to remove from the set and return them. While it may seem like a simple problem at first, just iterate count times and pop a random element at each iteration, the reality is a little bit more complicated. The problem is that the process of popping random element can get expensive if the count number is very large, so instead we use an arbitrary threshold and if count is big enough that it is too close to the cardinality of the set, we reverse the process. We only pop the number of elements that should be left in the set, set them aside, extract all the remaining elements from the set, return them and add back the small set of remaining elements in the set.
Looking at a set of 10 elements as an example, if count is 9, then remaining * SPOP_MOVE_STRATEGY_MUL is 5, which is not greater than 9, so we fall in "Case 3". In the case where count is 8, then 2 * 5 = 10, which is greater than count, so we pop eight times from the set, that's "Case 2".
SREM
module BYORedis
# ...
class SRemCommand < BaseCommand
def call
Utils.assert_args_length_greater_than(1, @args)
set = @db.lookup_set(@args.shift)
remove_count = 0
if set
@args.each do |member|
remove_count += 1 if @db.remove_from_set(key, set, member)
end
end
RESPInteger.new(remove_count)
end
def self.describe
Describe.new('srem', -3, [ 'write', 'fast' ], 1, 1, 1,
[ '@write', '@set', '@fast' ])
end
end
end
listing 9.33 The SRemCommand class
SREM relies on DB#remove_from_set, let's add it:
module BYORedis
class DB
# ...
def remove_from_set(key, set, member)
removed = set.remove(member)
@data_store.delete(key) if set.empty?
removed
end
# ...
end
end
Let's now add RedisSet#remove to complete the SREM implementation:
module BYORedis
class RedisSet
# ...
def remove(member)
case @underlying
when IntSet
member_as_integer = Utils.string_to_integer_or_nil(member)
if member_as_integer
@underlying.remove(member_as_integer)
else
false
end
when Dict then !@underlying.delete_entry(member).nil?
else raise "Unknown type for structure #{ @underlying }"
end
end
# ...
end
end
listing 9.34 The RedisSet#remove method
Up until now the Dict#remove method used to return the value of the deleted pair, or nil if the dict did not contain the given key. The problem with this approach is that if the value stored in the Dict was nil, the caller would not be able to differentiate the successful deletion of a pair, or a "miss" if the dictionary did not contain the key.
Similarly to how we initially implemented the get method by using the lower level method get_entry, we are adding the delete_entry method, which returns the full DictEntry instance for a successful deletion. With this change, callers can now know that a nil value is indeed a miss whereas a DictEntry instance, regardless of what the value of the value field is, is a successful deletion.
module BYORedis
class Dict
# ...
def delete_entry(key)
return if main_table.used == 0 && rehashing_table.used == 0
rehash_step if rehashing?
hash_key = SipHash.digest(RANDOM_BYTES, key)
iterate_through_hash_tables_unless_rehashing do |hash_table|
index = hash_key & hash_table.sizemask
entry = hash_table.table[index]
previous_entry = nil
while entry
if entry.key == key
if previous_entry
previous_entry.next = entry.next
else
hash_table.table[index] = entry.next
end
hash_table.used -= 1
return entry
end
previous_entry = entry
entry = entry.next
end
end
nil
end
def delete(key)
delete_entry(key)&.value
end
# ...
end
end
listing 9.35 The delete & delete_entry methods in the Dict class
The delete method is now written in terms of delete_entry. The &. operator allows us to concisely return nil from delete if delete_entry returned nil itself, in the case where the Dict does not contain key. If the value field of the DictEntry is nil, then callers of delete have no way of differentiating a miss, when the Dict does not contain key, and a successful deletion. If this is important to the callers, which in the case in SRemCommand, then callers can use delete_entry instead.
SMOVE
SMOVE is used to remove a member from a set and add it to another
module BYORedis
# ...
class SMoveCommand < BaseCommand
def call
Utils.assert_args_length(3, @args)
source_key = @args[0]
source = @db.lookup_set(source_key)
member = @args[2]
destination = @db.lookup_set_for_write(@args[1])
if source.nil?
result = 0
else
removed = @db.remove_from_set(source_key, source, member)
if removed
destination.add(member)
result = 1
else
result = 0
end
end
RESPInteger.new(result)
end
def self.describe
Describe.new('smove', 4, [ 'write', 'fast' ], 1, 2, 1,
[ '@write', '@set', '@fast' ])
end
end
end
listing 9.36 The SMoveCommand class
If the source set does not exist, there is nothing to do since we have no set to remove member from. If it does exist, then we call DB#remove_from_set, which we added earlier for the SREM command, if it returns true then we add the member in destination. Note that we return 1 as long as member was found in source, even if it was already in destination.
This wraps up the last set command!
Conclusion
You can find the code on GitHub.
With set commands implemented, we now have one last native data type left, sorted sets, and this is what Chapter 10 will cover.
Appendix A: A more idiomatic IntSet
The IntSet class we created earlier in the Chapter was trying to replicate as much as possible the logic used in intset.c in Redis, at the cost of not being really idiomatic Ruby. If we were to set aside the encoding, and use the Ruby Integer class as provided, we can end up with a simpler implementation:
module BYORedis
class IntSet
def initialize
@underlying_array = []
end
def add(member)
raise "Member is not an int: #{ member }" unless member.is_a?(Integer)
index = @underlying_array.bsearch_index { |x| x >= member }
if index.nil?
@underlying_array.append(member)
true
elsif @underlying_array[index] == member
false
else
@underlying_array.insert(index, member)
true
end
end
# ...
end
end
listing 9.37 The initialize & add methods in the IntSet class
The first thing we do in add is check that the argument is indeed an Integer, and abort if it isn't. It is up to callers of these methods to do the due diligence of calling this method with the correct argument type.
The next step is to find where in the array should the new element be added, and we use the bsearch_index method for that. By giving the block { |x| x >= member } block to the method, it will return the smallest index of an element that is greater than or equal to member. If no elements are greater than or equal to member, then it returns nil.
Based on these cases, there are three cases we need to consider, the first one, if index is nil, means that no elements in the array are greater than or equal to member, in other words, member is now the member with the largest value, and we should add it at the end of the array. This is what we do with the Array#append method.
Next is the case where index is not nil, and in this case there are two options, the value at index is either equal to member, or greater than member. If the value is equal to member, it means that there is already an Integer in the array with the same value as member, and it means that we have nothing to do, the member is already present.
The last case is if the value at index is greater than member. bsearch_index guarantees that if returned the smallest index of all the values greater than member, so we need to add member right before this element, and this is what Array#insert does, it inserts the given value before the element with the given index.
The next main method is the ability to check for the presence of a member in the set, this is what the include? method does:
def include?(member)
return false if member.nil?
!@underlying_array.bsearch { |x| member <=> x }.nil?
end
alias member? include?
listing 9.38 The IntSet#include? method
We're following Ruby's Set class naming convention here, naming the method include?, also accessible through the member? alias. We'll use the member? method throughout this chapter to use the same language used by the Redis commands such as SISMEMBER.
The include? methods relies almost exclusively on the bsearch method, which we've indirectly explored previously through its close sibling bsearch_index. Both methods use a similar API, the difference being that bsearch returns an element from the array whereas bsearch_index returns the index of an element. Both could have been used here given that the returned value itself is not that important, we already really care whether or not the result is nil.
These bsearch methods have two modes of operation, which can be a bit confusing these the mode is decided implicitly depending on the return value of the block passed to the method. The two modes are find-minimum & find-any. We've only used the find-minimum mode so far, by passing the block { |x| member <=> x } to the method, we end up using the find-any mode, because the Integer#<=> method returns an integer, -1, 0 or 1. The Ruby documentation of the method is surprisingly not clear at describing the behavior of this mode, on the other hand the man page of bsearch(3), accessible with man 3 bsearch, which is what the find-any mode is based after is a little bit more helpful:
The contents of the array should be in ascending sorted order according to the comparison function referenced by compar.
The compar routine is expected to have two arguments which point to the key object and to an array member, in that order. It should return an integer which is less than, equal to, or greater than zero if the key object is found, respectively, to be less than, to match, or be greater than the array member.
We need to "translate" this description given that it describes the C function, not the Ruby one, but the compar function is essentially very similar to the block argument, and the key object is the argument to the method, member in the include? method.
With that said, what the documentation tells us is that the block should return 0 if both values are equal, a negative value if member is less than x, and a positive value if member is greater than x. The <=>, often called "spaceship operator", does exactly that!
Using this block, bsearch will return the value if it finds it, or nil if it can't find it.
Let's now add the ability to remove an element from a set with the remove method:
def remove(member)
index = @underlying_array.bsearch_index { |x| member <=> x }
if index
@underlying_array.delete_at(index)
true
else
false
end
end
listing 9.39 The IntSet#remove method
The method method uses the bsearch_index method in a way almost identical to how the include? method uses the bsearch method. By using the Interger#<=> method, we will either receive the index of member in the array, or nil. If index is nil, there's nothing to remove, so we can return false and call it a day. On the other hand, if index is not nil, we use the Array#delete_at method, which deletes the element at the given index.
Let's now add the pop and random_member methods, which both behave very similarly, with the exception that random_member does not remove any elements from the array:
# ...
def pop
rand_index = rand(@underlying_array.size)
@underlying_array.delete_at(rand_index)
end
def random_member
rand_index = rand(@underlying_array.size)
@underlying_array[rand_index]
end
listing 9.40 The pop, & random_member methods in the IntSet class
Finally, we need a few more methods to provide an easy to use API for the IntSet class, namely, the methods empty? to check if the sets is empty or not, members, to return all the members in the set, cardinality, to return the size of the set, and each, to provide a way to iterate over all the members in the set. Ruby gives us tools that allow us to provide these methods without having to explicitly define them. We're using the Forwardable module to delegate some methods directly to the Array instance, @underlying_array. We're also using the alias keyword to provide some of these methods through the same naming conventions used in Redis. We also use the attr_reader approach to create an accessor for the @underlying_array instance variable, and alias it to members to provide a more explicit method name:
require 'forwardable'
module BYORedis
class IntSet
extend Forwardable
attr_reader :underlying_array
def_delegators :@underlying_array, :empty?, :each, :size
alias cardinality size
alias card cardinality
alias members underlying_array
def initialize
@underlying_array = []
end
# ...
end
end
listing 9.41 The members, empty?, each & cardinality methods in the IntSet class
And with these aliases, we now have completed the IntSet class, let's now use it, in combination with the Dict class, to implement the Set commands, starting with the one allowing us to create a new set.
Top comments (0)