SQL : Nouvel identifiant d'article entier basé sur la date

[Alkarex]

Discussion pour le choix d'un nouvel identifiant pour les articles.

Actuellement, FreshRSS utilise un CRC32 pour identifier les articles, encodé en base64 modifié.

Cela représente des problèmes majeurs, en particulier un problème de collisions trop important, et le fait que c'est peu pratique et lent pour les requêtes SQL.

• Risque de collision : pour un hachage parfaitement distribué sur n-bit, le risque de collision dépasse 50% quand le nombre d'articles dépasse 2^(n/2), soit actuellement seulement 65535 articles pour FreshRSS (j'en ai déjà 32266 en ayant commencé en août).
  http://www.codinghorror.com/blog/2007/08/url-shortening-hashes-in-practice.html
  https://fr.wikipedia.org/wiki/Paradoxe_des_anniversaires
• Peu pratique pour les requêtes SQL : l’identifiant actuel n'est pas dans l'ordre chronologique et ne peut du coup pas être utilisé tel quel pour la pagination (oblige à faire un concat de la date et de l'ID, peu performant). Voir les commentaires de Exemples de flux avec des dates dans le futur #151 pour plus de détails.
• Actuellement, l'identifiant est stocké en texte, ce qui est moins performant qu'un entier en particulier pour une clef primaire, et surtout qu'un concat avec la date est nécessaire pour les requêtes principales. Voir http://dev.mysql.com/doc/refman/5.1/en/encryption-functions.html
• La date est actuellement un champ de requête très important, et n'est pas indexé. Ça serait mieux de remplacer ce rôle dans une majorité (en volume) de requêtes par une clef primaire efficace.

---

J'aurais voulu utiliser un champ date incluant les microsecondes, mais c'est disponible seulement depuis la version 5.6 de MySQL (par exemple pas disponible sur l'actuelle Ubuntu LTS), du coup abandonné
http://dev.mysql.com/doc/refman/5.6/en/fractional-seconds.html

---

Du coup, je fais une proposition basée sur BIGINT (entier 64 bits) disponible sur MySQL depuis longtemps et SQLite :
http://dev.mysql.com/doc/refman/4.1/en/integer-types.html
http://www.sqlite.org/datatype3.html#affname

[Alkarex]

Je trouve que le plus pratique serait d'intégrer dans l'identifiant comme décrit ci-dessus la date de découverte / insertion de l'article dans la base de données, et de conserver le champ date inchangé (c'est-à-dire une date telle que déclarée par le flux).
Le fait de disposer de la date d'insertion dans la base de données évite le risque d'avoir un article ajouté à une date plus ancienne ce qui permet :

• une pagination efficace
• marquer tous les articles comme lus sans risquer de marquer comme lus des articles arrivés entre temps
• une synchronisation facile pour l'API

[Alkarex]

Actuellement, le entry.id est généré par un hachage de entry.guid. Hors, ce GUID ne semble pas très unique entre plusieurs flux. GUID provient de http://simplepie.org/wiki/reference/simplepie_item/get_id .

Je trouve qu'il faudrait au moins ajouter entry.url et/ou feed.url et faire un hachage. Puis considérer stoker GUID comme entier éventuellement, ou au pire CHAR(6).

GUID pourrait alors servir pour éviter les doublons avec UNIQUE(), un rôle que perd feed.id s'il intègre l'heure comme proposé. Fait d2d26bf

mysql> select guid from freshrss_entry ORDER BY LENGTH(guid) limit 10;
+------+
| guid |
+------+
| H    |
| 2    |
| 7    |
| 12   |
| 892  |
| 893  |
| 714  |
| 973  |
| 964  |
| 678  |
+------+

[Alkarex]

Pour simplifier, plutôt que d'utiliser un hachage, je pense finalement qu'il serait préférable d'utiliser seulement microtime(true) comme identifiant, transformé en BIGINT, les doublons étant évités grâce à UNIQUE(e.id_feed, e.guid) d2d26bf

En plus, on peut laisser faire le travail de conversion entier 64-bit / flottant à MySQL, ce qui permet d'éviter tout problème lorsque PHP est en 32-bit.

select CAST(1384898862.8061 * 1000000 AS SIGNED INTEGER);
+---------------------------------------------------+
| CAST(1384898862.8061 * 1000000 AS SIGNED INTEGER) |
+---------------------------------------------------+
|                                  1384898862806100 |
+---------------------------------------------------+

select (1384898862806100 / 1000000);
+------------------------------+
| (1384898862806100 / 1000000) |
+------------------------------+
|              1384898862.8061 |
+------------------------------+
1 row in set (0.00 sec)

Et pour l'affichage sur le client Web, une chaîne décimale directe ou du base64url par exemple :

function base64url_encode($data) {        //RFC 4648
        return strtr(rtrim(base64_encode($data), '='), '+/', '-_');
}
function base64url_decode($data) {        //RFC 4648
        return base64_decode(strtr($data, '-_', '+/'));
}

$id = 1384898862.8061;
$encoded = base64url_encode(pack('d', $id));
echo $encoded, "\n";        //Affiche JJezS_ii1EE
$decoded = unpack('d', base64url_decode($encoded));
echo $decoded[1], "\n";        //Affiche 1384898862.8061

Dans cet exemple, base64url fait gagner 4 octets sur 15 (-27%) mais au prix de plusieurs appels de fonctions.

[Alkarex]

À tester plus, mais a priori fini :-)

[marienfressinaud]

Pour ce que j'ai essayé, ça marche bien :)

[Alkarex]

Super :-)
Je viens d'envoyer un patch qui trie par e.id plutôt que e.date. Je ne sais pas s'il a eu le temps de passer dans on test. Je remets ici le résumé, pour le retrouver plus facilement :

Expérimentation : Classement selon la date d'ajout dans la base plutôt que selon la date déclarée par le flux (qui est parfois fausse dans le passé, dans le futur, ou absente).
Quelques conséquences :

• Les flux avec des dates erronées ne sont plus un problème
• Lorsqu'on fait "marquer tout comme lu", les articles arrivés pendant la lecture ne sont plus indûment marqués comme lus
• Les articles ont tendance à être plus regroupés par flux lorsqu'on les affiche par catégorie
• Si un utilisateur n'utilise pas de cron et n'utilise pas FreshRSS pendant plusieurs jours, lors du rafraîchissement, les nouveaux articles seront dans "Aujourd'hui" (à interpréter donc comme les articles reçus
  aujourd'hui, et non comme déclarés comme étant publiés aujourd'hui)
• La pagination est plus efficace

[marienfressinaud]

Alors je n'avais pas testé ça effectivement. Seulement il y a une chose qui me dérange, c'est justement le fait que les articles soient regroupés par flux plutôt que par date. Généralement je cherche plutôt à voir mes articles pour une date donnée (la veille ou l'avant-veille) plutôt que par flux. Et si je veux les voir par flux, il y a déjà la possibilité de filtrer...

[Alkarex]

Cela devrait toujours fonctionner comme tu le souhaites. La différence est
assez subtile, surtout lorsqu'on utilise un cron
Le 28 nov. 2013 02:09, "Marien Fressinaud" notifications@github.com a
écrit :

Alors je n'avais pas testé ça effectivement. Seulement il y a une chose
qui me dérange, c'est justement le fait que les articles soient regroupés
par flux plutôt que par date. Généralement je cherche plutôt à voir mes
articles pour une date donnée (la veille ou l'avant-veille) plutôt que par
flux. Et si je veux les voir par flux, il y a déjà la possibilité de
filtrer...

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/202#issuecomment-29432866
.

[marienfressinaud]

Ah oui d'accord, je viens de comprendre le comportement. Le problème c'est lorsqu'on importe des flux (OPML) c'est que de très vieux articles peuvent se retrouver tout en haut de la liste au détriment des plus récents

[Alkarex]

Effectivement, au tout premier import, ce n'est pas optimal, mais cela
devrait aller pour les rafraîchissement suivants, ou dès le lendemain

[Alkarex]

En fait, j'ai une idée pour l'import OPML, qui est de faire comme dans le
script de migration, c'est-à-dire générer les e.id en se basant sur la date
déclarée. Je tâcherai de faire ça demain

[marienfressinaud]

Ok :) sinon oui, le comportement pour les jours suivants me convient mais il faudra quand même voir à l'usage ce qu'il en est réellement

[Alkarex]

Voilà, semble maintenant beaucoup mieux pour l'ajout de nouveaux flux

[marienfressinaud]

Parfait ! Et les performances pour l'actualisation sont géniales aussi ! :)

[Alkarex]

:-)
Ça sera même encore un tout petit peu mieux après quelques dernières optimisations de ce côté là, comme la suppression de l'index sur e.date.