Memory management: Unlimited solution with code block system
At Problem section we stated:
We have specified the problem, next sections explain the solution. Our problem does not have only one possible solution. Actually, we have found two kinds of solutions:
- Solutions based on limited access to resources: we establish some limits to users, threads, requests, … in order to ensure that there is no leak.
- Solutions based on unlimited access to resources: we modify our core design, our use cases (dataClay threads, execution classes, models) or which services we provide to ensure that there are no leaks.
Let’s imagine that when a method is registered in dataClay, it is ‘split’ in what we will call ‘Code blocks’ or ‘set of instructions’.
First, we must define how we are going to split the method and why. Our main objective is to allow the release of resources in any case. For that this solution proposes the process of requests by states in which each state is a code block. Code blocks are atomic since they require sequential execution as well as methods in traditional applications. We can only stop a request when it is changing its state, it is moving from one block to another. Stopping the requests allow us to release resources if we persist the state. For instance: if the method belongs to a huge object and there is not enough resources, we stop the requests using this object and we clean it from memory (we wait for its GC). Then we will be able to run new requests. Deciding when and which requests we should stop is a matter of Resource Contention problem.
The concept of code instructions is already specified in some articles:
Basic code block: a sequence of instructions such that each instruction except the last one has exactly one successor, and such that no instruction except the first one can be the target of a jump.
We propose a similar block division but adding something else. We consider a basic code block a set of instructions that:
- No instruction is target of a jump instruction except the first one.
- All instructions have a next instruction except the last one.
One method is, then, a set of code blocks. Some blocks might have various ‘next blocks’ in case of jump. In addition, we specify that:
- There will be no more than one instruction of the type INVOKE that belongs to a dataClay registered class. And this instruction is the end of the block. More concretely, any line of code that implies to invoke a method in a dataClay’s registered class, since it can produce a remote call and then waiting threads.
¿Why don’t we split the code only if we find some INVOKE? We need to split them in basic blocks since we do not want blocks that contain jumps. A block with jumps can end up with loops or any recursive execution that could retain resources.
This ‘split’ seems complicated but it is not. Java 7+ introduced the concept of Frame in order to allow the verification of classes (during class loading) to be done in one time. Three things are verified during this process: all instructions are well formed, all targets of instruction exist in the code and all instructions that require references will find the correct type in the stack. The last one is done using Frames. The type of an element in the stack is variable (can be ints, floats..) and it is only possible to know it on runtime. Historically, these checks were done by executing many times the verification algorithm with all kinds of types. It was very slow. In order to improve this, Java 7+ introduced a new instruction that reports the types of the elements in the stack. However, adding a ‘Frame’ instruction per each instruction based on the types of the stack was also a big penalty. So, they decided to add this information only in positions that are target of a jump instruction. If you think about it, the type of an element in the stack can only change if there is a situation like this (if, else…). If there are no jumps, the control flow is lineal and an element in the stack will always belong to the same type.
Having said that, we could use Frame instructions to split our methods in basic blocks. Then, we should split them in blocks with only one invoke instruction.
Let’s study this solution on a more technical level with some example. As a basic design, each block, could have as parameters:
- ID of the block to execute after finishing this one.
- Local variables required by the block (included the parameters of the method itself)
Let’s see an example:
void main() { ... String id = carFactory.newCar(true); //remote execution, carFactor in DS1 } String newCar(boolean paintIt) { Car car = neighborFactory.newCarInOtherDS(); //creates a car in DS2 if (paintIt) { car.paint(); } else { car.defaultPaint(); } return car.getID(); }
Will be translated to:
void newCar_Block0(BlockID nextBlockID, boolean paintIt) { Car car = neighborFactory.newCarInOtherDS_Block0(<ID of Block1>); newCar_Block1(null, paintIt, car); //only if no remote call (see later) } void newCar_Block1(BlockID nextBlockID, boolean paintIt, Car car) { if (paintIt) { newCar_Block4(<ID of Block3>, car); } else { newCar_Block2(<ID of Block3>, car); } } void newCar_Block2(BlockID nextBlockID, Car car) { car.paint(); newCar_Block3(null, car); //only if no remote call } void newCar_Block4(BlockID nextBlockID, Car car) { car.defaultPaint(); newCar_Block3(null, car); //only if no remote call } String newCar_Block3(BlockID nextBlockID, Car car) { return car.getID(); }
graph TD;
START-->B1;
B1-->B2;
B1-->B4;
B2-->B3;
B4-->B3;
B3-->EXIT;
The code block system allows our code to be totally asynchronous. Each invocation of a method (like neighborFactory.newCarInOtherDS()) Can produce two cases:
The object is in another node: in case of jump between nodes, as you can imagine, the ID of the block to execute is used to know which block we should execute when the request has finished. So, in case a jump is produced, we end the execution of the block.
The object is here (linking blocks): If there is no jump, this ID is not used since the bytecode itself will make us jump to the next block or to return if it is the last block. You could think that linking blocks is just an optimization since we could use the next Block ID to know which block to execute. Like:
Car newCar_Block0(BlockID nextBlockID, boolean paintIt) { Car car = newCarInOtherDS_Block0(<ID of Block1>); return car; }
In that case we execute the block 0 and using nextBlockID we execute the block 1. But the block 1 has many paths, so we should generate something like:
BlockID newCar_Block1(BlockID nextBlockID, boolean paintIt, Car car) { if (paintIt) { return <ID of Block2>; } else { return <ID of Block3>; } }
But, where should we place the variables the block 2 and 3 must receive? One option would be to return a complex object (BlockID + variables). However, as you can see, this option is beginning to be more complex than simply delegating this work to the bytecode. Also, less instructions means more performance.
No block will return any result except ‘Return blocks’, the end of the method.
When the execution of a return block has finished, the result is sent to the node/client that requested the execution. For that, it is necessary that before executing the first block (block 0) we save the relation Request ID → Channel to answer after the execution. In case any jump or any stop of the process happens, we know to whom we should send the result.
Let’s see an example of the execution of the block 0:
void newCar_Block0(BlockID nextBlockID, boolean paintIt) { Car car = neighborFactory.newCarInOtherDS_Block0(<ID of Block1>); newCar_Block1(null, paintIt, car); }
- One request with ID 1 arrives to DS1 where the object carFactory is stored.
- The thread T1 is created in order to execute the request.
- We annotate in DS1 the information RequestID 1 → Channel of the client to answer.
- T1 executes newCar_Block0
- Since neighborFactory is in DS2, we realize an asynchronous execution to DS2 in the method ‘newCarInOtherDS’: we annotate that for the request 1 we are waiting a notification (end of execution) and, once it is received, we should execute the block with ID 1.
- We send the request to DS2.
- T1 is ended and released.
- DS2 receives a request with ID 2. The Thread T2 is created. The object ‘car’ is created and returned to DS1.
- DS1 receives a notification that the method ‘newCarInOtherDS’ has finished and its request was ID 1. DS1 proceeds to execute the next block of the request 1 with the result obtained.
- Analogous process for next blocks, except the last one, which will send the result to the client.
Thereby, our code is totally asynchronous:
- Threads are released when jumping to other nodes.
- We could stop a request that is consuming many resources.
- This system offers us parallelism opportunities.
- This system offers the possibility to improve GC (we could unload objects between blocks executions, visited elements in a loop for instance).
- It is very important to evaluate the penalty caused by this solution. We want to ask some questions: If the user would like to have an asynchronous system, wouldn’t he implement something like this?
Formally, this solution solves the predicates explained in the Problem section:
Since we will be able to persist the state of a request (between blocks), the state of the stack will be also persisted and we will release the stack so the GC will be able to clean those variables.
- Remote executions: Any thread that is waiting for a remote call to finish can be stopped, persisted and recovered later. Therefore the memory retained by them is released.
- All memory filled by objects kept alive by stacks: We could stop any request that is using too much memory in order to allow other threads to work.
There will be no leak here since if we have too many threads, we could persist some of them and recover them whenever we want (policies, but that’s another problem, Resource contention).
- Iterative execution: We could persist the state of threads using too much memory.
- Recursive execution: We could persist the state of threads waiting.
Finally, some more comments about this solution:
The language could establish a maximum number of method per class. This could be solved by nesting classes or linking them. CarFactory1 class, CarFactory2 class,...
We specify here some ideas to improve this solution due to its performance impact.
- Block unification: we could think about different options for requests that are not going to jump or retain resources. These requests could run a different kind of block (a unified one).
Both unlimited solutions explained here are totally language dependent. The block system may only be possible in Java but in other languages the asynchronicity could be achieved in a different way. However, we could consider that a ‘Code block’ is something that each language should define.
We have formally proved that our unlimited solution satisfies both predicates.