druid 🚀 - Move from ByteBuffer to Memory

Unresolved problems

Big-endian format that is currently used in Druid and ByteBuffers?

leventov on 30 Jan 2017

+ Design

"Global" (immutable)Memory's bounds are checked optionally via assertions/guarded by static final boolean flag, "local" position and limit are check explicitly manually, with helper methods or versions of read and write methods of Memory, which accept read/write position and "local" limits.

leventov on 30 Jan 2017

@leventov there's a problem with moving Memory to the Druid source tree, which is that it would then make the current implementations of Sketches not work. They would have to either be re-implemented depending on Druid (which is a huge dependency for them to take) or we would have to have some sort of compatibility layer between the two.

I do think that it is likely for Druid to have some classes that make it easier to use Memory for various operations, which would definitely live in Druid. The "read-only" version seems like something we should get the Memory library to support.

The non-native-endian problem basically means that our initial version of the integration will have to do non-native-endian reads (i.e. convert after reading non-native-endian value). Then, in a subsequent version, we will have to create a new serialization version that is only native endian.

The close/free stuff is already done.

The MagicAccessImpl thing looks cool. Is that basically a thing where we can put any arbitrary address and length in and it gives back a DirectByteBuffer that uses that? If so, that could be useful, yeah.

cheddar on 30 Jan 2017

@cheddar I think sooner or later the proposed Memory should anyway become a part of Druid source, because it is a critical dependency and it's not good to depend on PR review/release cycle done by Yahoo exclusively, not Druid community. This is the same story as with java-util/bytebuffer-collections/extendedset and Metamarkets. Sooner, i. e. from the very beginning, is better.

Another solution is to move DataSketches lib to github.com/druid-io.

We could also add DataSketches's Memory <-> Druid's Memory conversion. Since Druid's Memory is supposed to be based on the DataSketches's one, it should be easy.

What do people from Imply (@gianm, @fjy) think on this question?

The MagicAccessImpl thing looks cool. Is that basically a thing where we can put any arbitrary address and length in and it gives back a DirectByteBuffer that uses that? If so, that could be useful, yeah.

I think it is needed for being able to make a refactoring gradually, not all-or-nothing. But it is super-ugly, likely won't work on any JDK except OpenJDK/Oracle JDK, likely won't work on Java 9 at all. So better it to be a temporary hack. If there are huge libraries which Druid depends on and they require ByteBuffer, it could also be a problem, because it means that the hack couldn't be removed.

leventov on 31 Jan 2017

@leventov @cheddar ,

+ Goal

Eliminate current Endian craziness in Druid by standardizing on native-endian.

leerho on 31 Jan 2017

👍2

Fwiw, I think it is better to try to do an all-or-nothing swap of the libraries and just make sure that we support the same persisted data. It's a much larger PR and will be a significant QA/code review risk, but this is also something that I think we either want to take whole-hog or not at all.

I propose we bring this up at the dev sync tomorrow, I'll make sure to mention it.

cheddar on 31 Jan 2017

@leventov @cheddar Interesting discussion. I just have a few comments

"Don't make a lot of Object copies when a Memory object has to be "sliced", ...". The MemoryRegion(R) is a view of its parent as "slice" is for ByteBuffer; no data is copied.

If the concern is the over-creation of these shell objects, with Memory you could create a read-only view of the parent once, and then just pass the offset and permitted length to the downstream users of some sub-chunk; no object creation at all. This is a little messy for the downstream users but safe. With BB this is not possible, because the position, limit, etc are always writable, which could screw up the parent.

MagicAccessorImpl. I've been looking at this and it concerns me.

It brings in yet another hierarchy of dependencies (org.objectweb.asm), which could make maintenance & debugging rather challenging.
Creating a DirectByteBuffer requires calling the internal Bits.reserveMemory() and unreserveMemory(), which call the sun.misc.SharedSecrets() that keeps track of all created instances of DirectByteBuffer so that they can be properly freed. I don't see any mechanisms in the MagicAccessorImpl that does this. Of course, I may not fully grok how it works :).

Using the JVM Cleaner. Although this might be possible, the Java gurus that I have spoken with, who work on the internals of the JVM, advise me to never use Cleaner as it can be quite dangerous (and hazardous to your mental health :) ). This and the above point are why I don't recommend trying to create a DirectByteBuffer from a Memory. Creating a HeapByteBuffer from Memory is trivial and can be done with the current code.
Memory already has read-only implementations of NativeMemory and MemoryRegion.
Memory has no dependencies outside Java, and you can think of it as a wrapper around Unsafe. This being the case, it would be possible to create classes in Memory that leverage the same UnsafeUtil and include position, limit, rewind, etc. But, is this really necessary? Being able to read old data should not be a problem, but using Memory is a different programming paradigm that new downstream applications would need to get used to.
Memory was designed as a fast mechanism for random access of different primitive types sharing the same backing memory, similar to a C struct and union combined. ByteBuffer was designed for fast stream-based IO buffer operations, for which it does a splendid job. Reading a TCP/IP packet stream cannot be read with a random access paradigm so there is no choice. Reading data from RAM can be read either in a random access paradigm or sequentially, which depends on the application. But it seems to me to be overly restrictive for Druid to require that downstream processes must use a sequential paradigm in order to process their data out of RAM. Processing sketch data structures is a good example that requires random access, but I'm sure there will be many others.

Converting Druid away from ByteBuffers will be a lot of work no matter what path is chosen.

leerho on 31 Jan 2017

👍2

@leventov On the question of whether Memory should be part of Druid or not, my thought is that it is weird for Druid to depend on sketches-core, but if Memory stuff was broken out into its own library that both Druid and sketches-core used, then that could be fine. To me the decision of incorporating anything into the Druid tree or using it as a dependency should be made based on:

Do we think we'll want to make changes to the library?
Does the library have other users/contributors that we want to share development efforts with?

IMO, if the answer to those questions are "yes" and "no", respectively, for a given library then we should incorporate it into Druid. If the answers are anything else then it's better to keep it separate. I think for extendedset, bytebuffer-collections, and large portions of java-util, Druid was the only user so it made sense to merge them in. Memory has at least one other active user (datasketches) so to me that suggests including it as a dependency.

If that causes problems for Druid development we could always revisit.

gianm on 31 Jan 2017

👍1

@leerho Could you elaborate on what's wrong with Cleaner? It's been added recently to a few places in the Druid code base and if it's scary I'd like to understand why.

gianm on 31 Jan 2017

@cheddar

Fwiw, I think it is better to try to do an all-or-nothing swap of the libraries and just make sure that we support the same persisted data. It's a much larger PR and will be a significant QA/code review risk, but this is also something that I think we either want to take whole-hog or not at all.

Would you also propose changing factorizeBuffered to take Memory on the aggregators?

gianm on 31 Jan 2017

@gianm yes, I would propose that the BufferedAggregators essentially become MemoryAggregators. A good amount of the speed gains that we can expect from the change will come from the intermediate processing layer, which means that the aggregators would have to change.

This will have wide-reaching affects on anyone that has done their own aggregators as extensions, but I think that it is the only way to actually make the change (and that's part of the risk of the change and why I think it will take a while to get it actually accepted)

cheddar on 31 Jan 2017

Sounds like it's time to make the 0.11.0 milestone in github then!

gianm on 31 Jan 2017

Does that mean a mmap call will return the Memory , aggregators will base on the Memory too ?

weijietong on 1 Feb 2017

@weijietong yes, that is the proposed change. We discussed the process and we are currently exploring two phases

convert the "persist and read" paths to be based on Memory. This might affect ComplexMetricSerde but should not affect the aggregators
convert the query processing, this will affect aggregators

We will try to complete phase 1 entirely before phase 2. The Memory interface should then also provide the interface required to integrate with other systems (like a distributed FS) if that is a requirement. We can try to guess at the right "factory" interface to enable slotting in other Memory implementations as an extension point.

cheddar on 1 Feb 2017

@gianm

"Could you elaborate on what's wrong with Cleaner? It's been added recently to a few places in the Druid code base and if it's scary I'd like to understand why."
I just found out that our corp email was screwing up and has not been sending my replies :( !!I have a hunch that a number of my replies have been going into a bit-bucket!So here is the reply I sent at noon today.

Creates another dependency on a non-public internal set of classes of the JVM.- It is not clear to me that Cleaner is essential, or at least it hasn't been essential so far.

More: There is no way to achieve from Java the performance attained using Unsafe and this is why it is so widely used. Cleaner, on the other hand, is a convenience in that it allows programmers not to have to worry about freeing resources that they have allocated.

Overusing Cleaner can cause contention, and block GC operations. See https://srvaroa.github.io/java/jvm/unsafe/2016/08/28/sun-misc-cleaner.html.

There are other attempts to create public Cleaners, but from what I have read, with varied success.
DirectByteBuffers (DBBs) are created with a messy process inside the JVM using VM calls, Bits.reserveMemory(), which calls an internal SharedSecrets() that tracks all instances of DBB. and of course Cleaner.

I do not recommend attempting to create your own DirectByteBuffers outside the JVM. And I don't recommend attempting to create a DBB from a Memory object. Create DBBs sparingly, and reuse them if you can.

On Tuesday, January 31, 2017 9:38 AM, Gian Merlino <[email protected]> wrote:

@leerho Could you elaborate on what's wrong with Cleaner? It's been added recently to a few places in the Druid code base and if it's scary I'd like to understand why.—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub, or mute the thread.

leerho on 1 Feb 2017

Very glad to see this process, I think this will be a great huge refactor job to Druid，but it's valuable.

Btw , the coding convention of Druid ,with too much anonymous inner class 、functional programming, makes codes verbose 、unreadable. Guava has officially announced the
Caveats . Functional programming is the language like scala which is good at . If you accept this opinion, maybe we can refactor the indexing and querying part of the codes by the way at this milestone.

@leerho I think Memory may implement a reference count memory recycle algorithm like what Netty
does , not to depend on the cleaner of JVM.

weijietong on 1 Feb 2017

@leerho @weijietong

On `Cleaner`

I don't see real options.

Mandatory manual close() / free(). I want to write database in Java, not C++98. Memory leaks, use-after-free guaranteed. It works (only with very experienced teams and if a lot of resources invested into code quality) in C++ projects because C++ developers are disciplined and have a lot of experience dealing with pitfalls of manual memory management. We are not.
Mandatory manual reference counting = shared_ptr. I don't want to write database in C++11 either. Seriously, I had experience developing "better ByteBuffer frameworks" 3-4 times, the last one is https://github.com/OpenHFT/Chronicle-Bytes. Reference counting is implemented there. My experience from this attempt: reference counting doesn't work in Java. Fortunately Chronicle Bytes also use Cleaners as safety net, so manual reference counting is not mandatory with Chronicle Bytes.
It might work in Netty, but keep in mind that Netty is a more narrowly scoped framework, there are a few patterns how buffers are used there. I'm not sure they have to share buffers between concurrent threads, we have(?) in groupBy. Nevertheless I see messages in @normanmaurer's Twitter about finding another memory leak in Netty almost every single weak.

finalize() - a slower alternative to Cleaner, which causes GC problems.
Do you know other options?

IMO DirectByteBuffer's approach with using Cleaner and not requiring manual memory management is just right for Java. The two mistakes that they made are

No "public" way to voluntary "free" the buffer before it is reclaimed by GC, however everybody use ((DirectByteBuffer) bb).clean().
It doesn't implement AutoCloseable, so couldn't be used in try-with-resources statement. This is why we have to add wrappers like MappedByteBufferHandler

But those mistakes could be easily fixed in Memory.

Creates another dependency on a non-public internal set of classes of the JVM.- It is not clear to me that Cleaner is essential, or at least it hasn't been essential so far.

It is already a dependency.

Overusing Cleaner can cause contention, and block GC operations. See https://srvaroa.github.io/java/jvm/unsafe/2016/08/28/sun-misc-cleaner.html.

At least it won't be worse than now, because every DirectByteBuffer uses Cleaner internally. There is no reason why we should use more "native" Memory objects, than DirectByteBuffer objects now. Likely we can use less Memory objects, because there is no 2 GB limitation in Memory and some distinct ByteBuffers used now probably could be coalesced.

Another advantages of using Cleaners:

Ability to interop (zero-copy conversion) Memory <-> ByteBuffer, that could appear to be needed even if we take all-or-nothing refactoring approach
This allows to use Memory just as we currently use ByteBuffers without regression. It will greatly reduce the risk and size of the refactoring.

leventov on 1 Feb 2017

@cheddar @gianm

On `Memory` in Druid source

Do we think we'll want to make changes to the library?

Yes during the initial refactoring and experimentation, when the refactoring is complete, maybe very rarely.

So I think the approach with breaking Memory into a small library works, if Yahoo guys change it during the refactoring so that there is complete agreement on it's design and implementation.

I think for extendedset, bytebuffer-collections, and large portions of java-util, Druid was the only user so it made sense to merge them in.

Most important reason is that we want to make changes in those libs, which affect Druid code as well, i. e. "cross-lib refactoring". This is less likely for Memory, again, if it is reviewed thoroughly during the refactoring.

leventov on 1 Feb 2017

@leerho

Closer look at `Memory` design

`NativeMemory`

I'm concerned about offset -> address conversion with using two instance fields: nativeRawStartAddress_ + objectBaseOffset_ + offsetBytes There should be a way to avoid this cost in critical places. Hotspot JIT itself is not very good and reliable at moving field reads outside loops, even if the fields are not changed, even if the fields are `final`. I suggest to make those offsets part of `offsetBytes` value, passed to every method. It makes `Memory` effectively stateless, if assertions (or a special boolean flag, controlling bound checks) are off. Other approaches: - Use `getAddress()` and raw `Unsafe` bypassing `Memory`. Downsides: - Losing assertion-enabled bound checks - Explicit dependencies on `Unsafe` in more parts of the code. - Add a set of `getXxxByAddress()` and `putXxxByAddress()` methods to `Memory`, i. e. wrap bound check and `Unsafe` call. Downside: more methods in the interface, which is easy to confuse unintentionally.
Mixing Unsafe get/put with some object (memArray_ is not null) and with "raw" address (memArray_ is null) at the same site may have negative performance implications. To be tested.

`MemoryRegion`

Things I'm concerned about

Mutability via assign().
volatile fields.
Delegation to "abstracted" base mem_.

I suggested instead of MemoryRegion, where it is used, to create another copy of NativeMemory or NativeMemoryR with adjusted bounds.

leventov on 1 Feb 2017

@leventov Thank you for your comments!

"Mandatory manual close() / free(). I want to write database in Java, not C++98. ... C++11".
I don't want you to have to write in C++ either.

But if you read some of the visceral comments coming from the Oracle-dominated JCP and even some of the authors of the JEPs submitted to the JCP, we (you and I) are not writing in "Java" either as we have broken the rules by writing "... libraries and applications that, knowingly or not, make use of these non-standard, unstable and unsupported internal APIs." and "If you want to perform dangerous manual memory allocations, there are other languages for that." This is scary language by folks that have major influence on the future direction of Java. (There may be some glimmers of hope in the latest JEP 260 proposal, but we will have to wait and see.)

Clearly, we are writing Java code in a grey area where we are trying to get as close to the metal as possible and still produce robust and maintainable systems. I am open to morphing Memory, within reason, respecting current backward compatibility issues, into what would also be acceptable to the Druid designers.

finalize(): The Memory use of finalize() is pretty benign and narrow (but I'm open to other solutions). Currently, any direct memory allocation via AllocMemory(), does not actually rely on finalize() directly to free memory. Instead, if the JVM calls finalize() an exception is thrown informing the developer that he/she did not properly freeMemory(). The only instances of Memory that even expose the finalize() method are those that actually used AllocMemory() or MemoryMappedFile() to create native, off-heap memory. This was done intentionally to reduce the number of finalize objects that the JVM has to track. My understanding from @cheddar is that these are required only in a few places in Druid, and the actual number of these allocations is not huge.

It is an assumption, on my part, that the number of developers who actually have to write the code that creates and frees native memory in Druid is a small number of skilled Java developers who could quickly learn the patterns doing these allocations correctly. The number of developers that receive views of Memory for reading /writing of data can be much larger. These folks will not have the burden of worrying about freeing memory and even if they did attempt to free memory it results in a no-op.

I have more comments on some of your excellent following posts to the one above. But I have to break away for a few hours.

leerho on 1 Feb 2017

@leerho

Two recent PRs (which @gianm mentioned): StupidPool fixes and it's follow-up specifically move away replace finalize() to using Cleaners. Applying this change in Metamarkets's production led to 50% less GC CPU, less pauses and pauses shorter:

0.9.2-mmx-19 is the version where "StupidPool fixes" PR was backported.
This improvement happened in two pre-Christmas weeks, which are as busy as previous weeks. Extra decrease in the Christmas week is because of reduced load.

In your previous messages you raise concern about Cleaner's scalability. I agree it's not ideal and the cost is not trivial, but finalize() is even less scalable and slower.

Because of the mistake in the finalize() design that allows to "resurrect" objects during the finalize(), Objects with finalize() overridden couldn't often been reclaimed during the specific GC pause/phase even if unreachable, that often leads to OutOfMemoryErrors. After this "StupidPool fixes" backport we see much less OOMs in production: before there were several OOMs each week, after - a few (maybe less than 5) OOMs during a month and a half.

But if you read some of the visceral comments coming from the Oracle-dominated JCP and even some of the authors of the JEPs submitted to the JCP, we (you and I) are not writing in "Java" either as we have broken the rules by writing "... libraries and applications that, knowingly or not, make use of these non-standard, unstable and unsupported internal APIs." and "If you want to perform dangerous manual memory allocations, there are other languages for that." This is scary language by folks that have major influence on the future direction of Java. (There may be some glimmers of hope in the latest JEP 260 proposal, but we will have to wait and see.)

Cleaner is "less" an internal and unsupported API than say MagicAccessorImpl and SharedSecrets: sun.misc.Cleaner is standardized in Java 9 as java.lang.ref.Cleaner as a replacement for finalization.

I don't agree with the argument that "Cleaner is so hard to use right that only Java gurus and JDK authors should be allowed to do that."

We already use Cleaner successfully
In Java 9 it is exposed to the public, so considered by JDK authors to be comprehensible and safe enough to be used by all Java developers.

leventov on 1 Feb 2017

@leventov Ok, given that Cleaner is getting promoted, I'll concede. And if we need to migrate Memory to Cleaner, we will do it.

I want to return to your "Closer look at Memory". Thank you for your critique, your suggestions are very welcome!

First the 3 MemoryRegion issues.

The volatile modifiers I had already decided to remove.
Making MemoryRegion immutable is also possible, but there are some use cases, for example, where having a mutable version eliminates the need for the JVM to create millions of objects.
Removing the "delegation" aspect of the MR methods could also be fixed, but in my own testing I have found that JIT does a pretty good job of eliminating method call layers.
NativeMemory, offset -> address conversion issues

nativeRawStartAddress_ and objectBaseOffset_ play an important role in communicating what the backing memory actually is and how to properly set up the correct addresses for Unsafe. There is a little state table at the top of NativeMemory that illustrates the different values of these variables and the states of Memory.

The most dramatic speedup is achieved when the method called is static final. For the cases where speed is absolutely critical I create the static methods required where I pass what I call the memObj, and memAdd which are derived from a Memory instance. And in the most critical cases, where I need to access several such methods, rather than relying on class variables, I will bring them into the the top of the method to increase the probability that they end up on the stack. As an example, see lines 135-150. My point here is not to recommend that everyone do this, but that it is possible to do this from a Memory instance when required.

leerho on 2 Feb 2017

@leerho thanks.

Making MemoryRegion immutable is also possible, but there are some use cases, for example, where having a mutable version eliminates the need for the JVM to create millions of objects.

Sounds reasonable, let's keep it mutable.

Removing the "delegation" aspect of the MR methods could also be fixed, but in my own testing I have found that JIT does a pretty good job of eliminating method call layers.

In my experience it JIT makes inlines methods well but keeps artifact checks in the generated assembly, i. e. class checks. Making MemoryRegion delegation-free helps with it.
Also it should be pretty easy to implement without need to change the code that uses MemoryRegion.
Also consider implicit mutability problem, if MemoryRegion wraps another MemoryRegion, and the base is changed, so the derived MR is also implicitly changed. IMO it's safer and easier if we explicitly state that created MR borrows bounds and backing storage of the base MR at the moment of creation and future changes to the base MR doesn't affect the created MR.

nativeRawStartAddress_ and objectBaseOffset_ play an important role in communicating what the backing memory actually is and how to properly set up the correct addresses for Unsafe. There is a little state table at the top of NativeMemory that illustrates the different values of these variables and the states of Memory.

I understand this. My proposal is to incorporate those offsets into the primitive long offsetBytes, passed around everywhere. I. e. in each Memory, 0 is not a valid offsetBytes, bytes offsets between Memory.start() and Memory.end() (example names) are valid. start() and end() are determined by each Memory depending on the backing storage. I. e. for off-heap allocated Memory, .start() returns the allocated address. For byte[]-backed Memory, .start() is ARRAY_BYTE_BASE_OFFSET. Then, in all getXxx() and putXxx() no conversion is needed, only assertion-enabled bound checks and call to Unsafe with the given offsetBytes.

Or in other words, make what is currently returned from getCumulativeOffset(offsetBytes) the offsetBytes.

We took this approach in Chronicle Bytes' BytesStore and it worked out well.

The most dramatic speedup is achieved when the method called is static final. For the cases where speed is absolutely critical I create the static methods required where I pass what I call the memObj, and memAdd which are derived from a Memory instance. And in the most critical cases, where I need to access several such methods, rather than relying on class variables, I will bring them into the the top of the method to increase the probability that they end up on the stack. As an example, see lines 135-150. My point here is not to recommend that everyone do this, but that it is possible to do this from a Memory instance when required.

This is what I described as an option above:

Use getAddress() and raw Unsafe bypassing Memory. Downsides:
- Losing assertion-enabled bound checks
- Explicit dependencies on Unsafe in more parts of the code.

And I can add to this list the concern of mixing access with null and non-null as memObj, that I mentioned above. It may turn or not to be a performance problem, but if it will, you should add x2 more boilerplate to the code like you referenced. Or it could be encapsulated in Memory by making two different impls: OffHeapMemory and HeapMemory.

ByteBuffer also does this by splitting DirectByteBuffer and HeapByteBuffer, that could also be a sign that expressing them with a single class is suboptimal.

leventov on 2 Feb 2017

👍1

@leventov This is all very substantive feedback, thank you!

Also consider implicit mutability problem, if MemoryRegion wraps another MemoryRegion, and the base is changed, so the derived MR is also implicitly changed. IMO it's safer and easier if we explicitly state that created MR borrows bounds and backing storage of the base MR at the moment of creation and future changes to the base MR doesn't affect the created MR.

Good point! Fortunately hierarchical MR are not that frequent. But you are right that once created, the leaf node MR should directly reference itself back to the backing store and not its MR parent.

Use getAddress() and raw Unsafe bypassing Memory. Downsides:
Losing assertion-enabled bound checks
Explicit dependencies on Unsafe in more parts of the code.

Yep! But I see no way around these for truly critical speed sections. We just have to try to clearly identify and document these sections and limit the number of them.

And I can add to this list the concern of mixing access with null and non-null as memObj, that I mentioned above. It may turn or not to be a performance problem, but if it will, you should add x2 more boilerplate to the code like you referenced. Or it could be encapsulated in Memory by making two different impls: OffHeapMemory and HeapMemory.

ByteBuffer also does this by splitting DirectByteBuffer and HeapByteBuffer, that could also be a sign that expressing them with a single class is suboptimal.

Just because it was done in BB, doesn't by definition make it optimal. I'm not very impressed with the ByteBuffer architecture. The ByteBuffer hierarchy under the covers explodes into nearly 100 classes which had to be machine generated and vary hugely in their performance and all sharing inadequate and clumsy APIs. (e.g., HeapBB R/W of longs are about 8X slower than a Heap LongBuffer R/W of longs! No excuse!) Which may have been ok for reading and writing packet streams, but clumsy for anything else.

Let's discuss strategy. We have discussed a number of things:

The implicit (hierarchical) mutability issue needs to be fixed and should not be that difficult.
We agree to keep MR mutable.
The two class vars nativeRawStartAddress_ and objectBaseOffset_: If I understand your concern, it performance and that it requires two accesses of class vars instead of one. I'd have to creates some tests of this, but I have a hunch that the speed improvement would be minor compared to the penalty of the methods not being static.

I have to run now, but lets try to make a list :)

leerho on 2 Feb 2017

@leerho

Yep! But I see no way around these for truly critical speed sections. We just have to try to clearly identify and document these sections and limit the number of them.

I suggested a way that is likely as fast as static method approach, if Memory is a local variable in a loop, JIT will likely pull it's class check out of the loop: making "CumulativeOffset" the offsetBytes. It's explained in details in my previous comment.

It's important to make methods on Memory abstraction as fast as possible, not just provide workarounds. Consider BufferAggregator.aggregate(). We don't want all buffer aggregators to use address and Unsafe directly. The method signature should be changed to aggregate(Memory mem, long position). So we want trivial operations with Memory in BufferAggregator.aggregate() impls to be fast. Extracting Memory.getCumulativeOffset(), Memory.array() from Memory in a trivial aggregate() which makes just two operations with Memory: one get and one put (e. g. see DoubleMaxBufferAggregator) makes little sense.

leventov on 2 Feb 2017

Flink does something similar (you may already know):

I'm surprised that you'd not want to use Netty's allocator. Are the leaks that bad or that widespread? There are some goodies in addition to the allocator:

Presto:

(Pardon the intrusion, but I'm trying to understand why almost every big open source Java project ends up creating its own Unsafe based memory manager)

AshwinJay on 3 Feb 2017

@AshwinJay We aren't creating yet another unsafe based memory manager, instead we are borrowing these from DataSketches Memory lib.

@leventov On the discussion regarding cleaner vs using free, here is my take:

Memory is supposed to be allocated in large chunks so we allocate very few times
We have clear entry exit points for where Memory is being allocated (1-2 places in the whole code base) and this is the correct programming model for Memory.
We already have a finalize in Memory incase someone forgets to free explicitly. Finalize will be slower, but it is very infrequent.

Do you see value in having us use cleaner for Memory? Would love to know your thoughts.

niketh on 4 Feb 2017

@niketh

ByteBuffer.allocate() is used 152 times, allocateDirect() - 6 times, Files.map() - 9 times.

We already have a finalize in Memory incase someone forgets to free explicitly. Finalize will be slower, but it is very infrequent.

The problem is OOMs because of inability to reclaim finalizable objects on a given GC phase. Allocating larger objects only makes it worse.
Currently StupidPool of ByteBuffers allocates as many ByteBuffers as ResourceHolders, the effect of changing that resource holders from using finalize() to Cleaner is big. It was N ByteBuffer (Cleaner) + N ResourceHolders (finalize()). It is changed to N ByteBuffers (Cleaner) + N ResourceHolders (Cleaner). If you will change to N Memory (finalize()) + N ResourceHolders (Cleaner), I expect the effect will be just opposite to the shown above.

leventov on 4 Feb 2017

@niketh already having finalize() is not an argument, IMHO, because changing from finalize() to Cleaner and back is a 100 line change with zero implications on the rest of the codebase.

leventov on 4 Feb 2017

@leventov Makes sense, We will make Memory use cleaners instead of finalize.

niketh on 4 Feb 2017

@leventov

The "mutable MemoryRegion problem" has been fixed. I decided that a mutable MemoryRegion was not worth this risk, so I made it immutable. In looking at where we had used the mutability it was basically an end-around to not having a relative position and it was easy to convert these cases to use an immutable MR. @cheddar and I discussed this and we think that what would be more useful would be a true "positional" parallel interface. It is open for discussion how this would be implemented.
NativeMemory, offset -> address conversion issues. I am still looking at this.
"Removing the "delegation" aspect of the MR methods" Holding off on this until later.
Meanwhile @niketh is busy implementing Cleaner.

leerho on 4 Feb 2017

@leerho thanks.

I made some benchmarks, which are similar to Druid's TopN double aggregations: https://github.com/leventov/zero-cost-memory

Benchmark                                             (alloc)  Mode  Cnt   Score   Error  Units
ZeroCostMemoryBenchmark.processByteBuffer              direct  avgt    5   4.648 ± 0.106  ns/op
ZeroCostMemoryBenchmark.processByteBuffer                heap  avgt    5  15.783 ± 0.504  ns/op
ZeroCostMemoryBenchmark.processNoOffsetMemory          direct  avgt    5   3.004 ± 0.017  ns/op
ZeroCostMemoryBenchmark.processNoOffsetMemory            heap  avgt    5   2.988 ± 0.092  ns/op
ZeroCostMemoryBenchmark.processNoOffsetTwoImplMemory   direct  avgt    5   2.991 ± 0.088  ns/op
ZeroCostMemoryBenchmark.processNoOffsetTwoImplMemory     heap  avgt    5   3.009 ± 0.138  ns/op
ZeroCostMemoryBenchmark.processTwoFinalOffsetMemory    direct  avgt    5   3.675 ± 0.103  ns/op
ZeroCostMemoryBenchmark.processTwoFinalOffsetMemory      heap  avgt    5   3.700 ± 0.164  ns/op
ZeroCostMemoryBenchmark.processTwoOffsetMemory         direct  avgt    5   3.696 ± 0.116  ns/op
ZeroCostMemoryBenchmark.processTwoOffsetMemory           heap  avgt    5   3.704 ± 0.130  ns/op

Quick takeaways:

Having no Memory-internal offsets makes difference - it's faster.
Making fields final doesn't make any difference.
Separating "direct" and "heap" impl doesn't make difference.

Will investigate assembly and verify results later.

leventov on 5 Feb 2017

@leerho

one-offset memory is as good as no-offset:

ZeroCostMemoryBenchmark.processOneOffsetMemory   direct  avgt    5  3.008 ± 0.087  ns/op
ZeroCostMemoryBenchmark.processOneOffsetMemory     heap  avgt    5  3.017 ± 0.165  ns/op

Given this, and that moving from 0-indexed ByteBuffers to no-offset Memory (start()-indexed) is risky because requires to change carefully a lot of code, while moving to 0-indexed Memory is very straightforward (almost find-replace), I suggest to implement Memory with a single internal offset field.

leventov on 5 Feb 2017

Interesting. I'm ready to turn in for the night, but I did a lot of thinking about this this weekend. Also I have some benchmarks I have created as well. I need to do some updates and will share them with u tomorrow.

leerho on 6 Feb 2017

@leventov

I (think) I am done with the first phase of changes to Memory.

Cleaner implemented
NativeMemory can now be constructed with any of the 8 valid primitive arrays.
NativeMemory computes a cumBaseOffset = nativeBaseOffset + objectBaseOffset. This means only one instance variable is accessed for the get/put methods.
Rewrote a most of the key related javadocs (assuming I could find them all)
We found a "bug" in the original NativeMemory(byteBuffer) constructor in that if the BB was RO the resulting NM was not! The only way around this was to create a factory method that detects this and then constructs either a NM or a NMR.

The next thing I want to look at is simplifying the MR so that it extends NM rather than Memory. This may eliminate the need for MR or most of its code anyway. I need to figure out a way make this change backward compatible. Not sure how yet. Thoughts?

The other more radical thought I had would be to convert Memory into an abstract class that NM extends rather than implements. This would be a huge change that would definitely break Backward Compatibility. It also reduces future flexibility as it becomes a single inheritance tree. I really don't like this idea. Thoughts?

leerho on 10 Feb 2017

@leerho let's focus on the interface first, internals could be changed later.

1.

The other more radical thought I had would be to convert Memory into an abstract class that NM extends rather than implements. This would be a huge change that would definitely break Backward Compatibility. It also reduces future flexibility as it becomes a single inheritance tree. I really don't like this idea. Thoughts?

I actually like the idea and suggest just to do this.

It allows to add static factory methods right to Memory, instead of a separate Memories.
It allows to share some logic in the most natural way. E. g. I'm sure we will need to implement putUtf8(String) in Memory. Can do that right in Memory instead of separate MemoryUtils and calling it from each Memory implementation.

So there is an abstract class Memory with static factory methods for creating different kinds of Memory all other classes in the com.yahoo.memory package are package-private.

About breaking compat: IMO better to break compat early by hiding _all_ constructors behind static factory methods that allows great flexibility later (add/remove implementations). Than to realise that we want to break compat later, after Druid is refactored to use Memory.

Make Memory Closeable or AutoCloseable to allow try-with-resources.
Move PositionalMemoryRegion suggested by @niketh from #3915 to the same package.

About implementations

The next thing I want to look at is simplifying the MR so that it extends NM rather than Memory. This may eliminate the need for MR or most of its code anyway. I need to figure out a way make this change backward compatible. Not sure how yet. Thoughts?

Since MemoryRegion is unmodifiable now, and there will be PositionalMemoryRegion, I'm losing the point of MemoryRegion.

Actually I think there are too much Memory implementations. I think everything could be implemented using just one: NativeMemory. There could be a ReadOnlyMemory super-interface of Memory, and to obtain a "read-only view" of Memory, we just cast to ReadOnlyMemory.

leventov on 11 Feb 2017

The memory architecture kind of grew organically from something quite simple, all the while trying to add functionality while maintaining backward compatibility. It is admittedly kind of unwieldy now and needs a complete refresh. There are some other urgent reasons I need to publish a new release of the library and the complete reworking of the memory module will take some time. So I will likely do a new release, then we can work together on what the new Memory architecture and interfaces need to look like. Let me put some thoughts into a new architecture and I'll pass it by you.

I have thought about adding Strings, but I have resisted because it is the start of a slippery slope. Strings could be done now by converting the string to a byte[] or char[] first using the encoding of your choice.

leerho on 11 Feb 2017

@leerho

The memory architecture kind of grew organically from something quite simple, all the while trying to add functionality while maintaining backward compatibility. It is admittedly kind of unwieldy now and needs a complete refresh. There are some other urgent reasons I need to publish a new release of the library and the complete reworking of the memory module will take some time. So I will likely do a new release, then we can work together on what the new Memory architecture and interfaces need to look like. Let me put some thoughts into a new architecture and I'll pass it by you.

Sure, there is no hurry for releasing the new API.

I have thought about adding Strings, but I have resisted because it is the start of a slippery slope. Strings could be done now by converting the string to a byte[] or char[] first using the encoding of your choice.

Yes, it is possible, but my heart bleeds when I see how inefficient it is. 3-4 unnecessary data copies, creating a lot of garbage objects, ThreadLocal access, comparison of unrelated Strings. And it is done not only during segment construction, it could be done thousands of times in the Druid historical query path, if the query uses DimensionSelector.lookupName() to build a BitSet.

Here is my API proposition:

abstract class Memory implements AutoCloseable {
  static WritableMemory allocate(long size);
  static WritableMemory allocateDirect(long size);
  static Memory wrap(ByteBuffer);
  static WritableMemory wrapForWrite(ByteBuffer);
  static Memory map(File);
  static Memory map(File, long pos, long len);
  static WritableMemory mapForWrite(File);
  static WritableMemory mapForWrite(File, long pos, long len);

  PositionedMemoryRegion region(long start, long limit);

  ByteBuffer toReadOnlyByteBuffer();

  .. get methods

  void close();
}

abstract class WritableMemory extends Memory {
  WritablePositionedMemoryRegion regionForWrite(long start, long limit);

  .. put methods
}

interface PositionedMemoryRegion extends AutoCloseable {
  Memory memory();
  long position();
  PositionedMemoryRegion position(long position);

  .. get methods without offset parameter

  void close();
}

interface WritablePositionedMemoryRegion extends PositionedMemoryRegion {
  WritableMemory memory();

  .. put methods without offset parameter
}

leventov on 11 Feb 2017

@leventov

This is _very_ similar to what I was thinking. I am working out the low level details of what offset & address values to keep and where in the hierarchy.

Some subtle differences: You seem to prefer having two primary classes: a "read-only" Memory and WritableMemory. But the Memory wrapForWrite(ByteBuffer) seems inconsistent and also would throw an exception if the given BB is read-only. I would prefer having one public Memory from which one could create the read-only and writable versions. In the case of BB, we could have:

static Memory wrap(ByteBuffer);  //results in a RO `Memory` if ByteBuffer is RO.
static Memory wrapForReadOnly(ByteBuffer) //results in a RO `Memory` regardless of the state of ByteBuffer.

We would have to do something similar for mapped files.

Question about AutoCloseable: Other than being recognized by try-with-resources construct, are there any other JVM costs associated with this? Cleaner keeps a linked-list of all Cleaners, for example. More specifically, are there any hidden costs associated with having the heap-associated parts of the Memory hierarchy AutoCloseable, when they clearly don't need it?

Question about "positional" capabilities: Do we need all the capabilities now present in Buffer? Or a subset? I think we might regret doing a subset.

leerho on 11 Feb 2017

@leerho

Separation between "readable" and "writable" interfaces has proven to be a good move. Most recently designed (buffer) APIs have it, e. g. in Chronicle Bytes: ReadCommon and WriteCommon, in Argona: DirectBuffer and MutableDirectBuffer. Also a bit unrelated, but Kotlin has separate read-only List, Set, Map, Collection and MutableList, MutableSet, MutableMap and MutableCollection interfaces.

This is like const modifier in C++. Without separation, contracts of methods that take buffers as parameters are always unclear: could this method modify the buffer or not? If it's not, how do we protect from unintentional modification? This spawns a lot of unnecessary .asReadOnlyBuffer() in Druid source code now, out of "fear" or for "safety". If e. g. ObjectStrategy.fromByteBuffer() accepts read-only Memory, it makes the contract clear, and no "asReadOnly" conversion is needed on the boundaries: java compiler and type system check everything for us. We should avoid just two things: explicit cast to WritableMemory in our code, and using Memory as generic type argument. Both could be enforced using Checkstyle rules.

I took the idea of giving to the read-only interfaces and static factory methods short names, and to writable versions - longer names from Kotlin as well. It favors using read-only when possible.

Question about AutoCloseable: Other than being recognized by try-with-resources construct, are there any other JVM costs associated with this? Cleaner keeps a linked-list of all Cleaners, for example. More specifically, are there any hidden costs associated with having the heap-associated parts of the Memory hierarchy AutoCloseable, when they clearly don't need it?

No, there is no penalty. AutoCloseable allows special syntax construction: try-with-resources, similarly to how Iterable allows for-each loop.

Question about "positional" capabilities: Do we need all the capabilities now present in Buffer? Or a subset? I think we might regret doing a subset.

I think we don't know the answer to this question until we actually try to migrate Druid's code. @niketh needed right away in the first PR: #3915

leventov on 11 Feb 2017

@leventov

Some ideas:

All classes package private except where noted. Thus, only two public classes.

The classes noted as "Thought abstractions" may not be actual classes, as they are very small with only a constructor and 2-3 instance variables. They also might appear as simple interfaces.
For example, the only difference between DirectR and DirectW is the parent class that they extend. Indentation indicates "extends".

BaseMemory // Thought abstraction

    public Memory //has "absolute" Read-Only methods and launches the rest using factory methods
        DirectR // Thought abstraction. 
            MemoryDR   //Requires AutoClosable and Cleaner
            ByteBufDR
            MapDR      //Requires AutoClosable and Cleaner
        HeapR // Thought abstraction
            MemoryHR
            ByteBufHR

        MemoryW //has the "absolute" W methods
            DirectW // Thought abstraction. 
                MemoryDW   //Requires AutoClosable and Cleaner
                ByteBufDW
                MapDW      //Requires AutoClosable and Cleaner
            HeapW // Thought abstraction
                MemoryW
                ByteBufW

    public PositionalMemory //has positional "Buffer" logic & variables, positional RO methods, and launches the rest
        DirectPR // Thought abstraction. 
            MemoryPDR.    //Requires AutoClosable and Cleaner
            ByteBufPDR
            MapPDR.       //Requires AutoClosable and Cleaner
        HeapPPR // Thought abstraction
            MemoryPHR
            ByteBufPHR

        MemoryPW //positional W methods
            DirectPW // Thought abstraction. 
                MemoryPDW.   //Requires AutoClosable and Cleaner
                ByteBufPDW
                MapPDW.      //Requires AutoClosable and Cleaner
            HeapPW // Thought abstraction
                MemoryPW
                ByteBufPW

leerho on 11 Feb 2017

@leventov

I think you misunderstood my previous comment. I have no problem with "separation". My concern was

But the Memory wrapForWrite(ByteBuffer) seems inconsistent and also would throw an exception if the given BB is read-only.

leerho on 12 Feb 2017

@leventov

Go to experimental to look at early "sketch" of what I'm thinking at the moment. The hierarchical outline is in package-info.

leerho on 12 Feb 2017

@leerho

But the Memory wrapForWrite(ByteBuffer) seems inconsistent and also would throw an exception if the given BB is read-only.

Inconsistent with what? Yes, it should throw exception if the given BB is read-only. Why this is bad?

Generally I think wrap(BB) might even not be needed at all. It could be needed only on the boundaries with third-party libraries, which use ByteBuffer. Even if it is needed, it is going to be used in a very few places.

leventov on 12 Feb 2017

@leventov

DataSketches will need wrap(BB) as there are many other users outside of Druid who have BB.

My comment on inconsistent was a misinterpretation of what you were trying to do. Never mind :)

In experimental I have the first skeleton round-trip working: reading and writing longs to direct memory. Take a look.

leerho on 12 Feb 2017

@leerho

I don't see your arguments against the idea of separating read-only and writable on the type system level, by making two separate interfaces, rather than on runtime level, by having impls which throw UnsupportedOperationException.

My arguments pro this idea are:

Clearer for readers, safer interfaces of methods like ObjectStrategy.read()
Don't need asReadOnly() conversion on boundaries, there is automatic upcast to the read-only interface.
Can have twice less classes in the memory package, R/W separation not needed.

leventov on 13 Feb 2017

@leventov

OK. You are right. I thought I would be able to save some code duplication of the R/W methods, but there will the same amount of code duplication either way. The current scheme requires 1 read method and 2 write methods (one throws). Full splitting at the public level will require 2 reads and 1 write.

I don't see the 2X reduction in number of classes. Most of the classes I have at the leaf level (MemoryDR, etc.) can be consolidated as the sister leafs only differ by the factory method. I split them up just for my own clarity while laying it out.

I will try it your way and see what happens :)

leerho on 13 Feb 2017

@leventov

Checked in the totally split skeleton into experimental. Again I don't see a 2X difference in number of classes just due to this change.

Why did you do the following:

  static Memory wrapForWrite(ByteBuffer);

I would think you would want the following, which is simpler:

  static WritableMemory wrap(ByteBuffer);

The same applies to map.

leerho on 13 Feb 2017

@leerho thank you!

Why did you do the following:

static Memory wrapForWrite(ByteBuffer);
I would think you would want the following, which is simpler:

It's a mistake in my comment (now fixed), yes definitely it should return the writable interface.

Mostly LGTM, a couple of comments:

Memory allocate() doesn't make sense, only reading from just allocated memory.
We completely forgot about #3716 and the idea to use Memory instead of it's DataInput and DataOutput. For this, it seems to me that Memory should be stateless (no fields) and have a public constructor. Essentially, it should be like Java 8's interface with static factory methods and default implementations of some methods. We use abstract class just in order to overcome artificial limitations of interfaces in Java 7. Also would really like to hear @weijietong's feedback on the interfaces that we are designing.

leventov on 13 Feb 2017

@leerho regarding x2 less classes, I meant that the separation between read-only and writable implementations is not needed. There are only writable implementations. The only thing that e. g. map() does is delegation to mapWritable(), and return the read-only interface. It is safe on the type-system level with very little precautions. Your approach with runtime separation provides extra safety, if you want to keep this safety - yes, you either still have x2 classes, or e. g. have a boolean flag "writable" and check it guarded by assertion, e. g. in checkOffset() method, along with the offset check.

leventov on 13 Feb 2017

@leventov

WRT memory allocate() makes no sense. I know, it is a temporary place holder for a region, which I will address next. There are several other silly constructs in the skeleton that need to be ironed out.
WRT DataInput / DataOutput. I didn't follow that discussion very closely. So perhaps you could restate the objective and the benefit of overloading that on top of what we are trying to do now. Nonetheless, I am very skeptical that Memory could be made stateless, without compromising other objectives like achieving performance of Unsafe with a safer and friendlier interface, and effectively replacing ByteBuffer with a much richer API.

leerho on 13 Feb 2017

@leerho

WRT DataInput / DataOutput. I didn't follow that discussion very closely. So perhaps you could restate the objective and the benefit of overloading that on top of what we are trying to do now. Nonetheless, I am very skeptical that Memory could be made stateless, without compromising other objectives like achieving performance of Unsafe with a safer and friendlier interface, and effectively replacing ByteBuffer with a much richer API.

I meant to make Memory stateless (hence remove BaseMemory), but not the package-private implementation classes, essentially push fields from BaseMemory down to the private classes. I don't think it should affect performance at all.

The idea is that a third-party could provide a Memory implementation based e. g. on distributed FS.

leventov on 13 Feb 2017

@leventov

BaseMemory is a "thought abstraction" at the moment and may migrate down the hierarchy anyway. But we can do that optimization later. Right now, I want to get the basic skeleton machinery of R/W Regions, ByteBuffers and MMF working and start some characterization tests to see where we stand on performance. If it is as simple as you say, then I'm not going to worry about it right now.

However, something that we should consider at this early stage is whether we will need thread concurrency. And instead of wrapping everything with Synchronized after we are all done, which is rather inefficient, we should think about using low-level read/write locks, or perhaps optimistic locking.

leerho on 13 Feb 2017

@leerho

However, something that we should consider at this early stage is whether we will need thread concurrency. And instead of wrapping everything with Synchronized after we are all done, which is rather inefficient, we should think about using low-level read/write locks, or perhaps optimistic locking.

Because of this and generally, I think it's time to try to apply this API, in a manner similar to #3915

leventov on 13 Feb 2017

@leventov

Hmm. The only way I see to do that is to make M and WM abstract and create the concrete impls with the Unsafe calls a layer below. The BM functionality must be at the same level (or higher) then where the Unsafe calls occur. Not sure how that impacts performance.

leerho on 13 Feb 2017

@leventov

Could use your thoughts with a conundrum using Cleaner. Cleaner is directly tied to an object while finalize() is indirect in that the JVM keeps track of those objects that have a finalize method.

Unsafe is stateful with native address (in various forms) and an optional object reference.

1) Create a parent class that refers to a native region in memory using Unsafe with these state values and register it with the JVM Cleaner.

2) Create a child "region" class that needs to refer to that same region of memory as a "view".
It has to copy or refer to those same state variables (perhaps modified by an offset) in order to use Unsafe.

3) The parent's cleaner.clean() is called and the parent's references to native memory are all cleaned up and the memory is freed from the OS.

How do we clean the child? If the users still holds a reference to the child and tries to do any operation with Unsafe against the state variables it knows about, it will result in a seg-fault. Even if the nativeBaseAddress is set to zero!

Option A) If the parent has a Cleaner, then the children have to register their own cleaner as well. But it could create a race condition if the Parent cleaner is called preemptively by the user.

Option B) Similar to A, but we don't allow the user to ever call Cleaner preemptively. Once the GC starts all the user threads are disabled so we couldn't have the race condition.

If B is the way to go I have concern that we may have only a few parent objects, but have many thousands of child views of that parent. Will that overwhelm the Cleaner's linked list?

leerho on 17 Feb 2017

@leventov

Option C) I should've thought of this. The child has to hold a reference to the Parent, AND we can't allow preemptive cleans. Only when all the children and the parent are dereferenced will the GC clean it all up.

leerho on 17 Feb 2017

@leerho my suggestion is

Only one Cleaner per allocation. When views, subregions, positioned etc. are created, they have a reference to the "parent", but they shouldn't delegate their getXxx/putXxx methods to the parent, they copy address to their own fields, for faster access. They don't create their own Cleaners.
Manual clean via close() is allowed.
Cleaner and parent both reference AtomicBoolean "cleaned", which is set to true from inside Cleaner.
In their assertion-enabled methods, e. g. in checkIndex(), this flag is checked, and exception "use after free" is thrown, if already set to true.
If we encounter segfault in tests or production we turn on assertions for the memory package, and see where do we have use-after-free.

leventov on 17 Feb 2017

@leventov thanks, that is where I was headed. I wasn't so sure about the manual clean but if all of this is on a single thread it makes sense. We would have to think harder if this activity was across multiple threads.

leerho on 17 Feb 2017

@leerho @leventov IMO I think the cleaned flag isn't a great idea, its better not to have explicit close. Only NM registers cleaner, MR does nothing, NM clean will only get called when there is no one holding on the reference.
Having a cleaned flag will mean that we have to keep doing assert checks in checkIndex() or equivalent check somewhere else

niketh on 17 Feb 2017

@niketh

Having a cleaned flag will mean that we have to keep doing assert checks in checkIndex() or equivalent check somewhere else

Yes. What's the problem with that? From performance perspective, it's free, JIT will remove that code entirely.

better not to have explicit close.

Nobody obligates you to use explicit close(), but sometimes it is handy and obviously safe:

try (Memory mem = Memory.map(file)) {
  read something from file...
}

Because ByteBuffer doesn't implement AutoCloseable, we had to create a wrapper: MappedByteBufferHandler. Let's not repeat this mistake with Memory.

leventov on 17 Feb 2017

👍1

@leventov

I have implemented a skeleton with two different schemas:

Notes:

The AllocateMap has not been incorporated yet,
Lots of methods missing
Both RO Regions and W Regions are done.
Very primitive tests
If you look at the code, it is currently configured as Version A, using WritableMemory2. With minor changes I can convert it to Version B using WritableMemory.

Version A:

public Memory (read only) is abstract, with no class vars
public WritableMemory is concrete, but NO duplication of code is required

Version A
  public abstract class Memory (no class vars)
    - public static RO methods: wrapping arrays, ByteBuffers, Maps
    - public abstract RO methods: get<primitive>, get<primitive>Array. region

      class MemoryImpl extends Memory
        - Concrete RO impls of Memory

      public class WritableMemory extends MemoryImpl 
        - public static W methods: wrapping arrays, ByteBuffer, Map, Direct alloc, autoByteArray
        - public W methods: put<primitive>, put<primitive>Array, getMemoryRequest(), freeMemory()

          class AllocateDirect extends WritableMemory implements AutoClosable
            - Allocates direct memory, uses Cleaner

          class AllocateMap extends WritableMemory implements AutoClosable
            - Allocates direct memory, uses Cleaner (for Map)

Version B:

public Memory is abstract with no class vars
public WritableMemory is abstract with no class vars,
However, the WritableMemoryImpl concrete class requires duplication of all the MemoryImpl code

Version B
  public abstract class Memory (no class vars)
    - static RO methods: wrapping arrays, ByteBuffers, Maps
    - abstract RO methods: get<primitive>, get<primitive>Array. region

      class MemoryImpl extends Memory ()
        - Concrete RO impls of Memory

      public abstract class WritableMemory extends Memory (no class vars)
        - static W methods: wrapping arrays, ByteBuffers, Maps, Direct alloc, autoByteArrays
        - abstract W methods: put<primitive>, put<primitive>Array, getMemoryRequest(), freeMemory()

        class WritableMemoryImpl extends WritableMemory
          - Concrete RO impls of Memory (DUPLICATE CODE)
          - Concrete W impls of WritableMemory

          class AllocateDirect extends WritableMemoryImpl implements AutoClosable
            - Allocates direct memory, uses Cleaner

          class AllocateMap extends WritableMemoryImpl implements AutoClosable
            - Allocates direct memory, uses Cleaner (for Map)

I understand you wanted no state at the top of the hierarchy, but it is still not clear to me why.
any instantiation will have state.

I prefer Version A, because no code duplication is required and fewer classes. If we allowed class vars at the root we could eliminate another class.

Comments?

leerho on 18 Feb 2017

@leventov

I have added the AtomicBoolean into the Dealocator for Cleaner and added the asserts for the current get/put methods for the Version A. Also added some tests where the Parent is freed, and the child region detects that the region is no longer valid via assert. Seems to work.

I think I will move to a Version C, similar to what you suggested earlier, with only one writable implementation, and use asserts to detect writable and JDK7 vs 8, etc. Maintaining this R/W separation is a PITA.

leerho on 19 Feb 2017

@leerho VersionA + Boolean flag to check if the parent has been freed looks good.
What is approach C ?

niketh on 20 Feb 2017

It is in the parallel package memory3.

leerho on 20 Feb 2017

@leventov @niketh

See package-info

Version C is the furthest along and I have implemented the mechanisms for

AtomicBoolean check for valid allocation with asserts
asReadOnly() and violation detection with asserts
regions
JDK 7 & 8 detection & substitution.

Not yet Done:

Maps,
Many more methods to fill in from the current Memory
Need to transfer the JavaDocs,
Convert the UnitTests
Develop strategy for moving customers from current Memory to this one.

I have more than enough so that I can start some characterization tests and see how it performs against the current Memory.

Please review and comment, as the next stages will be a lot of work and I'd like to get feedback now.

leerho on 21 Feb 2017

@leerho sorry for late review. I like version B most. You don't have to duplicate code, because you don't need MemoryImpl, you can return WritableMemoryImpl from static factory methods which return Memory (read-only) as well. And read-only flag also won't be needed in this case, because Java compiler will ensure there are no illegal accesses, if we follow two simple rules: don't explicitly cast any Memory instance to WritableMemory, and don't use Memory as generic parameter.

I believe it's important to keep read-only and writable interfaces separate, I explained above why: https://github.com/druid-io/druid/issues/3892#issuecomment-279173943

leventov on 21 Feb 2017

@leerho Memory asked to be stateless and implementation-less to allow implementation based on completely different principles than Unsafe, e. g. something backed by network-attached storage: https://github.com/druid-io/druid/issues/3892#issuecomment-279304755

However it is not necessary now, because there is no reaction from @weijietong and probably he doesn't need #3716 anymore. Anyway, it could be fixed relatively easily later, if needed, because it doesn't incur API changes.

leventov on 22 Feb 2017

@leventov

Sorry, I had completely misinterpreted a previous statement of yours:

regarding x2 less classes, I meant that the separation between read-only and writable implementations is not needed. There are only writable implementations. The only thing that e. g. map() does is delegation to mapWritable(), and return the read-only interface. It is safe on the type-system level with very little precautions. Your approach with runtime separation provides extra safety, if you want to keep this safety - yes, you either still have x2 classes, or e. g. have a boolean flag "writable" and check it guarded by assertion, e. g. in checkOffset() method, along with the offset check.

Now that I read it again carefully and in the context of your latest comments, I understand what happened. I interpreted "implementations" as "classes that have been implemented", assuming the looser interpretation of "implementations". What you meant by "implementations" is "concrete classes" as opposed to an "abstract classes". And since in the same paragraph, you suggested having a boolean flag, the looser interpretation of "implementations" directly leads to Version C!

I will go back to Version B, but with ONE concrete WritableMemory class and no Memory concrete class :)

In your statement:

if we ... don't explicitly cast any Memory instance to WritableMemory...

Who are "we"? You and I certainly won't do that. But what is there to prevent a user from doing that? :)

And to make sure I understand what you mean, could you give me a code example of what you mean by:

and don't use Memory as generic parameter.

Thank you for your clarification on the need for the stateless root. I may as well keep the root stateless.

I have completed some initial characterization tests on the performance of this new hierarchy based Version C. (I don't expect the different versions to vary much since they should all collapse down to a single object after compilation and JIT). It is a little better than the current Memory implementation based on an interface, but still not as good as pure static calls, which will still be possible if a WritableMemory object is passed and the user goes to the trouble.

Current Memory Performance

rwmemoryheapdirect_21feb17

Version C Memory Performance

rwmemorycheapdirect_21feb17

Memory Performance using Static Methods Wrapping Unsafe

rwmemoryheapdirectviastaticunsafe_21feb17

leerho on 22 Feb 2017

Who are "we"? You and I certainly won't do that. But what is there to prevent a user from doing that? :)

DataSketches contributors and Druid contributors. It could be enforced even by adding a custom "Regexp" rule to checkstyle config, that looks for (WritableMemory) and Memory>

leventov on 22 Feb 2017

@leventov

I think you are referring to Java Generics instead of the linguistic definition of "generic" meaning "nonexclusive", "wide", or "universal" i.e., don't do:

class foo<Memory> ... { //do WritableMemory stuff }

This is essentially another form of bad casting.

leerho on 22 Feb 2017

@leventov

I'm concerned that the rule _don't explicitly cast any Memory instance to WritableMemory_ will be very difficult to enforce. Not all users of DataSketches and/or Druid will necessarily be contributors, or participate in our forums, or use our checkstyle configurations.

So I'd like to keep the boolean readOnly as a backup check, in the hopes that at some point they at least run their code with assertions enabled. There is no cost at run-time.

leerho on 22 Feb 2017

@leerho

So I'd like to keep the boolean readOnly as a backup check, in the hopes that at some point they at least run their code with assertions enabled. There is no cost at run-time.

Ok.

One thing that wasn't discussed and designed yet, is how do we support big-endian writes and reads, to support legacy formats.

Options:

Explicit putXxxBigEndian(offset, v)/getXxxBigEndian(offset) or putXxx(offset, v, ByteOrder order) methods in the main interface. (This approach is taken in Argona's buffers)
A separate implementation, with own factory methods like mapFile(f, ByteOrder order), or a conversion method Memory.asBigEndian()
No support, need to convert and use ByteBuffer to be able to read and write legacy formats.

leventov on 28 Feb 2017

@leventov

Supporting BE/LE is messy. We need to consider dual-mode cases: e.g., reading TCP/IP packets where the protocol fields are BE, and the payload could be LE. Not that I want to write packet handlers, but I could believe that careless use of ByteBuffer (without always specifying endianness) could lead to horrible mixed endianness data!

I also don't want to encourage the propagation of BE data when it is clearly unnecessary and a significant performance hit.

Explicit: putXBigEndian(offset, v) ... would double the already large number of methods, and becomes a slippery slope WRT how we implement the other variants (positional). I'm not really keen on this one.
Per call: putX(offset, v, ByteOrder order) incurs a cost with every put/get whether BE or LE. So I'm definitely opposed to this unless it is a totally separate implementation.
Totally separate implementation: All put/get methods would be of the form putX(offset, v, ByteOrder order). This has the advantage of covering the horrible mixed endianness cases. The specific factory mapFile(f, offset, capacity) would not have to specify endianness as this is an option on every put/get that the mapping class extends. However, wrapping ByteBuffer, with its internal endianness state, properly (and maintain sanity) may take a little more thought. E.g., do we keep the endianness state of BB in our state and make it visible? How easy would it be for a developer to accidentally end up with double byte-swaps?

A separate implementations is a lot of work, and, IMHO, provides little incentive for developers to fix the fundamental underlying problem. Keeping these separate implementations in sync with changes to the basic implementation could be a maintenance headache.

No support: I kinda like this one as it would really encourage developers to go back and regenerate their data using LE (if at all possible) or at least somehow mark the data as "deprecated" to be eventually replaced with the LE form. One option would require developers to explicitly call byte swappers for every put/get call. We could provide efficient byte swapper methods (only 3), but that would be the extent of it.
Separate Library Another possibility is a totally separate package, possibly in the Druid domain, that implements these variants (which, at this point, could be based on true interfaces) and underneath calls or extends the Memory package, which will always be Native-Endianness and non-positional.

Whatever we recommend here needs to be in context with however we decide to support other variants (e.g., positional put/gets, thread-safe?, ...). Is the positional approach also a totally separate implementation? Or should we ask developers to write their own positional logic that wraps the calls they need? (We could provide example code on how to do that.)

With all the potential separate implementation variants (basic, endianness, positional, thread-safe, etc), we are talking about a huge amount of code, and way beyond what I originally envisioned as a small, fast library that simply extends Unsafe. And, BTW, NONE of these other implementations will have the speed of the basic implementation (and where I start losing interest).

leerho on 28 Feb 2017

@leventov

BTW, so far, these other variants will not be able to leverage the stateless base classes Memory and WritableMemory that we have in the current design. This calls into question the value of these stateless classes and makes them more like bloat. I am seriously considering removing one or both of them.

leerho on 28 Feb 2017

@leerho

`putXBigEndian(offset, v)

Agree, it's bad. Also it looks more noisy and makes easy to make a mistake, forgetting "BigEndian" suffix somewhere.

putX(offset, v, ByteOrder order)

The same, and also noisy and even simpler to make (and harder to spot) mistakes, forgetting the third argument.

Totally separate implementation: All put/get methods would be of the form putX(offset, v, ByteOrder order).

Didn't understand how it's different from the previous.

This has the advantage of covering the horrible mixed endianness cases.

There shouldn't be such cases, at least I can speak for Druid. Either we need to support legacy file/network/cache-key formats which are big-endian only, or use native endian for new formats, and for non-persistent computational buffers, which live only within the JVM.

A separate implementations is a lot of work, and, IMHO, provides little incentive for developers to fix the fundamental underlying problem. Keeping these separate implementations in sync with changes to the basic implementation could be a maintenance headache.

_Let's keep in mind very clearly, that we develop a library not for abstract "developers", we develop it for ourselves._ Big-endian poisoned the Druid codebase for two reasons:

All ByteBuffer factory methods return big-endian ByteBuffer, and changing it to native order: order(ByteOrder.nativeOrder()) is very verbose.
asReadOnlyBuffer(), slice(), duplicate() return big-endian buffer regardless of the order of the parent, shame.

By merely making Memory's static factory methods to return native-ordered Memory by default, and ensure order inheritance on transformations, we fix the problem for all new code/new formats. On the other hand, Druid has to support old big-endian formats _forever_, so it's pointless to make it "painful" to use big-endian in order to "provide incentive" for ourselves to "move" to native order. It's just making our own live harder for nothing.

My suggestion
We can make a "NonNativeWritableMemoryImpl" class extending WritableMemoryImpl, and overriding 12 methods (6 getXxx and 6 putXxx) with delegation to super and swapping bytes. It's a burden, but IMO it's not _that bad_ to maintain those 12 methods + 12 similar methods for Positioned. Also keep in mind that Memory is supposed to be changed very rarely, after initially developed, unlike Druid/Datasketches code.

The advantage or this approach is that the implementation code could be fully shared for legacy formats (big-endian) and new formats (native-ordered), if nothing is changed except the byte order. If the matter of providing Memory with different byte order as the input for format reading/ output for format writing.

Factories: Memory.map(file) has counterpart, which accepts ByteOrder as an additional parameter: Memory.map(file, ByteOrder order). Factory code internally decides what to return: WritableMemoryImpl or "NonNativeWritableMemoryImpl", depending on the native platform byte order and the given byte order.

leventov on 1 Mar 2017

@leerho

Thread-safe Memory is not needed.

PositionedMemory could be made pretty fast IMO, if instead of wrapping Memory and keeping a separate "position" field, it's made very similar to WritableMemoryImpl, with the difference that cumulativeOffset is not a final field, and updated on each operation.

BTW, so far, these other variants will not be able to leverage the stateless base classes Memory and WritableMemory that we have in the current design. This calls into question the value of these stateless classes and makes them more like bloat. I am seriously considering removing one or both of them.

I believe in stateless and separation of stateless hierarchy (Memory) and Positioned. Let's made initial API with them separate, and if in the process/after the migration of Druid and Datasketches code it is be proven that separation is not needed, they could be merged. This extra refactoring pass, based on the actual migration experience will be needed anyway.

leventov on 1 Mar 2017

@leventov

12 methods (6 getXxx and 6 putXxx)

Lets count just the ones impacted by byte-order: 24 primitive puts/gets + 6 atomic = 30:

getChar, getCharArray, getShort, getShortArray, getInt, getIntArray, getLong, getLongArray,
getFloat, getFloatArray, getDouble, getDoubleArray, putChar, putCharArray, putShort,
putShortArray, putInt, putIntArray, putLong, putLongArray, putFloat, putFloatArray, putDouble,
putDoubleArray, getAndAddInt, getAndAddLong, compareAndSwapInt, compareAndSwapLong,
getAndSetInt, getAndSetLong

Thread-safe Memory is not needed.

I'm not convinced. Let's look at Druid's SynchronizedUnion:

This came about in a real-time query application where data was continuously being ingested into sketches in Druid and the same sketches were being accessed by multiple query threads. In order to solve the concurrency problem quickly, the entire Union object was wrapped with a brute-force synchronized approach on all the methods, which is unnecessarily slow. What we actually could use in the Druid case is a single-writer, multiple reader read/write locks, or even better, optimistic locking. I have some folks investigating this now. In order to do this with off-heap data structures the Java locking mechanisms will not work. We will at least require the use of the unsafe atomic methods mentioned above and likely modification of the put/get calls as well. I don't have the full answer on this yet.

leerho on 1 Mar 2017

@leerho ok, I was wrong. 30 + 30 = 60 similar methods is a big burden, but I still think it's feasible to write them once, with almost no attention required later. Also many methods may delegate to each other on WritableMemoryImpl level: float methods delegate to int methods, double to long, char to short or vice-versa. Such methods don't need to overridden in "NonNativeWritableMemoryImpl".

This came about in a real-time query application where data was continuously being ingested into sketches in Druid and the same sketches were being accessed by multiple query threads. In order to solve the concurrency problem quickly, the entire Union object was wrapped with a brute-force synchronized approach on all the methods, which is unnecessarily slow. What we actually could use in the Druid case is a single-writer, multiple reader read/write locks, or even better, optimistic locking. I have some folks investigating this now. In order to do this with off-heap data structures the Java locking mechanisms will not work. We will at least require the use of the unsafe atomic methods mentioned above and likely modification of the put/get calls as well. I don't have the full answer on this yet.

Either int or long memory "fields" + compareAndSwap operations on them + may need to add getIntVolatile, putIntVolatile, putIntOrdered, getLongVolatile, putLongVolatile, putLongOrdered could be used for implementing lightweight spin locks. Or some synchronization mechanisms used, external to Memory objects. "ThreadSafeMemory" is not a solution.

leventov on 1 Mar 2017

@leventov

I think we are close to agreement. I haven't added the volatile and ordered methods yet until I see what our whole approach for the concurrent sketches will actually require.

leerho on 1 Mar 2017

@leventov

I have a a design issue perhaps you could comment on:

A ByteBuffer has an internal ReadOnly / Writable state (as does a file). Because we now have only one implementation, WritableMemoryImpl, the internal helper class AccessByteBuffer must return a WritableMemoryImpl. Similarly, the AccessDirectMap also returns a WritableMemoryImpl.

Close():

I do not provide close() in Memory, it is only available in WritableMemory. I don't want downstream read-only users to inadvertently close the original BB or Map object.

This means that I can't provide in Memory a public static Memory wrap(ByteBuffer) or a public static Memory map(file ...) because ultimately these objects need to be closed so that the atomic valid flag is set to false and propagates to any child regions.

So the only way to create a RO Memory instance of a BB (or map) is via asReadOnly() from a WritableMemory instance. This also means that I cannot throw an error during construction if the user attempts to create a WritableMemory of a RO BB or Map.

And, the only way during runtime to detect a write against a WritableMemory instance of a RO BB is when asserts are enabled. Can we live with this?

Maps are safer in that if the file is RO, the OS will throw an error on an attempted write.

Any better ideas?

leerho on 3 Mar 2017

@leerho

Memory should also be closeable, because it's needed for a common pattern:

try (Memory mem = Memory.map(file)) {
  .. read something from file
}

I didn't understand it clearly but probably the rest of the problem will go away also.

Downstream read-only users can inadvertently close Memory: I agree it's not great, but currently I think it's a required trade-off (maybe my mind will change when we do actual Druid code migration and see how it works). As I noted here: https://github.com/druid-io/druid/issues/3892#issuecomment-280742485, Memory.close() should be rarely used. Maybe we can apply policy that any Memory object is closed only in the case class as where it's created, if a class accepts Memory as a parameter (downstream user), it must not close it.

leventov on 3 Mar 2017

@leventov

The pattern I am worried about is:

WritableMemory wmem = WritableMemory.writableWrap(ByteBuffer writableBB);
Memory mem = wmem.asReadOnly();

// pass mem as an argument to 1000 different downstream clients that need read access ...
// ...if any one of them accidentally calls close() you are hosed! 

wmem.close(); //The owner of the original object should be the only one closing it.

I don't understand what your "tradeoff" concern is. Since we only have one way to instantiate a BB we could make it less verbose: WritableMemory wmem = WritableMemory.wrap(BB). Or perhaps we could make the name more concise: WriteMemory or Wmemory. So we would have:

WMemory wmem = WMemory.wrap(ByteBuffer writableBB);
Memory mem = wmem.asReadOnly();

I would recommend that we start with not allowing Memory.close(). Memory.close may be rare in Druid, but I am worried about other environments including Yahoo!

leerho on 3 Mar 2017

Ok, let's try something like MemoryHandle extends AutoCloseable, with Memory get() method. Memory.map() and allocateDirect return MemoryHandle, other static factory methods return just Memory. And Memory with WritableMemory are _not_ AutoCloseable.

Then the pattern above is

try (MemoryHandle mh = Memory.map(file)) {
  Memory mem = mh.get();
  .. read from file
}

Memory mem = wmem.asReadOnly();

Shouldn't need asReadOnly(), just upcast: Memory mem = wmem;. And actually this line not needed, just pass wmem to methods that accept Memory.

WriteMemory, Wmemory

I like natural English WritableMemory most

leventov on 3 Mar 2017

@leventov

Does your MemoryHandle apply to BB? Could you give me a skeleton of what MH extends and includes?

I need the asReadOnly to set the readOnly flag, which an upcast will not do. The RO flag is the only backup to detect a improper cast of (WritableMemory) memory.

leerho on 3 Mar 2017

Does your MemoryHandle apply to BB?

If you mean "should Memory.wrap(BB) return MemoryHandle" I think no, because somebody who allocated BB should care about closing it.

MemoryHandle should be similar to MappedByteBufferHandler. Since Memory still want to be able to catch use-after-free, Cleaner should still be private to Memory (WritableMemoryImpl). The only difference is that Memory.close() made package-private, and only MemoryHandleImpl can access it. (MemoryHandle itself is an interface)

I need the asReadOnly to set the readOnly flag, which an upcast will not do. The RO flag is the only backup to detect a improper cast of (WritableMemory) memory.

You shouldn't be able to obtain WritableMemory which is not actually writable, in the first place :)
If asReadOnly() just makes a check and returns this, it's ok

leventov on 3 Mar 2017

@leventov

Something like:

public final class MemoryHandler implements AutoCloseable {
  private final WritableMemory wmem;

  MemoryHandler( WritableMemoryImpl wmem) {
    this.wmem = wmem;
  }

  public Memory get() { return wmem.asReadOnly(); } //sets the RO flag
  public WritableMemory getWritable() { return wmem; }

  //calls the package private close() method of wmem
  public void close() { wmem.close(); }
}

AccessByteBuffer, AllocateDirectMap and AllocateDirect all extend WritableMemoryImpl and return MH. So do all the static methods that create heap array backed Memory or WritableMemory.

Now the only way to close the retained WritableMemoryImpl is through MH and there can be only one owner of an MH. This also means MH is the only class that the compiler detects that requires a close() or should be implemented with try-with-resource.

The rest of the hierarchy is the same.

leerho on 3 Mar 2017

@leerho

I forgot that we have Memory and WritableMemory, in this case I would prefer to have two separate interfaces MemoryHandle and WritableMemoryHandle extends MemoryHandle, both with a single get() method, because getWritable() allows Memory.map(file).getWritable(), that shouldn't be allowed.

AccessByteBuffer, AllocateDirectMap and AllocateDirect all extend WritableMemoryImpl

I don't understand why it is needed to have subclasses with only specialized constructors. It will make difficult to implement NonNativeWritableMemoryImpl. I suggest to implement AccessByteBuffer's, AllocateDirectMap's and AllocateDirect's logic in static factory methods, then passing all prepared arguments to WritableMemoryImpl or NonNativeWritableMemoryImpl constructors.

leventov on 3 Mar 2017

Also I want to return to asReadOnly(), I don't actually understand what exactly it will check? It should be possible to upcast WritableMemory to Memory, because during query processing some buffers first act as writable, and then as read-only.

leventov on 3 Mar 2017

@leventov

What is making things tricky is that we only have one implementation, WritableMemoryImpl, which allows problematic casts. I am beginning to feel that splitting into two impls would be a lot cleaner, safer, and just not worry about the 30+ duplicated methods. I have already organized the code in the WritableMemoryImpl class so that all the RO methods are together, so a simple copy & paste should be straightforward.

With two impls, asReadOnly creates a new class, and going from a Memory to WritableMemory would never be possible.

#

One impl:
The readOnly flag is only checked on the write methods with an assert. So if you cast a Memory object to a WritableMemory the readOnly flag will be true and not change and will throw an assertion error (with -ea).

As I explained before, ByteBuffers and Maps have their own internal RO/W state. And because we have only one writable impl, we can end up with an RO map/BB wrapped by the writable impl. This creates the need for the readOnly flag and the assert check of W methods.

If you do Memory mem = (WritableMemory)writableMem, the readOnly flag remains false (writable). the Memory API prevents writes, but then this also allows a downstream client to do the reverse cast, since the underlying impl is the same. I don't see any easy solution to this other than having two impls.

#

I do like the MemoryHandler idea as it isolates only those objects that actually require AutoCloseable from those that do not.

leerho on 3 Mar 2017

@leventov

I don't understand why it is needed to have subclasses with only specialized constructors. It will make difficult to implement NonNativeWritableMemoryImpl.

AllocateDirect and AllocateDirectMap both require Cleaner as a field. The Cleaners have different implementations. These two need to be a subclass so that a user call of close() at the root of the hierarchy does the work specified in the appropriate subclass.
Also, the WritableMemoryImpl class is already huge, so I was looking for opportunities to split out well defined subsets of code.
AccessByteBuffer has a lot of specialized logic so it made sense to make it a separate class.

Honestly, I haven't thought much about how to extend all this for BigEndian, or Positional either. I am just trying to get the basic functioning done with a workable public API.

leerho on 3 Mar 2017

@leventov

Using an intermediate interface we can leverage AllocateDirect, AllocateDirectMap and AccessByteBuffer across multiple implementations.

Since positional will need to leverage both NE and BE, it should be a true interface.

leerho on 4 Mar 2017

What is making things tricky is that we only have one implementation, WritableMemoryImpl, which allows problematic casts. I am beginning to feel that splitting into two impls would be a lot cleaner, safer, and just not worry about the 30+ duplicated methods. I have already organized the code in the WritableMemoryImpl class so that all the RO methods are together, so a simple copy & paste should be straightforward.

Personally I don't care that much about code duplication, but keep in mind "NonNative" subclasses, they should also be duplicated then.

With two impls, asReadOnly creates a new class, and going from a Memory to WritableMemory would never be possible.

This is actually what I want to avoid, see the very first message in this thread, "Goals" section, "Don't make a lot of Object copies when a Memory object has to be "sliced", "converted to read-only", etc.". See https://github.com/druid-io/druid/pull/3716#issuecomment-274658045. Currently Druid creates millions of unnecessary read-only ByteBuffers, "for safety". But I think mere separation of interfaces, Memory and WritableMemory, provides enough safety.

the Memory API prevents writes, but then this also allows a downstream client to do the reverse cast, since the underlying impl is the same. I don't see any easy solution to this other than having two impls.

We are creating library for ourselves, not for "dumb users who will do the wrong thing if they could". There is a solution: don't do reverse casts! I'm pretty sure nobody will ever try to do reverse casts, but then it is catched during code review, and even could be enforced using checkstyle rules, as suggested above: https://github.com/druid-io/druid/issues/3892#issuecomment-279173943

AllocateDirect and AllocateDirectMap both require Cleaner as a field. The Cleaners have different implementations. These two need to be a subclass so that a user call of close() at the root of the hierarchy does the work specified in the appropriate subclass.

My intention was that there is a Cleaner field in WritableMemoryImpl, and it's null when cleaning is not needed (e. g. heap allocation). And close() method contains something like

if (cleaner != null) {
  cleaner.clean();
}

Also, the WritableMemoryImpl class is already huge, so I was looking for opportunities to split out well defined subsets of code.

The problem is requirement for "NonNative" subclass, that will multiply the amount of code, if there is more than one "WritableMemoryImpl"

Using an intermediate interface we can leverage AllocateDirect, AllocateDirectMap and AccessByteBuffer across multiple implementations.

Don't understand this

Since positional will need to leverage both NE and BE, it should be a true interface.

The only reason why Memory and WritableMemory are not true interfaces, is ability to have static factory methods. My idea was to create Positional from existing Memory or WritableMemory objects, using region(start, limit) method. So Positional itself doesn't have static factory methods and could be a true interface.

leventov on 7 Mar 2017

@leventov

With two impls, asReadOnly creates a new class, and going from a Memory to WritableMemory would never be possible.
This is actually what I want to avoid, see the very first message in this thread, "Goals" section, "Don't make a lot of Object copies when a Memory object has to be "sliced", "converted to read-only", etc.".

I'm trying to understand exactly what you are trying to avoid. When I say "creates a new class", what I mean is a new wrapper pointing to the same resource. Only a few pointer registers get created. With a single impl asReadOnly can be done with an up-cast. But slices will always require a new wrapper object. Also viewing a resource as positional will require creating a different wrapper object pointing to the same resource. (It is also possible to create two views of the same resource using different endianness just using different wrappers).

What is the use pattern that you think is creating all these "unnecessary objects"?

Are the vast majority of ByteBuffer objects created to protect the parent's position and limit state from being changed by the child and to protect the children from affecting each other?
If this is the case then:

WritableMemory wMem = //original resource
Memory mem = wMem.asReadOnly() //created only once

//pass mem to many children
ChildProcess(mem, offset, length) {
    //Each child can either read directly using offsets, or
    Buffer buf = mem.asBuffer(). //I am suggesting that "Buffer" = "PositionalMemory" 
    buf.setPosition(offset);
    buf.setLimit(offset + length);
    //yes, this creates another wrapper, but may be necessary depending on what the child is doing
    ....
}

Even if we have both R and W impls, the asReadOnly wrapper is created only once. This should dramatically reduce the number of distinct wrapper objects. With ByteBuffer, the children have to be protected from each other so a new wrapper is required for each child.

leerho on 7 Mar 2017

@leerho

I'm trying to understand exactly what you are trying to avoid. When I say "creates a new class", what I mean is a new wrapper pointing to the same resource. Only a few pointer registers get created. With a single impl asReadOnly can be done with an up-cast. But slices will always require a new wrapper object. Also viewing a resource as positional will require creating a different wrapper object pointing to the same resource. (It is also possible to create two views of the same resource using different endianness just using different wrappers).

Currently in Druid, a lot of asReadOnlyBuffer() are called on already read-only buffers, because there is no way to distinguish between read-only and writable on type level, and "asReadOnlyBuffer()" is called "for safety". Slicing should be partially replaced with passing primitive "position" (and, optionally, "size"/"limit") arguments along with Memory objects. Currently slicing is also partially fostered by the fact that "positional" and "absolute" interfaces are mixed in ByteBuffer.

I'm afraid we are entering design paralysis phase, let's iterate specifically on points where we disagree. API first. How I currently see it:

abstract class Memory {
  static WritableMemory allocate(long size);
  static WritableMemoryHandler allocateDirect(long size);
  static Memory wrap(ByteBuffer);
  static WritableMemory wrapForWrite(ByteBuffer);
  static MemoryHandler map(File);
  static MemoryHandler map(File, long pos, long len);
  static WritableMemoryHandler mapForWrite(File);
  static WritableMemoryHandler mapForWrite(File, long pos, long len);

  // no fields

  long size();

  ByteOrder order();
  Memory withOrder(ByteOrder order);

  Buffer buffer(long position, long limit);

  .. getXxx(long pos) methods
}

abstract class WritableMemory extends Memory {
  // no fields
  WritableMemory withOrder(ByteOrder order);
  WritableBuffer buffer(long position, long limit);
  Memory asReadOnly();

  .. putXxx(position) methods
}

interface Buffer {

  .. getXxx() methods
}

interface WritableBuffer {
  .. putXxx() methods
}

interface MemoryHandler extends AutoCloseable {
  Memory get();

  void close();
}

interface WritableMemoryHandler extends MemoryHandler {
  WritableMemory get();
}

leventov on 7 Mar 2017

@leventov

Here is what is implemented so far and compiles (see memory4):
Completing Buffer, WritableBuffer, asNonNativeEndian(), asNativeEndian() is pretty mechanical from here.

public abstract class Memory {
  public static MemoryHandler wrap(final ByteBuffer byteBuf)
  public static MemoryHandler map(final File file)
  public static MemoryHandler map(final File file, final long fileOffset, final long capacity)
  public abstract Memory region(long offsetBytes, long capacityBytes)
  public static Memory wrap(final prim-type[] arr)
  public abstract void copy(long srcOffsetBytes, WritableMemory destination, long dstOffsetBytes,
      long lengthBytes)
  public abstract getXXX(offset) methods
  ... plus other read misc
  public abstract asNonNativeEndian() //not implemented
  public abstract asNativeEndian() //not implemented
}

public abstract class WritableMemory {
  public static WritableMemoryHandler wrap(final ByteBuffer byteBuf)
  public static WritableMemoryHandler map(final File file)
  public static WritableMemoryHandler map(final File file, final long fileOffset, final long capacity)
  public static WritableMemoryHandler allocateDirect(final long capacityBytes)
  public static WritableMemoryHandler allocateDirect(final long capacityBytes, final MemoryRequest memReq)
  public abstract WritableMemory region(long offsetBytes, long capacityBytes)
  public abstract Memory asReadOnly();
  public static WritableMemory allocate(final int capacityBytes)
  public static WritableMemory wrap(final prim-type[] arr)
  public abstract void copy(long srcOffsetBytes, WritableMemory destination, long dstOffsetBytes,
      long lengthBytes);
  public abstract getXXX(offset) methods
  ... plus other read misc
  public abstract void putXXX(long offsetBytes, prim-type value)
  ... plus other write misc
  public abstract MemoryRequest getMemoryRequest()
  public abstract asNonNativeEndian() //not implemented
  public abstract asNativeEndian() //not implemented
}

public interface MemoryHandler extends AutoCloseable {
  Memory get()
  void close()
  void load()        //only for memory-mapped-files
  boolean isLoaded() //only for memory-mapped-files
}

public interface WritableMemoryHandler extends AutoCloseable {
  WritableMemory get()
  void close()
  void load()        //only for memory-mapped-files
  boolean isLoaded() //only for memory-mapped-files
  void force()       //only for memory-mapped-files
}

public abstract Buffer { //Not implemented
}

public abstract WritableBuffer { //Not implemented
}

leerho on 8 Mar 2017

@leerho

wrap(ByteBuffer) returns Handler instead of just Memory - might complicate implementation, while not actually needed.
wrap(ByteBuffer) should inherit endianness from the buffer.
asNonNativeEndian() and asNativeEndian() won't be convenient, in Druid we need to convert endianness when we know the specific endianness that we need, usually BIG_ENDIAN. So using this API, it would be something like ByteOrder.nativeOrder() == ByteOrder.BIG_ENDIAN ? mem.asNativeEndian() : mem.asNonNativeEndian(), instead of just mem.withOrder(ByteOrder.BIG_ENDIAN)
What for MemoryRequest?
load(), isLoaded() and force() implementation requires JNI. And those methods are unused in Druid. I think they could be dropped.

Everything else looks good to me.

leventov on 8 Mar 2017

@leventov

wrap(ByteBuffer) returns Handler instead of just Memory - might complicate implementation, while not actually needed.

I'm was being conservative here, this is easy to remove after we have discussed it. I was trying to capture the scenario where the owner of a BB passes a writable region to a client and then lets his own BB go out of scope thinking that he is done with it and no changes can be made. If the owner uses try-with-resources or close(), then the client's copy is immediately marked invalid even though the JVM won't collect it until the client's handle is released. This is a variant on the use-after-close scenario.

wrap(ByteBuffer) should inherit endianness from the buffer.

Good catch. Thank you.

asNonNativeEndian() and asNativeEndian()

Good point, I can do the detection of whether the chosen endianness is different from the native internally.

What for MemoryRequest?

This is for off-heap dynamic data structures that can possibly grow in size and where the process that is managing this data structure does not "own" the allocation of memory. This is a simple callback mechanism to allow the algorithm that is managing the data structure to request more memory if needed.

Sketches is an excellent example of this. Some sketches, like Theta Sketches, have an upper bound in size. Others, like the quantiles sketches don't have an upper bound, but they grow very very slowly. They all start very small in size, e.g., a Theta Update Sketchwith a few entries can be a few hundred bytes, but can grow to a megabyte or so depending on how it is configured.
When you have millions of these sketches, the overall size adds up. Fortunately, our typical data is highly fragmented into many different dimensions and the resulting stream lengths are highly skewed with power-law distributions. This means that the vast majority of sketches only ever get a few entries, and the number of sketches that actually grow to full size is a tiny fraction. But which ones? If you allocate full space for all the sketches you would be wasting terabytes of RAM. The MemoryRequest mechanism allows the systems engineer to allocate orders-of-magnitude less space for all the required sketches and then allocate more space only for those few sketches that do require it as needed.

So far, Druid has been managing its off-heap space using direct ByteBuffers. But once you start moving away from ByteBuffers and start allocating off-heap memory directly, you are essentially managing your own heap. I really don't want to go down the slippery-slope of creating our own malloc, as that would be a significant undertaking. The MemoryRequest is a simplistic mechanism that hopefully, will delay our having to design a actual malloc/free system.

load(), isLoaded() and force() implementation requires JNI.

We are accessing these methods and their internal implementation using reflection calls to the underlying methods, which seem to be working. Using these calls can speed up access to mapped files considerably.

leerho on 8 Mar 2017

@leerho ok. Could you complete memory4 (buffers, endianness, a bunch of get/put methods), so we can start actual refactoring of Druid?

leventov on 8 Mar 2017

Also I think copy() should be called get(), similar to ByteBuffer and to resolve ambiguity: copy to or copy from?

leventov on 8 Mar 2017

How about copyTo. In BB get() is used for primitives and getXXXArray() for getting into your local context. Neither get() or put() make sense here as you could be copying bytes out of the JVM entirely.

Buffers and endianness will be quite a bit of work. Ultimately, I'd like to create a set of pragmas and a generator so that they can all be created automatically. If I only start with a few methods, could you give me a list of which ones to start with?

leerho on 8 Mar 2017

copyTo() is good.

Actually for starting refactoring implementation is not needed, so endianness could be delayed, just get/put methods should be present (for Memory and Buffer), maybe with UnsupportedOperationException impl.

leventov on 8 Mar 2017

@leventov

wrap(ByteBuffer) should inherit endianness from the buffer.

Until I figure out how exactly I want to do endianness, the current Memory is only NE. So, for now, attempting to wrap a BE BB is an error, which it now checks.

leerho on 9 Mar 2017

@leventov @niketh

Consolidating Memory / MemoryImpl, WritableMemory / WritableMemoryImpl.

I haven't had any real reason to do this until now. However, after discussing with @niketh some of the issues he had to address when trying to implement the current DataSketches Memory into Druid I learned about some additional capabilities that would have been very helpful. One very important capability was:

A byte-level compareTo(other) or static compare( a, b ) for entire blocks of memory.

This enables a byte ordering on objects independent of datatype, which Druid uses a lot. Because of our multiple Impls, I don't want to have to generate all the combinations of compare(Memory, Memory), compare(Memory, WritableMemory), etc.

So here returns a root class that only knows about bytes, call it BaseBytes. It would have one field, MemoryState (which we could rename as BaseState). Both Memory, WritableMemory, Buffer, WritableBuffer (which now may as well be impls) would extend BaseBytes.

BaseBytes would have static methods that would just do byte operations, such as compare(BaseBytes a, BaseBytes b), copy( a, b), or even the possibility of Transform(a, b) ... as long as the operation doesn't need any information about the structure or type of data. Because BaseState would also be at that level, it can check for RO state and would know the base offsets, etc. All read-only, strictly byte oriented methods could also be moved to BaseBytes.

Even though BaseBytes is a common root class, it is not possible to cast from Memory to WritableMemory via BaseBytes. This is not caught at compile time, but it is caught at runtime.

Thoughts?

leerho on 10 Mar 2017

@leerho
What about Memory.compareTo(offset, len, Memory other, otherOffset, otherLen)? You don't need any special API method or implementation compare(Memory, WritableMemory), because WritableMemory extends Memory, so you can always use the same method.

leventov on 10 Mar 2017

@leventov Look again. WritableMemory does not extend Memory. This is the two impl model. Also, in your snippet you only need one len.

leerho on 10 Mar 2017

@leerho it means that new objects are required to be created where WritableMemory is passed to a method, accepting read-only Memory, that makes the situation with the third goal in the very first message in this thread even worse that it used to be with ByteBuffers. With ByteBuffers, API encourages to create asReadOnly() copies "out of fear", but it was not required. With what you propose, it is simply required. I disagree with this.

Actually I didn't notice in your proposition in this message: https://github.com/druid-io/druid/issues/3892#issuecomment-284964809 that WritableMemory doesn't extend Memory. I disagree with this.

When WritableMemory extends Memory and all methods, that are not supposed to write, accept Memory, it's impossible to accidentally violate read/write satefy, you should intentionally cast Memory to WritableMemory (and even this could be hardly prohibited with a simple Checkstyle rule). On the contrary, it's super-easy to violate bounds safety (off-by-ones, wrong primitive argument, etc.) And yet we agree to not make bound checks by default (only with assertions enabled).

Read/write safety IMO is not a problem at all, as soon as there is a read-only superclass Memory, that ByteBuffer API lacks. Making the system even "more read/write safe" doesn't deserve even little sacrifices.

Not to mention that "WritableMemory not extending Memory" creates a lot of problems with code sharing, starting from the method that we are discussing, compareTo(). And a lot more methods: copyTo(), hash code computation, compression, object deserialization, etc.

leventov on 10 Mar 2017

Also, in your snippet you only need one len.

Sometimes you want to compare byte sequences of different lengths, as well as it's not prohibited to compare Strings of different lengths.

leventov on 10 Mar 2017

@leventov @niketh

All fixed. One impl. Cast to Memory from WritableMemory works. Both compareTo and copyTo have been implemented. @niketh is working on the Buffer / WritableBuffer impls.

leerho on 13 Mar 2017

@leerho thanks!

I see you decided to name WritableMemory's static factory methods with "writable" prefix. This is because you are concerned about overloading of Memory's methods? In this case I suggest to move them to Memory, because WritableMemory.writableMap() is a needless repetition. It could be Memory.writableMap().

leventov on 13 Mar 2017

@leventov

Yes, I was getting overloading errors, but the reason was because I still had WritableResouceHandler and ResourceHandler as separate classes from the previous scheme. By making WritableResourceHandler extend ResourceHandler (parallel to WritableMemory extend Memory) it fixed the overloading problem.

I have removed all the prefixes of writable except for one: writableRegion(offset, capacity). This method works off of an instance instead of the class. The call is myMem.writableRegion(...), so there is no repetition.

We could also make this a static method and then the calls would be WritableMemory.region(WritableMemory mem, long offset, long capacity) and Memory.region(Memory mem, long offset, long capacity). Then there would be no "writable" prefixes on method names.

This way of creating a region would then be virtually the same as if you just passed (Memory, offset, capacity) to a client, and let them do their own positioning. The latter does not create a new object but the client has a view of the total parent capacity. The former creates a new object wrapper, but limits the client to what they can see. There are use cases for both.

I do prefer accessing the Writable "constructor-type" methods from the WritableMemory class.

leerho on 13 Mar 2017

@leerho Thanks.

The current form: mem.writableRegion() is OK to me.

leventov on 13 Mar 2017

@leventov @niketh @cheddar @gianm @weijietong @AshwinJay

Development of the new memory architecture has been migrated from experimental/memory4 to its own, more visible repository memory in DataSketches.

I have completed the central Memory and WritableMemory implementation and first wave of unit tests, with coverage at about 95%. I think (hope) the API is fairly stable. I will try to put together a set of bullet points summarizing the features of the API and why some of the choices were made. Meanwhile, I look forward to any comments or suggestions you have.

@niketh and I will soon be focusing on a positional extension to this work.

I want to thank @leventov for his thoughtful contributions for much of this design.

leerho on 16 Mar 2017

@leventov @niketh @cheddar @gianm @weijietong @AshwinJay

The Memory and Buffer hierarchies are checked in to master. @niketh is working on more unit tests, especially for the Buffer hierarchy. Hopefully we can have a release to Maven Central this week. Please look it over.

leerho on 22 Mar 2017

@leerho you mean here: https://github.com/DataSketches/memory?

I think we completely agree on API, except that it misses (?) byteOrdering functionality, that is needed for making refactoring of Druid. Because we need to support many old formats which are big-endian.

I didn't review internal implementation details because actual refactoring of Druid and/or DataSketches with the new API may demonstrate that the new API is problematic in some ways and needs to be reworked. So I'm going to review implementation details of Memory after Druid refactoring PR.

leventov on 22 Mar 2017

you mean here: https://github.com/DataSketches/memory?

Yes.

It was recommended by both @cheddar and @niketh that the byte-ordering functionality is not essential, and that it was more important to get this package out, so that folks can start working with it. I have no plans to implement byte-ordering.

@niketh already has submitted a PR based on the original memory API and has a real good understanding of the implementation issues, and will be the one using this new API to resubmit a new PR based on it. Certainly if he runs into issues with the API we will make adjustments.

leerho on 22 Mar 2017

It was recommended by both @cheddar and @niketh that the byte-ordering functionality is not essential, and that it was more important to get this package out, so that folks can start working with it. I have no plans to implement byte-ordering.

This is one of the things that actual attempt of refactoring of Druid should verify. So yes, we can try to start refactoring without byteOrdering functionality and see if it works well.

leventov on 22 Mar 2017

@leerho
BTW since Druid has now officially moved to Java 8, should Memory still support Java 7? I see https://github.com/DataSketches/sketches-core/ is also Java 8.

If it shouldn't, Memory and WritableMemory could be made interfaces, because interfaces support static methods in Java 8. If you want. However should be checked that performance is the same.

leventov on 24 Mar 2017

@leventov Performance degrades quite a bit with interfaces, unfortunately. Now that I have it working as abstract hierarchies, I'm not sure I want to change it.

Buffer, etc. is now working and with unit test coverage at 96%.

leerho on 24 Mar 2017

Netty found the same issue with interfaces: http://netty.io/wiki/new-and-noteworthy-in-4.0.html#bytebuf-is-not-an-interface-but-an-abstract-class

leventov on 28 Mar 2017

@cheddar @leerho @niketh as far as I can reason from public sources, this project is under development. According to https://github.com/druid-io/druid/issues/3892#issuecomment-276548114, could the query processing part be migrated first, and then the serde part? The processing part blocks #4422.

leventov on 19 Jun 2017

My 2cents concerns

b-slim on 29 Apr 2018

@b-slim

The facts are as follows:

The current internal implementation of Memory is heavily dependent on the Unsafe class, as many high-performance libraries do. However, the architecture of Memory has been designed so that a non-Unsafe implementation could be created without impacting the API.

Druid has not moved to JDK 9 yet, nor have many of the other systems that currently use the library. So there hasn't been a great deal of pressure to move to JDK 9, yet. Nonetheless, when the time comes we will move to 9, 10, 11 or whatever.

My comment in the memory docs that you highlighted is simply the truth. We have not had the time, resources or the requirement to move to JDK 9 or 10. So it obviously hasn't been tested to work against JDK 9 or 10 either. I'm clearly not going to guarantee code that hasn't been tested. And I don't plan to start extensive testing until it becomes a requirement.

There have been only 2 people heavily involved in the design and implementation of the Memory repository in DataSketches, @leventov and myself. And both of us are very busy people.

If you understand the value in the Memory API as @leventov and I do, then how about contributing a helping hand?

leerho on 30 Apr 2018

how about contributing a helping hand?

@leerho it will be a great honor and learning experience to help. Am wondering by help you are referring to move Memory to be jdk9 compatible or refactor Druid code base to start using The Memory lib?

b-slim on 1 May 2018

You could help by start doing some testing w/ Memory:

1) Do some testing w/ JDK9. What are the blockers? My understanding is that JDK9 allows access to Unsafe, but we have to add some code to access it. How and where do changes need to be made? My concern is that we will have to have a special code base for JDK9 that cannot be used with JDK8. Please investigate. You will need to create your own jars from master as the latest code has not been released to Maven Central yet. Although I hope it will be soon.
2) What about JDK10? Same questions.
3) Once you have some answers as to where it breaks and what we need to do, we can strategize on the best way to go forward. Don't submit any PR's, it is too early. If you want to show us code we can look at code on your own repo.

As a longer range contribution, you could investigate VarHandles and MethodHandles. Will they help at all? I'm not convinced from what I have read, but I have not played with them yet. If they look promising, you could do some detailed timing characterization and find out how they perform.

Then there is the OpenJDK Panama Project and JEP 191. These have been on the sideline for years, but if it they were ever adopted it would make life so much simpler for us. Do some digging and find out where they are headed and when! Contact John Rose and Charles Nutter... ask them!

You could become our migration expert !! :)

leerho on 1 May 2018

This issue has been marked as stale due to 280 days of inactivity. It will be closed in 2 weeks if no further activity occurs. If this issue is still relevant, please simply write any comment. Even if closed, you can still revive the issue at any time or discuss it on the [email protected] list. Thank you for your contributions.

stale[bot] on 21 Jun 2019

This issue has been closed due to lack of activity. If you think that is incorrect, or the issue requires additional review, you can revive the issue at any time.

stale[bot] on 5 Jul 2019

This issue is no longer marked as stale.

stale[bot] on 30 Jul 2019

This issue has been marked as stale due to 280 days of inactivity. It will be closed in 4 weeks if no further activity occurs. If this issue is still relevant, please simply write any comment. Even if closed, you can still revive the issue at any time or discuss it on the [email protected] list. Thank you for your contributions.

stale[bot] on 6 May 2020

Let's keep this open, it's still interesting and relevant. Some recent work includes #9308 and #9314. IMO, as a next step, it'd be interesting to look at switching VectorAggregators and their callers to a Memory-based API.

gianm on 6 May 2020

This issue is no longer marked as stale.

stale[bot] on 6 May 2020

Druid: Move from ByteBuffer to Memory

Most helpful comment

All 131 comments

On `Cleaner`

On `Memory` in Druid source

Closer look at `Memory` design

`NativeMemory`

`MemoryRegion`

#

#

Related issues

Druid: Move from ByteBuffer to Memory

Most helpful comment

All 131 comments

On Cleaner

On Memory in Druid source

Closer look at Memory design

NativeMemory

MemoryRegion

#

#

Related issues

On `Cleaner`

On `Memory` in Druid source

Closer look at `Memory` design

`NativeMemory`

`MemoryRegion`