Large mutable byte array in Erlang

Question

As I am writing a simple Minecraft server application in Erlang, I am now concerned with the question of how to efficiently store and modify chunk data. For those who don't know about Minecraft's internals: I need to store a lot of binaries (100-1000) of up to 32kB size in memory. Until this point Erlang's builtin binaries are sufficient. But the server has to read and change some bytes (by their id) in these binaries quite often and I don't want to copy them around all the time.
A nice to have feature would be import and export from/to Erlang's standard binaries.

Is there any Erlang extension or database or whatever I could use for this?

Answer 1

Since binaries are read-only, I can think of the following approaches (assuming you expect high rate of changes):

1. Use tree-like structure with relatively small immutable binaries in the leafs. In that case, when you modify you data, you only need to re-create small leaf binary + all nodes up to the root. Assuming that changes are "local" to some position, I think, you can start with octo-tree.
2. Use "big" binaries + list of changes (that could be as simple list of functions). When you need to modify world, just add new function to the list. When someone asks for the world state, take base binary and apply all changes from the list. From time to time "squash" all changes and prepare a new baseline state binary. This could be combined with previous approach (tree with pairs of binary/changes in the leafs).
3. Move mutable world management to the external code. You can use NIFs or Ports. I think, that would be the fastest way. Also, I think it would be relatively easy to implement it. The first version of API could be as simple as world:new(X, Y, Z) -> ref(); world:get(Ref, X, Y, Z); world:set(Ref, X, Y, Z, Value);

Answer 2

My suggestion is to use a "rope" structure. Basically a tree-like structure, usually a splay or finger tree in which you allow to change parts of the tree only. Doing this the right way allows you to have the best of both worlds: immutability together with fast updates.

I don't know of a rope-implementation, but this is what you want to do.

An alternative is to use ets as a mutable array. It is quite fast for that kind of thing.

The third option is to use a spatial tree-structure to represent your world. Octrees or a BSP-like structure is something I'd grab for, blindly.