Propagación de recuento de referencia.

Un medio legible por ordenador conteniendo instrucciones de programa ejecutables para realizar un método incluyendo:

en una pluralidad de nodos en red donde cada nodo tiene su propio almacenamiento local de objetos, almacenando objetos los almacenamientos de objetos y compartiendo uno o más objetos, teniendo los objetos nombres globalmente únicos a través de los nodos en red y donde los nombres de objeto no cambian en base a donde los objetos están almacenados en los nodos;

mantener, en cada nodo, un recuento local de referencias LRC a nombres de objeto, independientemente de cualquier instancia de objeto almacenada en el almacenamiento local de objetos, manteniéndose el LRC como un entero con signo, donde se hacen ajustes en el LRC para cada nueva referencia y desreferencia locales y una desreferencia de un nombre de objeto puede generar un valor LRC negativo;

donde la propiedad de nombres de objeto es asignada a diferentes nodos, asignándose un rango de nombres de objeto a uno de los nodos de red y la propiedad asignada a nodo inicia un paso de determinación de recuento global de referencias GRC para todo o para un subconjunto del rango, incluyendo el paso de determinación de GRC:

proporcionando el nodo propietario una etiqueta única para un objeto para el que se ha de determinar un GRC;

intercambiando los nodos mensajes con la etiqueta única, por lo que los otros nodos proporcionan al nodo propietario su LRC para el objeto;

calculando el nodo propietario el GRC como una suma de los LRCs recibidos de los otros nodos y el LRC del nodo propietario para el objeto; y

si el GRC resultante es cero, el nodo propietario envía un mensaje de borrado con la etiqueta única a los otros nodos.

Propagación de recuento de referencia Campo de la invención La presente invención se refiere al almacenamiento de objetos de datos, y más en particular a un método y aparato para el seguimiento de objetos almacenados en una pluralidad de nodos en una red de iguales manteniendo al mismo tiempo una visión global de las referencias de los objetos.

Antecedentes A efectos de rendimiento o redundancia, los modernos sistemas de almacenamiento pueden estar formados a partir de componentes discretos, llamados nodos, que están interconectados con una red, tal como una red TCP/IP. Cada nodo es típicamente un ordenador plenamente funcional con CPUs, almacenamiento, memoria, etc. La organización de los nodos en dicho sistema puede ser una red de iguales, lo que significa que todos los nodos son iguales (es decir, no hay autoridad de gestión central y ningún nodo está privilegiado) . Como compañeros iguales, los nodos comunican entre sí para resolver el estado. Organizar un sistema de almacenamiento como una red de iguales puede proporcionar una solución de almacenamiento más elástica y escalable, puesto que se puede añadir nodos incrementalmente para rendimiento y/o capacidad, y si un nodo falla, el sistema de almacenamiento sigue funcionando.

Lo que distingue un sistema de almacenamiento de red de iguales de una colección de ordenadores es que los nodos del sistema comunican uno con otro con respecto al almacenamiento de datos subyacente, la sanidad de cada nodo, etc. Específicamente, los nodos del sistema pueden copiar e intercambiar información a efectos de rendimiento e integridad de datos. Esta información puede estar en forma de objetos de datos, o archivos, donde un objeto puede ser una porción de un archivo.

Dado que los objetos se propagan a través del sistema, se requieren estructuras de datos para: a) conocer dónde están los objetos; y b) conocer cuándo los objetos ya no son necesarios. En los sistemas de la técnica anterior donde los objetos tienen recuentos de referencia, es decir, el número de veces que un objeto es referenciado por otro objeto u otra estructura de datos, un objeto puede ser desasignado o borrado de forma segura (por ejemplo, recogida de basura) cuando su recuento de referencias cae a cero.

Sin embargo, hacer el seguimiento de recuentos de referencia relativos a miles de millones de objetos, cuando se pasan millones de objetos por segundo, da lugar a tráfico de red y costos de CPU inaceptables si se usan algoritmos simplistas.

Otro reto es determinar que el recuento de referencias es realmente cero, y luego hallar todas las instancias de objetos para poder borrarlos. Hay una necesidad creciente de protocolos más eficientes y fiables para seguimiento de objetos con el fin de superar estos problemas.

US2011022566 describe un sistema de archivos que tiene un sistema de archivos de firma digital donde los datos, los metadatos y los archivos son considerados como objetos cuyas referencias son mapeadas por las huellas. El objeto está provisto de la huella globalmente única y derivada de contenido. Un objeto raíz dispone de las huellas de todos los objetos de mapeado. Los cambios en el objeto raíz son rastreados para obtener la historia de la actividad del sistema de archivos.

XP040153040 (B. GOLDBERG: "Generational Reference Counting: A Reduced-Communication Distributed Storage Reclamation Scheme") describe un algoritmo de recuento de referencia generacional (GRC) que implementa un recuento local de referencias que permiten valores negativos con el fin de lograr un sistema libre de error en el caso de mensajes de referencia/desreferencia asíncronos en recuperación de almacenamiento en un almacenamiento de objetos distribuidos.

Resumen de la invención En un aspecto de la invención, se facilita un sistema y método para el seguimiento de referencias de objetos a través de una pluralidad de nodos de red, donde los objetos están distribuidos entre los nodos almacenando una o más instancias de un objeto (las instancias de un objeto contienen datos idénticos) en uno o más nodos de la red. En esta red, las instancias de un objeto pueden ser todas iguales (de iguales) , en contraposición a las instancias entre las que hay alguna relación de jerarquía o maestro/esclavo, es decir, una instancia es primaria o más privilegiada que otra. Estas instancias de iguales pueden ser gestionadas colectivamente por los nodos de red, sin un agente de gestión centralizada. Como se describe más adelante según varias realizaciones de la invención, se facilitan métodos y sistemas para el seguimiento de estas instancias de objetos almacenadas en una pluralidad de nodos de red, seguimiento que permite una determinación global de cuándo un objeto no tiene referencias a través de los nodos en red y puede ser desasignado de forma segura.

Según un aspecto de la invención, cada nodo tiene un almacenamiento local de objetos para efectuar el seguimiento y opcionalmente almacenar objetos en el nodo, y los almacenamientos locales de objetos comparten colectivamente las instancias localmente almacenadas de los objetos a través de la red. Una o más aplicaciones, por ejemplo, un sistema de archivos y/o un sistema de almacenamiento, usan los almacenamientos locales de objetos para almacenar todos los datos persistentes de la aplicación como objetos. La aplicación puede requerir un recuento de referencias para cada objeto almacenado, incluyendo el recuento de referencias el número de referencias al objeto respectivo. Según un aspecto de la invención, el recuento global de referencias para un objeto puede ser rastreado manteniendo en cada nodo un recuento local de referencias LRC a nombres de objeto (en contraposición a instancias de objetos) en el nodo respectivo, incluyendo el valor del LRC una suma de ajustes de recuento de referencias en el nodo local, donde el LRC es independiente de cualquier instancia del objeto almacenado en el almacenamiento local de objetos. Desacoplando el recuento de referencias del recuento de instancias, este método permite valores negativos (enteros con signo) de un LRC, en contraposición a los métodos de la técnica anterior. Además, calculando una suma de los LRCs a partir de una pluralidad de nodos, aquí referida como un recuento global de referencias GRC, el GRC resultante puede ser usado para determinar si, para una aplicación particular que use los nodos en red para almacenar datos persistentes como objetos, es seguro desasignar un objeto (todas sus instancias) porque el objeto ya no está siendo referenciado por la aplicación. Si y solamente si se determina que el GRC es cero, es seguro desasignar las instancias de objetos para un objeto particular.

Según otro aspecto de la invención, la colocación de instancias de objetos en uno o varios nodos se lleva a cabo independientemente del nombre del objeto. En contraposición a los métodos de la técnica anterior que fuerzan la posición de almacenamiento de objetos en base al nombre de objeto, en varias realizaciones de la presente invención la colocación de instancias de objetos en los nodos puede ser determinada por el uso real o previsto de un objeto, por ejemplo, en base al rendimiento de la red o del sistema o la fiabilidad de los datos. Por ejemplo, un almacenamiento local de objetos, conociendo qué sistema (s) de archivo hace (n) referencia a un objeto concreto, puede determinar una colocación preferida del objeto en uno o varios nodos dependiendo del (de los) sistema (s) de archivo que use (n) el objeto. Este sistema es sustancialmente más robusto y eficiente que los sistemas de la técnica anterior que restringen la colocación de objetos de datos en nodos dependiendo de qué sea el objeto, por ejemplo, el nombre del objeto.

Según otro aspecto de la invención, cada nodo local mantiene su propio índice local para mapear nombres de objeto a posiciones físicas en el nodo local donde se almacenan los objetos. Este índice de mapeado puede incluir, por ejemplo, señalizadores a una o más posiciones en el nodo local donde se almacena la instancia de objeto. Las entradas del índice de mapeado local pueden incluir, para un nombre de objeto dado, el LRC y los señalizadores a una o más posiciones de almacenamiento en el nodo local.

Según una realización de la invención, se facilita un medio legible por ordenador conteniendo instrucciones de programa ejecutables para realizar un método incluyendo:

en una pluralidad de nodos en red para compartir objetos almacenados, los objetos tienen nombres globalmente únicos a través de los nodos en red y donde los nombres de objeto no cambian en base a dónde se almacenen los objetos en los nodos;

mantener, en cada nodo, un recuento local de referencias LRC a nombres de objeto, independientemente de cualquier instancia... [Seguir leyendo]

1. Un medio legible por ordenador conteniendo instrucciones de programa ejecutables para realizar un método incluyendo:

en una pluralidad de nodos en red donde cada nodo tiene su propio almacenamiento local de objetos, almacenando objetos los almacenamientos de objetos y compartiendo uno o más objetos, teniendo los objetos nombres globalmente únicos a través de los nodos en red y donde los nombres de objeto no cambian en base a donde los objetos están almacenados en los nodos;

mantener, en cada nodo, un recuento local de referencias LRC a nombres de objeto, independientemente de cualquier instancia de objeto almacenada en el almacenamiento local de objetos, manteniéndose el LRC como un entero con signo, donde se hacen ajustes en el LRC para cada nueva referencia y desreferencia locales y una desreferencia de un nombre de objeto puede generar un valor LRC negativo;

donde la propiedad de nombres de objeto es asignada a diferentes nodos, asignándose un rango de nombres de objeto a uno de los nodos de red y la propiedad asignada a nodo inicia un paso de determinación de recuento global de referencias GRC para todo o para un subconjunto del rango, incluyendo el paso de determinación de GRC:

proporcionando el nodo propietario una etiqueta única para un objeto para el que se ha de determinar un GRC;

intercambiando los nodos mensajes con la etiqueta única, por lo que los otros nodos proporcionan al nodo propietario su LRC para el objeto;

calculando el nodo propietario el GRC como una suma de los LRCs recibidos de los otros nodos y el LRC del nodo propietario para el objeto; y si el GRC resultante es cero, el nodo propietario envía un mensaje de borrado con la etiqueta única a los otros nodos.

2. El medio de la reivindicación 1, donde el método incluye: el propietario y otros nodos borran el objeto cuando el recuento GRC es cero.

3. El medio de la reivindicación 2, donde el paso de determinación incluye: los nodos operan como una red de nodos de iguales.

4. El medio de la reivindicación 3, donde el GRC se calcula mientras se están leyendo o escribiendo objetos y recuentos de referencias de objetos locales están siendo modificados.

5. El medio de la reivindicación 1, donde los almacenamientos locales de objetos incluyen colectivamente un espacio de nombre de los nombres de objeto globalmente únicos.

6. El medio de la reivindicación 1, donde el método incluye:

el almacenamiento local de objetos mantiene un índice de mapeado local del nombre de objeto, LRC y un indicador a cualquier posición física de objeto donde se almacena el objeto en el almacenamiento local de objetos.

7. El medio de la reivindicación 1, donde el método incluye: cada objeto tiene una huella de objeto derivada del contenido de objetos como su nombre de objeto.

8. El medio de la reivindicación 7, donde el método incluye: la huella incluye un hash del contenido de objetos.

9. El medio de la reivindicación 1, donde un sistema de archivos usa los almacenamientos locales de objetos colectivamente como un método para almacenar todos los datos persistentes del sistema de archivos.

10. El medio de la reivindicación 9, donde el método incluye:

todos los datos de sistema de archivos, metadatos y archivos incluyen objetos del (de los) almacenamiento (s) de objetos, teniendo cada objeto una huella de objeto como su nombre de objeto; las colecciones de objetos del sistema de archivos también incluyen objetos del (de los) almacenamiento (s) de 13

objetos, incluyendo cada colección un mapeado de una pluralidad de los objetos del sistema de archivos y teniendo su propia huella de objeto derivada del contenido de la colección, donde un cambio en uno o más objetos de la colección cambia la huella de objeto de la colección; y teniendo un objeto raíz del sistema de archivos una huella de objeto raíz derivada de todos los objetos del sistema de archivos, de tal manera que cada objeto en el sistema de archivos de espacio de nombres sea accesible a través del objeto raíz.

11. El medio de la reivindicación 1, donde el método incluye:

seleccionar, en base al rendimiento o la fiabilidad de la red o del sistema, uno o varios nodos como posición (es) para almacenar una o más instancias de un objeto independientemente del nombre de objeto.

12. El medio de la reivindicación 1, donde el método incluye:

la compartición de los objetos almacenados incluye comunicar entre nodos con respecto a nombres de objeto, LRCs y posiciones de objetos almacenados.

13. El medio de la reivindicación 1, donde el método incluye:

cuando una aplicación desreferencia un nombre de objeto y una copia del objeto no está almacenada en un nodo local, el nodo local genera un LRC de uno negativo.

14. El medio de la reivindicación 1, donde un sistema de almacenamiento usa los almacenamientos locales de objetos colectivamente como un método para almacenar todos los datos persistentes del sistema de almacenamiento.

15. Un aparato incluyendo:

una pluralidad de nodos en red, teniendo cada nodo un almacenamiento local de objetos para almacenar objetos en el nodo respectivo y teniendo los objetos nombres globalmente únicos a través de los nodos en red, donde los nombres de objeto no cambian en base a donde los objetos están almacenados en los nodos; compartiendo los almacenamientos locales de objetos uno o varios objetos;

una aplicación que usa los almacenamientos locales de objetos para almacenar datos persistentes como objetos, requiriendo la aplicación un recuento de referencias para cada objeto almacenado en los nodos en red incluyendo un número de recorridos independientes a través de la pluralidad de nodos al objeto respectivo;

medios para mantener un recuento local de referencias LRC a nombres de objeto en cada nodo, independientemente de cualquier instancia de objeto almacenada en el almacenamiento local de objetos, manteniéndose el LRC como un entero con signo;

donde se hacen ajustes al LRC para cada nueva referencia y desreferencia locales, donde una desreferencia de un 45 nombre de objeto puede generar un valor LRC negativo; y medios para determinar un recuento global de referencias GRC para un objeto, donde la propiedad de nombres de objeto es asignada a nodos diferentes, asignándose un rango de nombres de objeto a uno de los nodos de red, y la propiedad asignada a nodo está configurada para hacer que los medios de determinación inicien un paso de 50 determinación de GRC para todo o un subconjunto del rango, incluyendo los medios de determinación GRC y los nodos configurados para implementar pasos de determinación de GRC:

proporcionando el nodo propietario una etiqueta única para un objeto para el que se ha de determinar un GRC;

intercambiando los nodos mensajes con la etiqueta única, por lo que los otros nodos proporcionan al nodo propietario su LRC para el objeto;

calculando el nodo propietario el GRC como una suma de los LRCs recibidos de los otros nodos y el LRC del nodo propietario para el objeto; y 60 si el GRC resultante es cero, el nodo propietario envía un mensaje de borrado con la etiqueta única a los otros nodos.