Build your own redis

Wei-Yu

Buenas!

Hace poco comenté por feda /dev/ que había empezado con el libro de build your own redis que me había encontrado por inet. Como estoy ocioso y tenía ganas de hacer algo así de hace tiempo me puse con él. Estoy siguiendo el libro, que está en C, y pasándolo a Go como mi primera interacción real con el lenguaje así que se avecina spaghetti :grin:

En general estoy con esto por curiosear sobre cómo se hacen algunas cosas (ej. nunca había usado poll/epoll). Mi idea es sobre todo centrarme en el happy path y no darle muchas vueltas a que el código sea lo más eficiente o robusto; prefiero centrarme en la arquitectura y diseño general y sus building blocks.

Dejo el repo en el que estoy haciendo las cosas aquí:

NSFW

Si alguien quiere sumarse o comentar algo, adelante. Actualizaré por aquí según vaya haciendo algunas cosas. Ahora mismo estoy en el punto 6/14 del libro, pero iré picoteando un poco según vea, porque probablemente vuelva a releer o reimplementar cosas.

Esta semana espero poder acabar esa primera parte del libro.

Y eso es todo. Ahora que abrí el hilo ya puedo meter esto en el cementerio con el resto de proyectos tullidos.

8
B

Tengo corriendo desde hace tiempo un contenedor de redis pero, sinceramente, nunca he parado a leer sobre sus ventajas y usos. Esto y nosql es algo que tengo pendiente.

1 respuesta
JuAn4k4

No es mala idea para aprender a hacer sistemas distribuidos.

Conceptos como el CAP theorem, eventual consistency, fault tolerance, net splits, statefull distributed clusters, consistent hashing, bloom filters, replica-sets, master-máster, algoritmos de sincronización, vector clocks, etc.

Se pueden aprender muchas cosas haciendo un redis poco a poco, además que tienes un mundo de teoría en cuanto a cachés y sistemas distribuidos bastante trillado.

1 2 respuestas
B

.

1 respuesta
Wei-Yu

Apenas le he podido meter tiempo el finde, me ha dado para refactorizar el protocolo y actualizar la docu. También aproveché y arreglé alguna cosilla que me había quedado colgando como un typo que dejaba el socket de la conexión como blocking (así que casi todas las llamadas se quedaban colgadas esperando por más datos).

Se me queda para después el que las acciones (SET|GET|DEL) de verdad hagan algo sobre un map interno o algo así. Espero gamificar un poco el pico y pala de parte del curro que se hace pesado con los tests unitarios, porque si no ZZzzzZZzz.


#2 nosql hasta donde entiendo es mayormente blob/document store. Tienes alguna cosa adicional como temas de graph databases pero la mayoría de lo que te vas a encontrar van a ser document stores sustituyendo malamente un RDBMS. Redis al final lo vas a usar siempre como caché. En .net tienes la abstracción de IMemoryCache, sería tener eso detrás de un servicio http a grandes rasgos. Si no tienes nada que cachear, no lo usas (y aún necesitándolo a veces puedes tirar con la caché in memory).

#3 Por lo que he visto hojeando el libro es mayormente single process, sin nada de clustering ni nada así (para mí que eso daría para otro libro). Sí que me gustaría echarle un vistazo más a fondo a ese tema así que si alguien tiene una recomendación, adelante. Por ahora sigo con el DDIA avanzando poco a poco y re-revisando cosas según voy dándole vueltas a ideas.

#4 la captura es un layout del powertoys que tengo para "intentar concentrarme" (otra cosa es que lo haga kek). Mayormente estoy con nvim y vscode para debuggear, no me apetece echarle un vistazo al state of the art de los DAPs [1][2] como para intentar debuggear con nvim.

El código es y será bastante chapucerillo en general, me dedicaré a hacer code splitting simplista para poder trabajar tranquilo pero por el resto... las excepciones todas bubling hasta crashear el proceso, muchas cosas evidentes fuera del happypath que no pienso tocar por pereza, atajos varios... A menos que me "apetezca" no refactorizaré mucho.

1 1 respuesta
sergioRG

Siempre te quiero dar estrellita y siempre abro este hilo donde no tengo el login de GitHub, cuando llegue a casa te prometo que cae

1 1 respuesta
Kaledros
#5Wei-Yu:

powertoys

No sabía lo que era, lo he buscado y me flipa. Me alegra que MS se ponga las pilas y añada features que ya existen en MacOS y echaba mucho de menos en Win y también cosas que no vienen en MacOS por defecto pero que todo el mundo usa a través de apps recomendadas. A tope.

1 respuesta
Wei-Yu

#6 con que alguien se anime a hacer algo parecido me vale. Todas las semanas veo un montón de gente haciendo mil cosas y esto en realidad es un juguete pequeñito que en unos pocos días de curro se hace todo.

#7 sigue sin ser un tiling "real" porque simplemente haces un layout y ya. Lo más parecido a tiling wm que he visto en windows es este pero nunca lo he usado. Siempre usé i3 así que lo echo muchísimo de menos. Al menos windows-terminal es un 11/10 así que eso que me llevo.

1
Lecherito

#3 una de las cosas que lei hace poco fue el primer paper que publicaron sobre DynamoDB y la verdad es que esta muy curioso.

1 2 respuestas
desu

#9 es muy bueno, de mis papers favoritos que lei en 2019

como ese paper hay otros muy interesantes, el postgresql original de los 80, el map reduce de google... son interesantes

W0rd

#9 algún enlace?

1 respuesta
JuAn4k4

#11 así no sabes usar google puedes ahorrarte leerlo. https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf

1 respuesta
W0rd

#12 he pensado lo mismo xd pero justo entraba en una meeting, gracias por el link.

Wei-Yu

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:

  1. 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.
  2. 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).
  3. 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

1
desu

Un feedback que te voy a dar.

Es que yo en su dia tambien me centre mucho en el tecnicismo.

Pero hoy en dia, si volviese al pasado, trataria de centrarme mas en los casos de uso y funcionalidades... porque entonces los tecnicismos se explican y salen solos.

En lugar de mirar las estructuras de datos que mas me gustan o mas faciles de implementar, miraria el caso de uso que quiero implementar, y la estructura de datos que mejor funcionan.

Salu2

2 respuestas
Wei-Yu

#15 eso depende del motivo por el cual tienes el proyecto personal. Un proyecto personal tiene que ser fun driven development. Otras veces prototipando cosas he empezado por los casos de uso y flujos de usuario y lo he dejado sin picar nada, simplemente rompiendo y ordenando cosas me entretuve. Ahora quiero entretenerme con otra cosa; mi idea era seguir el libro pero me lo paso mejor saliéndome por la tangente.

2 respuestas
PiPePiTo

#15 #16 Para según qué casos los tecnicismos primero yo los agradezco... Si en ellos describen el por qué en un caso de uso de ejemplo.

Al menos para cosas técnicas prefiero primero el por qué y luego el cómo.

Porque hay peña que se queda con el cómo cuando lo mismo no se aplica en su por qué.

Cuestión de gustos

1 respuesta
desu

#16 si tu entiendes que no estas aprendiendo nada haciendolo como lo haces mas alla de un lenguaje de programacion perfecto.

pensaba que el objetivo era aprender redis tambien y no solo go.

porque leer una estructura de datos y picarlo no es aprender.

#17 si no sabes sabes el caso de uso por el que se usa una estructura de datos no sabes para que sirve no?

si lees el tecnicismo primero te sirve para conocer que existe... pero no porque existe ni como se usa.

1 respuesta
PiPePiTo

#18 ya, pero hay locos que aplican el primer resultado que se encuentran en google y los que se comen el marrón detrás ya es otra historia xD

Por eso lo decía que a mi gusto yo suelo poner ambos juntos, el tecnicismo, el por qué y un ejemplillo si puedo

La deuda técnica la pagamos todos xD

1 1 respuesta
desu

#19 Si si claro lo que dices. si tu pones una estructura de datos, lo que tienes que diseñar para que sea resilente a cambios internos es la api publica... que si cambia mucho tampoco pasa nada. y la api define los casos de uso que resuelves.

si tu tienes un HashMap por ejemplo, este se puede implementar de 100 maneras distintas... y tu al final solo te preocupa el map.get y el map.put

a mi si alguien me pone un hashmap con una lista, que se va iterando para buscar, me suda la poll mientras tenga el get y el put. si va lento ya lo cambiare. o si tengo que ir en paralelo. o si ahora lo tiro sombre otro hardware con simd...

las librerias estandard estan cambiando constantemente de algoritmos internos y estructura de datos y no te enteras no? porque el caso de uso es lo importante y cuando los casos de uso cambia, la implementacion cambia. no sirve de nada memorizar implementaciones.

@wei-yu creo que estas haciendo un buen research y seguro que algo se te queda. Si te motiva sigue por ahí que será más que no hacer nada.

Usuarios habituales