DKVS: Distributed Key-Value Store --- values processing

Introduction

The aim of this week's work is to create a series of tools for manipulating content associated with keys, such as:

concatenate values;
extract a substring from a value;
search for a substring within a value.

These tools follow the same general pattern:

request one value (or more if needed) via its/their key;
perform the necessary operations;
if needed, store the result as the value of a given key.

Examples are given below.

NOTE: just this once won't hurt, but the fact that we're asking you to code these tools in 3 separate source files might lead to a bit of "copy and paste" (between these files). A better alternative would have been to increase the genericity of the requested code and use pointers to functions; but in the end we didn't choose this (better) solution as it would have been too cumbersome for this project (requiring too much work in total).

I. `dkvs-client find`

The purpose of the dkvs-client find command (to be written in dkvs-client-find.c) is to return the position of a substring (value associated with a key) searched for in a value associated with (another) key. It takes two keys as arguments and returns the position of the value of the second key within the value of the first key. For instance, with the fake2.h fake network, which contains:

a: hello a
bb: hello bb
ab: hello ab
bbb: hello bbb

we would have:

$ ./fake-dkvs-client-2 find -- ab a
OK 0

$ ./fake-dkvs-client-2 find -- a ab
OK -1

$ ./fake-dkvs-client-2 find -- ab invalid_key
FAIL
ERROR: Not found
[+ help text]

$ ./fake-dkvs-client-2 find -- a
ERROR: Invalid command
[+ help text]

$ ./fake-dkvs-client-2 find
ERROR: Invalid command
[+ help text]

The position returned is the one furthest to the left (reading direction), starting from 0 (see example above). If the substring is not found, the returned position is -1 (see example above). Note that here (dkvs-client find), only positive positions are returned if the substring is found; thus the negative value $-1$ (the only possible negative value for return) indicates a "not found" (unlike the meaning of negative positions in dkvs-client substr below).

The dkvs-client find command will simply reply "OK position\n" or "FAIL\n" depending on whether all the operations performed were successful and led to the position (including -1 when not found), or whether one of them failed. Not finding the required substring is not considered a failure, but simply returns the value -1 as the position.

II. `dkvs-client substr`

The purpose of the dkvs-client substr command (to be written in dkvs-client-substr.c) is to extract a substring from a value and store the result associated to a new key (or overwrite the value of an existing key). The dkvs-client substr command therefore takes as arguments:

a key;
a position (see details below);
a length;
a key;

and:

retrieves the value associated with the first provided key;
extracts the corresponding substring as explained below;
stores this substring as the (new) value associated with the second key supplied.

For example, with the fake2.h fake network (more explanation below, read further):

$ ./fake-dkvs-client-2 substr -- bbb 2 5 new_key
[...]
bbb: hello bbb
new_key: llo b
--------------------------------
OK

$ ./fake-dkvs-client-2 substr -- bbb 0 1 new_key
[...]
bbb: hello bbb
new_key: h
--------------------------------
OK

$ ./fake-dkvs-client-2 substr -- bbb 0 9 new_key
[...]
bbb: hello bbb
new_key: hello bbb
--------------------------------
OK

$ ./fake-dkvs-client-2 substr -- bbb -1 1 new_key
[...]
bbb: hello bbb
new_key: b
--------------------------------
OK

$ ./fake-dkvs-client-2 substr -- bbb -5 4 new_key
[...]
bbb: hello bbb
new_key: o bb
--------------------------------
OK

$ ./fake-dkvs-client-2 substr -- bbb 3 new_key
ERROR: Invalid command
[+ help text]

$ ./fake-dkvs-client-2 substr -- bbb 3 7 new_key
FAIL
ERROR: Invalid command
[+ help text]

$ ./fake-dkvs-client-2 substr -- bbb 3 -1 new_key
FAIL
ERROR: Invalid command
[+ help text]

$ ./fake-dkvs-client-2 substr -- bbb -2 3 new_key
FAIL
ERROR: Invalid command
[+ help text]

The required substring is indicated by two integers: position and length. Position is measured positively from 0 in the read direction, or negatively from -1 in the reverse direction from the end of the string; length is simply the number of characters required (always greater than or equal to 0), with 0 indicating an empty string.

Example illustrating all positive and negative positions (without their sign) for the word "example", then some examples of interpretation of the two parameters position and length:

string:            example
positive position: 0123456
negative position: 7654321
length:            1234567
******************************

position length --> result

   0 2 --> ex
   1 1 --> x
   4 3 --> ple

  -1 1 --> e
  -2 2 --> le

   2 0 --> "" (empty string)
  -2 0 --> ""

   5 3 --> FAIL
  -1 2 --> FAIL
   5 -3 --> FAIL

The dkvs-client substr command will simply answer OK\n or FAIL\n depending on whether all the operations performed were successful or one of them failed. A length that is too long also corresponds to a failure, as shown in the example above.

To handle the position and length parameters, we highly recommand you make use of the atouint64() function which is provided in the new version of util.[ch] (copy them again from provided). This function converts a string to an uint64_t. In case of error, it returns 0 and sets errno to ERANGE (from errno.h). Notice also that if the string contains a negative number (greater than -UINT64_MAX), it is silently converted to a positive number inside the 0-UINT64_MAX range. You thus have to do a bit of arithmetics then. Pay attention not to overflow when doing so.

Note: the dkvs-client-substr command is therefore a simple way of copying a value to another key; for example:

$ ./fake-dkvs-client-2 substr -- bbb 0 9 new_key
[...]
bbb: hello bbb
new_key: hello bbb
--------------------------------
OK

Notice also that you can overwrite the same key:

$ ./fake-dkvs-client-2 substr -- bbb 1 4 bbb
[...]
ab: hello ab
bbb: ello
--------------------------------
OK

III. `dkvs-client cat`

The purpose of the dkvs-client cat command (to be written in dkvs-client-cat.c) is to concatenate the values of several keys and store the result under a new key (or overwrite the value of an existing key). For example, with the fake2.h fake network:

$ ./fake-dkvs-client-2 cat -- ab bbb new_key
[...]
new_key: hello abhello bbb
--------------------------------
OK

$ ./fake-dkvs-client-2 cat -- bbb ab a ab new_key
[...]
new_key: hello bbbhello abhello ahello ab
--------------------------------
OK

$ ./fake-dkvs-client-2 cat -- bbb ccc new_key
[...]
FAIL
ERROR: Not found
[+ help text]

The dkvs-client cat command therefore takes one or more existing keys as input, performs as many "get" operations to obtain the corresponding values and concatenates them, without any separator character, to finally store this result as the value associated with the key received as the last parameter (see examples above).

This command will simply answer "OK" or "FAIL" depending on whether all the operations performed were successful or one of them failed (see example above).

Note: this command can also be used to simply copy a value to another key (existing or not), for example:

$ ./fake-dkvs-client-2 cat -- ab bbb
[...]
ab: hello ab
bbb: hello ab
--------------------------------
OK

$ ./fake-dkvs-client-2 cat -- ab new_key
[...]
ab: hello ab
bbb: hello bbb
new_key: hello ab
--------------------------------
OK

IV. Testing and debugging

As usual, we provide you with a few tests, only end-to-end tests this time, in provided/tests/end-to-end. We still strongly recommend you to add your own tests after copying them into your done/ directory.

DKVS: Distributed Key-Value Store --- values processing

Introduction

I. dkvs-client find

II. dkvs-client substr

III. dkvs-client cat

IV. Testing and debugging

I. `dkvs-client find`

II. `dkvs-client substr`

III. `dkvs-client cat`