Which queues are possible to implement on a distributed database-backended variables?

Skip to first unread message


Dec 13, 2018, 1:54:14 AM12/13/18
to Scalable Synchronization Algorithms
I've wrote a Redis database-mapper for Zshell. Basically, you can bind e.g. scalar Zsh variable to STRING Redis field:

% ztie -d db/redis -a "" -SL string redis_string_var

or an array Zsh variable to LIST Redis field:

% ztie -d db/redis -f "" -SL list rd_list_var

and for other field types like HASH (zsh-hash), SET (zsh-array), SortedSET (zsh-hash). Then, one can use the variables in shell, like:

% redis_string_var=":: Hello Word ::"
% redis_list_var+=( elem1 'elem2' "elem3" )

The problem is that these database accesses aren't allowed for concurrency, because:

1. redis_list_var assignment (even if it's `+=', not `=') first reads all elements of the array, then deletes the list in second step, and then assigns the new values in a loop, i.e. in multiple steps invoking RPUSH (right-side append do the Redis list).
2. This is required by the Zshell internals, where there is only GSU, i.e. getter and setter BUT the third is unsetter. So the expected U-update is actually initial uncontrolled read and concatenation (in case of +=), and then just S-set with the whole new value.
3. I plan to write optimized *functions* (Zsh builtins) like ztappend {r|l} {var_name} {value}, to deal with that, now I'm just glad that I've reached a working, well tested (even with Valgrind automatic tests developed for this) base setup.
4. So even in case of string variable, += will result in read + concatenation + S-set, no U-update that would use some Redis append atomic instruction.

There is a nice use case for this – shell shared variables, also between machines. I have working setup between a shell account, a DigitalOcean droplet box and my home-box, through socat-based SSL tunnel (Redis network support is only a plain text, as it is designed to run at backend).

Having experience with the wait-free, lock-free queues I would want to implement some of them on this zredis-setup. I was writing the wiat-free and other queues 10 years ago, I basically forgot what they do require. Basing on the description, could one tell which queues are possible?

Best regards,
Reply all
Reply to author
0 new messages