Pencil

Reader

Read the latest posts from Pencil.

from Bunker Labs

I saw people being confused about message queues, so I figured I'd implement one in shell, just for fun. This would also let us explore the common pitfalls in implementing them.

What is a Message Queue?

A message queue is conceptually simple – it's a queue. You know, like the opposite of a stack. You put stuff in it, and later you can take stuff out. The “stuff” are messages. Of course, there is a very limited use-case to having a single queue. So instead, you want to have multiple, “named” queues (i.e “collections”).

Another part of a message queue is how you access it. There is a common type of MQ (Message Queue) called “pub/sub” – in this scheme, the MQ server keeps open connections to all the “subscribers” and sends all of them the message whenever it arrives. The other one is poll-based – the queue keeps each message until it gets explicitly read by a connection, via some sort of “reserve” keyword. This latter type is what we'll be implementing.

So, we have a few basic operations to implement:

  • Write a message to a named queue.
  • Read a message from a named queue.

That's really all there is to it! So let's get to implementing.

Storage Format

We can keep a queue in a flat file. We'll call it "$queue".queue. This allows us to have almost free writes – we just append to the file. Let's not worry about networking for now and write this down in ./lib/push.

# add message from stdin to queue
cat >> "$queue".queue

This has an obvious potential issue: shell operates line-wise, so what if the message we're writing is longer than a one-liner? We'll use the base64 utility. Note that it isn't part of POSIX, but neither is nmap's ncat (which we're going to be using for networking later), with both being extremely common.

We can now rewrite the above like this:

# add message from stdin to queue
base64 >> "$queue".queue

We're still assuming that we're going to get the message via stdin (somehow), and that the queue environment variable will be populated with the queue name.

Still, this storage format is pretty simple – the messages are listed, in order, oldest first, one per line. We can guarantee the “one per line” part because we base64-encode the messages.

Reading Just One Message

We need a way to pop items off the queue. Since we can guarantee there's only one message per line, it means getting the first message (first line) and everything else separately. Let's write a simple utility ./lib/pop that will print the topmost message (decoded), and truncate the old file.

# print message
head -n1 "$queue".queue | base64 -d
# get remaining messages
tail -n+2 "$queue".queue > "$queue".cut
# move post-cut queue into the true queue
mv "$queue".cut "$queue".queue

This has a few obvious disadvantages – it's full of crash-related race conditions. It does do the job, though, so we'll keep it for now.

Networking

We're going to use nmap's netcat implementation to handle networking for us. Initially, it'll look roughly like so, in ./launch:

export PATH="$(dirname $0)/lib:$PATH"
while ncat -l 1234 -c handler; do :; done

This will repeatedly make netcat listen on port 1234. Once a connection arrives, it'll run the handler binary found in PATH. Stdin of handler will be filled with data from the network pipe, and whatever handler prints to stdout will be sent back. Notably, stderr will not be sent over.

Let's write this handler, then: ./lib/handler:

#!/bin/sh
read cmd queue
[ -z "$queue" ] && queue=default
export queue

case "$cmd" in
pop) . pop ;;
push) . push ;;
esac

exit 0

This determines our wire format. The first line sent by the server will contain the command, followed by spaces or tabs, followed by an optional queue name. If there is no queue name, we assume the name is “default”. Currently, valid commands are “pop” and “push”, which run our previously made commands in .. Finally, after handling is done, we successfully quit.

If we want to add more commands, we can do it in the case "$cmd" section later.

Trying it Out

Let's launch it! ./launch

We can connect and see how things behave:

ncat localhost 1234
pop
^D # no output

ncat localhost 1234
push
package 1
^D

ncat localhost 1234
push
package 2
^D

ncat localhost 1234
pop
^D # package 1

Well, that's fun, it's already functional! We can improve it, however.

Crash Race Conditions

We're designing a serious MQ, so we need to think about potential failures. What if the process crashes during a transaction!? We should consider this.

If the launcher loop dies, the server is dead, not much surprise there, so we can ignore it. What if we pop, but crash after sending the data back, but before truncating the old data? This is actually relatively likely with larger queues because we need to process the entire file every time. Let's fix this by implementing a rudimentary rollback journal (first, without actually using it):

CUT="$queue".cut
OUT="$queue".out
QUEUE="$queue".queue

# determine message to send
head -n1 "$QUEUE" | base64 -d > "$OUT"

# calculate remaining messages
tail -n+2 "$QUEUE" > "$CUT"

# move post-queue into the true queue
cp "$CUT" "$QUEUE"

# send the message
cat "$OUT"

# delete rollback journal
rm "$CUT" "$OUT"

We now have a multipart rollback journal. Let's say we crashed before sending the message, and wanted to manually roll back the transaction. We could do that! We would need to write a base64 encoding of $OUT to a file, then append that file with $CUT, and we would have the old state back.

It bears noting that this is not how rollback journals are typically implemented – usually they're implemented by making a copy of the data, then operating on the “real” dataset, with rollback triggering a copy back, and a commit triggering a deletion of the journal. This non-traditional approach allows us to also keep the last transaction in mind for potential repeating, since we want to avoid dropping any jobs.

Of course because we have a queue, the actual state never has to be rolled back. New writes can be added to the state with no problem, and new reads can simply use the rollback journal's data as-is. With this understanding, we can now utilize it:

CUT="$queue".cut
OUT="$queue".out
QUEUE="$queue".queue

# create rollback journal if we don't have one yet
if ! [ -f "$CUT" ]; then
    # this step is idempotent
    head -n1 "$QUEUE" | base64 -d > "$OUT"
    tail -n+2 "$QUEUE" > "$CUT"
fi

# we might have been interrupted last round
# but this is idempotent
# so always do it
cp "$CUT" "$QUEUE"

# finish transaction and delete the rollback journal
cat "$OUT"
rm "$CUT" "$OUT"

Now the operations that take a while (the head, tail, and cp invocations) are guarded by the rollback journal. The only place where corruption can occur is between printing sending the message over and deleting the rollback journal. Furthermore, the consequence of this crash would simply be a repeat send of the message (a much less disastrous consequence than dropping a message).

We didn't eliminate the crash race condition per se, we simply reduced the odds of it triggering dramatically with only a handful of additional lines of code.

Let's take a similar approach for the push operation, but with a copy-on-write (CoW) write-ahead log (WAL). The idea behind the write-ahead log is that doing a verbatim write is faster than an append with post-processing, and that we can resume the post-processing later if need be. Let's look at what kind of workflow we expect to have:

QUEUE="$queue".queue
WAL="$queue".wal

# we perform a fast write
cat > "$WAL".1

# then we do the processing
base64 "$WAL".1 > "$WAL".2

# and the appending
cat "$QUEUE" "$WAL".2 > "$WAL".3

# then we commit
cp "$WAL".3 "$QUEUE"
rm "$WAL".*

As far as the client is concerned, as long as we do those other steps later, the push is done as soon as $WAL.1 is created. The processing can be done “in the background”, between invocations. Let's write the processor wal first:

QUEUE="$queue".queue
WAL="$queue".wal

# there's a transaction to handle
if [ -f "$WAL".1 ]; then
    [ -f "$WAL".2 ] || base64 "$WAL".1 > "$WAL".2
    # we always repeat this step,
    # in case a read has already changed the queue
    cat "$QUEUE" "$WAL".2 > "$WAL".3
    cp "$WAL".3 "$QUEUE"
    rm "$WAL".*
fi

Now we can call it as a part of our launcher loop:

#!/bin/sh
export PATH="$PWD/lib:$PATH"
# process any remaining transactions
checkpoint() (
    for queue in *.queue; do
        queue=$(basename "$queue" .queue)
        . wal
    done
)
checkpoint
while ncat -l 1234 -c handler; do
    # if the handler crashed, we can catch it here
    checkpoint
done

Just as before – we didn't entirely eliminate the crash race condition. After all, the server could crash in the middle of a push. And if we added a notification for completed pushes, the notification could fail to come, while the push would happen. However, we've significantly reduced the odds of queue corruption, to the point where we can avoid worrying about it as much.

Notably, this approach results in potentially missed or corrupted writes, as opposed to potential double-writes. This is to demonstrate how that's done, as opposed to the double-read philosophy we took with pop.

Parallelism

At this point, the server is done, if we're content with a single thread! What if two clients connect simultaneously? As of currently, they can't.

I'm done messing around for today, though, so maybe a follow-up (in a branch) will be made to provide parallelism.

You can find this version of the server over on github.

 
Read more...

from Hannah's Tip Corner

After getting lost in the UHS trying to find out what I was missing, I decided to compile a few hints that seem to work for pretty much everything. I have played and watched a couple of P&C's myself, and I can say that Syberia 1 does things a little differently. For one, there's no “combination” mechanic; you can use everything as-is.

In fact, some people have gone as far as claiming that this is less of a puzzle game and more of an interactive novel. For this reason, if you have the patience to sit through endless conversations and read through documents in seek for hints, this is probably what I'd consider the easiest P&C I've played.

Table of contents

Comparing different releases

PC (Steam) release (tested on Fedora 35):

  • Regular Proton crashes; use GE instead.
  • It will only run in 800x600 windowed mode. dgVoodoo seems to do nothing via Wine, and Dxwnd will crash as soon as you try to set a higher window size.
  • Recommended to use accessibility tools (you need to read documents to get hints).
  • Includes a complete PDF walkthrough if you open the system files.
  • You need to manually hide the cursor, or it will overlap the in-game cursor. Furthermore, it seems that this can only be achieved on X11.

Switch (Syberia 1 & 2) release:

  • There are two alternative modes — touchscreen and controller. Touchscreen mode highlights all elements you can interact with at every moment. Controller mode scrolls through all elements you can interact with, but it does not show them all at once.
  • Phone will not let you use the number pad (phone numbers are added to your contact list automatically).
  • Long dialogues scroll very fast. There are several languages to choose from, so choose one you can understand by hearing. Languages available: German, English, Spanish, French, Italian, Russian, Polish and Japanese.
  • Autosave every time you do something or move from one screen to the next.
  • Bonus content you unlock as you progress (concept sketches, as far as I've seen so far).

DS release:

  • No voice acting.
  • Menu is displayed on the top screen. Touchscreen replaces the mouse.
  • Number pad is hidden.
  • Cinematics look mostly like they do on PC (it seems to be a direct port, after all).
  • Drag items to use them.
  • On the items menu, drag items below the Read sign (not onto).

Have you covered every conversation topic?

I am the kind of person that tries to get to know every NPC, but I know people who just skips dialogue and skims through. In here, you pretty much need to go out of your way to hit every conversation topic at least once. Not only they're giving you hints (duh), but some events are only triggered after hitting the right conversation topics.

Listen to the phone calls, too!

Considering phone calls come from nowhere and disrupt the flow, I wouldn't be surprised if you wanted to ignore them. However, phone calls are also important in the game, as one character will give you a hint you need to use later on.

Maybe you need to check the leaflets again!

I also tend to read every item description and every book, trying to get as much of the lore as possible for extra flavour. This is actually a common trope (2x duh), but sometimes the tips are actually in a leaflet (or a book, or a newspaper cutout, or a-) that you read a long while ago and have forgotten about since.

Talk with the NPCs again! (And listen to them again)

This game seems to be heavy on conversation; you really need to invest yourself in the characters for the plot to progress. Not only is this game lacking combination items, but it also seems to be lax in item usage altogether (at least early on). And remember – they're giving you hints, you need to listen (3x duh)!

A small puzzle spoiler, not saying which one

There is one puzzle where you will only get through after having a back-and-forth conversation with three different parties. You don't need to hit every conversation topic every single time, you will know what you need to choose, but bear this in mind before trying to look for missing items for the upteenth time.

 
Read more...