Empiezo el mensaje con la buena ración de aesthetics.
Esta semana mayormente estuve leyendo, la verdad que tampoco le hice mucho caso al libro porque tiene un guión muy a piñón fijo y me suelo aburrir con esas cosas.
Redis internamente usa 4 tipos de datos [1]:
- Strings are implemented using a C dynamic string library so that we don't pay (asymptotically speaking) for allocations in append operations. This way we have O(N) appends, for instance, instead of having quadratic behavior.
- Lists are implemented with linked lists.
- Sets and Hashes are implemented with hash tables.
- Sorted sets are implemented with skip lists (a peculiar type of balanced trees).
En el ejemplo del libro sólo se utilizan dos; 1) hash tables y 2) AVL trees para implementar los sorted sets (que son uno de los puntos destacables de redis hasta donde entiendo?). AVL trees son una implementación de self balancing binary trees que es fácil de hacer, pero en redis se usa una skiplist, que supuestamente también es fácil de implementar. Como no soy una persona educada en las ciencias y las artes no conocía el skiplist, pero hay una buena explicación en [2].
En un principio mi idea era usar skiplist porque, por motivos evidentes, nunca escribí ninguna y además la parte de rebalancear el árbol me parece algo coñazo si estás pensando en concurrencia, mientras que he visto implementaciones lock free de la skiplist que parecen sencillitas. Me encontré con un post de stackoverflow [3] que es una mina, tiene dos respuestas muy buenas con mucha info y el paper de concurrent programming without locks [4] que ponen parece muy guay (y muy largo me cago en la puta 60 paginazas). También me encontré con un mensaje del autor de redis hablando de por qué escogió skiplists [5] que básicamente se reduce a su sencillez para implementar, razonar e iterar sobre ellas vs los árboles que introducen mayor complejidad.
Buscando un poco sobre lock free skiplists y tirando del hilo de las respuestas de stack overflow me puse a leer el source del ConcurrentSkipListMap [6] de la stdlib de java y a menos que me canse imagino que tiraré por aquí para ir haciendo mis cosas, porque me pareció guay la idea de delegar en el GC el borrado (independientemente de lo bien/mal que vaya luego a nivel de perf). La verdad que el comentario que hay en la clase es to largo pero está muy guay, recomiendo leerlo porque es bastante entretenido y tiene bastantes referencias.
edit: CAS aquí es 'compare and swap' la wiki inglesa explica bien lo que es
Ya que estaba aproveché y le eché un vistazo rápido a la docu de go sobre el garbage collector [7], que no está nada mal. No explica "nada nuevo" pero está bien reeler cosas para afianzar. Y si no tienes ni la más remota idea de cómo funciona un GC no es mal página para apuntar cosas sobre las que leer.
Luego me puse a explorar un poco el source de redis, hacer arqueología con el historial de git y me empecé a dispersar con cosas. Ahora mismo no tengo claro del todo las estructuras internas que utiliza redis y es a lo siguiente que quería meterle mano. Está guay en github que puedes ver el historial de un fichero y es fácil identificar lo que viene de PRs o cambios importantes porque ves muchos avatares relacionados con el commit. Por ejemplo esta pull [8] es en la que se añaden las quicklists [9] y se dejan de utilizar linked lists y skip lists para usar la misma implementación de ambas (lo que dejaría obsoleto el comentario que cito al principio), pero tampoco me queda claro del todo qué utiliza redis para qué y por qué (y tampoco sé cuánto quiero conocer de esto lol).
También me queda pendiente leer algo más de la taxonomía de las data structures porque la verdad que me sacas del ABC y me pierdo. Tampoco es algo que me interese mucho (#sorrynotsorry) pero si me apetece le daré un repaso.
Así como próximos objetivos no sé muy bien qué marcarme. Voy a acabar de leer unas cosas que se me han quedado y creo que más o menos los siguientes pasos que puedo hacer son:
- Implementar la skiplist. Y si me aburro pues dejarla medio coja, porque si me empiezo a aburrir de algo y me fuerzo es instadrop de todo F.
- Limpiar algo el código
a. Limpiar alguna guarrada que se me ha quedado (como el uso guarrete de los buffers o dejar de marear la perdiz con los integers).
b. Mejorar la respuesta del servidor para que sea parseable programáticamente (aunque sea añadir un flag para error/not found/success + payload).
- Aprovechar lo que me de para seguir leyendo de data structures y ver si así dejo de ser un iletrado.
[1] https://stackoverflow.com/a/9626334
[2] https://opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/SkipList.html
[3] https://stackoverflow.com/q/256511
[4] https://www.cl.cam.ac.uk/research/srg/netos/papers/2007-cpwl.pdf
[5] https://news.ycombinator.com/item?id=1171934
[6] https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java
[7] https://tip.golang.org/doc/gc-guide
[8] https://github.com/redis/redis/pull/2143
[9] https://matt.sh/redis-quicklist
