cabol / shards Goto Github PK

View Code? Open in Web Editor NEW

294.0 13.0 36.0 2.41 MB

Partitioned ETS tables for Erlang and Elixir

Home Page: https://hexdocs.pm/shards

License: MIT License

Makefile 0.79% Erlang 99.21%

erlang elixir ets partitioning sharding

shards's Introduction

Shards

ETS tables on steroids!

Sharding for ETS tables out-of-box.

Why might we need Sharding/Partitioning for the ETS tables? The main reason is to keep the lock contention under control enabling ETS tables to scale out and support higher levels of concurrency without lock issues; specially write-locks, which most of the cases might cause significant performance degradation.

Therefore, one of the most common and proven strategies to deal with these problems is Sharding or Partitioning; the principle is pretty similar to DHTs.

This is where shards comes in. Shards is an Erlang/Elixir library fully compatible with the ETS API, but it implements sharding or partitioning on top of the ETS tables, completely transparent and out-of-box.

See the getting started guide and the online documentation.

Installation

Erlang

In your rebar.config:

{deps, [
  {shards, "1.1.0"}
]}.

Elixir

In your mix.exs:

def deps do
  [{:shards, "~> 1.1"}]
end

For more information and examples, see the getting started guide.

Important links

Blog Post - Transparent and out-of-box sharding support for ETS tables in Erlang/Elixir.
Projects using shards:
- shards_dist - Distributed version of shards. It was moved to a separate repo since v1.0.0.
- Nebulex – Distributed Caching framework for Elixir.
- ExShards – Elixir wrapper for shards; with extra and nicer functions.
- KVX – Simple Elixir in-memory Key/Value Store using shards (default adapter).
- Cacherl Distributed Cache using shards.

Testing

$ make test

You can find tests results in _build/test/logs, and coverage in _build/test/cover.

NOTE: shards comes with a helper Makefile, but it is just a simple wrapper on top of rebar3, therefore, you can do everything using rebar3 directly as well (e.g.: rebar3 do ct, cover).

Generating Edoc

$ make docs

NOTE: Once you run the previous command, you will find the generated HTML documentation within doc folder; open doc/index.html.

Contributing

Contributions to shards are very welcome and appreciated!

Use the issue tracker for bug reports or feature requests. Open a pull request when you are ready to contribute.

When submitting a pull request you should not update the CHANGELOG.md, and also make sure you test your changes thoroughly, include unit tests alongside new or changed code.

Before to submit a PR it is highly recommended to run make check before and ensure all checks run successfully.

Copyright and License

Shards source code is licensed under the MIT License.

shards's People

Contributors

Stargazers

Watchers

shards's Issues

Allow to create the `state` passing the rest of its attributes

Basically, provide in shards_state functions like:

shards_state:new/1: new(NumShards)
shards_state:new/2: new(NumShards, Module)
shards_state:new/3: new(NumShards, Module, PickShardFun)
shards_state:new/4: new(NumShards, Module, PickShardFun, PickNodeFun)

Implement `update_counter` and `update_element` in `shards_dist`

Implement update_counter and update_element functions for shards_dist.

Add performance and scalability tests

A first round of performance tests was done, check this BLOG POST

Remove `auto_eject_nodes` property from `state` – it isn't being used

The auto_eject_nodes prop is not being used, so it can be removed from the state.

Support for `select_replace`

Refactor shards to use TIDs instead of names (atoms) for handling the partitions

LRU Feature may be

Can we have a feature of autodeleting record if its retrieved for X amount of time making free space for other objects to use the space ? something like LRU logic

Fix `shards_dist` and `shards` specs to consider the case when `rpc` returns `{badrpc, Reason}`

Currently, the module shards_dist uses rpc to run distributed calls, and in the specs the case whet rpc returns {badrpc, Reason} is not being considered.

I see two ways to handle this:

Just fix the specs considering this case (specs have to be fixed not only in shards_dist but also in shards, since it is a wrapper on top of it). In this case we can create a type like:

-type rpc_res(R) :: R | {badrpc, Reason :: term()}

And re use it from the the specs, like so:

-spec update_counter(
        Tab      :: atom(),
        Key      :: term(),
        UpdateOp :: term(),
        State    :: shards_state:state()
      ) -> rpc_res(integer() | [integer()]).

Handle the {badrpc, Reason} internally and raise an exception with the corresponding error.

%% @private
rpc_call(Node, Module, Function, Args) ->
  handle_rpc_res(rpc:call(Node, Module, Function, Args)).

%% @private
handle_rpc_res({badrpc, {'EXIT', {Reason, _}}}) ->
  error(Reason);
handle_rpc_res(Res) ->
  Res.

And reuse the private function rpc_call/4 internally.

Evaluate both alternatives and come up with the best approach.

Fix `shards` to work well with `ordered_set` tables.

Currently, shards doesn't behaves well when tables are ordered_set type, because results are sorted per shards, but not at global level (across all configured shards). The same problem happens with shards_dist across different node.

NOTE: This might be tricky to solve.

Modify `shards_local` to avoid additional table types, handle a flag `sharded` instead.

Currently, shards_local has two additional table types: sharded_bag and sharded_duplicated_bag. The idea is remove these types, keeps the current ones, and handle a flag sharded instead – to know when the key should be modified to be sharded or not.

Fulfil ETS API for `shards_local`

ETS Functions:

shards:info/1 bad argument crash

Can lose a race between looking up the shards and calling ets:info/1, getting undefined instead of a list, and:

[error] GenServer Braun.CacheMonitor terminating
** (ArgumentError) argument error
    (stdlib 3.13.2) :lists.keyfind(:size, 1, :undefined)
    (shards 0.6.2) deps/shards/src/shards_local.erl:1531: anonymous fn/3 in :shards_local.shards_info/3
    (shards 0.6.2) deps/shards/src/shards_lib.erl:161: anonymous fn/4 in :shards_lib.keyupdate/4

Paginated select/match raises `badarg` when used with large data

When paginating over a large number of records using select or match sometimes a badarg error is raised

Unify `pick_shard_fun` and `pick_node_fun` in a single spec

Both pick_shard_fun and pick_node_fun receive the same parameters and produce the same result – given a Key, Range and Op return a value between 0..Range-1.

The spec for both funs might be:

-type pick_fun() :: fun((key(), range(), op()) -> non_neg_integer() | any).

In case of pick_node_fun, the rest of the logic of select from the node list the Nth element (returned by pick_node_fun) might be handled in shards_dist module.

Make shards just a library to work locally and move shards_dist to a separate project/repo

This implies a big refactoring, since currently shards_dist is very coupled to shards. Therefore, once the refactor is done, shards_dist won't be supported afterward, it will take some time to implement shards_dist again based on the new shards architecture.

Failed to start shard_sup

I'm trying to run my cache on alpine linux and I'm getting errors. I'm using the nebulex library btw.

Process #PID<0.2814.0> terminating: {{:shutdown, {:failed_to_start_child, Studio.Cache, {:shutdown, {:failed_to_start_child, :shards_sup, {:EXIT, {:undef, [{:shards_sup, :start_link, [Studio.Cache.LocalSupervisor], []}, {:supervisor, :do_start_child, 2, [file: 'supervisor.erl', line: 365]}, {:supervisor, :start_children, 3, [file: 'supervisor.erl', line: 348]}, {:supervisor, :init_children, 2, [file: 'supervisor.erl', line: 314]}, {:gen_server, :init_it, 2, [file: 'gen_server.erl', line: 365]}, {:gen_server, :init_it, 6, [file: 'gen_server.erl', line: 333]}, {:proc_lib, :init_p_do_apply, 3, [file: 'proc_lib.erl', line: 247]}]}}}}}}, {Studio.Application, :start, [:normal, []]}}

Implement `ets:rename/2`

Rename tables support.

Improve test coverage (ideally 100%)

Rollback when `insert_new` fails

Despite this operation is not atomic, at least roll-back or delete previously inserted entries if insert_new fails on one shard.

Issues on Erlang v21

In an elixir project:

===> Compiling shards
===> Compiling src/shards_task.erl failed
src/shards_task.erl:281: erlang:get_stacktrace/0: deprecated; use the new try/catch syntax for retrieving the stack backtrace
src/shards_task.erl:284: erlang:get_stacktrace/0: deprecated; use the new try/catch syntax for retrieving the stack backtrace
src/shards_task.erl:287: erlang:get_stacktrace/0: deprecated; use the new try/catch syntax for retrieving the stack backtrace

** (Mix) Could not compile dependency :shards, ".mix/rebar3 bare compile --paths "_build/dev/lib/*/ebin"" command failed. You can recompile this dependency with "mix deps.compile shards", update it with "mix deps.update shards" or clean it with "mix deps.clean shards"

Modify `shards:new/2` function to return only the table name in case of success

Currently, shards:new/2 return a tuple {TabName, State}, the idea id make it more compatible with original ets:new/2, returning only the table name (an atom).

OTP < 18 not supported

shards_owner_sup is making use of the newly introduced map support for supervisor child specs and flags (https://www.erlang.org/downloads/18.0), this prevents older versions from being able to use shards. Maybe co-existence could be possible by detecting the target OTP version and generating either the old tuple format or the new one.

Distributed shards in 1.0?

Does this project no longer support distributing shards across multiple nodes?

Use the metadata ETS table for storing the partitions TIDs, instead of building atoms in runtime for table names

Implement sharding at global level.

Currently, shards only supports sharding locally, where each created table (logical table) is represented internally and transparently by multiple physical ETS tables. The idea is extent the API at cluster level, having multiple erlang nodes with their own local shards inside. Here is needed a consistent hashing algorithm, so the idea is to use Google Jumping Consistent Hashing. See also toy_kv.

Implement `select/match` pagination ops for `shards_dist`

Implement:

select/3, select_count/3, select_reverse/3, select_count/3
match/3, match_delete/3, match_object/3

Compilation error with OTP 26

When compiling using OTP 26 and rebar 3.22.0 we get the following error:

❯ rebar3 compile +debug_info
===> Fetching rebar3_proper v0.12.1
===> Analyzing applications...
===> Compiling rebar3_proper
===> Fetching rebar3_ex_doc v0.2.23
===> Analyzing applications...
===> Compiling rebar3_ex_doc
===> Verifying dependencies...
===> Analyzing applications...
===> Compiling shards
===> Compiling src/shards.erl failed
src/shards.erl:1505:23: type variable 'Pos' is only used once (is unbound)
src/shards.erl:1505:28: type variable 'Value' is only used once (is unbound)

These are the detailed rebar and OTP versions:

❯ rebar3 --version
rebar 3.22.0 on Erlang/OTP 26 Erts 14.1.1
❯ erl -eval '{ok, Version} = file:read_file(filename:join([code:root_dir(), "releases", erlang:system_info(otp_release), "OTP_VERSION"])), io:fwrite(Version), halt().' -noshell
26.1.2

We believe this to be related to this change introduced in OTP 26: https://www.erlang.org/patches/otp-26.0#OTP-18389

Add support for `ordered_set` locally (`shards_local`)

This is a Nice-To-Have issue, since it might be very complex/tricky.

Improve `shards_local:info/1,2` to be compliant with ETS functions

The idea is to return information about the shards as well, like number of shards, a list of shards tables. etc. So instead of return only a list with the info for each shard, return a mixed tuple list with the regular ETS info and additionally with the shards info. For items like memory and size it would be necessary to sum all shards values.

Create the module shards_group as dynamic supervisor for creating/deleting tables dynamically as part of a supervision tree

Separate `shards` from specific consistent hashing implementation.

Put Jumping Consistent Hash related modules in a different repo, keep shards totally agnostic to specific consistent hash algorithm implementations.

Improve `shards_local` fix #4 – `ordered_set` support.

Currently, a workaround was implemented to support ordered_set tables (#4), the idea is come up with a better solution.

This is a Nice-To-Have issue, since it might be very complex/tricky.

Make distribution function (pick none/shard) configurable.

Currently shards_dist uses Jumping Consistent Hashing, but it would be good to make this function to calculate/pick the node totally configurable.

I don't know if make sense do the same for shards_local, because locally, we always have the same amount of shards and the function is pretty dump and simple (erlang:phash2/2).

file2tab,tab2file not working

shards:new(live,[{scope, g},{nodes, [node()]}]).
shards:insert(live,{k2,val2}).
true
shards:insert(live,{k4,val2}).
true
shards:insert(live,{k23,val2}).
true

shards:lookup(live,k23).
[{k23,val2}]

shards:tab2list(live).
** exception error: undefined function shards_dist:tab2list/2
(ejabberd@localhost)10> shards:tab2file(live,"/tmp/test").
** exception error: undefined function shards_dist:tab2file/3

above functions dont work.

from ets it does work.
ets:tab2list(live_2).
[{k2,val2}]

Allow to call `shards_local` without the state – using a default state.

Most of the cases, the tables are created with default parameters, normally shards is used locally, using default pick funs. For those cases, it is not necessary to recover the state first, it can be created with default parameters, and avoid an unnecessary call to the ETS control table – such as shards does currently. To achieve this, two things are required:

Improve shards_state module, add setters functions in order to be able to create a sate and modify its properties.
In shards_local module, for all those function that receives the state as parameter, add an equivalent function without the state, creating a default one. E.g.: for shards_local:insert/3:

insert(Tab, ObjOrObjL, State)

Create an equivalent function without the State param, like this:

insert(Tab, ObjOrObjL) ->
  insert(Tab, ObjOrObjL, shards_state:new()).

Improve `file2tab` and `tab2file` in `shards_local` to be compliant with ETS functions

Current file2tab and tab2file works with a list of files instead of a single filename (as ETS functions).

For tab2file function the idea is generate one file per shard using ets:tab2file/3, and also generate a master file with the given Filename that holds the information about the other shards files in order to be able to recover them later using ets:file2tab/1,2.

For file2tab the idea would be read the master file given by Filename, get the rest of the shards files info and then restore the table (using ets:file2tab/1,2 for each shard).

rebar2 compatibility

Projects that still rely on rebar2 are unable to build shards (example on Mac):
cc /Users/luis.rascao/Projects/shards/c_src/jumping_hash.o -arch x86_64 -shared -L /Users/luis.rascao/Projects/erlang/17.4-hipe/lib/erl_interface-3.7.20/lib -lerl_interface -lei -o /Users/luis.rascao/Projects/shards/c_src/../priv/jumping_hash.so Undefined symbols for architecture x86_64: "_enif_get_uint", referenced from: _compute in jumping_hash.o "_enif_get_ulong", referenced from: _compute in jumping_hash.o "_enif_make_badarg", referenced from: _compute in jumping_hash.o "_enif_make_int", referenced from: _compute in jumping_hash.o

rebar2 compat would help adoption

Operation of the shards:info/2 does not match

Thank you for a nice library.

This is to report that the shards:info/2 is different from the ets:info/2 behavior.

> shards:info(mytab, name).
** exception error: bad argument
     in function  ets:lookup_element/3
        called as ets:lookup_element(mytab,'$shards_state',2)
...
> ets:info(mytab, name).
undefined

Improve documentation

Create a guides folder and put all documentation there
Create a first getting-started.md file and more part of the README there
Create a shards.md in order to document everything related to design, overall configuration, etc.

Automatically distributed table setup when `shards:new/2` is called with opt `{nodes, [node()]}`

When function shards:new/2 is called with option {nodes, [node()]} and option {scope, g} is set as well, create the table on the given nodes and them join them automatically.

Missing support for keypos

For people using records in ets tables, it is essential to support setting the keypos.

Support named and unnamed tables

Allows to register `shards_sup` with custom name (given as parameter)

Currently, shards is tied to shards_sup and it's registered with the same module name (shards_sup). The idea is to allow to pass the supervisor name as parameter, and for shards:new/2 define another option {sup_name, atom()}.

update_counter spec is not the same as ETS.

The current shards spec expects an integer result when calling update_counter/3, however ETS allows to pass a list of operations:

%%  From Erlang docs
update_counter(Tab, Key, X3 :: [UpdateOp]) -> [Result]

This unfortunately is messing with dialyzer since I'm calling something like this in distributed mode:

case Shards.update_counter(@table, key, [{2, increment}, {4, 1, 0, now}]) do
   [count, _] when count < limit ->
      {:ok, count}

   # key not found, insert it
   {:badrpc, {:EXIT, {:badarg, _trace}}} -> 
      true = Shards.insert(@table, {key, increment, now, now})
      {:ok, increment}

   _other ->
      {:error, :invalid}
end

From dialyzer I get:

The pattern
[_count, _]

can never match the type
integer()
________________________________________________________________________________
The pattern
{:badrpc, {:EXIT, {:badarg, __trace}}}

can never match the type
integer()

Is this just a matter of updating the function spec?

Migrate from pg2 to pg (OTP 23)

Hi,

As of OTP 23, The pg2 module has been deprecated and replaced with similar but faster pg module.

I think for most parts changing pg2 with pg will do the trick.

But there are couple places in this library which used create/1 and delete/1 functions.
These functions are not present in pg.

All create/1 calls can be deleted.

Groups are automatically created when any process joins, and are removed when all processes leave the group. 
Non-existing group is considered empty (containing no processes).

source: https://erlang.org/doc/man/pg.html

But delete/1 is an issue! Since it may be used to clear a group but pg does not have a simple way of doing that.
A substitute would be:

pg:leave(Group, pg:get_members(Group))

I don't know if doing this is necessary!

And I wanted to thank you for your amazing libraries. ❤️

Implement `shards_registry` (in a separate repo); the analogous to Elixir `Registry` but in Erlang

shards_registry will be a very good example of using shards and at the same time a very useful lib too, since there will the analogous Elixir Registry but in Erlang.

Shards 0.6.2 doesn't compile on OTP 23.0.3 on OS X 10.15

Compiling src/shards_dist.erl failed
src/shards_dist.erl:125: pg2:join/2 is deprecated and will be removed in OTP 24; use use 'pg' instead
src/shards_dist.erl:130: pg2:get_members/1 is deprecated and will be removed in OTP 24; use use 'pg' instead
src/shards_dist.erl:135: pg2:leave/2 is deprecated and will be removed in OTP 24; use use 'pg' instead
src/shards_dist.erl:145: pg2:get_members/1 is deprecated and will be removed in OTP 24; use use 'pg' instead
src/shards_dist.erl:440: pg2:delete/1 is deprecated and will be removed in OTP 24; use use 'pg' instead
src/shards_dist.erl:441: pg2:create/1 is deprecated and will be removed in OTP 24; use use 'pg' instead

** (Mix) Could not compile dependency :shards, "/Users/.../.mix/rebar3 bare compile --paths="/Users/.../Projects/.../_build/dev/lib/*/ebin"" command failed. You can recompile this dependency with "mix deps.compile shards", update it with "mix deps.update shards" or clean it with "mix deps.clean shards"

Happened directly after upgrading OTP. Reinstalled erlang and elixir once afterwards. Unsure why it is failing due to depreciations.

Probably same issue as: #40 (comment)