Random IT Utensils

Availability Anywhere Part 20 — Nested full-tunnel VPN in another full-tunnel VPN with force tunnel mode

afish — Fri, 17 Feb 2023 09:00:25 +0000

This is the twentieth part of the Availability Anywhere series. For your convenience you can find other parts in the table of contents in Part 1 – Connecting to SSH tunnel automatically in Windows

We already know how to use full-tunnel VPN from a virtual machine on the host with TCP over File System. Today we’re going to see how to nest full-tunnel VPN inside another full-tunnel VPN.

Iimagine that you take your corporate laptop and go to the office. You want to connect to your client’s network, so you use full-tunnel VPN (something like Cisco AnyConnect or Wireguard). Your client configured their firewall to allow your office’s IP address. All works.

Now, you want to work from home. You take your corporate laptop and come back home. You try connecting to your client’s network, but they didn’t allow your home’s IP address to connect. You try connecting to your office’s network with a VPN and this works well. However, you can’t connect to your client’s VPN now because you can’t have two full-tunnel VPNs enabled. How to deal with that?

I managed to get something like that to work with the following setup:

On the host, install Hyper-V
On the host, install Hyper-V guest called VM_A. I used Windows 10 x86. It’s better to use x86 VM to avoid some issues with nested virtualization.
On the host, enable virtualization extension for VM_A with Get-VM | where Name -eq "VM_A" | Set-VMProcessor -ExposeVirtualizationExtensions $true
On the host, connect to Hyper-V guest VM_A with shared drive C:
In Hyper-V guest VM_A, install Virtual Box 4.2.36 which works on Windows x86. Some other version of Virtual Box possibly can work.
In Hyper-V guest VM_A, create Virtual Box guest VM_B. I used Windows 7 x86. Again, use x86 VM version.
Configure VirtualBox guest VM_B networking as NAT with default interface type (something like Intel PRO/1000 MT Desktop)
In VirtualBox guest VM_B, install Virtual Box guest addins
In VirtualBox, configure shared directory \\tsclient\C with full read-write options (uncheck read only) and with automount
In Hyper-V guest VM_A, configure VPN to your office’s network. Let’s call this connection VPN_A.
In VirtualBox guest VM_B, configure VPN to your client’s network. Let’s call this connection VPN_B
You may need to set DNS in VirtualBox guest VM_B to something like 8.8.8.8
Enable VPN_A, then enable VPN_B.

All should work. Mind that in order to use VPN based on layer 3 GRE protocol (like PPTP) for VPN_A, you may need to reconfigure Hyper-V guest to use bridging. I don’t know if it’s possible to use GRE-based VPN for VPN_B in this setup (I doubt that). However, typical corporate VPN-s use HTTPS on the way to avoid issues.

I tested this setup with Wireguard as VPN_A and Windows’ SSTP as VPN_B. It worked correctly. When VPN_A was enabled and VPN_B was disabled, then VirtualBox guest VM_B was visible to the internet from the IP address of VPN_A (so the IP address of the office). When both VPN_A and VPN_B were enabled, VirtualBox guest VM_B was visible to the internet from the IP address of VPN_B (client’s IP address). Also, shared drive from host was visible in VirtualBox guest VM_B when both VPN_A and VPN_B were enabled. Therefore, you can use TCP over File System properly to route the traffic from the host through any of the VPNs.

ILP Part 105 — Sudoku Cube

afish — Fri, 10 Feb 2023 09:00:18 +0000

This is the one hundred and fifth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we are going to solve the Sudoku Cube. It’s a variation of the regular Rubik’s cube in which we have digits on the cube and each side must have exactly nine different digits from one to nine. What’s more, digits on a side must all look the same direction.

I took photos of my cube. You can see them below:

The tricky part is what to do. With the regular cube it’s rather clear where each piece should go. The hard part is figuring out how to put it into place. With Sudoku Cube it’s much harder. We don’t actually see where to put each element. The first step is to “solve the grid”. We need to understand where to put elements.

Solving the grid

First, notice that the number 1 is symmetrical. We don’t know whether it’s facing “up” or “down”. Therefore, we need to assume it can look both directions. We could actually wonder similarly for number eight (which side is “up”) or six/nine, but for them we can make some assumptions. Eight should be narrower at the top. Nine has a label on it.

Second, we don’t know which directions the sides look into. Also, it may not be obvious from the very beginning, but each center has an orientation. This is different from the regular cube. There are algorithms to do so and we’ll see them later. However, for now we need to assume that any side can look any direction. Sometimes the cube is convenient and the “middle strap” sides look upwards, but we can’t assume that.

Therefore, we need to figure out where pieces go. Once we have that, we can then solve the grid.

We start by defining the permutations in this way:

This looks cryptic, so let’s analyze step by step.

Let’s start with the corners marked with red arrows and numbers. We can see six faces of the cube. Going from left to right, top to bottom, the faces are: up, left, front, right, back, down. We have eight corners of the cube. Therefore, there are eight pieces that we can rotate and put in given places. Places are numbered from oen to eight, and permutations are numbered from zero to two. We are going to encode each piece as a list of numbers and list of rotations.

Let’s take the Picture from the above in which you can see free sides of the cube. Let’s say that the side with numbers 3, 9, 4, 6, 1, 5, 5, 7, 9 is the front side, and the side with numbers 5, 4, 6, 3, 6, 5, 8, 2, 2 is the top one. You can see that we have a corner with number 4 to the right of 9 and above 5. This is the corner that we marked as 1_0 on the diagram screen. So we can see, that we can encode this corner as having one with the following sequence of numbers: 4, 8, 4. Therefore 1_0 = 4, 1_1 = 8, 1_2 = 4.

You can see the arrow going up. This is an arbitrary indication which face I consider “upwards” of this given field. Similarly, for other fields. We want to encode the rotation of a piece based on the orientation of the digit. We have four directions: aligned with the arrow encoded as zero, rotated clockwise once by ninety degrees encoded as one, rotated twice encoded as two, rotated three times encoded as three. Therefore, the rotations of the numbers 4, 8, 4 are 3, 2, 1.

We can now take each corner and encode it properly. This should be the encoding:

var corners = new []{
	new Corner(solver, "c1") { Values = new[]{4, 8, 4}, Rotations = new[] {3, 2, 1}},
	new Corner(solver, "c2") { Values = new[]{9, 5, 1}, Rotations = new[] {3, 2, 1}},
	new Corner(solver, "c3") { Values = new[]{5, 9, 1}, Rotations = new[] {2, 2, 1}},
	new Corner(solver, "c4") { Values = new[]{3, 7, 5}, Rotations = new[] {1, 0, 3}},
	new Corner(solver, "c5") { Values = new[]{2, 6, 7}, Rotations = new[] {0, 3, 0}},
	new Corner(solver, "c6") { Values = new[]{6, 3, 7}, Rotations = new[] {2, 1, 2}},
	new Corner(solver, "c7") { Values = new[]{4, 1, 6}, Rotations = new[] {3, 0, 0}},
	new Corner(solver, "c8") { Values = new[]{8, 9, 2}, Rotations = new[] {3, 1, 0}}
};

We can do the same for edges (middles on the sides). We have twelve edges, each edge has two pieces. They are marked with green numbers and arrows. This is how we encode the cube:

var edges = new []{
	new Edge(solver, "e1") { Values = new[]{9, 3}, Rotations = new[] {0, 3}},
	new Edge(solver, "e2") { Values = new[]{5, 2}, Rotations = new[] {0, 2}},
	new Edge(solver, "e3") { Values = new[]{7, 6}, Rotations = new[] {1, 2}},
	new Edge(solver, "e4") { Values = new[]{9, 8}, Rotations = new[] {2, 0}},
	new Edge(solver, "e5") { Values = new[]{3, 2}, Rotations = new[] {0, 2}},
	new Edge(solver, "e6") { Values = new[]{6, 9}, Rotations = new[] {1, 3}},
	new Edge(solver, "e7") { Values = new[]{2, 3}, Rotations = new[] {1, 3}},
	new Edge(solver, "e8") { Values = new[]{8, 5}, Rotations = new[] {3, 3}},
	new Edge(solver, "e9") { Values = new[]{8, 8}, Rotations = new[] {1, 2}},
	new Edge(solver, "e10") { Values = new[]{4, 2}, Rotations = new[] {1, 1}},
	new Edge(solver, "e11") { Values = new[]{3, 4}, Rotations = new[] {2, 0}},
	new Edge(solver, "e12") { Values = new[]{1, 7}, Rotations = new[] {3, 0}}
};

We also have centers. We don’t care about their orientation at this point.

Formulas

We basically want to do the following:

For each corner: assign exactly one position to a corner (position from one to eight) and one permutation (from zero to two)
Do the same for edges (twelve positions and two permutations)
Make sure that each face has all pieces but center oriented the same way
Make sure that number one can be oriented upside down (as it looks the same)
Make sure each face has digits from one to nine

Sounds easy. Let’s see the first implementation.

First implementation

Let’s start by encoding the grid. First, we’d like to encode the positions from the chart above. For corners, we take the value like 4_1 and serialize it to one number as 4 * 3 + 1 = 13. We do similarly for edges:

// 0 means empty
// Values are 1_0, 1_1, 1_2, 2_0, 2_1, ...
// Corners have 3 elements, so: 1_0 = 3 * 1 + 0 = 3
// Edges have 2 elements, so: 1_0 = 2 * 1 + 0 = 2
var diagram = new []{
	new[] {0, 0, 0, 16, 17, 26, 0, 0, 0, 0, 0, 0},
	new[] {0, 0, 0, 23, 0, 11, 0, 0, 0, 0, 0, 0},
	new[] {0, 0, 0, 14, 3, 4, 0, 0, 0, 0, 0, 0},
	new[] {17, 22, 13, 12, 2, 3, 5, 10, 25, 24, 16, 15},
	new[] {21, 0, 9, 8, 0, 4, 5, 0, 14, 15, 0, 20},
	new[] {19, 24, 11, 9, 6, 6, 7, 12, 23, 21, 18, 18},
	new[] {0, 0, 0, 10, 7, 8, 0, 0, 0, 0, 0, 0},
	new[] {0, 0, 0, 25, 0, 13, 0, 0, 0, 0, 0, 0},
	new[] {0, 0, 0, 20, 19, 22, 0, 0, 0, 0, 0, 0},
};

Now, we encode the orientation of each field (arrows). We assume -1 means empty field:

var fieldsOrientations = new []{
	new[] {-1, -1, -1, 3, 0, 0, -1, -1, -1, -1, -1, -1},
	new[] {-1, -1, -1, 3, 0, 1, -1, -1, -1, -1, -1, -1},
	new[] {-1, -1, -1, 2, 2, 1, -1, -1, -1, -1, -1, -1},
	new[] {3, 0, 0, 3, 0, 0, 3, 0, 0, 3, 0, 0},
	new[] {3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1},
	new[] {2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1},
	new[] {-1, -1, -1, 3, 0, 0, -1, -1, -1, -1, -1, -1},
	new[] {-1, -1, -1, 3, 0, 1, -1, -1, -1, -1, -1, -1},
	new[] {-1, -1, -1, 2, 2, 1, -1, -1, -1, -1, -1, -1}
};

Now, let’s make sure that each piece is put in a different position:

// Make corners in distinct positions
solver.Set(corners[0].FinalPosition, corners.Skip(1).Select(c => c.FinalPosition).ToArray());

// Make edges in distinct positions
solver.Set(edges[0].FinalPosition, edges.Skip(1).Select(e => e.FinalPosition).ToArray());

Let’s now start the magic. The idea is as follows: we ask the solver to assign positions and rotations to the pieces. We then iterate over all possibilities, check if a given possibility was selected by the solver, and then calculate the outcome. We then add the requirements to make the grid solved. Let’s begin with the corners.

Func> setupSingleCorner = (x, y) => {
	int number = diagram[x][y];
	int position = number / 3 - 1;
	int permutation = number % 3;
	
	IVariable piecePermutation = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set(solver.FromConstant(2));
	IVariable finalPermutation = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set(solver.FromConstant(2));
	IVariable pieceRotationValue = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set(solver.FromConstant(3));
	IVariable finalRotation = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set(solver.FromConstant(3));
	IVariable cornerValue = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set(solver.FromConstant(9)).Set(solver.FromConstant(1));
	
	foreach(var corner in corners){
		var matchingCorner = solver.Operation(corner.FinalPosition, solver.FromConstant(position));
		
		solver.Operation(
			matchingCorner,
			solver.Operation(corner.FinalPermutation, piecePermutation)
		).Set(solver.FromConstant(1));
		
		for(int possiblePermutation=0;possiblePermutation<3;++possiblePermutation){
			var matchingPermutation = matchingCorner.Operation(finalPermutation.Operation(solver.FromConstant(possiblePermutation)));
		
			solver.Operation(
				matchingPermutation,
				solver.Operation(pieceRotationValue, solver.FromConstant(corner.Rotations[possiblePermutation]))
			).Set(solver.FromConstant(1));
			
			solver.Operation(
				matchingPermutation,
				solver.Operation(cornerValue, solver.FromConstant(corner.Values[possiblePermutation]))
			).Set(solver.FromConstant(1));
		}
	}
	
	solver.Set(
		finalPermutation, 
		solver.Operation(
			solver.Operation(solver.FromConstant(permutation), piecePermutation),
			solver.FromConstant(3)
		)
	);
	
	solver.Set(
		finalRotation, 
		solver.Operation(
			solver.Operation(solver.FromConstant(fieldsOrientations[x][y]), pieceRotationValue),
			solver.FromConstant(4)
		)
	);
	
	return Tuple.Create(cornerValue, finalRotation);
};

For each corner from the diagram, we deserialize its position and permutation (lines 2-4). Next, we need to prepare some variables (lines 6-10) and then decipher the solution.

We iterate over each possible piece (line 12) and see if the corner was assigned to the field we analyze now (line 13). If that’s the case, then we copy the value of the assigned permutation to the temporary variable (lines 15-18).

Next, we do some magic. We would like to check all possible permutations to see which one was selected. To do that, we need to calculate what we call here finalPermutation. However, this is some kind of a cyclic dependency. First, we copy the permutation assigned by the solver and called corner.FinalPermutation to the variable piecePermutation (lines 15-18). Next, we need to add the permutation of the field to that value, calculate the modulo three, and assign that to the variable finalPermutation (lines 35-41). However, we then (or technically earlier) use the variable finalPermutation in line 21 to answer whether the current permutation we analyze is the one that was selected. Once we have that, we can copy the rotation of the corner (lines 23-26) and the value of the corner (lines 28-32).

Next, we do another time travel and we calculate the final orientation of the field by adding the orientation of the corner and the orientation (direction of the arrow) of the field. That’s in lines 43-49.

Finally, we return both the value and the final orientation (line 51).

Okay, we can now iterate over all corners of a given face:

Func[]> setupCorners = (x, y) => {
	var valuesAndRotations = new []{
		setupSingleCorner(x, y),
		setupSingleCorner(x, y+2),
		setupSingleCorner(x+2, y+2),
		setupSingleCorner(x+2, y)
	};
	
	return valuesAndRotations;
};

We need to do a very similar code with the edges:

Func> setupSingleEdge = (x, y) => {
	int number = diagram[x][y];
	int position = number / 2 - 1;
	int permutation = number % 2;
	
	IVariable piecePermutation = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set(solver.FromConstant(1));
	IVariable finalPermutation = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set(solver.FromConstant(1));
	IVariable pieceRotationValue = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set(solver.FromConstant(3));
	IVariable finalRotation = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set(solver.FromConstant(3));
	IVariable edgeValue = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set(solver.FromConstant(9)).Set(solver.FromConstant(1));
	
	calculatedRotations[x][y] = finalRotation;
	
	foreach(var edge in edges){
		var matchingEdge = solver.Operation(edge.FinalPosition, solver.FromConstant(position));
		
		solver.Operation(
			matchingEdge,
			solver.Operation(edge.FinalPermutation, piecePermutation)
		).Set(solver.FromConstant(1));
		
		for(int possiblePermutation=0;possiblePermutation<2;++possiblePermutation){
			var matchingPermutation = matchingEdge.Operation(finalPermutation.Operation(solver.FromConstant(possiblePermutation)));
		
			solver.Operation(
				matchingPermutation,
				solver.Operation(pieceRotationValue, solver.FromConstant(edge.Rotations[possiblePermutation]))
			).Set(solver.FromConstant(1));
			
			solver.Operation(
				matchingPermutation,
				solver.Operation(edgeValue, solver.FromConstant(edge.Values[possiblePermutation]))
			).Set(solver.FromConstant(1));
		}
	}
	
	solver.Set(
		finalPermutation, 
		solver.Operation(
			solver.Operation(solver.FromConstant(permutation), piecePermutation),
			solver.FromConstant(2)
		)
	);
	
	solver.Set(
		finalRotation, 
		solver.Operation(
			solver.Operation(solver.FromConstant(fieldsOrientations[x][y]), pieceRotationValue),
			solver.FromConstant(4)
		)
	);
	
	return Tuple.Create(edgeValue, finalRotation);
};

We iterate over all edges of a face:

Func[]> setupEdges = (x, y) => {
	var valuesAndRotations = new []{
		setupSingleEdge(x, y+1),
		setupSingleEdge(x+1, y),
		setupSingleEdge(x+1, y+2),
		setupSingleEdge(x+2, y+1)
	};
	
	return valuesAndRotations;
};

And we also get the value of the center:

Func setupCenter = (x, y) => {
	return solver.FromConstant(int.Parse("" + centers[x][y]));
};

We can now setup a single face:

Action setupSingleFace = (x, y) => {
	var valuesAndRotations = setupCorners(x, y).Concat(setupEdges(x, y)).ToArray();
	
	var valuesAndRotationsAndOnes = valuesAndRotations.Select(t => {
		var anotherPossibleRotation = solver.Operation(
			t.Item1.Operation(solver.FromConstant(1)),
			t.Item2.Operation(solver.FromConstant(2)).Operation(solver.FromConstant(4)),
			t.Item2
		);
		
		return Tuple.Create(t.Item1, t.Item2, anotherPossibleRotation);
	}).ToArray();
	
	// Make pairwise rotations equal = make pieces (but center) look the same direction
	for(int id=1; id < valuesAndRotationsAndOnes.Length; ++id){
		solver.Set(
			solver.Operation(
				solver.Operation(valuesAndRotationsAndOnes[id].Item2, valuesAndRotationsAndOnes[id-1].Item2),
				solver.Operation(valuesAndRotationsAndOnes[id].Item2, valuesAndRotationsAndOnes[id-1].Item3),
				solver.Operation(valuesAndRotationsAndOnes[id].Item3, valuesAndRotationsAndOnes[id-1].Item2),
				solver.Operation(valuesAndRotationsAndOnes[id].Item3, valuesAndRotationsAndOnes[id-1].Item3)
			),
			solver.FromConstant(1)
		);
	}
	
	var center = setupCenter(x + 1, y+1);
	
	// Make sudoku numbers
	solver.Set(center, valuesAndRotationsAndOnes.Select(t => t.Item1).ToArray());
};

We take all the values and rotations of corners and edges (line 2). We then need to take all the ones and calculate additional rotation. We check if the value is one (line 6) and if that’s the case, then we add another rotation (upside-down), otherwise we return the same rotation (lines 7-8).

Finally, we take all the sides and make sure that they all have the same rotations. So for each pair of pieces, either their rotations are equal, or their rotation and alternative rotation are equal, or their alternative rotations are equal (lines 15-25).

Finally, we add the center (line 27) and make sure that all numbers are different (line 30) which means that we have the sudoku requirement met.

We can now configure all faces:

Action setupFaces = () => {
	setupSingleFace(0, 3);
	setupSingleFace(3, 0);
	setupSingleFace(3, 3);
	setupSingleFace(3, 6);
	setupSingleFace(3, 9);
	setupSingleFace(6, 3);
};

setupFaces();

Let’s now add the goal, solve the problem, and print the result:

solver.AddGoal("goal", solver.FromConstant(0));

solver.Solve();

var template = new []{
	"     ---         ",
	"    |   |        ",
	"    |   |        ",
	"    |   |        ",
	" --- --- --- ---",
	"|   |   |   |   |",
	"|   |   |   |   |",
	"|   |   |   |   |",
	" --- --- --- --- ",
	"    |   |        ",
	"    |   |        ",
	"    |   |        ",
	"     ---         "
};

var numbersGrid = template.Select(x => x.ToArray()).ToArray();
var rotationsGrid = template.Select(x => x.ToArray()).ToArray();

Action printSingleCorner = (x, y, destinationX, destinationY) => {
	int number = diagram[x][y];
	int position = number / 3 - 1;
	int permutation = number % 3;
	
	var matchingCorner = corners.First(c => (int)Math.Round(solver.GetValue(c.FinalPosition)) == position);
	var piecePermutation = (int)Math.Round(solver.GetValue(matchingCorner.FinalPermutation));
	
	var finalPermutation = (permutation + piecePermutation) % 3;
	numbersGrid[destinationX][destinationY] = matchingCorner.Values[finalPermutation].ToString()[0];
	
	rotationsGrid[destinationX][destinationY] = matchingCorner.Rotations[finalPermutation].ToString()[0];
};

Action printCorners = (x, y, destinationX, destinationY) => {
	printSingleCorner(x, y, destinationX, destinationY);
	printSingleCorner(x, y+2, destinationX, destinationY + 2);
	printSingleCorner(x+2, y+2, destinationX + 2, destinationY + 2);
	printSingleCorner(x+2, y, destinationX + 2, destinationY);
};

Action printSingleEdge = (x, y, destinationX, destinationY) => {
	int number = diagram[x][y];
	int position = number / 2 - 1;
	int permutation = number % 2;
	
	var matchingEdge = edges.First(e => (int)Math.Round(solver.GetValue(e.FinalPosition)) == position);
	var piecePermutation = (int)Math.Round(solver.GetValue(matchingEdge.FinalPermutation));
	
	var finalPermutation = (permutation + piecePermutation) % 2;
	numbersGrid[destinationX][destinationY] = matchingEdge.Values[finalPermutation].ToString()[0];
	
	rotationsGrid[destinationX][destinationY] = matchingEdge.Rotations[finalPermutation].ToString()[0];
};

Action printEdges = (x, y, destinationX, destinationY) => {
	printSingleEdge(x, y+1, destinationX, destinationY + 1);
	printSingleEdge(x+1, y, destinationX + 1, destinationY);
	printSingleEdge(x+1, y+2, destinationX + 1, destinationY + 2);
	printSingleEdge(x+2, y+1, destinationX + 2, destinationY + 1);
};

Action printCenters = (x, y, destinationX, destinationY) => {
	numbersGrid[destinationX+1][destinationY+1] = centers[x+1][y+1];
};

Action printSingleFace = (x, y, destinationX, destinationY) => {
	printCorners(x, y, destinationX, destinationY);
	printEdges(x, y, destinationX, destinationY);
	printCenters(x, y, destinationX, destinationY);
};

Action printFaces = () => {
	printSingleFace(0, 3, 1, 5);
	printSingleFace(3, 0, 5, 1);
	printSingleFace(3, 3, 5, 5);
	printSingleFace(3, 6, 5, 9);
	printSingleFace(3, 9, 5, 13);
	printSingleFace(6, 3, 9, 5);
};

printFaces();

for(int row = 0; row < template.Length; ++ row){
	Console.Write(new String(numbersGrid[row]));
	Console.Write("          ");
	Console.WriteLine(new String(rotationsGrid[row]));
}

This works. In theory. I tried running that with NEOS for eight hours and it didn’t solve the problem, unfortunately. It was simply too complex.

Let’s see another solution.

Second implementation

In this solution we’ll apply many optimizations. We’ll store the positions as bitmasks instead of integers to use boolean flags (which are much faster). We won’t calculate the obtained direction of the face, but we’ll enforce which face must be selected. Finally, we won’t check the options and see if they were selected, but rather we will calculate what was selected end enforce the options. Let’s start.

First, we create a bitmask for directions of each face. We have six faces (sides) and four directions for each:

// face0_up, face0_right, face0_down, face0_left, face1_up ...
// front = 0, right = 1, back = 2, left = 3, up = 4, down = 5
var facesDirections = Enumerable.Range(0, 6 * 4).Select(d => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray();

Next, we encode a bitmask what value was assigned to each corner side. We have six faces, four corners for each face, and nine numbers to choose from:

// face0_corner_top_right_value1, face0_corner_top_right_value2, ..., face0_corner_top_right_value9, face0_corner_bottom_right_value1,
// ..., face0_corner_bottom_right_value9, face0_corner_bottom_left_value1, ..., face0_corner_top_left_value_9, face1_corner_top_right_value1...
var cornersNumbers = Enumerable.Range(0, 6*4*9).Select(n => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray();

We do the similar for edges:

// face0_top_value1, face_0_top_value2, ..., face0_top_value9, face0_right_value1
// ..., face0_right_value9, face0_bottom_value1, ..., face0_bottom_value9, face0_left_value1, ...
// face0_left_value9, face1_top_value1...
var edgeNumbers = Enumerable.Range(0, 6*4*9).Select(n => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray();

Now, we can use these bitmasks to constrain the solution. We make sure that digits on a face look all the same direction. So, for each face we take the direction flags and make sure that only one flag is selected:

// Each face has exactly one direction
for(var faceId = 0; faceId < 6; ++faceId){
	solver.Operation(facesDirections.Skip(faceId * 4).Take(4).ToArray()).Set(solver.FromConstant(1));
}

We then make sure each corner has exactly one number. We have six faces and four corners on each face:

// Each corner has exactly one number
for(var cornerId = 0; cornerId < 6 * 4; ++cornerId){
	solver.Operation(cornersNumbers.Skip(cornerId * 9).Take(9).ToArray()).Set(solver.FromConstant(1));
}

We now need to see how corners are stored. Previously, corner.FinalPosition was an integer. Now it’s a long bitmasks of positions and permutations. We have eight possible positions and three permutations:

public class Corner$id {
	public int[] Values {get;set;}
	public int[] Rotations {get;set;}
	public IVariable[] FinalPosition {get; set;}
	public string Prefix {get;set;}
	
	public Corner(IMilpManager solver, string prefix){
		// position1_permutation0, position1_permutation1, position1_permutation2, position2_permutation0, ...
		FinalPosition = Enumerable.Range(0, 8*3).Select(d => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray();
		Prefix = prefix;
	}
}

Next, we make sure that each corner piece has exactly one position and one rotation selected:

// Each corner is in one place
foreach(var corner in corners){
	solver.Operation(corner.FinalPosition).Set(solver.FromConstant(1));
}

Next we need to make sure that each corner of the cube has exactly one piece assigned. We have eight corners, for each corner we take bit flags of each piece, and make sure that only one was selected:

// Exactly one piece in given corner
for(var cornerId = 0; cornerId < 8; ++cornerId){
	solver.Operation(
		corners.SelectMany(corner => corner.FinalPosition.Skip(cornerId * 3).Take(3)).ToArray()
	).Set(solver.FromConstant(1));
}

We do the same for edges:

// Each edge has exactly one number
for(var edgeId = 0; edgeId < 6 * 4; ++edgeId){
	solver.Operation(edgeNumbers.Skip(edgeId * 9).Take(9).ToArray()).Set(solver.FromConstant(1));
}

// Each edge is in one place
foreach(var edge in edges){
	solver.Operation(edge.FinalPosition).Set(solver.FromConstant(1));
}

// Exactly one piece in given edge
for(var edgeId = 0; edgeId < 12; ++edgeId){
	solver.Operation(
		edges.SelectMany(edge => edge.FinalPosition.Skip(edgeId * 2).Take(2)).ToArray()
	).Set(solver.FromConstant(1));
}

Now we need to make sure that each side has sudoku numbers:

var faceToCenters = new Dictionary>{
	{0, Tuple.Create(4, 4)},
	{1, Tuple.Create(4, 7)},
	{2, Tuple.Create(4, 10)},
	{3, Tuple.Create(4, 1)},
	{4, Tuple.Create(1, 4)},
	{5, Tuple.Create(7, 4)}
};

// Sudoku numbers on each face
for(var faceId = 0; faceId < 6; ++faceId){
	var centerPosition = faceToCenters[faceId];
	var centerNumber = int.Parse("" + centers[centerPosition.Item1][centerPosition.Item2]);

	var cornerDigits = Enumerable.Range(0, 4).Select(p => cornersNumbers.Skip(faceId * 4 * 9).Skip(p * 9).Take(9).ToArray()).ToArray();
	var edgeDigits = Enumerable.Range(0, 4).Select(p => edgeNumbers.Skip(faceId * 4 * 9).Skip(p * 9).Take(9).ToArray()).ToArray();
	var centerDigit = new [] { Enumerable.Range(0, 9).Select(i => i == centerNumber - 1 ? solver.FromConstant(1) : solver.FromConstant(0)).ToArray() };
	var vectors = cornerDigits.Concat(edgeDigits).Concat(centerDigit).ToArray();
		
	for(var digit = 0; digit < 9; ++ digit){
		solver.Operation(vectors.Select(v => v[digit]).ToArray()).Set(solver.FromConstant(1));
	}
}

We need two additional mappings from corners and edges to faces:

var cornersToFaces = new Dictionary, int> {
	{Tuple.Create(0, 3), 4},
	{Tuple.Create(0, 5), 4},
	{Tuple.Create(2, 3), 4},
	{Tuple.Create(2, 5), 4},
	{Tuple.Create(3, 0), 3},
	{Tuple.Create(3, 2), 3},
	{Tuple.Create(5, 0), 3},
	{Tuple.Create(5, 2), 3},
	{Tuple.Create(3, 3), 0},
	{Tuple.Create(3, 5), 0},
	{Tuple.Create(5, 3), 0},
	{Tuple.Create(5, 5), 0},
	{Tuple.Create(3, 6), 1},
	{Tuple.Create(3, 8), 1},
	{Tuple.Create(5, 6), 1},
	{Tuple.Create(5, 8), 1},
	{Tuple.Create(3, 9), 2},
	{Tuple.Create(3, 11), 2},
	{Tuple.Create(5, 9), 2},
	{Tuple.Create(5, 11), 2},
	{Tuple.Create(6, 3), 5},
	{Tuple.Create(6, 5), 5},
	{Tuple.Create(8, 3), 5},
	{Tuple.Create(8, 5), 5},
};

var edgesToFaces = new Dictionary, int> {
	{Tuple.Create(0, 4), 4},
	{Tuple.Create(1, 3), 4},
	{Tuple.Create(1, 5), 4},
	{Tuple.Create(2, 4), 4},
	{Tuple.Create(3, 1), 3},
	{Tuple.Create(4, 0), 3},
	{Tuple.Create(4, 2), 3},
	{Tuple.Create(5, 1), 3},
	{Tuple.Create(3, 4), 0},
	{Tuple.Create(4, 3), 0},
	{Tuple.Create(4, 5), 0},
	{Tuple.Create(5, 4), 0},
	{Tuple.Create(3, 7), 1},
	{Tuple.Create(4, 6), 1},
	{Tuple.Create(4, 8), 1},
	{Tuple.Create(5, 7), 1},
	{Tuple.Create(3, 10), 2},
	{Tuple.Create(4, 9), 2},
	{Tuple.Create(4, 11), 2},
	{Tuple.Create(5, 10), 2},
	{Tuple.Create(6, 4), 5},
	{Tuple.Create(7, 3), 5},
	{Tuple.Create(7, 5), 5},
	{Tuple.Create(8, 4), 5},
};

We also need to know where each corner is (whether it’s right top, right bottom, left bottom, left top). Similarly for edges (top, right, bottom, left):

var cornersToDiagonalEnds = new Dictionary, int> {
	{Tuple.Create(0, 3), 3},
	{Tuple.Create(0, 5), 0},
	{Tuple.Create(2, 3), 2},
	{Tuple.Create(2, 5), 1},
	{Tuple.Create(3, 0), 3},
	{Tuple.Create(3, 2), 0},
	{Tuple.Create(5, 0), 2},
	{Tuple.Create(5, 2), 1},
	{Tuple.Create(3, 3), 3},
	{Tuple.Create(3, 5), 0},
	{Tuple.Create(5, 3), 2},
	{Tuple.Create(5, 5), 1},
	{Tuple.Create(3, 6), 3},
	{Tuple.Create(3, 8), 0},
	{Tuple.Create(5, 6), 2},
	{Tuple.Create(5, 8), 1},
	{Tuple.Create(3, 9), 3},
	{Tuple.Create(3, 11), 0},
	{Tuple.Create(5, 9), 2},
	{Tuple.Create(5, 11), 1},
	{Tuple.Create(6, 3), 3},
	{Tuple.Create(6, 5), 0},
	{Tuple.Create(8, 3), 2},
	{Tuple.Create(8, 5), 1},
};

var edgesToAxisEnds = new Dictionary, int> {
	{Tuple.Create(0, 4), 0},
	{Tuple.Create(1, 3), 3},
	{Tuple.Create(1, 5), 1},
	{Tuple.Create(2, 4), 2},
	{Tuple.Create(3, 1), 0},
	{Tuple.Create(4, 0), 3},
	{Tuple.Create(4, 2), 1},
	{Tuple.Create(5, 1), 2},
	{Tuple.Create(3, 4), 0},
	{Tuple.Create(4, 3), 3},
	{Tuple.Create(4, 5), 1},
	{Tuple.Create(5, 4), 2},
	{Tuple.Create(3, 7), 0},
	{Tuple.Create(4, 6), 3},
	{Tuple.Create(4, 8), 1},
	{Tuple.Create(5, 7), 2},
	{Tuple.Create(3, 10), 0},
	{Tuple.Create(4, 9), 3},
	{Tuple.Create(4, 11), 1},
	{Tuple.Create(5, 10), 2},
	{Tuple.Create(6, 4), 0},
	{Tuple.Create(7, 3), 3},
	{Tuple.Create(7, 5), 1},
	{Tuple.Create(8, 4), 2},
};

With all that prepared we can finally assert the corners:

Action setupSingleCorner = (x, y) => {
	int number = diagram[x][y];
	int position = number / 3 - 1;
	int permutation = number % 3;
	var face = cornersToFaces[Tuple.Create(x, y)];
	var diagonalEnd = cornersToDiagonalEnds[Tuple.Create(x, y)];
	
	foreach(var corner in corners){
		for(var piecePermutation = 0; piecePermutation < 3; ++piecePermutation){
			var wasPicked = corner.FinalPosition.Skip(position * 3).Skip(piecePermutation).First();
			var finalPermutation = (permutation + piecePermutation) % 3;
			var finalRotation = (corner.Rotations[finalPermutation] + fieldsOrientations[x][y]) % 4;
			var value = corner.Values[finalPermutation];
			
			if(value == 1){
				solver.Operation(
					wasPicked,
					solver.Operation(
						facesDirections.Skip(face * 4).Take(4).ToArray()[finalRotation],
						facesDirections.Skip(face * 4).Take(4).ToArray()[(finalRotation + 2)%4]
					)
				).Set(solver.FromConstant(1));
			}else{
				solver.Operation(
					wasPicked,
					facesDirections.Skip(face * 4).Take(4).ToArray()[finalRotation]
				).Set(solver.FromConstant(1));
			}
			
			solver.Operation(
				wasPicked,
				cornersNumbers.Skip(face * 4 * 9).Skip(diagonalEnd * 9).Take(9).ToArray()[value - 1]
			).Set(solver.FromConstant(1));
		}
	}
};

We take some metadata about the piece we are in (lines 2-6). Next, we iterate over all corners and permutations. However, this time instead of asking “is this corner in that permutation assigned to this field”, we simply take what was assigned and enforce the proper bitflags.

We first take the bit indicating whether a given piece was assigned to this corner and this permutation (line 10). Next, we calculate the final permutation in this field (line 11) and the final rotation including directions of the arrows (line 12). We also take the value of the piece (line 13). Notice that this time we don’t extract these values from the ILP variables. We precalculate them outside of the model which is much faster.

We can now do two simple constraints. First, if this digit is one (line 15) then we enforce this constraint: if this piece was picked (line 17), then direction of the face needs to be either the same as the direction of the piece (line 19) or the opposite (line 20). If the digit is not one, then we enforce the constraint, that if the piece was picked, than the boolean flag indicating the direction of the face must be selected (line 26).

The crucial difference is that we don’t calculate the direction within the model now. We do the causation outside of the model. We encode something like “I don’t know what piece was selected, but if the piece I’m currently looking at was selected, then this bit flag of the face direction must be selected too”.

The next constraint we add is for the numbers: if the piece was picked (line 31) then the number assigned to the corner is selected (line 32). Again, we don’t care about the actual value if it was selected or not. We just make sure that if it was selected, then some other bit flag is set.

We can now setup all corners:

Action setupCorners = (x, y) => {
	setupSingleCorner(x, y);
	setupSingleCorner(x, y+2);
	setupSingleCorner(x+2, y+2);
	setupSingleCorner(x+2, y);
};

We do very similar stuff for edges:

Action setupSingleEdge = (x, y) => {
	int number = diagram[x][y];
	int position = number / 2 - 1;
	int permutation = number % 2;
	var face = edgesToFaces[Tuple.Create(x, y)];
	var axisEnd = edgesToAxisEnds[Tuple.Create(x, y)];
	
	foreach(var edge in edges){
		for(var piecePermutation = 0; piecePermutation < 2; ++piecePermutation){
			var wasPicked = edge.FinalPosition.Skip(position * 2).Skip(piecePermutation).First();
			var finalPermutation = (permutation + piecePermutation) % 2;
			var finalRotation = (edge.Rotations[finalPermutation] + fieldsOrientations[x][y]) % 4;
			var value = edge.Values[finalPermutation];
			
			if(value == 1){
				solver.Operation(
					wasPicked,
					solver.Operation(
						facesDirections.Skip(face * 4).Take(4).ToArray()[finalRotation],
						facesDirections.Skip(face * 4).Take(4).ToArray()[(finalRotation + 2)%4]
					)
				).Set(solver.FromConstant(1));
			}else{
				solver.Operation(
					wasPicked,
					facesDirections.Skip(face * 4).Take(4).ToArray()[finalRotation]
				).Set(solver.FromConstant(1));
			}
			
			solver.Operation(
				wasPicked,
				edgeNumbers.Skip(face * 4 * 9).Skip(axisEnd * 9).Take(9).ToArray()[value - 1]
			).Set(solver.FromConstant(1));
		}
	}
};

Action setupEdges = (x, y) => {
	setupSingleEdge(x, y+1);
	setupSingleEdge(x+1, y);
	setupSingleEdge(x+1, y+2);
	setupSingleEdge(x+2, y+1);
};

Finally, we encode faces:

Action setupSingleFace = (x, y) => {
	setupCorners(x, y);
	setupEdges(x, y);
};

Action setupFaces = () => {
	setupSingleFace(0, 3);
	setupSingleFace(3, 0);
	setupSingleFace(3, 3);
	setupSingleFace(3, 6);
	setupSingleFace(3, 9);
	setupSingleFace(6, 3);
};

setupFaces();

We run it and this is the result we get:

Tried aggregator 2 times.
MIP Presolve eliminated 7285 rows and 3504 columns.
MIP Presolve modified 1149 coefficients.
Aggregator did 3596 substitutions.
Reduced MIP has 979 rows, 844 columns, and 4885 nonzeros.
Reduced MIP has 844 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.03 sec. (15.56 ticks)
Found incumbent of value 0.000000 after 0.03 sec. (24.88 ticks)

Root node processing (before b&c):
  Real time             =    0.03 sec. (25.19 ticks)
Parallel b&c, 12 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    0.03 sec. (25.19 ticks)
     ---                        ---
    |239|                      |333|
    |568|                      |3 3|
    |147|                      |333|
 --- --- --- ---           --- --- --- ---
|829|523|681|529|          |222|111|111|111|
|157|618|974|347|          |2 2|1 1|1 1|1 1|
|634|497|532|681|          |222|111|111|111|
 --- --- --- ---            --- --- --- ---
    |863|                      |111|
    |219|                      |1 1|
    |457|                      |111|
     ---                        ---

It took 30 milliseconds to find the answer. First implementation couldn’t do that in 8 hours. Not to mention that the first implementation ran on Gurobi in NEOS, and the second one was running with CPLEX on my local machine.

Reading the solution

Let’s read the solution. We can see that when we hold the cube in a way that the top side has center 6, front side has center 1, and bottom side has center 1, then the top side looks to the left, left side looks down, front and right and back and down sides look to the right. We can also see all the numbers assigned, so we know the “colors” of the pieces. We can now apply the regular algorithms for solving the cube.

The last remaining piece is how to rotate centers. There are two algorithms for that:

Top center clockwise and front center counter-clockwise: f b’ l r’ u d’ f’ u’ d l’ r f’ b u
Top center 180 degrees: u r l uu r’ l’ u r l uu r’ l’

We can now easily solve the cube:

Lessons learned

There are some important tricks we applied to optimize the solution:

We stored numbers as bitflags instead of storing them as integers. This is a common trick. If you know the range of the variables, then don’t use integers. Bitflags are much faster.
We precalcualted results outside of the model. Instead of creating a variable with a value of the face rotation, we calculated the rotation outside of the model, and then added a constraint (basically, an “if” condition in the ILP)
We didn’t compare numbers. Generally, don’t do that if it’s possible. Instead, just create a boolean flag indicating the result of comparison and use it later onw. The difference is subtle but improves the performance a lot.
We didn’t use “if else” conditions. They look easy, but they are really the performance killer.

With all these improvements in place, we managed to solve the cube in milliseconds.

Distributed Designs Part 3 — Taking lock in MVCC for transactional outbox pattern

afish — Fri, 03 Feb 2023 09:00:30 +0000

This is the third part of the Distributed Designs series. For your convenience you can find other parts in the table of contents in Part 1 — Outbox without idempotency nor synchronous commit

Last time we saw how to use transactional outbox pattern with multiple databases and no synchronous commit. We also learned how to take the lock on the database end to make sure that we can scale out the Relay. However, what if we use Multi-version Concurrency Control (MVCC) or can’t enforce pessimistic locking in general? Can we implement the lock in that case?

Solution

We need to implement leases. The idea is:

Create a table with leases
Take the lease if it’s not taken yet
Process rows
Release the lease

The only tricky part is how to release the lease automatically in case of a crash. However, this we can do with timestamps. The idea is:

CREATE TABLE leases(name VARCHAR(MAX), lease_time DATETIME);
INSERT INTO leases(name, lease_time) VALUES ('lease_name', NULL);

Now, we want to take the lease if and only if it’s not taken yet. Let’s do this:

while(true){
   beginTransaction(REPEATABLE READ);
   lease_name, existingTimestamp = SELECT name, lease_date FROM leases WHERE lease_date < NOW() AND name = 'lease_name';
   if(lease_name IS NOT NULL) {
      UPDATE leases SET lease_date = NOW() + 1 minute WHERE name = 'lease_name';
      try{
          COMMIT; // First commit
      }catch{
          // Someone updated the lease before us. Let's try again
          // The transaction is now rolled back
          continue;
      }
      
      // beginTransaction(REPEATABLE READ); Process messages and set their status properly; COMMIT;

      beginTransaction(REPEATABLE READ);
      UPDATE leases SET lease_date = NOW() WHERE name = 'lease_name';
      COMMIT;
   }else {
      // We didn't find the lease, so it's not available
      // Let's roll back and back off
      ROLLBACK;
      sleep(5);
      continue;
   }
}

We take the lease row. If it’s missing, then it means that the lease is not available (someone else holds it). We wait and try again.

If the lease is available, then we try to take it. We try updating the row and book it for one minute. We then try to commit. If this fails, then it means that someone else modified the lease. We need to back off and try again.

However, if we succeed to take the lease, then we can get the messages from the outbox table. We don’t need to do anything special now because nobody else will fiddle with the outbox. We need to finish in one minute, and then we can release the lease.

Why does it work? What isolation level should I use?

Let’s stop for a moment and analyze why it even works and what isolation level we should use. We tried updating the lease with the following:

UPDATE leases SET lease_date = NOW() + 1 minute WHERE name = 'lease_name';

What we should in fact do is this:

UPDATE leases SET lease_date = NOW() + 1 minute WHERE name = 'lease_name' AND lease_date = existingTimestamp;

If we run this query with REPEATABLE READ, then the database engine simply can’t let the UPDATE to complete if someone else modified the row. That’s because the UPDATE needs to read the row again (to check the filtering criteria). Since we run on REPEATABLE READ, then the second read must return exactly the same data. Therefore, either nobody else modified the row, or the UPDATE fails and the transaction is rolled back.

Therefore, after the first commit we can be sure that we have the lease. I can’t really imagine a database that would claim that it meets the ACID requirements and would still let this commit to succeed just to break the data later on. Such a database would be a very interesting (not necessarily useful) case. Obviously, with distributed databases we may get some different isolation levels, some the actual optimizations may be different and break this mechanism. However, according to the SQL standard, this solution should work, as it simply implements the Compare-and-swap operation on the database level.

In short, this is your checklist:

Use REPEATABLE READ
If you can enforce eager locks in the database, just use them without and leases and rely on the locks maintained by the database engine
If you can’t enforce eager locks (so the database engine uses optimistic locking), then implement the lease protocol defined above

Now you can scale your Relay to multiple instances and still get the correct results.

Summary

We implemented a generic lock for MVCC. You can use it for the transactional outbox pattern or for whatever else.

Distributed Designs Part 2 — Transactional outbox pattern and multiple instances of relay

afish — Fri, 27 Jan 2023 09:00:26 +0000

This is the second part of the Distributed Designs series. For your convenience you can find other parts in the table of contents in Part 1 — Outbox without idempotency nor synchronous commit

Last time we saw how to use transactional outbox pattern with multiple databases and no synchronous commit. We learned how to synchronize things between datacenters. The solution used delays in Relay component to get messages from the same datacenter only to avoid having the lock between databases.

Now, let’s consider another problem: can we scale out Relay? In other words, can we have multiple instances of Relay running in the same datacenter? Let’s see.

Should we scale Relay?

First, let’s be explicit: we most likely don’t need to scale the Relay. One instance is enough from the performance perspective. Obviously, there are cases when we have so many messages to propagate that we could benefit from parallelizing that, but it’s not as straightforward as it may seem. Relay needs to meet the following requirements:

Ideally, Relay shouldn’t produce duplicates (on the happy path)
Relay should process messages in the proper order. We don’t want to reorder the events if possible
Relay should be fast. We should avoid locks and delays if possible

Being that said, it gets tricky to parallelize Relay. We need to send messages serially, so there is no easy way to make it faster.

However, we may need to scale out Relay because we run things in parallel by default and we can’t have just one instance. Without going into details whether it’s reasonable, we may be forced to run multiple instances of Relay. How to do it?

Naïve scaling

When people describe transactional outbox pattern, they typically focus on the idea to insert business entity and message entity in the same transaction. However, there is another important problem to solve: how to read the messages from the table to avoid duplicating messages sent to the queue? If you just scale out Relay, then you’ll effectively get duplicates.

Typically, Relay works this way:

openTransaction();
var messages = getMessagesFromTheDatabase();
foreach (var message in messages){
    sendMessageToTheQueue(message);
    markMessageAsSent(message);
}
commitTransaction();

Let’s say there are two instances of Relay. Both of them get messages from the database, both of them send them to the queue, and then both of them try to mark messages as sent and commit changes to the database. However, one instance will succeed, and the other instance will simply fail. This is not a problem per se, the message is still delivered to the queue. However, with this approach we will have duplicates on the happy path.

To solve that, we need to block the latter Relay instance from reading the rows that are being processed by the former instance. To do that, we need to make sure that locks are properly taken on the database end. Specifically, we need the following:

When reading a row, a lock is taken
The lock prevents other transactions from modifying the row until the end of the current transaction
The lock prevents other transaction from reading the row

Let’s examine one by one.

When reading a row, a lock is taken

This is done automatically by the database engine. Whenever we touch the row, the locks are taken appropriately.

The lock prevents other transactions from modifying the row until the end of the current transaction

This is seemingly easy. We have various database isolation levels. However, they typically focus on reading the data when they can be modified by other transaction. However, just preventing the modifications is not enough. Let’s see why.

First, let’s create the table:

CREATE TABLE dbo.t (a INT);
INSERT INTO dbo.t(a) VALUES (10);

Let’s now try running things in parallel with READ COMMITTED (the default) using MS SQL:

SET TRANSACTION ISOLATION LEVEL READ COMMITTED 
BEGIN TRANSACTION
SELECT * FROM dbo.t
                                                                             SET TRANSACTION ISOLATION LEVEL READ COMMITTED
                                                                             BEGIN TRANSACTION
                                                                             SELECT * FROM dbo.t
                                                                             UPDATE dbo.t SET a = 3
                                                                             COMMIT
UPDATE dbo.t SET a = 2
COMMIT

First transaction reads the row, takes the lock, and immediately releases it. Second transaction reads the row, updates it, and commits. First transaction updates the row and commits. There is no error here, no exception. It just works. This way, we get duplicates in the queue.

Let’s change the isolation level to REPEATABLE READ:

SET TRANSACTION ISOLATION LEVEL REPEATABLE READ
BEGIN TRANSACTION
SELECT * FROM dbo.t
                                                                             SET TRANSACTION ISOLATION LEVEL REPEATABLE READ
                                                                             BEGIN TRANSACTION
                                                                             SELECT * FROM dbo.t
                                                                             UPDATE dbo.t SET a = 3
                                                                             -- THIS HANGS
UPDATE dbo.t SET a = 2
-- Msg 1205, Level 13, State 45, Line 5
-- Transaction (Process ID 53) was deadlocked on lock 
-- resources with another process and has been chosen 
-- as the deadlock victim. Rerun the transaction.
                                                                             COMMIT

First transaction reads the row. Second transaction reads the row properly. However, when it tries to update it, the second transaction hangs. The first transaction then hangs the same way and gets killed. The second transaction finishes properly. As a result, we get the duplicate in the queue. However, we observed the error in the Relay, but we can’t help that. It’s too late. We get the same with SERIALIZABLE.

However, what if we try that with MySQL? Since MySQL with InnoDB uses snapshots for REPEATABLE READ, we get the following:

SET TRANSACTION ISOLATION LEVEL REPEATABLE READ;
START TRANSACTION;
SELECT * FROM dbo.t;

                                                                             SET TRANSACTION ISOLATION LEVEL REPEATABLE READ;
                                                                             START TRANSACTION;
                                                                             SELECT * FROM dbo.t;
                                                                             UPDATE dbo.t SET a = 3;
                                                                             COMMIT;

UPDATE dbo.t SET a = 2;
COMMIT;

This works with no issue. When we move to SERIALIZABLE, we get this:

SET TRANSACTION ISOLATION LEVEL REPEATABLE READ;
START TRANSACTION;
SELECT * FROM dbo.t;

                                                                             SET TRANSACTION ISOLATION LEVEL REPEATABLE READ;
                                                                             START TRANSACTION;
                                                                             SELECT * FROM dbo.t;
                                                                             UPDATE dbo.t SET a = 3;

UPDATE dbo.t SET a = 2;
-- ERROR 1213 (40001): Deadlock found when 
-- trying to get lock; try restarting transaction

                                                                             COMMIT;

Therefore, SERIALIZABLE makes the issue visible. Similarly, for Oracle we would get ORA-08177: can't serialize access for this transaction.

From the theoretical point of view, we need to use REPEATABLE READ isolation level. However, the problem is with the actual implementations. Typically, the database engine doesn’t try to predict the future, so the engine won’t stop the transaction from moving forward just because something wrong could happen. Instead, the engine decides to roll things back in case of issues. That’s why we get an error in the REPEATABLE READ or SERIALIZABLE examples above. This is not enough for us, though. We need to prevent others from reading the rows and not let them move forward. To see how to do that, let’s move on.

The lock prevents other transaction from reading the row

When we read about database isolation levels, they typically focus on preventing modifications to the row we want to read. However, they don’t cover how to prevent other transactions from reading the row at all. To do that, we can use the SELECT FOR UPDATE syntax. In practice, this is not a matter of the isolation level, but rather a case of taking the lock for updates and the internal database implementation. Let’s see how to do that in MS SQL:

SET TRANSACTION ISOLATION LEVEL READ COMMITTED 
BEGIN TRANSACTION
SELECT * FROM dbo.t WITH (UPDLOCK)
                                                                             SET TRANSACTION ISOLATION LEVEL READ COMMITTED
                                                                             BEGIN TRANSACTION
                                                                             SELECT * FROM dbo.t WITH (UPDLOCK)
                                                                             -- This waits
UPDATE dbo.t SET a = 2
COMMIT
                                                                             UPDATE dbo.t SET a = 3
                                                                             COMMIT

Similarly, we can do the same in MySQL or Oracle using SELECT * FROM dbo.t FOR UPDATE;.

This way we can block the row and make sure that no duplicates are sent to the queue. And notice that it works with READ COMMITTED. Read on to understand why.

What isolation level should I choose? And what about snapshots?

Let’s now consider what isolation level we should choose and why.

In theory, we need to go with REPEATABLE READ or above. That’s because READ COMMITTED guarantees that we read only the committed data. However, committed doesn’t mean latest. We can read a row that has its values updated already but these values are not committed yet. What’s worse, in theory we can read data that has been changed already and committed to the database. If we take that to the extreme, we could even always read the same empty result, because at some point that’s what was committed to the database. This is crazy, but if our transaction doesn’t modify the rows at all, then it’s perfectly valid according to the definition (and completely unreasonable and unexpected).

However, REPEATABLE READ makes it much more predictable. That’s because the UPDATE statement needs to read the rows again. Therefore, if the row was modified at some point and committed to the database, then the UPDATE would fail because it wouldn’t find the same row which is against the definition of REPEATABLE READ. Therefore, we need to go with REPEATABLE READ to make sure the result is correct at the very end.

Use REPEATABLE READ

However, we also need to prevent others from reading the rows. To guarantee that, we can either rely on the definitions or on the actual implementation. According to the definitions of the isolation levels, we must use at least REPEATABLE READ. But in order to block other readers, we need to understand whether the database uses pessimistic or optimistic locking. Typically, common SQL databases use pessimistic locking with optimizations, so they take locks as late as possible and escalate them as late as possible. We can enforce taking locks earlier by using FOR UPDATE syntax which makes the database to take the locks eagerly. The side effect of that is that the protocol we defined above works with READ COMMITTED. That’s just a coincidence, not something that we should rely on.

However, this approach won’t work for snapshot isolation and Multi-version Concurrency Control (MVCC). That’s because MVCC effectively instructs the database to take locks as late as possible. The database will either fail with FOR UPDATE syntax, or the database will simply ignore it and carry on with optimistic locking. We’ll see in the next post how to fix that.

In short: use REPEATABLE READ and take locks eagerly to avoid rollbacks. If you can’t take locks eagerly (because the database uses MVCC or forces optimistic locking), then you need a different protocol that I cover here

What about the performance?

We can see that this approach will not give us benefits. How can we process things faster and still maintain the order? The solution would be to read messages in batches, send these batches to the queue, but commit them only after. This would effectively create a transaction in the queue. It would look like this:

readFirstHundredRows();
sendThemToTheQueue();
                                                   readSecondHundredRows();
                                                   sendThemToTheQueue();
commitRows();
                                                   commitRows();

This way we can improve the performance. However, implementing this solution is hard and it requires the way to commit messages on the queue end which may not be supported.

Summary

Transactional outbox pattern requires not only the transaction for the business entity and the message, but also the careful extraction of the messages. It may be a little bit harder when we scale out Relay to run multiple instances.

.NET Inside Out Part 30 – Conditional types in C#

afish — Fri, 20 Jan 2023 09:00:35 +0000

This is the thirtieth part of the .NET Inside Out series. For your convenience you can find other parts in the table of contents in Part 1 – Virtual and non-virtual calls in C#

TypeScript has a very nice feature called conditional types. Can we mimic something like this in C#? Let’s say that we have one API endpoint that should return different output depending on the type of the input.

We can start with the following code:

using System;
					
public class Program
{
	public static void Main()
	{
		Console.WriteLine(GetForInput(new ScenarioAInput()).GetType());
		Console.WriteLine(GetForInput(new ScenarioBInput()).GetType());
	}
	
	public static Output GetForInput(Input input) where T: Scenario{
		if(typeof(Input).IsAssignableFrom(input.GetType())){
			return (Output)(object)GetForInputA((ScenarioAInput)(object)input);
		}
		if(typeof(Input).IsAssignableFrom(input.GetType())){
			return (Output)(object)GetForInputB((ScenarioBInput)(object)input);
		}
		
		throw new Exception("Bang!");
	}
	
	public static ScenarioAOutput GetForInputA(ScenarioAInput input){
		return new ScenarioAOutput();
	}
	
	public static ScenarioBOutput GetForInputB(ScenarioBInput input){
		return new ScenarioBOutput();
	}
}

public abstract class Scenario {
}

public class ScenarioA : Scenario{
}

public class ScenarioB: Scenario{
}

public abstract class Input where T: Scenario{
}

public class ScenarioAInput : Input {
}

public class ScenarioBInput : Input {
}

public abstract class Output where T: Scenario{
}

public class ScenarioAOutput: Output {
}

public class ScenarioBOutput: Output{
}

This works but is a little bit cumbersome. When we need to add new implementation, we need to add another if condition. Can we do better? Well, a little:

using System;
using System.Linq;
using System.Collections.Generic;
					
public class Program
{
	public static void Main()
	{
		Console.WriteLine(GetForInput(new ScenarioAInput()).GetType());
		Console.WriteLine(GetForInput(new ScenarioBInput()).GetType());
	}
	
	public static Output GetForInput(Input input) where T: Scenario {
		List implementations = new List(){
			new ScenarioA(),
			new ScenarioB()
		};
		
		foreach(var implementation in implementations){
			if(implementation.GetType().GetInterfaces().First().GetGenericArguments().First() == typeof(T)){
				return ((Scenario)implementation).Calculate(input);
			}
		}
		
		throw new Exception("Didn't work");
	}
}

public interface Scenario{
}

public interface Scenario : Scenario where T: Scenario {
	Output Calculate(Input input);
}

public class ScenarioA : Scenario {
	public Output Calculate(Input input){
		return new ScenarioAOutput();
	}
}

public class ScenarioB: Scenario {
	public Output Calculate(Input input){
		return new ScenarioBOutput();
	}
}

public abstract class Input where T: Scenario {
}

public class ScenarioAInput : Input {
}

public class ScenarioBInput : Input {
}

public abstract class Output where T: Scenario {
}

public class ScenarioAOutput: Output {
}

public class ScenarioBOutput: Output {
}

Now adding new type requires adding new instance to the collection. However, this time we can scan all the types and crate them on the fly as needed with DI or whatever other mechanism.

Availability Anywhere Part 19 — Banning RDP and SSH attacks

afish — Fri, 13 Jan 2023 09:00:05 +0000

This is the nineteenth part of the Availability Anywhere series. For your convenience you can find other parts in the table of contents in Part 1 – Connecting to SSH tunnel automatically in Windows

If you expose RDP or OpenSSH to the wide Internet, you’ll most likely get automated attacks. There is a way to block these attacks with firewall, but I didn’t find a nice solution to do so, so I created my own.

The idea is as follows: we periodically scan event log to get failed authentication attempts. We extract the IP address, and then ban it if it happened too often.

Event for RDP is in Security with ID 4625:

- 
- 
   
  4625 
  0 
  0 
  12544 
  0 
  0x8010000000000000 
   
  27785286 
   
   
  Security 
  COMPUTER 
   
  
- 
  S-1-0-0 
  - 
  - 
  0x0 
  S-1-0-0 
  administrator 
  domainname 
  0xc000006d 
  %%2313 
  0xc000006a 
  3 
  NtLmSsp 
  NTLM 
  LOCALPCNAME 
  - 
  - 
  0 
  0x0 
  - 
  ADDRESS 
  PORT

For OpenSSH we extract these two events: Applications and Services -> OpenSSH -> Admin for IDs 1 and 2:

- 
- 
   
  1 
  0 
  1 
  0 
  0 
  0x8000000000000000 
   
  46166 
   
   
  OpenSSH/Admin 
  COMPUTER 
   
  
- 
  sshd 
  fatal: Timeout before authentication for ADDRESS port PORT

and

- 
- 
   
  2 
  0 
  2 
  0 
  0 
  0x8000000000000000 
   
  45523 
   
   
  OpenSSH/Admin 
  COMPUTER 
   
  
- 
  sshd 
  error: maximum authentication attempts exceeded for invalid user root from ADDRESS port PORT ssh2 [preauth]

We ban them with the following:

while($True){	
	write-host (Get-Date)
	$timeFrame = (Get-Date).AddMinutes(-15)
	$attackThreshold = 20
	$maxEvents = 10000

	$logsWithPatterns = @(
		@("Security", 4625, @("Source Network Address")),
		@("OpenSSH/Admin", 2, @("maximum authentication attempts")),
		@("OpenSSH/Admin", 1, @("Timeout before authentication"))
	)

	$newIpAddressesToBan = $logsWithPatterns | %{
		$log = $_[0]
		$id = $_[1]
		$patterns = $_[2]
		write-host $log, " ", $id, " ", $patterns
		
		Get-WinEvent $log -maxevents $maxEvents | ? {$_.id -eq $id } | ?{$_.TimeCreated -ge $timeFrame } | %{ $_.message} | select-string  $patterns | %{ [regex]::match($_,'(\d{1,4}[.]\d{1,4}[.]\d{1,4}[.]\d{1,4})') } | ?{ $_.Success} | %{$_.Groups[0].Value} | group-object | ?{$_.Count -ge $attackThreshold} | %{$_.Name}
	}

	$newIpAddressesToBan = @(($newIpAddressesToBan | %{ $_.Substring(0, $_.lastIndexOf(".")) + ".0/255.255.255.0"}) | sort | get-unique)

	$existingBannedIpAddresses = @((get-netfirewallrule -displayname "Rule for banning" | Get-NetFirewallAddressFilter).RemoteAddress | sort | get-unique)

	$allIpAddresses = (($newIpAddressesToBan + $existingBannedIpAddresses) | sort | get-unique)

	netsh advfirewall firewall set rule name="Rule for banning" new remoteip=([string]::Join(",", $allIpAddresses))
	
	sleep -s 60
}

I get at most 10000 events from the last 15 minutes, and I look for at least 20 attempts from a given IP. I extract IPv4 addresses with a regexp. I also replace them with a network subnet with mask of 24 bits.

Just run this script in the background with Administrator privileges and it will automatically add new IP addresses to the firewall. You need to create the rule Rule for banning manually beforehand as you need. If you need some other patterns or event logs, just add them to the collection at the beginning.

Availability Anywhere Part 18 — Binding same port for multiple docker containers

afish — Fri, 06 Jan 2023 09:00:44 +0000

This is the eighteenth part of the Availability Anywhere series. For your convenience you can find other parts in the table of contents in Part 1 – Connecting to SSH tunnel automatically in Windows

Let’s say that you run a project with Docker that uses a webserver (like a frontend application). This application will need to talk to some other service, like backend or database. We already know hw to forward port from host to the container. This way we can host whatever service locally, and talk to it from the container. We can also expose the webserver port (be it 8080) to the host, so we can connect to it from our browser running locally.

Let’s now consider similar problem but in the opposite direction. Let’s say that we have multiple webservers running in multiple dockers, and we want to be able to connect to all of them simultaneously from the host. How to do that?

The problem we typically face is how we bind ports. When using docker, we typically do the following:

docker -p 8080:80

with docker-compose we would do this:

ports:
  - "8080:80"

However, we can’t expose multiple applications this way because only one binding is allowed. Technically, lines above try to bind port 80 in the container to the port 8080 on the default IP address of the Docker daemon (which is 0.0.0.0) or 0.0.0.0 for docker-compose. This effectively binds all available interfaces we have. So, how to deal with this? Let’s see multiple steps we can take.

First step – changing port bindings

That’s the easiest solution. Just change port bindings (to something like 8081:80) and off you go. The problem is that you need to keep a mental map of the bindings, you may need to change the connection strings, and you need to remember not to push these changes to the repository. The last one is especially tricky because you need to change the files for docker-compose that normally you want push to the repository.

Second step – using environment variables

12-Factor App Methodology tells us to use environment variables as much as possible. Based on that, we should change docker commands and docker-compose files to accept environment variables for port bindings. Since we can put these values in .env file and not push them to the repository, we can effectively change our configuration easily without changing the source code. However, since the connection strings are often in files that we need to push to the repository, this may still be not enough.

Unfortunately, this won’t work well if we decide to run the frontend locally (instead of running it in the docker). Since the frontend connects to the default port, this port won’t be available on the host (or will be mapped to some other application).

Third step – use separate network interfaces

Separate network interfaces can give us even more. When we bind ports like 8080:80, we actually bind them as in 0.0.0.0:8080:80. We already mentioned that 0.0.0.0 means “bind all interfaces”. However, we can change this to some other IP address. The question is which one to use.

Windows lets us create new loopback network interface with hdwwiz.exe. See the last section of this post for the instructions how to do that. Linux and Mac let us do similar with aliases and new loopback interfaces. What’s more, we can assign some new IP address to the interface (like 192.168.123.5) and use hosts file to map subdomain like MYPROJECT.localhost to that address.

This way we can easily separate the traffic. We now bind all ports to 192.168.123.5:80:80, change connection strings to sql://MYPROJECT.localhost:PORT, and finally connect to the application from the browser easily on MYPROJECT.localhost:80. We can also configure Multi-Account Containers in Firefox or FoxyProxy in Firefox/Chrome to connect via Socks proxy forwarded from the docker container, so we would just connect as we were in the docker.

The cool part is that this will work the same way regardless of running that in the docker or locally. If we run inside the docker, then MYPROJECT.localhost:PORT will resolve to something like 127.0.0.1:PORT which works well because we forward port from the host to the docker container. However, if we run it locally, then it will resolve to 192.168.123.5:PORT that is accessible from the host thanks to the interface.

What’s more, we can modify docker-compose and docker commands transparently and push changes to the repository. Other developers on the team won’t be affected, and we will be able to separate traffic from multiple projects locally. If some other developer doesn’t have new interface configured and hosts file modified, then MYPROJECT.localhost will resolve to 127.0.0.1 and will still work.

Creating new network interface with IP address

In Windows

Run hdwwiz.exe
Install the hardware that I manually select from the list (Advanced)
Network adapters
Microsoft -> Microsoft KM-TEST Loopback Adapter
Go to network adapters. Rename the new adapter to MYPROJECT. Manually set the IP address to something like 192.168.123.5. Set mask to 255.255.255.255. Set DNS IP to 8.8.8.8
Edit C:\windows\system32\drivers\etc\hosts and add the following line: 192.168.123.5 MYPROJECT.localhost

In Linux

ifconfig lo:1 192.168.123.5/24

In mac

ifconfig lo0 alias 192.168.123.5

ILP Part 104 — 12 stones riddle

afish — Fri, 30 Dec 2022 09:00:19 +0000

This is the one hundred and fourth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we are going to solve the 12 Stones Logic Puzzle. We have 12 stones, 11 of them are of equal weight, 1 is of unequal weight (could be lighter or heavier). We can use at most 3 weightings on a balance scale to find the odd stone and tell whether it’s lighter or heavier.

That’s gonna be a little bit tricky to understand, but let’s try it out. We want to implement an ILP model that will give us a recipe for finding the odd stone. Notice, that this problem seems to be even harder than NP class because we can’t verify the solution in polynomial time.

The idea is as follows:

We create 24 lists. Each list contains exactly 3 integers. Each integer indicates which subset of stones to put on the left side of the scale, and which stones to put on the right side of the scale.
Each list is supposed to determine the “designated stone”, so provide the weightings that will determine that the stone number is lighter (heavier).
For each list, we calculate the results of weightings for every possible input (which stone is odd and how). This gives us a three dimensional list of [listId][number of weighting][which stone is odd and how].
For each list, we make sure that we get unique weighting results for the “designated stone” of that list (so results of weightings for that list for other stones must be different).
Each list must expect unique result of weightings.
When two lists have the same prefix of how to put stones and what result to expect for first steps, then their -th step must be the same (to have deterministic solution).

That was quite a lot. Let’s see the code:

var stonesCount = 12;
var weightingsCount = 3;
var needToFindIfHeaverOrLigher = true;

// --------------------------------------------------------

// [listId][whichWeighting][whichStone][wasLeftLighter + wasRightLighter + wasEqual]
var weightingResultsCount = 3;
var weightingResults = Enumerable.Range(0, 2*stonesCount).Select(listId =>
	// Number of weighting
	Enumerable.Range(0, weightingsCount).Select(weighting =>
		// stone 1 lighter, stone 1 heavier, stone 2 lighter, stone 2 heavier, ...
		Enumerable.Range(0, 2 * stonesCount).Select(stoneId => 
			// wasLeftLighter, wasRightLighter, wasEqual
			Enumerable.Range(0, weightingResultsCount).Select(resultId => 
				solver.CreateAnonymous(Domain.BinaryInteger)
			).ToArray()
		).ToArray()
	).ToArray()
).ToArray();

// For each list, for each weighting, for each stone, exactly one result is possible
for(int listId = 0; listId < 2 * stonesCount; ++listId){
	for(int weighting = 0; weighting < weightingsCount; ++weighting){
		for(int stoneId = 0; stoneId < 2 * stonesCount; ++stoneId){
			solver.Operation(weightingResults[listId][weighting][stoneId]).Set(solver.FromConstant(1));
		}
	}
}


// [listId][whichWeighting][putOnLeft, putOnRight]		
// Stone 1 lighter, stone 1 heavier, stone 2 lighter, stone 2 heavier, stone 3 lighter...
var weightingLists = Enumerable.Range(0, 2*stonesCount).Select(listId =>
	// Number  of weighting
	Enumerable.Range(0, weightingsCount).Select(weighting =>
		// stone 1 on left, stone 2 on left, stone 3 on left, ..., stone #stonesCount on left, stone 1 on right...
		Enumerable.Range(0, 2 * stonesCount).Select(stoneId => 
			solver.CreateAnonymous(Domain.BinaryInteger)
		).ToArray()
	).ToArray()
).ToArray();

// For each list, for each weighting, make sure that we put some stone on the scale
for(int listId = 0; listId < 2 * stonesCount; ++listId){
	for(int weighting = 0; weighting < weightingsCount; ++weighting){
		solver.Operation(weightingLists[listId][weighting]).Set(solver.FromConstant(1));
	}
}

// For each list, for each weighting, make sure that each stone is either on the left, or on the right, or nowhere
for(int listId = 0; listId < 2 * stonesCount; ++listId){
	for(int weighting = 0; weighting < weightingsCount; ++weighting){
		for(int stoneId = 0; stoneId < stonesCount; ++stoneId){
			solver
				.Operation(weightingLists[listId][weighting][stoneId], weightingLists[listId][weighting][stonesCount + stoneId])
				.Set(solver.FromConstant(1));
		}
	}
}


// For each list, for each weighting, calculate the result based on the known input
for(int listId = 0; listId < 2 * stonesCount; ++listId){
	for(int weighting = 0; weighting < weightingsCount; ++weighting){
		for(int stoneId = 0; stoneId < 2 * stonesCount; ++stoneId){
			var stonesCountOnTheLeft = solver.Operation(weightingLists[listId][weighting].Take(stonesCount).ToArray());
			var stonesCountOnTheRight = solver.Operation(weightingLists[listId][weighting].Skip(stonesCount).Take(stonesCount).ToArray());
			
			var isThisListForLighterCase = stoneId % 2 == 0;
			
			var hasSpecialStoneOnLeft = weightingLists[listId][weighting][stoneId/2];
			var hasSpecialStoneOnRight = weightingLists[listId][weighting][stonesCount + stoneId/2];
			
			// Left has fewer stones (left is lighter)
			solver.Operation(
				stonesCountOnTheLeft.Operation(stonesCountOnTheRight),
				weightingResults[listId][weighting][stoneId][0]
			).Set(solver.FromConstant(1));
			
			// Right has fewer stones (right is lighter)
			solver.Operation(
				stonesCountOnTheLeft.Operation(stonesCountOnTheRight),
				weightingResults[listId][weighting][stoneId][1]
			).Set(solver.FromConstant(1));
			
			// Have equal stones
			if(isThisListForLighterCase){
				// Lighter stone is on the left (left is lighter)
				solver.Operation(
					stonesCountOnTheLeft.Operation(stonesCountOnTheRight)
						.Operation(hasSpecialStoneOnLeft),
					weightingResults[listId][weighting][stoneId][0]
				).Set(solver.FromConstant(1));
				
				// Lighter stone is on the right (right is lighter)
				solver.Operation(
					stonesCountOnTheLeft.Operation(stonesCountOnTheRight)
						.Operation(hasSpecialStoneOnRight),
					weightingResults[listId][weighting][stoneId][1]
				).Set(solver.FromConstant(1));
				
				// There is no lighter stone here (are equal)
				solver.Operation(
					stonesCountOnTheLeft.Operation(stonesCountOnTheRight)
						.Operation(hasSpecialStoneOnLeft.Operation(), hasSpecialStoneOnRight.Operation()),
					weightingResults[listId][weighting][stoneId][2]
				).Set(solver.FromConstant(1));
			}else {
				// Heavier stone is on the left (righti s lighter)
				solver.Operation(
					stonesCountOnTheLeft.Operation(stonesCountOnTheRight)
						.Operation(hasSpecialStoneOnLeft),
					weightingResults[listId][weighting][stoneId][1]
				).Set(solver.FromConstant(1));
				
				// Heavier stone is on the right (left is lighter)
				solver.Operation(
					stonesCountOnTheLeft.Operation(stonesCountOnTheRight)
						.Operation(hasSpecialStoneOnRight),
					weightingResults[listId][weighting][stoneId][0]
				).Set(solver.FromConstant(1));
				
				// There is no heavier stone here (are equal)
				solver.Operation(
					stonesCountOnTheLeft.Operation(stonesCountOnTheRight)
						.Operation(hasSpecialStoneOnLeft.Operation(), hasSpecialStoneOnRight.Operation()),
					weightingResults[listId][weighting][stoneId][2]
				).Set(solver.FromConstant(1));
			}
		}
	}
}


// For each list pair, for each prefix length, check if prefixes are the same and the weighting results are the same, then next step must be the same
for(int listId = 0; listId < 2 * stonesCount; ++listId){
	for(int listId2 = listId + 1; listId2 < 2 * stonesCount; ++listId2){
		var arePrefixesEqual = solver.FromConstant(1);
		for(int prefixLength = 0; prefixLength < weightingsCount; ++ prefixLength){
			for(int stoneId = 0; stoneId < 2*stonesCount; ++stoneId){
				solver
					.Operation(
						arePrefixesEqual,
						weightingLists[listId][prefixLength][stoneId].Operation(weightingLists[listId2][prefixLength][stoneId])
					).Set(solver.FromConstant(1));
			}
			
			for(int stoneId = 0; stoneId < 2*stonesCount; ++stoneId){
				arePrefixesEqual = arePrefixesEqual.Operation(
					weightingLists[listId][prefixLength][stoneId].Operation(weightingLists[listId2][prefixLength][stoneId])
				);
			}
			
			for(int weightingResult = 0; weightingResult < weightingResultsCount; ++weightingResult){
				arePrefixesEqual = arePrefixesEqual.Operation(
					weightingResults[listId][prefixLength][listId][weightingResult]
					.Operation(weightingResults[listId2][prefixLength][listId2][weightingResult])
				);
			}
		}
	}
}

// All list pairwise must have different expected stones and results
for(int listId = 0; listId < 2 * stonesCount; ++listId){
	for(int listId2 = listId + 1; listId2 < 2 * stonesCount; ++listId2){
		if(needToFindIfHeaverOrLigher == false && listId % 2 == 0 && listId2 == listId + 1){
			continue;
		}
	
		var areBothEqual = solver.FromConstant(1);
		for(int weighting = 0; weighting < weightingsCount; ++ weighting){
			for(int stoneId = 0; stoneId < 2*stonesCount; ++stoneId){
				areBothEqual = areBothEqual.Operation(
					weightingLists[listId][weighting][stoneId].Operation(weightingLists[listId2][weighting][stoneId])
				);
			}
			
			for(int weightingResult = 0; weightingResult < weightingResultsCount; ++weightingResult){
				areBothEqual = areBothEqual.Operation(
					weightingResults[listId][weighting][listId][weightingResult].Operation(weightingResults[listId2][weighting][listId2][weightingResult])
				);
			}
		}
		
		areBothEqual.Set(solver.FromConstant(0));
	}
}


// For each list, the designated stone must have different results than results for other stones
for(int listId = 0; listId < 2 * stonesCount; ++listId){
	for(int otherList = 0; otherList < 2 * stonesCount; ++otherList){
		if(listId == otherList){
			continue;
		}
		
		if(needToFindIfHeaverOrLigher == false && ((listId % 2 == 0 && otherList == listId + 1) || (listId % 2 == 1 && otherList == listId - 1))){
			continue;
		}
		
		var areBothEqual = solver.FromConstant(1);
		for(int weighting = 0; weighting < weightingsCount; ++ weighting){
			for(int weightingResult = 0; weightingResult < weightingResultsCount; ++weightingResult){
				areBothEqual = areBothEqual.Operation(
					weightingResults[listId][weighting][listId][weightingResult].Operation(weightingResults[listId][weighting][otherList][weightingResult])
				);
			}
		}
		
		areBothEqual.Set(solver.FromConstant(0));
	}
}

solver.AddGoal("goal", solver.FromConstant(0));
solver.Solve();


for(int listId = 0; listId < 2 * stonesCount; ++listId){
	Console.Write("Stone {0} {1}: ", listId/2 + 1, listId %2 == 0 ? "lighter" : "heavier");
	for(int weighting = 0; weighting < weightingsCount; ++weighting){
		var stonesOnTheLeft = string.Join(",", Enumerable
			.Range(0, stonesCount)
			.Select(stoneId => Tuple.Create(stoneId + 1, Math.Round(solver.GetValue(weightingLists[listId][weighting][stoneId])) > 0.5))
			.Where(tuple => tuple.Item2)
			.Select(tuple => tuple.Item1));
		var stonesOnTheRight = string.Join(",", Enumerable
			.Range(0, stonesCount)
			.Select(stoneId => Tuple.Create(stoneId + 1, Math.Round(solver.GetValue(weightingLists[listId][weighting][stonesCount + stoneId])) > 0.5))
			.Where(tuple => tuple.Item2)
			.Select(tuple => tuple.Item1));
			
		var weightingResult = Math.Round(solver.GetValue(weightingResults[listId][weighting][listId][0])) > 0.5
			? ">"
			: Math.Round(solver.GetValue(weightingResults[listId][weighting][listId][1])) > 0.5
				? "<"
				: Math.Round(solver.GetValue(weightingResults[listId][weighting][listId][2])) > 0.5
					? "="
					: "Something very wrong!";
			
		Console.Write("({0} ; {1}) [{2}] ; ", stonesOnTheLeft, stonesOnTheRight, weightingResult);
	}
	Console.WriteLine();
}

We set initial conditions in lines 1-3.

Next, we create the variables for weighting results (lines 7-20). That’s the four dimensional array. First dimension indicates which list this refers to. Second dimension indicates which weighting we perform (we have exactly 3 weightings in this scenario). Third level is for indicating which stone is odd (from the input). Last dimension consists of three binaries: whether the left side was lighter (moved up), whether the right side was lighter, whether both sides were equal.

Next, we make sure that we can get only one result for each weighting. This is in lines 22-29.

Next step defines another part of the model we have (lines 32-42). We need to define variables indicating which stones to put on the scale in each step. This is three dimensional array. First dimension indicates which list we have. Second dimension indicates which weighting we consider. Third dimension consists of 24 binaries: first 12 binaries indicate whether a given stone was put on the left side. Next 12 binaries do the same for the right side of the scale.

We now need to encode correctness conditions for the scale. First, we want to make sure, that we put some stones on the scale for each weighting. This is in lines 44-49. We basically take all the variables from the third dimension and make sure they are not all zeroes.

Next, we make sure that if we put a stone on the left side of the scale, then we don’t put it on the right side (and the opposite). This is in lines 51-60.

Next comes the core of the weightings. We need to calculate the result for a given list. ILP will evaluate some subset of stones to put on the scale, and we need to calculate how the scale moves. This is in lines 63-133. We iterate over every list, over every weighting, and over every instance of the input (which stone is odd and how). We then calculate some helper variables indicating whether we put more stones on one of the sides, whether this list is for checking if the stone is lighter or heavier, and whether the special stone has been put on the scale (and on which side). We then encode if conditions to make sure that the result of the weighting is stored properly.

Once we have that, we need to make sure, that our lists can actually identify the solution. We first make sure, that the algorithm we produce is deterministic. For each pair of lists, we take their prefix of steps, and if the prefixes match (so both lists tried weighting the same stones and expected the same results), then next step in both of the lists (which stones to put on the scale) must be the same. This is in lines 136-163.

Now, we need to make sure that our lists generate unique solutions. First, let’s take some list that is supposed to confirm that the third stone is lighter. We get the subsets of stones to weigh, we get the results of the weightings. We need to make sure that the result is unique, so for every other stone from the input we would get different results in weightings. This is in lines 165-.

Finally, we need to make sure that all 24 lists generate some unique weightings. If that’s the case, then we can be sure, that we get the proper algorithm for finding the odd stone. This is in lines 192-214.

We then solve the problem, and we print the solution.

Here comes some sample output:

var stonesCount = 4;
var weightingsCount = 3;
var needToFindIfHeaverOrLigher = true;

Tried aggregator 3 times.
MIP Presolve eliminated 9067 rows and 4572 columns.
MIP Presolve modified 33516 coefficients.
Aggregator did 10560 substitutions.
Reduced MIP has 24673 rows, 12164 columns, and 91360 nonzeros.
Reduced MIP has 12164 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.14 sec. (122.11 ticks)
Probing time = 0.09 sec. (45.11 ticks)
Tried aggregator 1 time.
MIP Presolve eliminated 580 rows and 290 columns.
Reduced MIP has 24093 rows, 11874 columns, and 89620 nonzeros.
Reduced MIP has 11874 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.08 sec. (63.97 ticks)
Probing time = 0.13 sec. (41.80 ticks)
Clique table members: 56542.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 12 threads.
Root relaxation solution time = 0.25 sec. (233.38 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0        0.0000  3549                      0.0000     5007
      0     0        0.0000  4634                  Cuts: 3327     8757
      0     0        0.0000  4153                  Cuts: 3136    12012
      0     0        0.0000  3716                  Cuts: 4801    14696
      0     0        0.0000  4840                  Cuts: 2543    16843
      0     2        0.0000  2182                      0.0000    16843
Elapsed time = 21.00 sec. (11370.65 ticks, tree = 0.01 MB, solutions = 0)
      3     5        0.0000  2182                      0.0000    17507
      7     9        0.0000  2843                      0.0000    19561
     12    14        0.0000  3079                      0.0000    27692
     17    19        0.0000  1784                      0.0000    32431
     22    24        0.0000  3615                      0.0000    40876
     33    35        0.0000   910                      0.0000    53631
     51    53        0.0000  1607                      0.0000    64149
    262   244        0.0000   999                      0.0000    88749
    271   245        0.0000  1496                      0.0000    99688
    359   289        0.0000   614                      0.0000   134357
Elapsed time = 32.19 sec. (16729.64 ticks, tree = 2.19 MB, solutions = 0)
    665   533        0.0000   813                      0.0000   171436
   1011   771        0.0000  1127                      0.0000   198237
   1441   975    infeasible                            0.0000   254716
   1524   971        0.0000  1466                      0.0000   296856
   1726  1087    infeasible                            0.0000   366176
   1899  1183        0.0000  1400                      0.0000   406975
   2235  1384    infeasible                            0.0000   464046
   2283  1387        0.0000  1261                      0.0000   503516
   2343  1395        0.0000  1740                      0.0000   548927
   2592  1537        0.0000   906                      0.0000   600827
Elapsed time = 60.58 sec. (27170.42 ticks, tree = 27.86 MB, solutions = 0)
   2882  1712        0.0000  1367                      0.0000   646003
   2907  1699    infeasible                            0.0000   683087
   2968  1676        0.0000  1964                      0.0000   777718
   2987  1677        0.0000  2320                      0.0000   797273
   3067  1701        0.0000  1557                      0.0000   852616
   3116  1708        0.0000  1854                      0.0000   906596
   3133  1725        0.0000  2004                      0.0000   917695
   3241  1771        0.0000  2111                      0.0000   952497
   3608  1922    infeasible                            0.0000  1057357
   3647  1893    infeasible                            0.0000  1096427
Elapsed time = 97.08 sec. (39043.42 ticks, tree = 27.39 MB, solutions = 0)
   3689  1893        0.0000  1526                      0.0000  1141849
   3703  1893        0.0000  1661                      0.0000  1153728
   3820  1870        0.0000  1386                      0.0000  1268057
   3862  1868    infeasible                            0.0000  1308167
   3902  1856    infeasible                            0.0000  1352170
   3967  1863    infeasible                            0.0000  1401294
   4019  1863    infeasible                            0.0000  1444617
*  4162+ 1800                            0.0000        0.0000  1504384    0.00%

GUB cover cuts applied:  112
Clique cuts applied:  548
Cover cuts applied:  1729
Implied bound cuts applied:  5596
Mixed integer rounding cuts applied:  598
Zero-half cuts applied:  1053
Gomory fractional cuts applied:  32

Root node processing (before b&c):
  Real time             =   20.80 sec. (11242.73 ticks)
Parallel b&c, 12 threads:
  Real time             =   99.58 sec. (35940.06 ticks)
  Sync time (average)   =   13.62 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =  120.38 sec. (47182.78 ticks)
Stone 1 lighter: (2 ; 4) [=] ; (3 ; 4) [=] ; (1,2 ; 3,4) [>] ;
Stone 1 heavier: (2 ; 4) [=] ; (3 ; 4) [=] ; (1,2 ; 3,4) [<] ;
Stone 2 lighter: (2 ; 4) [>] ; (1,3 ; 2,4) [<] ; (3 ; 2) [<] ;
Stone 2 heavier: (2 ; 4) [<] ; (1,3 ; 2,4) [>] ; (3,4 ; 2) [<] ;
Stone 3 lighter: (2 ; 4) [=] ; (3 ; 4) [>] ; ( ; 3,4) [>] ;
Stone 3 heavier: (2 ; 4) [=] ; (3 ; 4) [<] ; (1,4 ; 3) [<] ;
Stone 4 lighter: (2 ; 4) [<] ; (1,3 ; 2,4) [<] ; ( ; 3) [>] ;
Stone 4 heavier: (2 ; 4) [>] ; (1,3 ; 2,4) [>] ; (2 ; ) [<] ;

Let’s see how to read that. In this simpler example, we consider 4 stones, 3 weightings, we want to find whether the odd stone is heavier or lighter. Notice, that first step in all of the lists is the same. This makes sense (we actually enforced that), because we need to have a deterministic algorithm. Pick any input instance you want to verify. Let’s say, that we assume, that the odd stone is the stone number 3, and the stone is heavier.

We take the first list from the top, and we perform the first weighting. The solution tells us to weigh stones 2 (on the left) and 4 (on the right). We weight them together. Since we know that the odd stone is the stone number 3, we know the result of this weighting will be “both sides are equal”. We see that the first list expected the result to be equal (just like second, fifth, and sixth list). Since our first list is still correct, we move to the second step of the list.

This time we need to weigh stones 3 (on the left) and 4 (on the right). We know the stone number 3 is heavier, we get the result indicated as “<" (meaning that the left side is lower than the right one). We see that the first list expects a different result. So does the second list. Third, fourth, and fifth lists expected different results in the first step. So we move to the sixth list. That list matches our results, so we move to the third step. In the third step we weigh stones 1 and 4 (on the left) with the stone number 3 (on the right). Since we have two stones on the left, the left side is heavier This is exactly what this list expects. So we know that the odd stone is the stone number 3, and that the stone is heavier (as indicated by the list). We can try other inputs. Notice, that only one list will take us through all the steps properly. Let's see another example:

var stonesCount = 4;
var weightingsCount = 2;
var needToFindIfHeaverOrLigher = false;

Tried aggregator 3 times.
MIP Presolve eliminated 7691 rows and 3892 columns.
MIP Presolve modified 21184 coefficients.
Aggregator did 6560 substitutions.
Reduced MIP has 13789 rows, 6780 columns, and 53032 nonzeros.
Reduced MIP has 6780 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.09 sec. (78.93 ticks)
Probing time = 0.03 sec. (22.20 ticks)
Tried aggregator 1 time.
MIP Presolve eliminated 420 rows and 210 columns.
Reduced MIP has 13369 rows, 6570 columns, and 51772 nonzeros.
Reduced MIP has 6570 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.05 sec. (37.15 ticks)
Probing time = 0.06 sec. (19.96 ticks)
Clique table members: 32370.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 12 threads.
Root relaxation solution time = 0.16 sec. (140.05 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0        0.0000  2081                      0.0000     2874
*     0+    0                            0.0000        0.0000     4886    0.00%
      0     0        cutoff              0.0000        0.0000     4886    0.00%
Elapsed time = 1.92 sec. (1598.36 ticks, tree = 0.00 MB, solutions = 1)

GUB cover cuts applied:  387
Clique cuts applied:  471
Cover cuts applied:  543
Implied bound cuts applied:  673
Mixed integer rounding cuts applied:  89
Zero-half cuts applied:  262
Lift and project cuts applied:  3
Gomory fractional cuts applied:  46

Root node processing (before b&c):
  Real time             =    1.92 sec. (1598.96 ticks)
Parallel b&c, 12 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    1.92 sec. (1598.96 ticks)
Stone 1 lighter: (1 ; 2) [>] ; (1 ; 3) [>] ;
Stone 1 heavier: (1 ; 2) [<] ; (4 ; 1) [>] ;
Stone 2 lighter: (1 ; 2) [<] ; (4 ; 1) [=] ;
Stone 2 heavier: (1 ; 2) [>] ; (1 ; 3) [=] ;
Stone 3 lighter: (1 ; 2) [=] ; (4 ; 2) [=] ;
Stone 3 heavier: (1 ; 2) [=] ; (4 ; 2) [=] ;
Stone 4 lighter: (1 ; 2) [=] ; (4 ; 2) [>] ;
Stone 4 heavier: (1 ; 2) [=] ; (4 ; 2) [<] ;

We have 4 stones and 2 weightings this time, but we only need to find the odd stone, without telling whether it's heavier or lighter. Let's assume once again, that our odd stone is the stone number 3, and that the stone is heavier. Let's take first step. We weigh stones 1 and 2, we get that they are equal. There are four lists that match this result. Let's take first list from the top that works for us, that is the list number 5. Second step asks us to weigh stones 4 and 2. We know these stones are equal. However, this time we have at least two lists that match this input. Those are lists 5 and 6. Both of them indicate that the odd stone is the stone number 3, but we can't tell whether the stone is lighter or heavier. Let's take another example. Again, 4 stones and 2 weightings, but this time we want to know whether the stone is heavier or lighter:

var stonesCount = 4;
var weightingsCount = 2;
var needToFindIfHeaverOrLigher = true;


Tried aggregator 3 times.
MIP Presolve eliminated 7979 rows and 4028 columns.
MIP Presolve modified 22428 coefficients.
Aggregator did 6816 substitutions.
Reduced MIP has 14617 rows, 7204 columns, and 55456 nonzeros.
Reduced MIP has 7204 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.08 sec. (81.46 ticks)
Probing time = 0.05 sec. (23.52 ticks)
Tried aggregator 1 time.
MIP Presolve eliminated 470 rows and 235 columns.
Reduced MIP has 14147 rows, 6969 columns, and 54046 nonzeros.
Reduced MIP has 6969 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.05 sec. (38.83 ticks)
Probing time = 0.05 sec. (21.59 ticks)
Clique table members: 33914.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 12 threads.
Root relaxation solution time = 0.16 sec. (157.25 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0        0.0000  2151                      0.0000     3069
      0     0        0.0000  3063                  Cuts: 1847     5294
      0     0        0.0000  2630                  Cuts: 1606     7065
      0     0        0.0000  2707                  Cuts: 3502     8995
      0     2        0.0000  1516                      0.0000     8995
Elapsed time = 9.16 sec. (6396.65 ticks, tree = 0.01 MB, solutions = 0)
      4     6        0.0000  1515                      0.0000     9602
      8    10        0.0000   946                      0.0000    12439
      9    11        0.0000  1474                      0.0000    14376
     16    18        0.0000   880                      0.0000    24078
     17    19        0.0000  1551                      0.0000    25430
     18    20        0.0000  2182                      0.0000    28371
     22    24        0.0000  1662                      0.0000    33220
     25    27        0.0000  2197                      0.0000    37737
     29    31        0.0000   950                      0.0000    41055
     81    77    infeasible                            0.0000    82804
Elapsed time = 16.22 sec. (11603.06 ticks, tree = 0.24 MB, solutions = 0)
    141    77    infeasible                            0.0000   130504
    207    84        0.0000   573                      0.0000   171817
    220    87        0.0000  1161                      0.0000   181888
    741   338        0.0000   502                      0.0000   261716
   1838   624        0.0000   511                      0.0000   306384
   2706   799        0.0000   473                      0.0000   364713
   2963   678        0.0000   968                      0.0000   447687
   3744   828    infeasible                            0.0000   495342
   4342   769    infeasible                            0.0000   567069
   4873   700        0.0000   749                      0.0000   643508
Elapsed time = 38.22 sec. (21634.35 ticks, tree = 0.71 MB, solutions = 0)
   5550  1011        0.0000   336                      0.0000   688323
   6408  1119    infeasible                            0.0000   753821
   6540   987    infeasible                            0.0000   889211
   6796   733    infeasible                            0.0000  1027923
   6887   668    infeasible                            0.0000  1082863
   7035   566    infeasible                            0.0000  1145077
   7310   401        0.0000   927                      0.0000  1247273
   7751   491        0.0000  1013                      0.0000  1288255
   8500   656        0.0000   769                      0.0000  1339779
   9399   708    infeasible                            0.0000  1414407
Elapsed time = 61.05 sec. (31695.72 ticks, tree = 1.13 MB, solutions = 0)
   9512   619        0.0000   638                      0.0000  1450005
   9620   548        0.0000   353                      0.0000  1485033
   9951   378        0.0000  1112                      0.0000  1602006
  10659   541        0.0000   241                      0.0000  1652664
  11056   602        0.0000   920                      0.0000  1686445
  11872   693        0.0000   899                      0.0000  1743247
  12902   674    infeasible                            0.0000  1823367
  13059   541    infeasible                            0.0000  1885856
  13184   450        0.0000   599                      0.0000  1924334
  13375   311        0.0000  1101                      0.0000  1990600
Elapsed time = 85.00 sec. (42071.90 ticks, tree = 0.33 MB, solutions = 0)
  13521   350        0.0000  1249                      0.0000  2016520
  14049   423        0.0000   987                      0.0000  2064605
  14529   468        0.0000  1053                      0.0000  2104572
  15776   529    infeasible                            0.0000  2220194
  15884   423    infeasible                            0.0000  2273648
  15975   355        0.0000  2000                      0.0000  2332887
  16153   353        0.0000  1040                      0.0000  2400556
  16231   385        0.0000   896                      0.0000  2408262
  16709   630        0.0000  1306                      0.0000  2457290
  17633   875        0.0000  1893                      0.0000  2553832
Elapsed time = 110.98 sec. (53742.88 ticks, tree = 0.69 MB, solutions = 0)
  17655   887        0.0000  2059                      0.0000  2572045
  17739   925        0.0000  2061                      0.0000  2592268
  18467  1245    infeasible                            0.0000  2809240
  18490  1222    infeasible                            0.0000  2862765
  18509  1203    infeasible                            0.0000  2894288
  18538  1174    infeasible                            0.0000  2954243
  18550  1162    infeasible                            0.0000  2977278
  18603  1111    infeasible                            0.0000  3071110
  18632  1082    infeasible                            0.0000  3113050
  18657  1057    infeasible                            0.0000  3152949
Elapsed time = 139.20 sec. (65489.88 ticks, tree = 1.02 MB, solutions = 0)
  18703  1035        0.0000  1538                      0.0000  3215507
  18766   992        0.0000  1513                      0.0000  3289399
  18773   991        0.0000  1954                      0.0000  3299613
  18785   987        0.0000  1870                      0.0000  3317451
  18810   968    infeasible                            0.0000  3353816
  18937   848        0.0000  1405                      0.0000  3504999
  18945   840    infeasible                            0.0000  3513374
  19002   807        0.0000  1521                      0.0000  3552254
  19027   788        0.0000   889                      0.0000  3567473
  19074   757        0.0000  1516                      0.0000  3598113
Elapsed time = 174.28 sec. (78644.14 ticks, tree = 0.72 MB, solutions = 0)
  19209   688        0.0000  1421                      0.0000  3671212
  19576   636        0.0000  1336                      0.0000  3793448
  19876   730        0.0000  1286                      0.0000  3830126
  20633   786        0.0000  1087                      0.0000  3919803
  20698   783        0.0000  1761                     -0.0000  3938066
  20701   783        0.0000  1772                     -0.0000  3939038
  20706   784        0.0000  1737                     -0.0000  3941101
  20712   785        0.0000  1527                     -0.0000  3943797
  20723   792        0.0000  1686                     -0.0000  3948083
  20744   802        0.0000  1368                     -0.0000  3960461
Elapsed time = 214.22 sec. (104503.67 ticks, tree = 7.09 MB, solutions = 0)
  20836   823        0.0000  1726                     -0.0000  3986141
  21274   760        0.0000   802                     -0.0000  4028859
  22072   706        0.0000   555                     -0.0000  4079944
  22658   913        0.0000   587                     -0.0000  4118471
  23413  1131        0.0000   638                     -0.0000  4165697
  24085  1269        0.0000  1102                     -0.0000  4208939
  24697  1362        0.0000  1467                     -0.0000  4249456
  24707  1364        0.0000  1395                     -0.0000  4250658
  24823  1048        0.0000  1095                     -0.0000  4257228
  25065  1071    infeasible                           -0.0000  4300075
Elapsed time = 239.13 sec. (123018.58 ticks, tree = 13.01 MB, solutions = 0)
  25299  1026        0.0000  1528                     -0.0000  4346987
  25703   880        0.0000  1260                     -0.0000  4413791
  25956   726        0.0000  1484                     -0.0000  4464113
  26326   642    infeasible                           -0.0000  4531938
  26709   764        0.0000  1392                     -0.0000  4600736
  27194   830        0.0000  1504                     -0.0000  4690663
  27505   881    infeasible                           -0.0000  4754242
  27728   910        0.0000  1401                     -0.0000  4805393
  28143   972    infeasible                           -0.0000  4890255
  29468  1242        0.0000  1129                     -0.0000  5156954
Elapsed time = 268.17 sec. (135740.89 ticks, tree = 0.72 MB, solutions = 0)
  30823  1629        0.0000  1514                     -0.0000  5412126
  32350  1829    infeasible                           -0.0000  5718157
  33681  2055        0.0000  1806                     -0.0000  5982692
  35083  2390        0.0000  1073                     -0.0000  6250237
  36581  2505        0.0000  1043                     -0.0000  6529869
  37841  2625    infeasible                           -0.0000  6817490
  39098  2867    infeasible                           -0.0000  7048531
  40747  3107    infeasible                           -0.0000  7290962
  42603  3141        0.0000  1660                     -0.0000  7563118
  44182  3230    infeasible                           -0.0000  7819515
Elapsed time = 361.98 sec. (174394.28 ticks, tree = 4.79 MB, solutions = 0)
  45619  3223    infeasible                           -0.0000  8097725
  46934  3130        0.0000  1454                     -0.0000  8347398
  48243  3130    infeasible                           -0.0000  8596902
  49646  3295        0.0000  1690                     -0.0000  8877792
  51457  3485        0.0000  1713                     -0.0000  9148822
  53014  3570    infeasible                           -0.0000  9418591
  54081  3625        0.0000  1030                     -0.0000  9606215
  55525  3715        0.0000  1189                     -0.0000  9877402
  56700  3928        0.0000   855                     -0.0000 10075168
  58063  4056    infeasible                           -0.0000 10333360
Elapsed time = 456.38 sec. (212954.00 ticks, tree = 10.13 MB, solutions = 0)
  59500  4151        0.0000  1234                     -0.0000 10584348
  60939  4343    infeasible                           -0.0000 10827749
  62208  4431        0.0000   936                     -0.0000 11070122
  63869  4520    infeasible                           -0.0000 11332455
  65291  4460    infeasible                           -0.0000 11588607
  66927  4504    infeasible                           -0.0000 11858213
  67955  4528        0.0000  1910                     -0.0000 12076043
  69355  4604    infeasible                           -0.0000 12348814
  70699  4650    infeasible                           -0.0000 12610568
  71789  4734        0.0000  1329                     -0.0000 12800946
Elapsed time = 545.30 sec. (251434.93 ticks, tree = 13.54 MB, solutions = 0)
  73016  4916        0.0000  1487                     -0.0000 13037540
  74506  5023    infeasible                           -0.0000 13269173
  76094  5090    infeasible                           -0.0000 13528840
  77625  5202        0.0000  1735                     -0.0000 13792072
  78726  5106    infeasible                           -0.0000 14003840
  79889  5084    infeasible                           -0.0000 14231445
  81320  5038    infeasible                           -0.0000 14505353
  82040  4900    infeasible                           -0.0000 14661949
  83548  4972        0.0000  1589                     -0.0000 14955703
  84626  4843    infeasible                           -0.0000 15167841
Elapsed time = 632.33 sec. (290030.55 ticks, tree = 14.75 MB, solutions = 0)
  86294  5088    infeasible                           -0.0000 15387594
  87804  5225        0.0000  1359                     -0.0000 15564328
  88886  5244    infeasible                           -0.0000 15699728
  90552  5271    infeasible                           -0.0000 15948314
  91964  5264    infeasible                           -0.0000 16180305
  93433  5389    infeasible                           -0.0000 16427669
  94565  5307        0.0000  1120                     -0.0000 16621300
  95994  5212        0.0000  1455                     -0.0000 16873270
  97427  5247    infeasible                           -0.0000 17129972
  98889  5287        0.0000   983                     -0.0000 17406516
Elapsed time = 719.33 sec. (328416.41 ticks, tree = 27.38 MB, solutions = 0)
  99907  5228        0.0000  1328                     -0.0000 17575397
 101302  5330    infeasible                           -0.0000 17823322
 102799  5214        0.0000   863                     -0.0000 18099640
 103764  5170        0.0000  1129                     -0.0000 18285881
 105271  5249        0.0000  1271                     -0.0000 18554404
 106449  5160        0.0000  1543                     -0.0000 18755055
 107926  5113        0.0000  1762                     -0.0000 19016073
 108946  5142    infeasible                           -0.0000 19221112
 110335  5099        0.0000   777                     -0.0000 19481823
 111545  4980        0.0000  1704                     -0.0000 19710912
Elapsed time = 805.23 sec. (366844.78 ticks, tree = 23.88 MB, solutions = 0)
 112585  4819        0.0000  1424                     -0.0000 19941208
 113784  4892        0.0000  1509                     -0.0000 20193029
 114777  4798    infeasible                           -0.0000 20389392
 116492  4784    infeasible                           -0.0000 20686235
 117583  4572    infeasible                           -0.0000 20908289
 118640  4660        0.0000   970                     -0.0000 21116568
 119860  4641    infeasible                           -0.0000 21355030
 121382  4590        0.0000  1454                     -0.0000 21627839
 122351  4608        0.0000  1265                     -0.0000 21797169
 123588  4526        0.0000  1700                     -0.0000 22052286
Elapsed time = 893.16 sec. (405404.89 ticks, tree = 19.45 MB, solutions = 0)
 124597  4542        0.0000  1581                     -0.0000 22246731
 125830  4603        0.0000  1411                     -0.0000 22485436
 127235  4523        0.0000  1640                     -0.0000 22742415
 128168  4478        0.0000  1636                     -0.0000 22911720
 129565  4484        0.0000  1000                     -0.0000 23181009
 130743  4487        0.0000  1599                     -0.0000 23351196
 132108  4479        0.0000  1378                     -0.0000 23550263
 133548  4330    infeasible                           -0.0000 23826937
 134461  4260        0.0000  1144                     -0.0000 24037776
 135337  4300        0.0000  1185                     -0.0000 24239681
Elapsed time = 980.72 sec. (444203.37 ticks, tree = 20.49 MB, solutions = 0)
 136369  4298        0.0000  1345                     -0.0000 24438674
 137776  4279    infeasible                           -0.0000 24669845
 138913  4133        0.0000  1142                     -0.0000 24923243
 139683  4024        0.0000  1013                     -0.0000 25089334
 140779  4056        0.0000  1273                     -0.0000 25275702
 142463  4028        0.0000  1275                     -0.0000 25559396
 143596  4029        0.0000  1421                     -0.0000 25801485
 144449  4108        0.0000  1474                     -0.0000 25999187
 145595  4199        0.0000  1814                     -0.0000 26236291
 146576  4192    infeasible                           -0.0000 26430551
Elapsed time = 1068.33 sec. (482851.65 ticks, tree = 23.50 MB, solutions = 0)
 147814  4325        0.0000  1747                     -0.0000 26660597
 149075  4345        0.0000  1244                     -0.0000 26937802
 150223  4396    infeasible                           -0.0000 27146886
 151396  4372        0.0000  1272                     -0.0000 27326098
 152752  4293        0.0000  1545                     -0.0000 27564920
 153548  4127        0.0000  1268                     -0.0000 27771342
 154765  4064        0.0000  1057                     -0.0000 27981568
 155488  3955    infeasible                           -0.0000 28150713
 156418  3765    infeasible                           -0.0000 28383049
 157341  3595        0.0000  1666                     -0.0000 28576333
Elapsed time = 1152.84 sec. (521275.28 ticks, tree = 22.79 MB, solutions = 0)
 158467  3589        0.0000  1136                     -0.0000 28815572
 159532  3561        0.0000  1803                     -0.0000 29040318
 160465  3611        0.0000  1598                     -0.0000 29279594
 161411  3625    infeasible                           -0.0000 29511805
 162031  3578        0.0000   832                     -0.0000 29642435
 163258  3549        0.0000   919                     -0.0000 29941674
 163927  3560        0.0000  1921                     -0.0000 30088371
 165262  3556        0.0000  1464                     -0.0000 30381954
 166573  3540    infeasible                           -0.0000 30624650
 167811  3509        0.0000  1489                     -0.0000 30890814
Elapsed time = 1243.14 sec. (559789.31 ticks, tree = 16.68 MB, solutions = 0)
 168651  3427    infeasible                           -0.0000 31073463
 170018  3445    infeasible                           -0.0000 31286141
 170741  3286        0.0000  1484                     -0.0000 31424810
 172175  3297    infeasible                           -0.0000 31707599
 172965  3208        0.0000  1736                     -0.0000 31868977
 174150  3090    infeasible                           -0.0000 32138345
 175160  3044        0.0000  1107                     -0.0000 32355657
 175994  2990        0.0000  1593                     -0.0000 32555554
 177147  2771    infeasible                           -0.0000 32778058
 178088  2697        0.0000  1883                     -0.0000 32977587
Elapsed time = 1330.00 sec. (598388.63 ticks, tree = 5.88 MB, solutions = 0)
 178865  2623        0.0000  1670                     -0.0000 33186397
 179659  2568    infeasible                           -0.0000 33347250
 180686  2520    infeasible                           -0.0000 33607419
 181816  2384        0.0000  1800                     -0.0000 33867732
 182642  2300    infeasible                           -0.0000 34051617
 183672  2248        0.0000  1716                     -0.0000 34251822
 184628  2049        0.0000  1881                     -0.0000 34486471
 185359  1843        0.0000   917                     -0.0000 34650208
 186210  1758        0.0000  1685                     -0.0000 34883935
 186808  1625    infeasible                           -0.0000 35060248
Elapsed time = 1418.44 sec. (637045.35 ticks, tree = 2.74 MB, solutions = 0)
 187666  1390        0.0000  1656                     -0.0000 35284509
 188282  1348        0.0000  1607                     -0.0000 35454477
 188974  1294    infeasible                           -0.0000 35658533
 189819  1284        0.0000  1344                     -0.0000 35878470
 190530  1111        0.0000  1847                     -0.0000 36069288
 191306  1126        0.0000  1961                     -0.0000 36238662
 192172  1193    infeasible                           -0.0000 36457694
 192817  1169        0.0000  1389                     -0.0000 36644583
 193478  1202        0.0000   408                     -0.0000 36869749
 194158  1161        0.0000  1825                     -0.0000 37060379
Elapsed time = 1506.59 sec. (676153.52 ticks, tree = 2.70 MB, solutions = 0)
 194823  1047    infeasible                           -0.0000 37314861
 195274   902        0.0000  2100                     -0.0000 37464452
 195909   731        0.0000  1760                     -0.0000 37659892
 196478   737    infeasible                           -0.0000 37804184
 197079   644    infeasible                           -0.0000 38034960
 197760   600        0.0000  1947                     -0.0000 38279954
 198275   538        0.0000  2168                     -0.0000 38437348
 198876   476    infeasible                           -0.0000 38643813
 199376   406    infeasible                           -0.0000 38820484
 200186   333        0.0000  2000                     -0.0000 38993643
Elapsed time = 1593.83 sec. (714834.63 ticks, tree = 0.36 MB, solutions = 0)
 200819   171    infeasible                           -0.0000 39193590
 201410    67    infeasible                           -0.0000 39359622
 201695     1    infeasible                           -0.0000 39435653

Root node processing (before b&c):
  Real time             =    9.05 sec. (6330.63 ticks)
Parallel b&c, 12 threads:
  Real time             = 1610.13 sec. (720154.57 ticks)
  Sync time (average)   =  172.85 sec.
  Wait time (average)   =    0.07 sec.
                          ------------
Total (root+branch&cut) = 1619.17 sec. (726485.20 ticks)
Stone 1 lighter: ILOG.CPLEX.CpxException: CPLEX Error  1217: No solution exists.

   at ILOG.CPLEX.CplexI.CALL(Int32 status)
   at ILOG.CPLEX.CplexI.GetXcache()
   at ILOG.CPLEX.Cplex.GetValue(INumExpr expr)
   at CplexMilpManager.Implementation.CplexMilpSolver.GetValue(IVariable variable) in C:\Users\afish\Desktop\milpmanager\CplexMilpSolver\Implementation\CplexMilpSolver.cs:line 160
   at IlpPlayground.Program420502851.<>c__DisplayClass18.b__8(Int32 stoneId)
   at System.Linq.Enumerable.WhereSelectEnumerableIterator`2.MoveNext()
   at System.Linq.Enumerable.WhereSelectEnumerableIterator`2.MoveNext()
   at System.String.Join[T](String separator, IEnumerable`1 values)
   at IlpPlayground.Program420502851.Start()
   at IlpPlayground.Env420502851.Start()

CPLEX indicates there are no solutions. This makes sense, we can't tell the solution for sure with 2 weightings only. Here comes the solution for 12 stones and 3 moves:

Stone 1 lighter: (1,2,3,4 ; 5,6,7,8) [>] ; (3,4,5,6 ; 1,8,9,10) [<] ; (5 ; 6) [=] ;
Stone 1 heavier: (1,2,3,4 ; 5,6,7,8) [<] ; (4,5,9,10 ; 1,2,7,8) [>] ; (1 ; 2) [<] ;
Stone 2 lighter: (1,2,3,4 ; 5,6,7,8) [>] ; (3,4,5,6 ; 1,8,9,10) [=] ; (11 ; 2) [<] ;
Stone 2 heavier: (1,2,3,4 ; 5,6,7,8) [<] ; (4,5,9,10 ; 1,2,7,8) [>] ; (1 ; 2) [>] ;
Stone 3 lighter: (1,2,3,4 ; 5,6,7,8) [>] ; (3,4,5,6 ; 1,8,9,10) [>] ; (3 ; 4) [>] ;
Stone 3 heavier: (1,2,3,4 ; 5,6,7,8) [<] ; (4,5,9,10 ; 1,2,7,8) [=] ; (11 ; 3) [>] ;
Stone 4 lighter: (1,2,3,4 ; 5,6,7,8) [>] ; (3,4,5,6 ; 1,8,9,10) [>] ; (3 ; 4) [<] ;
Stone 4 heavier: (1,2,3,4 ; 5,6,7,8) [<] ; (4,5,9,10 ; 1,2,7,8) [<] ; (7 ; 8) [=] ;
Stone 5 lighter: (1,2,3,4 ; 5,6,7,8) [<] ; (4,5,9,10 ; 1,2,7,8) [>] ; (1 ; 2) [=] ;
Stone 5 heavier: (1,2,3,4 ; 5,6,7,8) [>] ; (3,4,5,6 ; 1,8,9,10) [<] ; (5 ; 6) [<] ;
Stone 6 lighter: (1,2,3,4 ; 5,6,7,8) [<] ; (4,5,9,10 ; 1,2,7,8) [=] ; (11 ; 3) [=] ;
Stone 6 heavier: (1,2,3,4 ; 5,6,7,8) [>] ; (3,4,5,6 ; 1,8,9,10) [<] ; (5 ; 6) [>] ;
Stone 7 lighter: (1,2,3,4 ; 5,6,7,8) [<] ; (4,5,9,10 ; 1,2,7,8) [<] ; (7 ; 8) [>] ;
Stone 7 heavier: (1,2,3,4 ; 5,6,7,8) [>] ; (3,4,5,6 ; 1,8,9,10) [=] ; (11 ; 2) [=] ;
Stone 8 lighter: (1,2,3,4 ; 5,6,7,8) [<] ; (4,5,9,10 ; 1,2,7,8) [<] ; (7 ; 8) [<] ;
Stone 8 heavier: (1,2,3,4 ; 5,6,7,8) [>] ; (3,4,5,6 ; 1,8,9,10) [>] ; (3 ; 4) [=] ;
Stone 9 lighter: (1,2,3,4 ; 5,6,7,8) [=] ; (1,2,3 ; 9,10,11) [<] ; (9 ; 10) [>] ;
Stone 9 heavier: (1,2,3,4 ; 5,6,7,8) [=] ; (1,2,3 ; 9,10,11) [>] ; (9 ; 10) [<] ;
Stone 10 lighter: (1,2,3,4 ; 5,6,7,8) [=] ; (1,2,3 ; 9,10,11) [<] ; (9 ; 10) [<] ;
Stone 10 heavier: (1,2,3,4 ; 5,6,7,8) [=] ; (1,2,3 ; 9,10,11) [>] ; (9 ; 10) [>] ;
Stone 11 lighter: (1,2,3,4 ; 5,6,7,8) [=] ; (1,2,3 ; 9,10,11) [<] ; (9 ; 10) [=] ;
Stone 11 heavier: (1,2,3,4 ; 5,6,7,8) [=] ; (1,2,3 ; 9,10,11) [>] ; (9 ; 10) [=] ;
Stone 12 lighter: (1,2,3,4 ; 5,6,7,8) [=] ; (1,2,3 ; 9,10,11) [=] ; (1 ; 12) [<] ;
Stone 12 heavier: (1,2,3,4 ; 5,6,7,8) [=] ; (1,2,3 ; 9,10,11) [=] ; (1 ; 12) [>] ;

Big thanks to Tomasz Masternak. We had lots of fun discussing the problem.

Availability Anywhere Part 17 — Splitting physical monitor into multiple

afish — Fri, 23 Dec 2022 09:00:14 +0000

This is the seventeenth part of the Availability Anywhere series. For your convenience you can find other parts in the table of contents in Part 1 – Connecting to SSH tunnel automatically in Windows

Let’s say that we have a big physical screen that we would like to split into multiple screens. We would like to support a proper full-screen behavior, so not just like splitting a screen into windows, but screens that are completely independent from each other.

We can emulate this with OBS and Indirect Display Driver Sample. Install the driver as specified in GitHub to get additional 5 virtual monitors (not desktops).

Now, the trick is to juggle with OBS to manage screens. Currently, I have 3 physical screens numbered 1, 2, and 3. They are physically configured like this:

------- ------- -------
|     | |     | |     |
|  1  | |  2  | |  3  |
|     | |     | |     |
------- ------- -------

I have 5 additional virtual screens numbered 4, 5, 6, 7, 8. I turn off screen number 8, and other screens put to the left of my middle screen (2), like this:

------- ---- ---  ------- -------
|     | | 4 | 5 | |     | |     |
|  1  | ---- ---  |  2  | |  3  |
|     | | 6 | 7 | |     | |     |
------- ---------- ------- ------

Now, I start OBS, create a scene of the size of screen 1. I create 4 display captures for monitors 4, 5, 6, 7. I put them in the corners.
Finally, I select “Full Screen Projector Preview” and put it on the screen 1. This way I can move my mouse from screen 2 to the left to enter screens 5+7 and then 4+6. If I move the mouse pointer more to the left, then I end up in screen 1, but I don’t want to do it.

This works as physical monitors where I can use only screens 2-7. I can’t use screen 1 (as it would obscure screens 4-7), but that’s not a problem. I have 6 screens effectively at this point. Full screen works as expected. The problem is with connecting over RDP with multiple screens support, because then screen 1 obscures all screens 4-7. We could fix that by running similar OBS in the remote environment.

You can achieve the same in Mac with BetterDisplay.

Availability Anywhere Part 16 — Forwarding port from host to docker

afish — Sat, 17 Dec 2022 09:00:23 +0000

This is the sixteenth part of the Availability Anywhere series. For your convenience you can find other parts in the table of contents in Part 1 – Connecting to SSH tunnel automatically in Windows

Let’s say that we want to expose a port from the host machine to the docker container. For instance, we have a locally installed database and we want to access it from the docker container. If we’re on Linux, then we can use --network host and that will do the trick for us. However, this option is not supported on Mac or Windows. Let’s see how to do it in that case.

We are going to run an OpenSSH server inside the docker network, connect to it from the host, forward a remote port, and then connect to localhost.

Let’s start with creating a directory for the docker project:

mkdir -p ssh_tunnel

Let’s create SSH keys.

ssh-keygen -b 2048 -t rsa -f ssh_tunnel/tunnel_rsa

Next, create the configuration for OpenSSH. Just a default configuration with port forwarding enabled (AllowTcpForwarding set to yes). This is in file ssh_tunnel/sshd_config:

#	$OpenBSD: sshd_config,v 1.104 2021/07/02 05:11:21 dtucker Exp $

# This is the sshd server system-wide configuration file.  See
# sshd_config(5) for more information.

# This sshd was compiled with PATH=/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin

# The strategy used for options in the default sshd_config shipped with
# OpenSSH is to specify options with their default value where
# possible, but leave them commented.  Uncommented options override the
# default value.

Port 2222
#AddressFamily any
#ListenAddress 0.0.0.0
#ListenAddress ::

#HostKey /etc/ssh/ssh_host_rsa_key
#HostKey /etc/ssh/ssh_host_ecdsa_key
#HostKey /etc/ssh/ssh_host_ed25519_key

# Ciphers and keying
#RekeyLimit default none

# Logging
#SyslogFacility AUTH
#LogLevel INFO

# Authentication:

#LoginGraceTime 2m
#PermitRootLogin prohibit-password
#StrictModes yes
#MaxAuthTries 6
#MaxSessions 10

#PubkeyAuthentication yes

# The default is to check both .ssh/authorized_keys and .ssh/authorized_keys2
# but this is overridden so installations will only check .ssh/authorized_keys
AuthorizedKeysFile	.ssh/authorized_keys

#AuthorizedPrincipalsFile none

#AuthorizedKeysCommand none
#AuthorizedKeysCommandUser nobody

# For this to work you will also need host keys in /etc/ssh/ssh_known_hosts
#HostbasedAuthentication no
# Change to yes if you don't trust ~/.ssh/known_hosts for
# HostbasedAuthentication
#IgnoreUserKnownHosts no
# Don't read the user's ~/.rhosts and ~/.shosts files
#IgnoreRhosts yes

# To disable tunneled clear text passwords, change to no here!
PasswordAuthentication no
#PermitEmptyPasswords no

# Change to no to disable s/key passwords
#KbdInteractiveAuthentication yes

# Kerberos options
#KerberosAuthentication no
#KerberosOrLocalPasswd yes
#KerberosTicketCleanup yes
#KerberosGetAFSToken no

# GSSAPI options
#GSSAPIAuthentication no
#GSSAPICleanupCredentials yes

# Set this to 'yes' to enable PAM authentication, account processing,
# and session processing. If this is enabled, PAM authentication will
# be allowed through the KbdInteractiveAuthentication and
# PasswordAuthentication.  Depending on your PAM configuration,
# PAM authentication via KbdInteractiveAuthentication may bypass
# the setting of "PermitRootLogin without-password".
# If you just want the PAM account and session checks to run without
# PAM authentication, then enable this but set PasswordAuthentication
# and KbdInteractiveAuthentication to 'no'.
#UsePAM no

#AllowAgentForwarding yes
# Feel free to re-enable these if your use case requires them.
AllowTcpForwarding yes
GatewayPorts no
X11Forwarding no
#X11DisplayOffset 10
#X11UseLocalhost yes
#PermitTTY yes
#PrintMotd yes
#PrintLastLog yes
#TCPKeepAlive yes
#PermitUserEnvironment no
#Compression delayed
#ClientAliveInterval 0
#ClientAliveCountMax 3
#UseDNS no
PidFile /config/sshd.pid
#MaxStartups 10:30:100
#PermitTunnel no
#ChrootDirectory none
#VersionAddendum none

# no default banner path
#Banner none

# override default of no subsystems
Subsystem	sftp	internal-sftp

# Example of overriding settings on a per-user basis
#Match User anoncvs
#	X11Forwarding no
#	AllowTcpForwarding no
#	PermitTTY no
#	ForceCommand cvs server

And the ssh_tunnel/Dockerfile:

FROM lscr.io/linuxserver/openssh-server:latest

COPY sshd_config /config/ssh_host_keys/sshd_config

We could mount the volume instead, but I couldn’t get it to work with file permissions in Mac. Copying the file is good enough.

That’s it. We can now start the machinery. First, build the image:

docker build -t image_ssh ssh_tunnel

Now, let’s start or run the container with OpenSSH server:

docker start container_ssh 2>/dev/null || docker run -d \
  --name=container_ssh \
  -e TZ=Etc/UTC \
  -e "PUBLIC_KEY=YOUR_GENERATED_PUBLIC_KEY_HERE" \
  -p 127.0.0.1:58222:2222 \
  -p 127.0.0.1:YOUR_APPLICATION_PORT:YOUR_APPLICATION_PORT \
  -e USER_NAME=tunnel \
  --restart unless-stopped \
  image_ssh

Now, let’s clear the saved SSH fingerprint (in case when we restarted everything), kill existing session (if there is one), and connect to the container:

ssh-keygen -R '[localhost]:58222'
pkill -f "ssh -i $(pwd)/ssh_tunnel/tunnel_rsa tunnel@localhost -p 58222"
ssh -i "$(pwd)"/ssh_tunnel/tunnel_rsa tunnel@localhost -p 58222 -4 -o StrictHostKeyChecking=no -R YOUR_DEPENDENCY_PORT:127.0.0.1:YOUR_DEPENDENCY_PORT -fN

YOUR_DEPENDENCY_PORT is the port you’d like to forward to the container. This could be 5432 of your PostgreSQL server hosted locally, for instance. You can also see that we expose two ports from the container: 2222 as 58222 in order to connect to the OpenSSH server, and YOUR_APPLICATION_PORT which can be another application or dependency that you’d like to expose to another docker container or to external world.

Let’s now start or run our application:

docker start container_application 2>/dev/null || docker run \
  --name=container_application \
  --network 'container:container_ssh' \
  image_application

This way the application starts in the same network, so it can access localhost:YOUR_DEPENDENCYPORT that will go to the host via OpenSSH. At the same time, your container exposes YOUR_APPLICATION_PORT the regular way, so you can then configure additional tunnels.

You can clean all things up with the following (mind that it may remove some of your unused things):

ssh-keygen -R '[localhost]:58222'
pkill -f "ssh -i $(pwd)/ssh_tunnel/tunnel_rsa tunnel@localhost -p 58222"
docker stop container_application
docker rm container_application
docker rmi --force image_application
docker stop container_ssh 
docker rm container_ssh 
docker rmi image_ssh 
docker system prune
docker volume prune

Tested with Amazon Linux 2 and Ventura Mac with M1 chip. Should work with Windows as well, as long as you install OpenSSH client on your host (or use putty instead) and have some decent terminal. If you prefer to use PowerShell, then go with this code:

$location = (get-location).path
$Key = "${location}\ssh_tunnel\tunnel_rsa"
Icacls $Key /c /t /Inheritance:d
TakeOwn /F $Key
Icacls $Key /c /t /Grant:r ${env:UserName}:F
Icacls $Key /c /t /Remove:g Administrator "Authenticated Users" BUILTIN\Administrators BUILTIN Everyone System Users
Icacls $Key

docker build -t image_ssh ssh_tunnel

docker start container_ssh

if($LASTEXITCODE -ne 0){
docker run -d `
  --name=container_ssh`
  -e TZ=Etc/UTC `
  -e "PUBLIC_KEY=YOUR_GENERATED_PUBLIC_KEY_HERE" `
  -p 127.0.0.1:58222:2222 `
  -p 127.0.0.1:YOUR_APPLICATION_PORT:YOUR_APPLICATION_PORT `
  -e USER_NAME=tunnel `
  --restart unless-stopped `
  image_ssh
}

sleep 5

ssh-keygen -R '[localhost]:58222'
$replacedLocation = $location.replace("\", "/")
(Get-WmiObject win32_process -filter "Name='ssh.exe' AND CommandLine LIKE '%${replacedLocation}/ssh_tunnel/tunnel_rsa tunnel@localhost -p 58222%'").Terminate()
$sshStartBlock = { param([string]$pwd) ssh -i "$pwd/ssh_tunnel/tunnel_rsa" tunnel@localhost -p 58222 -4 -o StrictHostKeyChecking=no -R YOUR_DEPENDENCY_PORT:127.0.0.1:YOUR_DEPENDENCY_PORT -fN }
start-job -ScriptBlock $sshStartBlock -ArgumentList $replacedLocation

docker start container_application
if($LASTEXITCODE -ne 0){
docker run `
  --name=container_application `
  --network 'container:container_ssh' `
  image_application
}

This was tested with English-based Windows Server 2016 Datacenter. You may need to replace user names for different locales. Also, connecting to localhost should work with IPv4. If it defaults to IPv6, then change it to 127.0.0.1

Cleaning in PowerShell:

ssh-keygen -R '[localhost]:58222'
$location = (get-location).path
$replacedLocation = $location.replace("\", "/")
(Get-WmiObject win32_process -filter "Name='ssh.exe' AND CommandLine LIKE '%${replacedLocation}/ssh_tunnel/tunnel_rsa tunnel@localhost -p 58222%'").Terminate()
docker stop container_application
docker rm container_application
docker rmi --force image_application
docker stop container_ssh 
docker rm container_ssh 
docker rmi image_ssh 
docker system prune
docker volume prune

What’s more, we can make this dance with keys even simpler by using sish. That’s basically an OpenSSH server that allows for empty password authentication and other stuff, just like serveo.net