Part 50: Let's go RAIDing

Part 50 - Let's go RAIDing


=== Trash World Inbox ===

Last time, hacking the school, I got 710, 55 and 8 as best scores.

We got one improvement from Quackles this week.

As always, Quackles' extensive documentation speaks for itself. I like that the unroll allows you to skip lunch (although don't do that IRL too often).

It is indeed easy to change your code to get the activity all the way down to 3. As you say, put all the code in one big EXA, then REPL XB off after the initial LINK 800. Since the original XA is holding file 300 it can go on to the grade-11 host. The other activity point comes from that KILL which can be removed if the messenger, when done, also sends a 0 in LOCAL mode, and the writer checks for that the same way the reader did (temporarily store it in T, try an FJMP, then copying it to X).


=== Personal Storage Array ===




OST: Code and Registers

Alright, so x10x10x stored their anime on a drive array with three disks where all data is copied across all the disks for redundancy. However, this redundant array of independent disks is completely failing and it's up to us to retrieve their anime. Let's look at the assignment first.

- The data on this drive array is duplicated across three drives for redundancy, with a file name index stored in the controller (file 200). Unfortunately, the drive array is failing.
- For each file stored in the drive array, create a file in your host that contains the file name and data. Some values are corrupted and will read as a keyword (FAIL) instead of a number. You will need to read these values from a different drive that is not corrupted.
- Note that some links may be unreliable as a result of the drive array's impending failure.

That's not good. That drive is completely busted and I'll be lucky if I can get anything off of it.

The third point means that links 801, 802 and 803 will sometimes just disappear and then return a couple cycles later. If that happens during M transmission, well, the EXA will just wait. But if that happens when the EXA tries to LINK there, it will run into a wall and die.

Because everything is so unreliable, I'm going to handle the individual drives one by one. It'll be slower than parallelization but I have no idea how to make any sense of concurrent global M communication if links just randomly drop.


I have to admit, this puzzle gave me more trouble than I expected. It's mostly that whenever I thought I had all parts working together, one or two tests would screw up everything because their links dropped in an unexpected order. I ended up rewriting major chunks of my code several times before I got it working.

I think showing my thought process step by step as I'd do normally would be a bit confusing. So, instead I'll walk you through my actual working solution.

I'll start with XA which is rather simple but takes some work off of the main EXAs.



It starts with simply copying all the file IDs and file names from the index file. Once that's done, it will switch into local mode and let a visiting EXA know the next drive to LINK to. After each drive link ID it will also send a magic number, the purpose of which will become clear later.

Then to XB. It handles the bulk of the logic and does so by making many REPLs.
It starts by making a file to write the results to. It writes a 0 at the start (placeholder for later), then the file id and then the file name. The file name needs to be at the start of the result files when we're done. After SEEKing back to the file id, it jumps into local mode and waits for a message on M.

But it also REPLs itself and the REPL will run the same code for the next file. This repeats for all 6 files, after which the final REPL jumps to KICKSTART.

When this code is done, there are 7 EXAs in the home host. 6 of them are holding a (still mostly empty) result file, the 7th is the one that will kickstart the next step.

Let's look at the kickstarter.
The first thing the kickstarter does is link to the drive controller and ask XA for the host to link to. Then it actually needs to get there. This is difficult because there's no way to know if the link is open or not. I solved this by REPLing a drive EXA in a loop. If the EXA makes it, it immediately sends a message on M. TRYDRIVE tries to check if a message is being sent with the TEST MRD. If so, it continues, if not it makes another DRIVE EXA until it works.

It is possible that the link dies in the one cycle between the DRIVE EXAs LINK command and the M message. In that case, the EXA will have successfully reached it, but TRYDRIVE makes another instance regardless. This could even happen multiple times.

Now, that other instance can't actually link to the drive because with the one EXA in there, it's full. It'll either try repeatedly until it bonks into a missing link and dies, or it'll actually make it after the actual DRIVE EXA makes some space by GRABbing a file. That's why that EXA needs a KILL after the GRAB.

This bit of code actually gave me the most trouble. To save on activity, I tried to have XA handle all this, but then there's messages going from the drive to XA and from XA to the XBs... and it all seems to work until some link disconnects at the worst time and everything desyncs. Making the kickstarter personally responsible was the only solution that worked for me.

Anyway, we now got a stable EXA in the drive, and the kickstarter VOIDs its M. It then jumps back to local mode, copies the magic number from XA, goes back to the home host, and copies it to one of the six waiting EXAs (randomly chosen). Then the kickstarter's work is done and it stops.


Before we go back to the six EXAs at home, let's see the rest of DRIVE's logic.
It gets sent instructions on M for what file to grab, then copies all the data from that file on M, sending a 0 when it's done, and then waits for another M message to grab and copy another file. To kill this EXA you can just send it the id of a non-existent file.

As a note, I tried to see if swapping the COPY 0 M and DROP made the code any faster, in case that M message was slow. It didn't - the solution was one cycle slower overall. But more importantly, doing so increased the activity. It's something I noticed a few times in this task. Even the smallest timing difference will change where the EXAs are in the code when the links are open, and getting to the drives will get harder or easier.


The 6 EXAs in the home host all have a file (with the cursor sitting on the file ID) and are waiting for an M message. The kickstarter will send one, the magic value 1 from XA.
A randomly chosen EXA will accept this M, and then copy the file ID on global M. Only one EXA is listening - the one in the DRIVE. It will grab this file and start copying it. T is used as an intermediate so this EXA knows when the DRIVE EXA sends the terminating 0. Once that's the done, it will check whether the magic number is 6, and if not, increment it by 1 and send it on to the next EXA, and stop itself.

This way, one by one, all of the 6 EXAs will copy the data of their file from the first drive, and then just pass the baton to the next one. The random order doesn't matter because the EXAs run one by one and each knows which file ID it needs.

None of this code needs retries because if the link is down, the M calls will just wait.

The final EXA won't die, instead it will jump to NEXTROUND.



At this point, there are 6 files with partially corrupt data in the home host, one being held by the sole surviving EXA. The DRIVE EXA is waiting for a next file to pick up, and XA wants to send the next drive's link ID on local M.

NEXTROUND starts with sending a 0 to the DRIVE EXA so it dies. It then starts a second kickstarter. Again, that one will go to the drive controller, this time make a DRIVE EXA in the second drive, and come back to communicate the second magic number from XA, a 0.

The NEXTROUND EXA will use a similar REPL strategy as before, to make 6 EXAs each holding a file. This time it just uses a counter to go through all homemade file IDs (starting at 400), and the final REPL will die as it tries to grab a file that doesn't exist.

Again, all of them will wait for a message from the kickstarter, and it doesn't matter who gets it first. Importantly, this time the value isn't stored to X but in the placeholder at the start of the result file.

Next, the EXA jumps back into global mode, copies its file ID to the new DRIVE EXA and enters this FIXNEXT loop. How this works is, it copies the values from the DRIVE to X and checks if it's a number (valid). If so, it writes the value to F. If not, it skips writing this value. So, this code might write the same number twice from different files, but it will never overwrite a number with a FAIL. After this round, more values in the result file will be valid.

I did have to use X > -9999 instead of X < 9999 here because it turns out 9999 is a valid number in one of the tests.

DONEFIX is directly after this code, so no matter which branch hits the EOF, we end up here:
This time, the EXA already knows it's at the EOF. The DRIVE EXA sends a useless zero to report the same so we can just VOID that. The magic value is read from the start of the file (it was written there because the FIXNEXT loop required X as an intermediate), one is added to it. If the value is not 6 (or 12, I'll get to that), there's more EXAs waiting. The value is sent on local M, and if the value is under 6, this EXA dies by divide by zero.

If the value equals 6, the code jumps into NEXTROUND once more. The second DRIVE EXA gets killed, a third gets created, and the kickstarter comes back with a magic value of 6. A new set of 6 EXAs will be spawned, each one holding a partially fixed file, and each one will run another FIXNEXT loop, using the correct values from the third drive.

But, with the magic value starting at 6, this DONEFIX code works slightly differently. After incrementing it the first time, this value will not be 6 so it will never jump into NEXTROUND again. If it's 12 it will jump into FINISH. Otherwise, it'll hand the baton to the next EXA, and jump into CLEANUP now since X is always larger than 6.

Almost there.

FINISH just tells the 3rd DRIVE EXA to die. Then, all of the EXAs will delete the placeholder/magic value from the start of their file, as well as the file id. Leaving only the file name and the contents, which is the requirement.

XA already died since it ran out of lines of code to run.

Quite convoluted, but it works. It might not be the best idea to let all 6 file writing EXAs die each round and recreate them but this was the best way I found to keep control.

This runs at 5293/111/14.



Apparently my cycle count is the kind of solution many people found.

Top percentiles are 1012, 61 and 4. I bet the faster speed is gotten through some kind of parallelization but I have no clue how to set that up. The links disconnecting keeps messing with every idea I might otherwise have.

By the way, the activity is 14 because of XA going to the controller (1), the kickstarter going to the controller and back thrice (6), every DRIVE EXA that actually makes it into a drive (3), and a total of two duplicate DRIVE EXAs that LINK into the drive and need to be KILLed (4).

If anyone has any better scores let me know.

Next time, we help deadlock book a trip.