Maison développement back-end tutoriel php 编程技术缓存写法(三)

编程技术缓存写法(三)

Nov 30, 2016 am 09:27 AM

上次我们说了多级缓存,本章详细介绍下内存缓存该如何设计。

一:分析设计

假设有个项目有一定并发量,要用到多级缓存,如下:

2253.jpg

在实际设计一个内存缓存前,我们需要考虑的问题:

1:内存与Redis的数据置换,尽可能在内存中提高数据命中率,减少下一级的压力。

2:内存容量的限制,需要控制缓存数量。

3:热点数据更新不同,需要可配置单个key过期时间。

4:良好的缓存过期删除策略。

5:缓存数据结构的复杂度尽可能的低。

关于置换及命中率:我们采用LRU算法,因为它实现简单,缓存key命中率也很好。

LRU即是:把最近最少访问的数据给淘汰掉,经常被访问到即是热点数据。

关于LRU数据结构:因为key优先级提升和key淘汰,所以需要顺序结构。我看到大多实现,都采用链表结构、

即:新数据插入到链表头部、被命中时的数据移动到头部。 添加复杂度O(1) 移动和获取复杂度O(N)。

有没复杂度更低的呢? 有Dictionary,复杂度为O(1),性能最好。 那如何保证缓存的优先级提升呢?

二:O(1)LRU实现

我们定义个LRUCache类,构造参数maxKeySize 来控制缓存最大数量。

使用ConcurrentDictionary来作为我们的缓存容器,并能保证线程安全。

public class LRUCache<TValue> : IEnumerable<KeyValuePair<string, TValue>>
   {
       private long ageToDiscard = 0;  //淘汰的年龄起点
       private long currentAge = 0;        //当前缓存最新年龄
       private int maxSize = 0;          //缓存最大容量
       private readonly ConcurrentDictionary<string, TrackValue> cache;
       public LRUCache(int maxKeySize)
       {
           cache = new ConcurrentDictionary<string, TrackValue>();
           maxSize = maxKeySize;
       }
   }
Copier après la connexion

上面定义了 ageToDiscard、currentAge 这2个自增值参数,作用是:标记缓存列表中各个key的新旧程度。

核心实现步骤如下:

1:每次添加key时,currentAge自增并将currentAge值分配给这个缓存值的Age,currentAge始终增加。

public void Add(string key, TValue value)
       {
           Adjust(key);
           var result = new TrackValue(this, value);
           cache.AddOrUpdate(key, result, (k, o) => result);
       }
       public class TrackValue
       {
           public readonly TValue Value;
           public long Age;
           public TrackValue(LRUCache<TValue> lv, TValue tv)
           {
               Age = Interlocked.Increment(ref lv.currentAge);
               Value = tv;
           }
       }
Copier après la connexion

2:在添加时,如超过最大数量。检查字典里是否有ageToDiscard年龄的key,如没有循环自增检查,有则删除、添加成功。

ageToDiscard+maxSize= currentAge ,这样设计就能在O(1)下保证可以淘汰旧数据,而不是使用链表移动。

public void Adjust(string key)
        {
            while (cache.Count >= maxSize)
            {
                long ageToDelete = Interlocked.Increment(ref ageToDiscard);
                var toDiscard =
                      cache.FirstOrDefault(p => p.Value.Age == ageToDelete);
                if (toDiscard.Key == null)
                    continue;
                TrackValue old;
                cache.TryRemove(toDiscard.Key, out old);
            }
        }
Copier après la connexion

过期删除策略

大多数情况下,LRU算法对热点数据命中率是很高的。 但如果突然大量偶发性的数据访问,会让内存中存放大量冷数据,也就是缓存污染。

会引起LRU无法命中热点数据,导致缓存系统命中率急剧下降。也可以使用LRU-K、2Q、MQ等变种算法来提高命中率。

过期配置

1:我们通过设定、最大过期时间来尽量避免冷数据常驻内存。

2:大多数情况每个缓存的时间要求不一致的,所以在增加单个key的过期时间。

private TimeSpan maxTime;
public LRUCache(int maxKeySize,TimeSpan maxExpireTime){}
 
 //TrackValue增加创建时间和过期时间
public readonly DateTime CreateTime;
public readonly TimeSpan ExpireTime;
Copier après la connexion

删除策略

1:关于key过期删除,最好使用定时删除了。 这样可以最快释放被占用的内存,但很明显,大量的定时器对CPU吃不消的。

2:所以我们采用惰性删除、在获取key的时检查是否过期,过期直接删除。

public Tuple<TrackValue, bool> CheckExpire(string key)
        {
            TrackValue result;
            if (cache.TryGetValue(key, out result))
            {
                var age = DateTime.Now.Subtract(result.CreateTime);
                if (age >= maxTime || age >= result.ExpireTime)
                {
                    TrackValue old;
                    cache.TryRemove(key, out old);
                    return Tuple.Create(default(TrackValue), false);
                }
            }
            return Tuple.Create(result, true);
        }
Copier après la connexion

3:惰性删除虽然性能最好,对于冷数据来说,还是没解决缓存污染问题。 所以我们还需定期清理。

比如:开个线程,5分钟去遍历检查key一次。这个策略根据实际场景可配置。

public void Inspection()
        {
            foreach (var item in this)
            {
                CheckExpire(item.Key);
            }
        }
Copier après la connexion

惰性删除+定期删除基本能满足我们需求了。

总结

如果继续完善下去,就是内存数据库的雏形,类似redis。

比如:增加删除key的通知,增加更多数据类型。 本篇也是参考了redis、Orleans的实现。


Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
2 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Repo: Comment relancer ses coéquipiers
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Comment obtenir des graines géantes
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Combien de temps faut-il pour battre Split Fiction?
3 Il y a quelques semaines By DDD

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Supprimez les valeurs en double du tableau PHP à l'aide d'expressions régulières Supprimez les valeurs en double du tableau PHP à l'aide d'expressions régulières Apr 26, 2024 pm 04:33 PM

Comment supprimer les valeurs en double du tableau PHP à l'aide d'expressions régulières : utilisez l'expression régulière /(.*)(.+)/i pour faire correspondre et remplacer les doublons. Parcourez les éléments du tableau et vérifiez les correspondances à l'aide de preg_match. S'il y a une correspondance, ignorez la valeur ; sinon, ajoutez-la à un nouveau tableau sans valeurs en double.

A quoi sert la programmation et à quoi sert de l'apprendre ? A quoi sert la programmation et à quoi sert de l'apprendre ? Apr 28, 2024 pm 01:34 PM

1. La programmation peut être utilisée pour développer divers logiciels et applications, notamment des sites Web, des applications mobiles, des jeux et des outils d'analyse de données. Ses domaines d'application sont très larges, couvrant presque tous les secteurs, notamment la recherche scientifique, la santé, la finance, l'éducation, le divertissement, etc. 2. L'apprentissage de la programmation peut nous aider à améliorer nos compétences en résolution de problèmes et nos capacités de réflexion logique. Lors de la programmation, nous devons analyser et comprendre les problèmes, trouver des solutions et les traduire en code. Cette façon de penser peut cultiver nos capacités analytiques et abstraites et améliorer notre capacité à résoudre des problèmes pratiques.

Créez des applications basées sur un navigateur avec Golang Créez des applications basées sur un navigateur avec Golang Apr 08, 2024 am 09:24 AM

Créez des applications basées sur un navigateur avec Golang Golang se combine avec JavaScript pour créer des expériences frontales dynamiques. Installez Golang : visitez https://golang.org/doc/install. Configurez un projet Golang : créez un fichier appelé main.go. Utilisation de GorillaWebToolkit : ajoutez le code GorillaWebToolkit pour gérer les requêtes HTTP. Créer un modèle HTML : créez index.html dans le sous-répertoire des modèles, qui est le modèle principal.

La clé du codage : libérer la puissance de Python pour les débutants La clé du codage : libérer la puissance de Python pour les débutants Oct 11, 2024 pm 12:17 PM

Python est un langage d'introduction à la programmation idéal pour les débutants grâce à sa facilité d'apprentissage et ses fonctionnalités puissantes. Ses bases incluent : Variables : utilisées pour stocker des données (nombres, chaînes, listes, etc.). Type de données : Définit le type de données dans la variable (entier, virgule flottante, etc.). Opérateurs : utilisés pour les opérations mathématiques et les comparaisons. Flux de contrôle : contrôlez le flux d'exécution du code (instructions conditionnelles, boucles).

Java Made Simple : un guide du débutant sur la puissance de programmation Java Made Simple : un guide du débutant sur la puissance de programmation Oct 11, 2024 pm 06:30 PM

Java Made Simple : Guide du débutant sur la puissance de programmation Introduction Java est un langage de programmation puissant utilisé dans tout, des applications mobiles aux systèmes d'entreprise. Pour les débutants, la syntaxe de Java est simple et facile à comprendre, ce qui en fait un choix idéal pour apprendre la programmation. Syntaxe de base Java utilise un paradigme de programmation orienté objet basé sur les classes. Les classes sont des modèles qui organisent ensemble les données et les comportements associés. Voici un exemple simple de classe Java : publicclassPerson{privateStringname;privateintage;

Créer l'avenir : programmation Java pour les débutants absolus Créer l'avenir : programmation Java pour les débutants absolus Oct 13, 2024 pm 01:32 PM

Java est un langage de programmation populaire qui peut être appris aussi bien par les développeurs débutants que par les développeurs expérimentés. Ce didacticiel commence par les concepts de base et progresse vers des sujets avancés. Après avoir installé le kit de développement Java, vous pouvez vous entraîner à la programmation en créant un simple programme « Hello, World ! ». Une fois que vous avez compris le code, utilisez l'invite de commande pour compiler et exécuter le programme, et « Hello, World ! » s'affichera sur la console. L'apprentissage de Java commence votre parcours de programmation et, à mesure que votre maîtrise s'approfondit, vous pouvez créer des applications plus complexes.

Résolution de problèmes avec Python : débloquez des solutions puissantes en tant que codeur débutant Résolution de problèmes avec Python : débloquez des solutions puissantes en tant que codeur débutant Oct 11, 2024 pm 08:58 PM

Python permet aux débutants de résoudre des problèmes. Sa syntaxe conviviale, sa bibliothèque complète et ses fonctionnalités telles que les variables, les instructions conditionnelles et les boucles permettent un développement de code efficace. De la gestion des données au contrôle du flux du programme et à l'exécution de tâches répétitives, Python fournit

Démystifier C : un chemin clair et simple pour les nouveaux programmeurs Démystifier C : un chemin clair et simple pour les nouveaux programmeurs Oct 11, 2024 pm 10:47 PM

C est un choix idéal pour les débutants qui souhaitent apprendre la programmation système. Il contient les composants suivants : fichiers d'en-tête, fonctions et fonctions principales. Un simple programme C capable d'imprimer "HelloWorld" a besoin d'un fichier d'en-tête contenant la déclaration de fonction d'entrée/sortie standard et utilise la fonction printf dans la fonction principale pour imprimer. Les programmes C peuvent être compilés et exécutés à l'aide du compilateur GCC. Après avoir maîtrisé les bases, vous pouvez passer à des sujets tels que les types de données, les fonctions, les tableaux et la gestion des fichiers pour devenir un programmeur C compétent.

See all articles