4 ms·

"9) Active memory defragmentation. Redis is able to defragment the memory while online..." I'm so amazed that this is a thing.

ihsw2 9y ago
Memory fragmentation is largely related to the allocator you're using (ie: glibc malloc, jemalloc, tcmalloc) and previously it was up to the OS to manage this (ie: freeing up unused memory). Now with active memory defragmentation things are a bit more pleasant, specifically with high delete load actually freeing up unused memory in a timely manner without impacting performance too much. Previously, to fully recover unused memory, you would have to restart the Redis server. Obviously this is not feasible but when Redis is using >50% more memory on a 120GB machine than it should then you will have to consider this an occasional housekeeping option -- now, as mentioned, this ridiculous task is no longer necessary.
- xxs 9y ago
  120GB on a single thread, yeah. Redis has been abused for quite some time but 120GB is way out of reasonable reach for current CPU arch if you use a single core only (even if you switch off hyper threading)
  - iagooar 9y ago
    Call me a slowpoke, but I wasn't aware that Redis was single core!
    - lozenge 9y ago
      It makes it great for storing distributed locks, semaphores, and thanks to Lua scripting it can store/update cache invalidation lists - eg https://github.com/Suor/django-cacheops https://github.com/Suor/django-cacheops
      - deleted 9y ago
        [deleted]
  - jackmott 9y ago
    just randomly curious here - why? hash time gets absurd?
    - ihsw2 9y ago
      Presumably, time complexity for most operations correspond directly with CPU usage. See here for an example with RPUSH: https://redis.io/commands/rpush https://redis.io/commands/rpush RPUSH is O(1) which the best you can possibly get. ZADD on the other hand is O(log(n)), which is quite good but at a large scale it becomes easier to run into performance limitations, especially on high workloads. Performing O(n) operations on large data sets is out of the question unless you're comfortable with Redis being unavailable for multiple seconds/minutes. That said, you will have to limit yourself to operations that are computationally simple (ie: O(1) or O(log(log(n))) or pre-shard across multiple instances (or run a Redis cluster).
      - rhizome 9y ago
        Redis on MOSIX might be an interesting experiment.
- FLUX-YOU 9y ago
  >Now with active memory defragmentation things are a bit more pleasant, specifically with high delete load actually freeing up unused memory in a timely manner without impacting performance too much. Is Redis managing this itself using simple calls to Jemalloc, or is Jemalloc doing it on its own because it has better algorithms than the OS?
  - ihsw2 9y ago
    With regards to better algorithms than the OS -- jemalloc is not quite there yet. Here is an illuminating discussion between Redis and Jemalloc devs regarding this: https://github.com/jemalloc/jemalloc/issues/566 https://github.com/jemalloc/jemalloc/issues/566 Redis will perform its own housekeeping, hence the usage of the term 'active.' AFAIK, rather than metadata being stored for this, there is a periodic active scan and manual measurement. See more here: https://github.com/antirez/redis/pull/3720 https://github.com/antirez/redis/pull/3720
- tgjsrkghruksd 9y ago
  That's only part of the "os" if you mean part of the installed libc, as opposed to part of the kernel. Managing heap is done in userspace.
jackmott 9y ago
It is one of those things where people say "Java can be faster than C/C++ because it can compact memory" and the C/C++ lady says "here, hold my beer"
- xxs 9y ago
  To be fair only a compacting GC can do that
  - user5994461 9y ago
    And the Java GC is NUMA aware. The C compiler is not.
    - mianos 9y ago
      WTF
  - bluGill 9y ago
    That isn't strictly true. You do not need to do garbage collection to compact memory. The data needed to do memory compaction and garbage collection largely overlaps, so you may as well do both, but you don't have to. To implement either you need to do a scan of all pointers in memory - for a garbage collection you save a currently in use list, for compaction you need to a map of where they are so you can change them latter. What you do with that data is different, but only the first step is the same. (though garbage collection can feed the empty places into the compactor which makes that work easier) I've actually been thinking about how to do compaction in C++. The reason you cannot do it in general is code like "socket.send(new object, sizeof(void*)". The remote is then expected to send back that pointer which you cast to object and reference. Evil code for sure with a lot of failure cases that result in leaks or security holes, but possible.
    - xxs 9y ago
      Compaction is rather trivial with stop the world phase. Doing it without is a lot more challenging.
faragon 9y ago
Memory fragmentation can be avoided by construction, e.g. using trees allocated in linear storage (e.g. like std::map is implemented, or the maps in libsrt [1]). For strings a binary tree (or a B/B+ could be faster), and it would not require defragmentation nor rehashing (and worst access time would be log(n), instead of O(n)). Make growing the tree using realloc() is "free" on systems with virtual memory map/remap. [1] https://github.com/faragon/libsrt https://github.com/faragon/libsrt
modarts 9y ago
Seriously, that sounds magical
praseodym 9y ago
Could anyone explain me why this is needed with virtual memory? Wouldn't the OS take care of handling gaps of free space?

ihsw2 9y ago

Memory fragmentation is largely related to the allocator you're using (ie: glibc malloc, jemalloc, tcmalloc) and previously it was up to the OS to manage this (ie: freeing up unused memory). Now with active memory defragmentation things are a bit more pleasant, specifically with high delete load actually freeing up unused memory in a timely manner without impacting performance too much. Previously, to fully recover unused memory, you would have to restart the Redis server. Obviously this is not feasible but when Redis is using >50% more memory on a 120GB machine than it should then you will have to consider this an occasional housekeeping option -- now, as mentioned, this ridiculous task is no longer necessary.

xxs 9y ago
120GB on a single thread, yeah. Redis has been abused for quite some time but 120GB is way out of reasonable reach for current CPU arch if you use a single core only (even if you switch off hyper threading)
- iagooar 9y ago
  Call me a slowpoke, but I wasn't aware that Redis was single core!
  - lozenge 9y ago
    It makes it great for storing distributed locks, semaphores, and thanks to Lua scripting it can store/update cache invalidation lists - eg https://github.com/Suor/django-cacheops https://github.com/Suor/django-cacheops
    - deleted 9y ago
      [deleted]
- jackmott 9y ago
  just randomly curious here - why? hash time gets absurd?
  - ihsw2 9y ago
    Presumably, time complexity for most operations correspond directly with CPU usage. See here for an example with RPUSH: https://redis.io/commands/rpush https://redis.io/commands/rpush RPUSH is O(1) which the best you can possibly get. ZADD on the other hand is O(log(n)), which is quite good but at a large scale it becomes easier to run into performance limitations, especially on high workloads. Performing O(n) operations on large data sets is out of the question unless you're comfortable with Redis being unavailable for multiple seconds/minutes. That said, you will have to limit yourself to operations that are computationally simple (ie: O(1) or O(log(log(n))) or pre-shard across multiple instances (or run a Redis cluster).
    - rhizome 9y ago
      Redis on MOSIX might be an interesting experiment.
FLUX-YOU 9y ago
>Now with active memory defragmentation things are a bit more pleasant, specifically with high delete load actually freeing up unused memory in a timely manner without impacting performance too much. Is Redis managing this itself using simple calls to Jemalloc, or is Jemalloc doing it on its own because it has better algorithms than the OS?
- ihsw2 9y ago
  With regards to better algorithms than the OS -- jemalloc is not quite there yet. Here is an illuminating discussion between Redis and Jemalloc devs regarding this: https://github.com/jemalloc/jemalloc/issues/566 https://github.com/jemalloc/jemalloc/issues/566 Redis will perform its own housekeeping, hence the usage of the term 'active.' AFAIK, rather than metadata being stored for this, there is a periodic active scan and manual measurement. See more here: https://github.com/antirez/redis/pull/3720 https://github.com/antirez/redis/pull/3720
tgjsrkghruksd 9y ago
That's only part of the "os" if you mean part of the installed libc, as opposed to part of the kernel. Managing heap is done in userspace.

jackmott 9y ago

It is one of those things where people say "Java can be faster than C/C++ because it can compact memory" and the C/C++ lady says "here, hold my beer"

xxs 9y ago
To be fair only a compacting GC can do that
- user5994461 9y ago
  And the Java GC is NUMA aware. The C compiler is not.
  - mianos 9y ago
    WTF
- bluGill 9y ago
  That isn't strictly true. You do not need to do garbage collection to compact memory. The data needed to do memory compaction and garbage collection largely overlaps, so you may as well do both, but you don't have to. To implement either you need to do a scan of all pointers in memory - for a garbage collection you save a currently in use list, for compaction you need to a map of where they are so you can change them latter. What you do with that data is different, but only the first step is the same. (though garbage collection can feed the empty places into the compactor which makes that work easier) I've actually been thinking about how to do compaction in C++. The reason you cannot do it in general is code like "socket.send(new object, sizeof(void*)". The remote is then expected to send back that pointer which you cast to object and reference. Evil code for sure with a lot of failure cases that result in leaks or security holes, but possible.
  - xxs 9y ago
    Compaction is rather trivial with stop the world phase. Doing it without is a lot more challenging.

faragon 9y ago

Memory fragmentation can be avoided by construction, e.g. using trees allocated in linear storage (e.g. like std::map is implemented, or the maps in libsrt [1]). For strings a binary tree (or a B/B+ could be faster), and it would not require defragmentation nor rehashing (and worst access time would be log(n), instead of O(n)). Make growing the tree using realloc() is "free" on systems with virtual memory map/remap. [1] https://github.com/faragon/libsrt https://github.com/faragon/libsrt

modarts 9y ago

Seriously, that sounds magical

praseodym 9y ago

Could anyone explain me why this is needed with virtual memory? Wouldn't the OS take care of handling gaps of free space?